Avoid copying SkyKeys into a set and then into a map when retrieving them. Instead, just put them directly into a map. This avoids the memory churn and CPU cost of the set.

As a result, we have to use HashMaps instead of ImmutableMap.Builders, which I hope is ok (especially since we're not keeping them around), and due to that, we have some nice nondeterminism in the returned order, which matters for some cycle-checking tests.

Also, don't use a map at all when we don't need to (when building events).

Note that, since we have to deduplicate at some point, this means that changing the return type of SkyFunction.Environment#getValues to not be a random-access map is probably not worth it. Changing the return type of ProcessableGraph#getBatch to not be a random access map might still be worthwhile, although it might require some funny operations.

--
MOS_MIGRATED_REVID=131070418

2 files changed, 18 insertions, 22 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java b/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
index f6782e4c32..b10be322cd 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
@@ -22,7 +22,6 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
-import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.AbstractAction;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
@@ -57,21 +56,19 @@ import com.google.devtools.build.skyframe.AbstractSkyFunctionEnvironment;
 import com.google.devtools.build.skyframe.BuildDriver;
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationResult;
-import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrExceptionUtils;
 import com.google.devtools.build.skyframe.ValueOrUntypedException;
-
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-
 import javax.annotation.Nullable;
 
 /**
@@ -142,9 +139,9 @@ public final class ActionsTestUtil {
 
     @Override
     protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(
-        Set<SkyKey> depKeys) {
+        Iterable<SkyKey> depKeys) {
       EvaluationResult<SkyValue> evaluationResult;
-      Map<SkyKey, ValueOrUntypedException> result = Maps.newHashMapWithExpectedSize(depKeys.size());
+      Map<SkyKey, ValueOrUntypedException> result = new HashMap<>();
       try {
         evaluationResult = driver.evaluate(depKeys, /*keepGoing=*/false,
             ResourceUsage.getAvailableProcessors(), eventHandler);
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index c8464b4291..b9f97815df 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -878,7 +878,7 @@ public class ParallelEvaluatorTest {
 
   @Test
   public void triangleBelowHeadCycle() throws Exception {
-    graph = new InMemoryGraphImpl();
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     SkyKey aKey = GraphTester.toSkyKey("a");
     SkyKey bKey = GraphTester.toSkyKey("b");
     SkyKey cKey = GraphTester.toSkyKey("c");
@@ -935,25 +935,25 @@ public class ParallelEvaluatorTest {
   /** Regression test: "value cannot be ready in a cycle". */
   @Test
   public void selfEdgeWithExtraChildrenUnderCycle() throws Exception {
-    graph = new InMemoryGraphImpl();
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     SkyKey aKey = GraphTester.toSkyKey("a");
-    SkyKey bKey = GraphTester.toSkyKey("b");
+    SkyKey zKey = GraphTester.toSkyKey("z");
     SkyKey cKey = GraphTester.toSkyKey("c");
-    tester.getOrCreate(aKey).addDependency(bKey);
-    tester.getOrCreate(bKey).addDependency(cKey).addDependency(bKey);
+    tester.getOrCreate(aKey).addDependency(zKey);
+    tester.getOrCreate(zKey).addDependency(cKey).addDependency(zKey);
     tester.getOrCreate(cKey).addDependency(aKey);
     EvaluationResult<StringValue> result = eval(/*keepGoing=*/true, ImmutableList.of(aKey));
     assertEquals(null, result.get(aKey));
     ErrorInfo errorInfo = result.getError(aKey);
     CycleInfo cycleInfo = Iterables.getOnlyElement(errorInfo.getCycleInfo());
-    assertThat(cycleInfo.getCycle()).containsExactly(bKey).inOrder();
+    assertThat(cycleInfo.getCycle()).containsExactly(zKey).inOrder();
     assertThat(cycleInfo.getPathToCycle()).containsExactly(aKey).inOrder();
   }
 
   /** Regression test: "value cannot be ready in a cycle". */
   @Test
   public void cycleWithExtraChildrenUnderCycle() throws Exception {
-    graph = new InMemoryGraphImpl();
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     SkyKey aKey = GraphTester.toSkyKey("a");
     SkyKey bKey = GraphTester.toSkyKey("b");
     SkyKey cKey = GraphTester.toSkyKey("c");
@@ -973,7 +973,7 @@ public class ParallelEvaluatorTest {
   /** Regression test: "value cannot be ready in a cycle". */
   @Test
   public void cycleAboveIndependentCycle() throws Exception {
-    graph = new InMemoryGraphImpl();
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
     SkyKey aKey = GraphTester.toSkyKey("a");
     SkyKey bKey = GraphTester.toSkyKey("b");
     SkyKey cKey = GraphTester.toSkyKey("c");
@@ -1088,16 +1088,16 @@ public class ParallelEvaluatorTest {
 
   @Test
   public void manyUnprocessedValuesInCycle() throws Exception {
-    graph = new InMemoryGraphImpl();
-    SkyKey lastSelfKey = GraphTester.toSkyKey("lastSelf");
-    SkyKey firstSelfKey = GraphTester.toSkyKey("firstSelf");
-    SkyKey midSelfKey = GraphTester.toSkyKey("midSelf");
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
+    SkyKey lastSelfKey = GraphTester.toSkyKey("zlastSelf");
+    SkyKey firstSelfKey = GraphTester.toSkyKey("afirstSelf");
+    SkyKey midSelfKey = GraphTester.toSkyKey("midSelf9");
     // We add firstSelf first so that it is processed last in cycle detection (LIFO), meaning that
     // none of the dep values have to be cleared from firstSelf.
     tester.getOrCreate(firstSelfKey).addDependency(firstSelfKey);
     for (int i = 0; i < 100; i++) {
       SkyKey firstDep = GraphTester.toSkyKey("first" + i);
-      SkyKey midDep = GraphTester.toSkyKey("mid" + i);
+      SkyKey midDep = GraphTester.toSkyKey("midSelf" + i + "dep");
       SkyKey lastDep = GraphTester.toSkyKey("last" + i);
       tester.getOrCreate(firstSelfKey).addDependency(firstDep);
       tester.getOrCreate(midSelfKey).addDependency(midDep);
@@ -1301,9 +1301,8 @@ public class ParallelEvaluatorTest {
    */
   @Test
   public void cycleWithMultipleUnfinishedChildren() throws Exception {
-    graph = new InMemoryGraphImpl();
-    tester = new GraphTester();
-    SkyKey cycleKey = GraphTester.toSkyKey("cycle");
+    graph = new DeterministicHelper.DeterministicProcessableGraph(new InMemoryGraphImpl());
+    SkyKey cycleKey = GraphTester.toSkyKey("zcycle");
     SkyKey midKey = GraphTester.toSkyKey("mid");
     SkyKey topKey = GraphTester.toSkyKey("top");
     SkyKey selfEdge1 = GraphTester.toSkyKey("selfEdge1");