Avoid list copy in BuildingState.getNextDirtyDirectDeps

Also, in GroupedList, short-circuit expensive group equality check
with a reference check, saving time and garbage when groups are the
same object.

--
MOS_MIGRATED_REVID=109795332

5 files changed, 51 insertions, 9 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
index 80ed7f900f..7723b06000 100644
--- a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
+++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
@@ -28,15 +28,18 @@ import java.util.List;
 import java.util.Set;
 
 /**
- * Encapsulates a list of lists. Is intended to be used in "batch" mode -- to set the value of a
+ * Encapsulates a list of groups. Is intended to be used in "batch" mode -- to set the value of a
  * GroupedList, users should first construct a {@link GroupedListHelper}, add elements to it, and
  * then {@link #append} the helper to a new GroupedList instance. The generic type T <i>must not</i>
  * be a {@link List}.
  *
  * <p>Despite the "list" name, it is an error for the same element to appear multiple times in the
  * list. Users are responsible for not trying to add the same element to a GroupedList twice.
+ *
+ * <p>Groups are implemented as lists to minimize memory use. However, {@link #equals} is defined
+ * to treat groups as unordered.
  */
-public class GroupedList<T> implements Iterable<Iterable<T>> {
+public class GroupedList<T> implements Iterable<Collection<T>> {
   // Total number of items in the list. At least elements.size(), but might be larger if there are
   // any nested lists.
   private int size = 0;
@@ -66,6 +69,24 @@ public class GroupedList<T> implements Iterable<Iterable<T>> {
     size += helper.size();
   }
 
+  public void appendGroup(Collection<T> group) {
+    // Do a check to make sure we don't have lists here. Note that if group is empty,
+    // Iterables.getFirst will return null, and null is not instanceof List.
+    Preconditions.checkState(!(Iterables.getFirst(group, null) instanceof List),
+        "Cannot make grouped list of lists: %s", group);
+    switch (group.size()) {
+      case 0:
+        return;
+      case 1:
+        elements.add(Iterables.getOnlyElement(group));
+        break;
+      default:
+        elements.add(group);
+        break;
+    }
+    size += group.size();
+  }
+
   /**
    * Removes the elements in toRemove from this list. Takes time proportional to the size of the
    * list, so should not be called often.
@@ -163,6 +184,9 @@ public class GroupedList<T> implements Iterable<Iterable<T>> {
     for (int i = 0; i < this.elements.size(); i++) {
       Object thisElt = this.elements.get(i);
       Object thatElt = that.elements.get(i);
+      if (thisElt == thatElt) {
+        continue;
+      }
       if (thisElt instanceof List) {
         // Recall that each inner item is either a List or a singleton element.
         if (!(thatElt instanceof List)) {
@@ -191,7 +215,7 @@ public class GroupedList<T> implements Iterable<Iterable<T>> {
    * iterator is needed here because, to optimize memory, we store single-element lists as elements
    * internally, and so they must be wrapped before they're returned.
    */
-  private class GroupedIterator implements Iterator<Iterable<T>> {
+  private class GroupedIterator implements Iterator<Collection<T>> {
     private final Iterator<Object> iter = elements.iterator();
 
     @Override
@@ -201,7 +225,7 @@ public class GroupedList<T> implements Iterable<Iterable<T>> {
 
     @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
     @Override
-    public Iterable<T> next() {
+    public Collection<T> next() {
       Object obj = iter.next();
       if (obj instanceof List) {
         return (List<T>) obj;
@@ -216,7 +240,7 @@ public class GroupedList<T> implements Iterable<Iterable<T>> {
   }
 
   @Override
-  public Iterator<Iterable<T>> iterator() {
+  public Iterator<Collection<T>> iterator() {
     return new GroupedIterator();
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
index 5550f82b3b..0fe858e0ed 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -176,7 +176,7 @@ public class BuildingState {
    * Which child should be re-evaluated next in the process of determining if this entry needs to
    * be re-evaluated. Used by {@link #getNextDirtyDirectDeps} and {@link #signalDep(boolean)}.
    */
-  private Iterator<Iterable<SkyKey>> dirtyDirectDepIterator = null;
+  private Iterator<Collection<SkyKey>> dirtyDirectDepIterator = null;
 
   BuildingState() {
     lastBuildDirectDeps = null;
@@ -354,8 +354,7 @@ public class BuildingState {
     Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
     Preconditions.checkState(evaluating, this);
     Preconditions.checkState(dirtyDirectDepIterator.hasNext(), this);
-    List<SkyKey> nextDeps = ImmutableList.copyOf(dirtyDirectDepIterator.next());
-    return nextDeps;
+    return dirtyDirectDepIterator.next();
   }
 
   Collection<SkyKey> getAllRemainingDirtyDirectDeps() {
@@ -378,6 +377,10 @@ public class BuildingState {
     directDeps.append(depsThisRun);
   }
 
+  void addDirectDepsGroup(Collection<SkyKey> group) {
+    directDeps.appendGroup(group);
+  }
+
   /**
    * Returns the direct deps found so far on this build. Should only be called before the node has
    * finished building.
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index 95d23bd702..055487adb3 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -450,6 +450,12 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
+  public synchronized void addTemporaryDirectDepsGroupToDirtyEntry(Collection<SkyKey> group) {
+    Preconditions.checkState(!isDone(), "add group temp shouldn't be done: %s %s", group, this);
+    buildingState.addDirectDepsGroup(group);
+  }
+
+  @Override
   public synchronized boolean isReady() {
     Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
     return buildingState.isReady();
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
index 8d9b51db5f..d9f5c87676 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -307,6 +307,14 @@ public interface NodeEntry extends ThinNodeEntry {
   void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper);
 
   /**
+   * Add a group of direct deps to the node. May only be called with a {@link Collection} returned
+   * by {@link #getNextDirtyDirectDeps()} just before enqueuing those direct deps during dependency
+   * checking.
+   */
+  @ThreadSafe
+  void addTemporaryDirectDepsGroupToDirtyEntry(Collection<SkyKey> group);
+
+  /**
    * Returns true if the node is ready to be evaluated, i.e., it has been signaled exactly as many
    * times as it has temporary dependencies. This may only be called while the node is being
    * evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index 802e940f69..e9c18b136b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -869,7 +869,8 @@ public final class ParallelEvaluator implements Evaluator {
           // in #invalidatedByErrorTransience means that the error transience node is not newer
           // than this node, so we are going to mark it clean (since the error transience node is
           // always the last dep).
-          state.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck));
+          state.addTemporaryDirectDepsGroupToDirtyEntry(directDepsToCheck);
+
           for (Map.Entry<SkyKey, NodeEntry> e
               : graph.createIfAbsentBatch(directDepsToCheck).entrySet()) {
             SkyKey directDep = e.getKey();