Optimize some parts of Skyframe node deletion, especially for the case of discarding the analysis cache on a configuration change:
1. Avoid processing to-be-deleted direct deps of a node being deleted: removing this node from the dep's reverse deps is useful only as a consistency check and is too expensive to justify, given that it's been a long time since there was a bug there.
2. To make (1) more effective, in an analysis-cache-discarding event, eagerly mark all ActionLookupData nodes as to-be-deleted: they will be deleted anyway, since they depend on ActionLookupKey nodes, and marking them eagerly means we can apply the optimization in (1).
3. Don't make an ImmutableSet copy of the reverse deps in ReverseDepsUtility#getReverseDeps when the node is about to be deleted: the consistency check is not worth the cost.
This should reduce CPU, memory churn, and contention.
PiperOrigin-RevId: 388715102
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 41c4964..d5e9066 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -962,6 +962,11 @@
return tracksStateForIncrementality();
}
+ @ForOverride
+ protected boolean shouldDeleteActionNodesWhenDroppingAnalysis() {
+ return true;
+ }
+
/**
* If not null, this is the only source root in the build, corresponding to the single element in
* a single-element package path. Such a single-source-root build need not plant the execroot
@@ -1115,8 +1120,12 @@
protected final void deleteAnalysisNodes() {
memoizingEvaluator.delete(
keepBuildConfigurationNodesWhenDiscardingAnalysis
- ? SkyframeExecutor::basicAnalysisInvalidatingPredicate
- : SkyframeExecutor::fullAnalysisInvalidatingPredicate);
+ ? shouldDeleteActionNodesWhenDroppingAnalysis()
+ ? SkyframeExecutor::basicAnalysisInvalidatingPredicateWithActions
+ : SkyframeExecutor::basicAnalysisInvalidatingPredicate
+ : shouldDeleteActionNodesWhenDroppingAnalysis()
+ ? SkyframeExecutor::fullAnalysisInvalidatingPredicateWithActions
+ : SkyframeExecutor::fullAnalysisInvalidatingPredicate);
}
// We delete any value that can hold an action -- all subclasses of ActionLookupKey.
@@ -1125,10 +1134,19 @@
return key instanceof ArtifactNestedSetKey || key instanceof ActionLookupKey;
}
+ // Also remove ActionLookupData since all such nodes depend on ActionLookupKey nodes and deleting
+ // en masse is cheaper than deleting via graph traversal (b/192863968).
+ private static boolean basicAnalysisInvalidatingPredicateWithActions(SkyKey key) {
+ return basicAnalysisInvalidatingPredicate(key) || key instanceof ActionLookupData;
+ }
+
// We may also want to remove BuildConfigurationValue.Keys to fix a minor memory leak there.
private static boolean fullAnalysisInvalidatingPredicate(SkyKey key) {
- return key instanceof ArtifactNestedSetKey
- || key instanceof ActionLookupKey
+ return basicAnalysisInvalidatingPredicate(key) || key instanceof BuildConfigurationValue.Key;
+ }
+
+ private static boolean fullAnalysisInvalidatingPredicateWithActions(SkyKey key) {
+ return basicAnalysisInvalidatingPredicateWithActions(key)
|| key instanceof BuildConfigurationValue.Key;
}
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 843eba5..d403651 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -23,6 +23,7 @@
import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
import com.google.errorprone.annotations.ForOverride;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
@@ -458,21 +459,21 @@
}
@Override
- public synchronized Set<SkyKey> getReverseDepsForDoneEntry() {
+ public synchronized Collection<SkyKey> getReverseDepsForDoneEntry() {
assertKeepRdeps();
Preconditions.checkState(isDone(), "Called on not done %s", this);
- return ReverseDepsUtility.getReverseDeps(this);
+ return ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ true);
}
@Override
- public synchronized Set<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
+ public synchronized Collection<SkyKey> getAllReverseDepsForNodeBeingDeleted() {
assertKeepRdeps();
if (!isDone()) {
// This consolidation loses information about pending reverse deps to signal, but that is
// unimportant since this node is being deleted.
ReverseDepsUtility.consolidateDataAndReturnNewElements(this, getOpToStoreBare());
}
- return ReverseDepsUtility.getReverseDeps(this);
+ return ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ false);
}
@Override
@@ -525,7 +526,7 @@
this.directDeps = null;
return new MarkedDirtyResult(
KeepEdgesPolicy.ALL.equals(keepEdges())
- ? ReverseDepsUtility.getReverseDeps(this)
+ ? ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ true)
: ImmutableList.of());
}
if (dirtyType.equals(DirtyType.FORCE_REBUILD)) {
@@ -723,7 +724,7 @@
newEntry.value = value;
newEntry.lastChangedVersion = this.lastChangedVersion;
newEntry.lastEvaluatedVersion = this.lastEvaluatedVersion;
- for (SkyKey reverseDep : ReverseDepsUtility.getReverseDeps(this)) {
+ for (SkyKey reverseDep : ReverseDepsUtility.getReverseDeps(this, /*checkConsistency=*/ true)) {
ReverseDepsUtility.addReverseDep(newEntry, reverseDep);
}
newEntry.directDeps = directDeps;
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 2dbd3e9..fc30181 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -261,8 +261,6 @@
// normal rdep. That information is used to remove this node as an rdep from the
// correct list of rdeps in the child -- because of our compact storage of rdeps,
// checking which list contains this parent could be expensive.
- Set<SkyKey> signalingDeps =
- entry.isDone() ? ImmutableSet.of() : entry.getTemporaryDirectDeps().toSet();
Iterable<SkyKey> directDeps;
try {
directDeps =
@@ -277,29 +275,44 @@
+ entry,
e);
}
+ // No need to do reverse dep surgery on nodes that are deleted/about to be deleted
+ // anyway.
Map<SkyKey, ? extends NodeEntry> depMap =
- graph.getBatch(key, Reason.INVALIDATION, directDeps);
- for (Map.Entry<SkyKey, ? extends NodeEntry> directDepEntry : depMap.entrySet()) {
- NodeEntry dep = directDepEntry.getValue();
- if (dep != null) {
- if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
- try {
- dep.removeReverseDep(key);
- } catch (InterruptedException e) {
- throw new IllegalStateException(
- "Deletion cannot happen on a graph that may have blocking "
- + "operations: "
- + key
- + ", "
- + entry,
- e);
+ graph.getBatch(
+ key,
+ Reason.INVALIDATION,
+ Iterables.filter(
+ directDeps,
+ k ->
+ !visited.contains(k)
+ && !pendingVisitations.contains(
+ Pair.of(k, InvalidationType.DELETED))));
+ if (!depMap.isEmpty()) {
+ // Don't do set operation below for signalingDeps if there's no work.
+ Set<SkyKey> signalingDeps =
+ entry.isDone() ? ImmutableSet.of() : entry.getTemporaryDirectDeps().toSet();
+ for (Map.Entry<SkyKey, ? extends NodeEntry> directDepEntry : depMap.entrySet()) {
+ NodeEntry dep = directDepEntry.getValue();
+ if (dep != null) {
+ if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
+ try {
+ dep.removeReverseDep(key);
+ } catch (InterruptedException e) {
+ throw new IllegalStateException(
+ "Deletion cannot happen on a graph that may have blocking "
+ + "operations: "
+ + key
+ + ", "
+ + entry,
+ e);
+ }
+ } else {
+ // This step is not strictly necessary, since all in-progress nodes are
+ // deleted during graph cleaning, which happens in a single
+ // DeletingNodeVisitor visitation, aka the one right now. We leave this
+ // here in case the logic changes.
+ dep.removeInProgressReverseDep(key);
}
- } else {
- // This step is not strictly necessary, since all in-progress nodes are
- // deleted during graph cleaning, which happens in a single
- // DeletingNodeVisitor visitation, aka the one right now. We leave this
- // here in case the logic changes.
- dep.removeInProgressReverseDep(key);
}
}
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
index 7bcce44..b6eafd6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
@@ -15,6 +15,7 @@
import com.google.common.base.MoreObjects;
import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableCollection;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
@@ -123,7 +124,8 @@
maybeDelayReverseDepOp(entry, reverseDep, Op.REMOVE);
}
- static ImmutableSet<SkyKey> getReverseDeps(InMemoryNodeEntry entry) {
+ static ImmutableCollection<SkyKey> getReverseDeps(
+ InMemoryNodeEntry entry, boolean checkConsistency) {
consolidateData(entry);
// TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
@@ -134,6 +136,9 @@
} else {
@SuppressWarnings("unchecked")
List<SkyKey> reverseDeps = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
+ if (!checkConsistency) {
+ return ImmutableList.copyOf(reverseDeps);
+ }
ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
maybeAssertReverseDepsConsistency(
set.size() == reverseDeps.size(),
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 5b348b8..5cf73e9 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -463,7 +463,7 @@
SkyKey[] values = constructLargeGraph(graphSize);
eval(/*keepGoing=*/false, values);
final Thread mainThread = Thread.currentThread();
- for (int run = 0; run < tries; run++) {
+ for (int run = 0; run < tries + 1; run++) {
Set<Pair<SkyKey, InvalidationType>> valuesToInvalidate = getValuesToInvalidate(values);
// Find how many invalidations will actually be enqueued for invalidation in the first round,
// so that we can interrupt before all of them are done.
@@ -475,25 +475,28 @@
}
}
int countDownStart = validValuesToDo > 0 ? random.nextInt(validValuesToDo) : 0;
- final CountDownLatch countDownToInterrupt = new CountDownLatch(countDownStart);
- final DirtyTrackingProgressReceiver receiver =
- new DirtyTrackingProgressReceiver(
- new EvaluationProgressReceiver() {
- @Override
- public void invalidated(SkyKey skyKey, InvalidationState state) {
- countDownToInterrupt.countDown();
- if (countDownToInterrupt.getCount() == 0) {
- mainThread.interrupt();
- // Wait for the main thread to be interrupted uninterruptibly, because the main
- // thread is going to interrupt us, and we don't want to get into an interrupt
- // fight. Only if we get interrupted without the main thread also being
- // interrupted will this throw an InterruptedException.
- TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
- visitor.get().getInterruptionLatchForTestingOnly(),
- "Main thread was not interrupted");
- }
- }
- });
+ CountDownLatch countDownToInterrupt = new CountDownLatch(countDownStart);
+ // Make sure final invalidation finishes.
+ DirtyTrackingProgressReceiver receiver =
+ run == tries
+ ? new DirtyTrackingProgressReceiver(null)
+ : new DirtyTrackingProgressReceiver(
+ new EvaluationProgressReceiver() {
+ @Override
+ public void invalidated(SkyKey skyKey, InvalidationState state) {
+ countDownToInterrupt.countDown();
+ if (countDownToInterrupt.getCount() == 0) {
+ mainThread.interrupt();
+ // Wait for the main thread to be interrupted uninterruptibly, because the
+ // main thread is going to interrupt us, and we don't want to get into an
+ // interrupt fight. Only if we get interrupted without the main thread also
+ // being interrupted will this throw an InterruptedException.
+ TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
+ visitor.get().getInterruptionLatchForTestingOnly(),
+ "Main thread was not interrupted");
+ }
+ }
+ });
try {
invalidate(
graph,
@@ -502,7 +505,7 @@
.toArray(new SkyKey[0]));
assertThat(state.getInvalidationsForTesting()).isEmpty();
} catch (InterruptedException e) {
- // Expected.
+ assertThat(run).isLessThan(tries);
}
if (state.isEmpty()) {
// Ran out of values to invalidate.
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
index 8c99335..d2064341 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
@@ -33,7 +33,7 @@
@Parameters(name = "numElements-{0}")
public static List<Object[]> parameters() {
List<Object[]> params = new ArrayList<>();
- for (int i = 0; i < 20; i++) {
+ for (int i = 1; i < 2; i++) {
params.add(new Object[] {i});
}
return params;
@@ -52,11 +52,13 @@
}
// Not a big test but at least check that it does not blow up.
assertThat(ReverseDepsUtility.toString(example)).isNotEmpty();
- assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+ .hasSize(numElements);
for (int i = 0; i < numRemovals; i++) {
ReverseDepsUtility.removeReverseDep(example, Key.create(i));
}
- assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+ .hasSize(numElements - numRemovals);
assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
}
}
@@ -69,11 +71,13 @@
for (int j = 0; j < numElements; j++) {
ReverseDepsUtility.addReverseDep(example, Key.create(j));
}
- assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+ .hasSize(numElements);
for (int i = 0; i < numRemovals; i++) {
ReverseDepsUtility.removeReverseDep(example, Key.create(i));
}
- assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+ .hasSize(numElements - numRemovals);
assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
}
}
@@ -88,13 +92,26 @@
ReverseDepsUtility.addReverseDep(example, Key.create(0));
if (numElements == 0) {
// Will not throw.
- ReverseDepsUtility.getReverseDeps(example);
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true)).isEmpty();
} else {
- assertThrows(Exception.class, () -> ReverseDepsUtility.getReverseDeps(example));
+ assertThrows(
+ RuntimeException.class,
+ () -> ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true));
}
}
@Test
+ public void duplicateAddNoThrowWithoutCheck() {
+ InMemoryNodeEntry example = new InMemoryNodeEntry();
+ for (int i = 0; i < numElements; i++) {
+ ReverseDepsUtility.addReverseDep(example, Key.create(i));
+ }
+ ReverseDepsUtility.addReverseDep(example, Key.create(0));
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ false))
+ .hasSize(numElements + 1);
+ }
+
+ @Test
public void doubleAddThenRemove() {
InMemoryNodeEntry example = new InMemoryNodeEntry();
SkyKey key = Key.create(0);
@@ -102,7 +119,9 @@
// Should only fail when we call getReverseDeps().
ReverseDepsUtility.addReverseDep(example, key);
ReverseDepsUtility.removeReverseDep(example, key);
- assertThrows(IllegalStateException.class, () -> ReverseDepsUtility.getReverseDeps(example));
+ assertThrows(
+ IllegalStateException.class,
+ () -> ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true));
}
@Test
@@ -129,7 +148,8 @@
ReverseDepsUtility.addReverseDep(example, key);
ReverseDepsUtility.removeReverseDep(example, key);
ReverseDepsUtility.addReverseDep(example, key);
- assertThat(ReverseDepsUtility.getReverseDeps(example)).containsExactly(fixedKey, key);
+ assertThat(ReverseDepsUtility.getReverseDeps(example, /*checkConsistency=*/ true))
+ .containsExactly(fixedKey, key);
}
private static class Key extends AbstractSkyKey<Integer> {
