Skip to main content
summaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
authorJonah Graham2018-05-24 16:03:19 -0400
committerJonah Graham2018-05-28 19:49:16 -0400
commitd462ce74ff2735dcee3bde61a835565bc2caa182 (patch)
tree78eabcf19671ce587d892714ee94a1f47c8a52ca /core
parent957dae8f4ea9069c9fa67e4e1082ff588bd2a5cb (diff)
downloadorg.eclipse.cdt-d462ce74ff2735dcee3bde61a835565bc2caa182.tar.gz
org.eclipse.cdt-d462ce74ff2735dcee3bde61a835565bc2caa182.tar.xz
org.eclipse.cdt-d462ce74ff2735dcee3bde61a835565bc2caa182.zip
Bug 519391: avoid iterating and copying large lists
The BuildConsolePartitioner used to compute partitions from offsets by iterating over the list of partitions. This strategy is fine for small build outputs. But outputs in the 100,000+ line range can have huge number of partitions. This commit updates the logic to take advantage of the fact that the partitions are sorted and contiguous to do binary searches to find the partition, and uses a new method (computePartitioningAsList) to use a view onto the original partitions list instead of significant copying. Change-Id: I4395df36431a6ae45e6b77d6f76fd29532347ac5
Diffstat (limited to 'core')
-rw-r--r--core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitioner.java97
-rw-r--r--core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitionerEditData.java10
-rw-r--r--core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsoleViewer.java13
-rw-r--r--core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/DocumentMarkerManager.java2
4 files changed, 79 insertions, 43 deletions
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitioner.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitioner.java
index 8726c5cc49..58c2d76e1b 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitioner.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitioner.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2002, 2017 QNX Software Systems and others.
+ * Copyright (c) 2002, 2018 QNX Software Systems and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -19,6 +19,7 @@ import java.io.IOException;
import java.io.OutputStream;
import java.net.URI;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.List;
import java.util.concurrent.atomic.AtomicBoolean;
@@ -61,9 +62,13 @@ public class BuildConsolePartitioner
/**
* Active list of partitions, must only be accessed form UI thread which
- * provides implicit lock
+ * provides implicit lock.
+ *
+ * The partitions are required to be sorted, and the partitions must not have
+ * any gaps. (The Offset + Length of partition N must equals the Offset of
+ * partition N + 1.)
*/
- List<ITypedRegion> fPartitions = new ArrayList<ITypedRegion>();
+ List<BuildConsolePartition> fPartitions = new ArrayList<>();
/**
* Active document, must only be accessed form UI thread which provides
* implicit lock
@@ -365,39 +370,70 @@ public class BuildConsolePartitioner
*/
@Override
public ITypedRegion[] computePartitioning(int offset, int length) {
+ List<BuildConsolePartition> list = computePartitioningAsList(offset, length);
+ return list.toArray(new ITypedRegion[list.size()]);
+ }
+
+ public List<BuildConsolePartition> computePartitioningAsList(int offset, int length) {
+ List<BuildConsolePartition> list;
if (offset == 0 && length == fDocument.getLength()) {
- return fPartitions.toArray(new ITypedRegion[fPartitions.size()]);
- }
- int end = offset + length;
- List<ITypedRegion> list = new ArrayList<ITypedRegion>();
- for (int i = 0; i < fPartitions.size(); i++) {
- ITypedRegion partition = fPartitions.get(i);
- int partitionStart = partition.getOffset();
- int partitionEnd = partitionStart + partition.getLength();
- if ((offset >= partitionStart && offset <= partitionEnd)
- || (offset < partitionStart && end >= partitionStart)) {
- list.add(partition);
+ list = fPartitions;
+ } else {
+ int fromIndex = getPartitionIndex(offset);
+ int toIndex = getPartitionIndex(offset + length - 1);
+ if (fromIndex < 0 && toIndex < 0) {
+ // entire range falls outside, should be unreachable
+ return Collections.emptyList();
+ } else if (fromIndex < 0) {
+ fromIndex = 0;
+ } else if (toIndex < 0) {
+ toIndex = fPartitions.size() - 1;
}
+ list = fPartitions.subList(fromIndex, toIndex + 1);
}
- return list.toArray(new ITypedRegion[list.size()]);
+ return list;
}
/**
* @see org.eclipse.jface.text.IDocumentPartitioner#getPartition(int)
*/
@Override
- public ITypedRegion getPartition(int offset) {
- for (int i = 0; i < fPartitions.size(); i++) {
- ITypedRegion partition = fPartitions.get(i);
- int start = partition.getOffset();
- int end = start + partition.getLength();
- if (offset >= start && offset < end) {
- return partition;
- }
+ public BuildConsolePartition getPartition(int offset) {
+ int partitionIndex = getPartitionIndex(offset);
+ if (partitionIndex >= 0) {
+ return fPartitions.get(partitionIndex);
}
return null;
}
+ private int getPartitionIndex(int offset) {
+ BuildConsolePartition searchTerm = new BuildConsolePartition(null, offset, 0, null, null, 0);
+ int index = Collections.binarySearch(fPartitions, searchTerm,
+ (a, b) -> Integer.compare(a.getOffset(), b.getOffset()));
+ if (index >= 0) {
+ // exact match to beginning of a partition
+ return index;
+ } else if (index == -1) {
+ // before first partition
+ return -1;
+ } else if (index == -(fPartitions.size() + 1)) {
+ // either in or after last partition
+ BuildConsolePartition lastPartition = fPartitions.get(fPartitions.size() - 1);
+ int lastPartitionEnd = lastPartition.getOffset() + lastPartition.getLength();
+ assert offset >= lastPartition.getOffset();
+ if (offset < lastPartitionEnd) {
+ // within last partition
+ return fPartitions.size() - 1;
+ } else {
+ // after last partition
+ return -1;
+ }
+ } else {
+ // within a partition
+ return -(index + 1) - 1;
+ }
+ }
+
@Override
public IRegion documentChanged2(DocumentEvent event) {
String text = event.getText();
@@ -407,20 +443,19 @@ public class BuildConsolePartitioner
fEditData.clear();
return new Region(0, 0);
}
- ITypedRegion[] affectedRegions = computePartitioning(event.getOffset(), text.length());
- if (affectedRegions.length == 0) {
+ List<BuildConsolePartition> affectedRegions = computePartitioningAsList(event.getOffset(), text.length());
+ if (affectedRegions.size() == 0) {
return null;
}
- if (affectedRegions.length == 1) {
- return affectedRegions[0];
+ if (affectedRegions.size() == 1) {
+ return affectedRegions.get(0);
}
- int affectedLength = affectedRegions[0].getLength();
- for (int i = 1; i < affectedRegions.length; i++) {
- ITypedRegion region = affectedRegions[i];
+ int affectedLength = 0;
+ for (BuildConsolePartition region : affectedRegions) {
affectedLength += region.getLength();
}
- return new Region(affectedRegions[0].getOffset(), affectedLength);
+ return new Region(affectedRegions.get(0).getOffset(), affectedLength);
}
public IConsole getConsole() {
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitionerEditData.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitionerEditData.java
index eac79240c3..6996a49ce4 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitionerEditData.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsolePartitionerEditData.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2016, 2017 Kichwa Coders and others.
+ * Copyright (c) 2016, 2018 Kichwa Coders and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -49,7 +49,7 @@ public class BuildConsolePartitionerEditData {
/**
* New partitions that match the new contents.
*/
- List<ITypedRegion> getNewPartitions();
+ List<BuildConsolePartition> getNewPartitions();
/**
* All the streams that have been written to since the last update.
@@ -73,7 +73,7 @@ public class BuildConsolePartitionerEditData {
* Editable partitions, all modifications are made to this copy of the
* partitions, then the UI thread occasionally gets these updates
*/
- private List<BuildConsolePartition> fEditPartitions = new ArrayList<BuildConsolePartition>();
+ private List<BuildConsolePartition> fEditPartitions = new ArrayList<>();
/**
* Set to true when an edit causes the document marker manager to need to be
@@ -318,7 +318,7 @@ public class BuildConsolePartitionerEditData {
boolean problemsAdded;
long newOffset;
String newConents;
- List<ITypedRegion> newPartitions;
+ List<BuildConsolePartition> newPartitions;
List<IBuildConsoleStreamDecorator> streamsNeedingNotifcation;
synchronized (this) {
@@ -346,7 +346,7 @@ public class BuildConsolePartitionerEditData {
}
@Override
- public List<ITypedRegion> getNewPartitions() {
+ public List<BuildConsolePartition> getNewPartitions() {
return newPartitions;
}
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsoleViewer.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsoleViewer.java
index 46e80f2dc9..d0be3b589c 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsoleViewer.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/BuildConsoleViewer.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2002, 2013 QNX Software Systems and others.
+ * Copyright (c) 2002, 2018 QNX Software Systems and others.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
@@ -11,11 +11,12 @@
*******************************************************************************/
package org.eclipse.cdt.internal.ui.buildconsole;
+import java.util.List;
+
import org.eclipse.jface.text.BadLocationException;
import org.eclipse.jface.text.DocumentEvent;
import org.eclipse.jface.text.IDocument;
import org.eclipse.jface.text.IDocumentListener;
-import org.eclipse.jface.text.ITypedRegion;
import org.eclipse.jface.text.TextViewer;
import org.eclipse.swt.SWT;
import org.eclipse.swt.custom.LineBackgroundEvent;
@@ -163,10 +164,10 @@ public class BuildConsoleViewer extends TextViewer
// Note, computePartitioning actually doesn't change anything in partitioning,
// but only computes number of affected regions.
- ITypedRegion[] regions = partitioner.computePartitioning(event.lineOffset, event.lineText.length());
- StyleRange[] styles = new StyleRange[regions.length];
- for (int i = 0; i < regions.length; i++) {
- BuildConsolePartition partition = (BuildConsolePartition) regions[i];
+ List<BuildConsolePartition> regions = partitioner.computePartitioningAsList(event.lineOffset, event.lineText.length());
+ StyleRange[] styles = new StyleRange[regions.size()];
+ for (int i = 0; i < regions.size(); i++) {
+ BuildConsolePartition partition = regions.get(i);
if (partition.getStream()== null) return;
Color colorFG = partition.getStream().getColor();
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/DocumentMarkerManager.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/DocumentMarkerManager.java
index 5819976669..45659f3441 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/DocumentMarkerManager.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/buildconsole/DocumentMarkerManager.java
@@ -111,7 +111,7 @@ class DocumentMarkerManager {
BuildConsolePartition getCurrentPartition() {
if ( 0 <= highlightedPartitionIndex &&
highlightedPartitionIndex < fPartitioner.fPartitions.size() ) {
- BuildConsolePartition p = (BuildConsolePartition)fPartitioner.fPartitions.get(highlightedPartitionIndex);
+ BuildConsolePartition p = fPartitioner.fPartitions.get(highlightedPartitionIndex);
return p;
}
return null;

Back to the top