Track changed and dirtied keys separately during invalidation

Reduces the number of allocations during invalidation. Has a magnified
effect when optional support for interruptibility is turned off.

--
MOS_MIGRATED_REVID=108978068

1 files changed, 21 insertions, 32 deletions

diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 2e012e90be..2b23b92815 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -20,7 +20,6 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableList.Builder;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.ErrorClassifier;
@@ -33,7 +32,6 @@ import com.google.devtools.build.skyframe.ThinNodeEntry.MarkedDirtyResult;
 
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
@@ -161,8 +159,6 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
     return executor.getInterruptionLatchForTestingOnly();
   }
 
-  protected abstract long count();
-
   protected void informInvalidationReceiver(SkyKey key,
       EvaluationProgressReceiver.InvalidationState state) {
     if (invalidationReceiver != null) {
@@ -249,11 +245,6 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
     }
 
     @Override
-    protected long count() {
-      return visited.size();
-    }
-
-    @Override
     protected boolean getSupportInterruptions() {
       return true;
     }
@@ -340,9 +331,13 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
   /** A node-dirtying implementation. */
   static class DirtyingNodeVisitor extends InvalidatingNodeVisitor<ThinNodeQueryableGraph> {
 
-    private final Set<Pair<SkyKey, InvalidationType>> visited =
+    private final Set<SkyKey> changed =
         Collections.newSetFromMap(
-            new ConcurrentHashMap<Pair<SkyKey, InvalidationType>, Boolean>(
+            new ConcurrentHashMap<SkyKey, Boolean>(
+                EXPECTED_VISITED_SET_SIZE, .75f, DEFAULT_THREAD_COUNT));
+    private final Set<SkyKey> dirtied =
+        Collections.newSetFromMap(
+            new ConcurrentHashMap<SkyKey, Boolean>(
                 EXPECTED_VISITED_SET_SIZE, .75f, DEFAULT_THREAD_COUNT));
     private final boolean supportInterruptions;
 
@@ -372,11 +367,6 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
     }
 
     @Override
-    protected long count() {
-      return visited.size();
-    }
-
-    @Override
     protected boolean getSupportInterruptions() {
       return supportInterruptions;
     }
@@ -398,7 +388,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
      * {@link NodeEntry} ignores the second marking.
      *
      * The invariant that we do not process a (SkyKey, InvalidationType) pair twice is enforced by
-     * the {@link #visited} set.
+     * the {@link #changed} and {@link #dirtied} sets.
      *
      * The "invariant" is also enforced across builds by checking to see if the entry is already
      * marked changed, or if it is already marked dirty and we are just going to mark it dirty
@@ -409,30 +399,29 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
      */
     @Override
     @ThreadSafe
-    public void visit(Iterable<SkyKey> keys, final InvalidationType invalidationType,
-        final boolean mustExist) {
+    public void visit(
+        Iterable<SkyKey> keys, final InvalidationType invalidationType, final boolean mustExist) {
       Preconditions.checkState(invalidationType != InvalidationType.DELETED, keys);
       final boolean isChanged = (invalidationType == InvalidationType.CHANGED);
+      Set<SkyKey> setToCheck = isChanged ? changed : dirtied;
       int size = Iterables.size(keys);
-      ArrayList<Pair<SkyKey, InvalidationType>> invalidationPairs = new ArrayList<>(size);
+      ArrayList<SkyKey> keysToGet = new ArrayList<>(size);
       for (SkyKey key : keys) {
-        Pair<SkyKey, InvalidationType> invalidationPair = Pair.of(key, invalidationType);
-        if (visited.add(invalidationPair)) {
-          invalidationPairs.add(invalidationPair);
+        if (setToCheck.add(key)) {
+          keysToGet.add(key);
         }
       }
-      List<SkyKey> keysToGet =
-          Lists.transform(invalidationPairs, Pair.<SkyKey, InvalidationType>firstFunction());
       if (supportInterruptions) {
-        pendingVisitations.addAll(invalidationPairs);
+        for (SkyKey key : keysToGet) {
+          pendingVisitations.add(Pair.of(key, invalidationType));
+        }
       }
       final Map<SkyKey, ? extends ThinNodeEntry> entries = graph.getBatch(keysToGet);
-      for (final Pair<SkyKey, InvalidationType> invalidationPair : invalidationPairs) {
+      for (final SkyKey key : keysToGet) {
         executor.execute(
             new Runnable() {
               @Override
               public void run() {
-                SkyKey key = invalidationPair.getFirst();
                 ThinNodeEntry entry = entries.get(key);
 
                 if (entry == null) {
@@ -442,7 +431,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                           + "node",
                       key);
                   if (supportInterruptions) {
-                    pendingVisitations.remove(invalidationPair);
+                    pendingVisitations.remove(Pair.of(key, invalidationType));
                   }
                   return;
                 }
@@ -451,7 +440,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                   // If this node is already marked changed, or we are only marking this node
                   // dirty, and it already is, move along.
                   if (supportInterruptions) {
-                    pendingVisitations.remove(invalidationPair);
+                    pendingVisitations.remove(Pair.of(key, invalidationType));
                   }
                   return;
                 }
@@ -464,7 +453,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                 if (markedDirtyResult == null) {
                   // Another thread has already dirtied this node. Don't do anything in this thread.
                   if (supportInterruptions) {
-                    pendingVisitations.remove(invalidationPair);
+                    pendingVisitations.remove(Pair.of(key, invalidationType));
                   }
                   return;
                 }
@@ -477,7 +466,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                 dirtyKeyTracker.dirty(key);
                 // Remove the node from the set as the last operation.
                 if (supportInterruptions) {
-                  pendingVisitations.remove(invalidationPair);
+                  pendingVisitations.remove(Pair.of(key, invalidationType));
                 }
               }
             });