Bug 530649 - Optimize probable case of building 1 project
One of the typical actions can be to build only one project. Optimize
the computation of filtered graph in that case so it only returns the
project node and skips computation of edges as we know there won't be
any.
Change-Id: Iebd969522e46d92b1f8b45ec4a012beb2456e6f1
Signed-off-by: Mickael Istria <mistria@redhat.com>
diff --git a/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java b/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java
index 9f33a66..4b89f03 100644
--- a/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java
+++ b/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java
@@ -677,30 +677,50 @@
*/
public static <T> Digraph<T> buildFilteredDigraph(Digraph<T> initialGraph, Predicate<T> filterOut, Class<T> clazz) {
Digraph<T> res = new Digraph<>(clazz);
- Set<Vertex<T>> toRemove = new LinkedHashSet<>(); // Make it a TreeSet using depth as comparator?
+ Set<T> toRemove = new LinkedHashSet<>(); // Make it a TreeSet using depth as comparator?
for (Vertex<T> vertex : initialGraph.vertexList) {
- if (!filterOut.test(vertex.id)) {
- res.addVertex(vertex.id);
+ T id = vertex.id;
+ if (!filterOut.test(id)) {
+ res.addVertex(id);
} else {
- toRemove.add(vertex);
+ toRemove.add(id);
}
}
- Set<Edge<T>> edges = new LinkedHashSet<>(initialGraph.getEdges());
- for (Vertex<T> vertexToRemove : toRemove) {
+ if (res.vertexList.size() < 2) { // 0 or 1 node -> no edge
+ return res;
+ }
+ final Set<Edge<T>> edgesWithRemovedRef = new LinkedHashSet<>();
+ initialGraph.getEdges().forEach(edge -> {
+ if (toRemove.contains(edge.from) || toRemove.contains(edge.to)) {
+ edgesWithRemovedRef.add(edge);
+ } else {
+ res.addEdge(edge.from, edge.to);
+ }
+ });
+ for (T idToRemove : toRemove) {
Set<Edge<T>> incoming = new LinkedHashSet<>();
Set<Edge<T>> outgoing = new LinkedHashSet<>();
- for (Edge<T> edge : edges) {
- if (edge.from == vertexToRemove.id) {
+ for (Edge<T> edge : edgesWithRemovedRef) {
+ if (edge.from == idToRemove) {
outgoing.add(edge);
- } else if (edge.to == vertexToRemove.id) {
+ } else if (edge.to == idToRemove) {
incoming.add(edge);
}
}
- edges.removeAll(incoming);
- edges.removeAll(outgoing);
- incoming.forEach(incomingEdge -> outgoing.forEach(outgoingEdge -> edges.add(new Edge<>(incomingEdge.from, outgoingEdge.to))));
+ edgesWithRemovedRef.removeAll(incoming);
+ edgesWithRemovedRef.removeAll(outgoing);
+ incoming.forEach(incomingEdge -> outgoing.forEach(outgoingEdge -> {
+ Edge<T> edge = new Edge<>(incomingEdge.from, outgoingEdge.to);
+ if (toRemove.contains(edge.from) || toRemove.contains(edge.to)) {
+ edgesWithRemovedRef.add(edge);
+ } else {
+ res.addEdge(edge.from, edge.to);
+ }
+ }));
}
- edges.forEach(edge -> res.addEdge(edge.from, edge.to));
+ if (!edgesWithRemovedRef.isEmpty()) {
+ throw new IllegalStateException("There should be no remaining edge at this point."); //$NON-NLS-1$
+ }
return res;
}
}
diff --git a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java
index f8646fb..60ee53f 100644
--- a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java
+++ b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java
@@ -45,6 +45,7 @@
digraph.freeze();
ComputeProjectOrder.computeVertexOrder(digraph, Object.class);
long duration = System.currentTimeMillis() - timestamp;
+ System.err.println(duration);
assertTrue(duration < 1000);
}
@@ -64,12 +65,28 @@
Digraph<Object> filtered = ComputeProjectOrder.buildFilteredDigraph(digraph, o -> false, Object.class);
assertEquals(digraph.vertexMap.keySet(), filtered.vertexMap.keySet());
long duration = System.currentTimeMillis() - timestamp;
+ System.err.println(duration);
assertTrue(duration < 1000);
// keep only 1 element
timestamp = System.currentTimeMillis();
filtered = ComputeProjectOrder.buildFilteredDigraph(digraph, o -> o != initialVertex, Object.class);
assertEquals(Collections.singleton(initialVertex), filtered.vertexMap.keySet());
duration = System.currentTimeMillis() - timestamp;
+ System.err.println(duration);
+ assertTrue(duration < 1000);
+ // keep half elements
+ timestamp = System.currentTimeMillis();
+ Predicate<Object> removeOneOutOfTwo = new Predicate<Object>() {
+ private int i = 0;
+
+ @Override
+ public boolean test(Object t) {
+ return (i++) % 2 == 0;
+ }
+ };
+ filtered = ComputeProjectOrder.buildFilteredDigraph(digraph, removeOneOutOfTwo, Object.class);
+ duration = System.currentTimeMillis() - timestamp;
+ System.err.println(duration);
assertTrue(duration < 1000);
}
