Remove reverse deps lazily, only when the node has finished building and we discover that it no longer has certain deps.

In the common case, where a node's deps do not change in the end, this reduces lock contention and CPU.

The downside of this is that we now create a set of the previous reverse deps during each evaluation of a node. We don't store this set in order to conserve memory, so we pay for it in CPU. We will probably only construct it two or three times (most SkyFunctions don't have so many groups), so the cost shouldn't be so high, but we can try to mitigate if it shows up in profiling.

--
MOS_MIGRATED_REVID=122566267

1 files changed, 25 insertions, 11 deletions

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 924771a232..0fafa861a3 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -159,9 +159,9 @@ public interface NodeEntry extends ThinNodeEntry {
   /**
    * Similar to {@link #addReverseDepAndCheckIfDone}, except that {@param reverseDep} must already
    * be a reverse dep of this entry. Should be used when reverseDep has been marked dirty and is
-   * checking its dependencies for changes. The caller must treat the return value just as they
-   * would the return value of {@link #addReverseDepAndCheckIfDone} by scheduling this node for
-   * evaluation if needed.
+   * checking its dependencies for changes or is rebuilding. The caller must treat the return value
+   * just as they would the return value of {@link #addReverseDepAndCheckIfDone} by scheduling this
+   * node for evaluation if needed.
    */
   @ThreadSafe
   DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep);
@@ -259,7 +259,8 @@ public interface NodeEntry extends ThinNodeEntry {
    * created, this is just any elements that were added using {@link #addTemporaryDirectDeps} (so it
    * is the same as {@link #getTemporaryDirectDeps}). If this node is marked dirty, this includes
    * all the elements that would have been returned by successive calls to
-   * {@link #getNextDirtyDirectDeps}.
+   * {@link #getNextDirtyDirectDeps} (or, equivalently, one call to
+   * {@link #getAllRemainingDirtyDirectDeps}).
    *
    * <p>This method should only be called when this node is about to be deleted after an aborted
    * evaluation. After such an evaluation, any nodes that did not finish evaluating are deleted, as
@@ -274,15 +275,28 @@ public interface NodeEntry extends ThinNodeEntry {
   Iterable<SkyKey> getAllDirectDepsForIncompleteNode();
 
   /**
+   * If an entry {@link #isDirty}, returns all direct deps that were present last build, but have
+   * not yet been verified to be present during the current build. Implementations may lazily remove
+   * these deps, since in many cases they will be added back during this build, even though the node
+   * may have a changed value. However, any elements of this returned set that have not been added
+   * back by the end of evaluation <i>must</i> be removed from any done nodes, in order to preserve
+   * graph consistency.
+   *
+   * <p>Returns the empty set if an entry is not dirty. In either case, the entry must already have
+   * started evaluation.
+   *
+   * <p>This method does not mutate the entry. In particular, multiple calls to this method will
+   * always produce the same result until the entry finishes evaluation. Contrast with
+   * {@link #getAllDirectDepsForIncompleteNode}.
+   */
+  Set<SkyKey> getAllRemainingDirtyDirectDeps();
+
+  /**
    * Notifies a node that it is about to be rebuilt. This method can only be called if the node
-   * {@link DirtyState#NEEDS_REBUILDING}. It returns the remaining deps of the node that had not
-   * yet been checked: all the keys that would be returned by successive calls to
-   * {@link #getNextDirtyDirectDeps}. It is the caller's responsibility to (uninterruptibly) remove
-   * the reverse deps those deps have on this node in order to keep the graph consistent. After this
-   * call, this node no longer has a dep on the nodes whose keys were returned by this call and
-   * is ready to be rebuilt (it will be in {@link DirtyState#REBUILDING}).
+   * {@link DirtyState#NEEDS_REBUILDING}. After this call, this node is ready to be rebuilt (it will
+   * be in {@link DirtyState#REBUILDING}).
    */
-  Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps();
+  void markRebuilding();
 
   /**
    * Returns the {@link GroupedList} of direct dependencies. This may only be called while the node