Fix performance regression in CriticalPathComputer.
Previously, when actions are change pruned, we add their entire transitive closure to critical path graph. This could slow down incremental builds if the action graph is large and only a small portion of it is invalidated.
This CL improves that by only adding actions that are invalidated (including change pruned).
We achieve that by updating Skyframe to emit change pruning event. These event are only emitted for nodes that were invalidated by dirtiness check during incremental builds. So that the CriticalPathComputer now operates on a subset of action graph that only contains dirty actions. This is more correct and performant for incremental builds.
PiperOrigin-RevId: 716146196
Change-Id: I71add4240458b5d4087b1af81a41202f98fee947
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionChangePrunedEvent.java b/src/main/java/com/google/devtools/build/lib/actions/ActionChangePrunedEvent.java
new file mode 100644
index 0000000..9a93bd30
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionChangePrunedEvent.java
@@ -0,0 +1,17 @@
+// Copyright 2025 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.actions;
+
+/** An event that is fired after an action is change pruned. */
+public record ActionChangePrunedEvent(ActionLookupData actionLookupData) {}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Actions.java b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
index 4c4d632..de5a2d6 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Actions.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
@@ -91,8 +91,8 @@
// Non-Actions cannot be shared.
&& a instanceof Action
&& b instanceof Action
- && a.getKey(actionKeyContext, /*artifactExpander=*/ null)
- .equals(b.getKey(actionKeyContext, /*artifactExpander=*/ null))
+ && a.getKey(actionKeyContext, /* artifactExpander= */ null)
+ .equals(b.getKey(actionKeyContext, /* artifactExpander= */ null))
&& artifactsEqualWithoutOwner(
a.getMandatoryInputs().toList(), b.getMandatoryInputs().toList())
&& artifactsEqualWithoutOwner(a.getOutputs(), b.getOutputs());
@@ -241,11 +241,7 @@
if (equalOutput != null) {
// Yes: assert that its generating action and this artifact's are compatible.
verifyGeneratingActionKeys(
- equalOutput,
- generatingActionKey,
- allowSharedAction,
- actionKeyContext,
- actions);
+ equalOutput, generatingActionKey, allowSharedAction, actionKeyContext, actions);
}
// Was this output already seen, so it has a generating action key set?
if (!output.hasGeneratingActionKey()) {
@@ -264,11 +260,7 @@
}
// Key is already set: verify that the generating action and this action are compatible.
verifyGeneratingActionKeys(
- output,
- generatingActionKey,
- allowSharedAction,
- actionKeyContext,
- actions);
+ output, generatingActionKey, allowSharedAction, actionKeyContext, actions);
}
}
actionIndex++;
@@ -381,18 +373,17 @@
}
/**
- * Returns the escaped name for a given relative path as a string. This takes
- * a short relative path and turns it into a string suitable for use as a
- * filename. Invalid filename characters are escaped with an '_' + a single
- * character token.
+ * Returns the escaped name for a given relative path as a string. This takes a short relative
+ * path and turns it into a string suitable for use as a filename. Invalid filename characters are
+ * escaped with an '_' + a single character token.
*/
public static String escapedPath(String path) {
return PATH_ESCAPER.escape(path);
}
/**
- * Returns a string that is usable as a unique path component for a label. It is guaranteed
- * that no other label maps to this string.
+ * Returns a string that is usable as a unique path component for a label. It is guaranteed that
+ * no other label maps to this string.
*/
public static String escapeLabel(Label label) {
String path = label.getPackageName() + ":" + label.getName();
@@ -419,8 +410,12 @@
return null;
}
- var generatingActionKey = ((Artifact.DerivedArtifact) artifact).getGeneratingActionKey();
- var actionLookupKey = generatingActionKey.getActionLookupKey();
+ return getAction(graph, ((Artifact.DerivedArtifact) artifact).getGeneratingActionKey());
+ }
+
+ public static ActionAnalysisMetadata getAction(
+ WalkableGraph graph, ActionLookupData actionLookupData) throws InterruptedException {
+ var actionLookupKey = actionLookupData.getActionLookupKey();
// In analysis caching build with cache hits, deserialized ActionLookupValues do not contain
// actions, so the generating action for the artifact does not exist in the graph. It would
@@ -433,7 +428,7 @@
if (graph.getValue(actionLookupKey) instanceof ActionLookupValue actionLookupValue) {
// Not all ActionLookupKeys resolve to an ActionLookupValue, e.g. RemoteConfiguredTargetValue.
if (actionLookupValue.getNumActions() > 0) {
- return actionLookupValue.getActions().get(generatingActionKey.getActionIndex());
+ return actionLookupValue.getActions().get(actionLookupData.getActionIndex());
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/BUILD b/src/main/java/com/google/devtools/build/lib/actions/BUILD
index 6c53e20..b681ae0 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/actions/BUILD
@@ -36,6 +36,7 @@
"ActionCacheAwareAction.java",
"ActionCacheChecker.java",
"ActionCacheUtils.java",
+ "ActionChangePrunedEvent.java",
"ActionCompletionEvent.java",
"ActionConcurrencyMeter.java",
"ActionConflictException.java",
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java
index 74cab9c..5484018 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java
@@ -16,6 +16,7 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.Sets;
import com.google.common.eventbus.EventBus;
+import com.google.devtools.build.lib.actions.ActionChangePrunedEvent;
import com.google.devtools.build.lib.actions.ActionExecutionStatusReporter;
import com.google.devtools.build.lib.actions.ActionLookupData;
import com.google.devtools.build.lib.analysis.ConfiguredTargetValue;
@@ -148,6 +149,13 @@
}
}
+ @Override
+ public void changePruned(SkyKey skyKey) {
+ if (skyKey.functionName().equals(SkyFunctions.ACTION_EXECUTION)) {
+ eventBus.post(new ActionChangePrunedEvent((ActionLookupData) skyKey.argument()));
+ }
+ }
+
/**
* {@inheritDoc}
*
diff --git a/src/main/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputer.java b/src/main/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputer.java
index 49f0c75..de734a8 100644
--- a/src/main/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputer.java
+++ b/src/main/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputer.java
@@ -14,7 +14,6 @@
package com.google.devtools.build.lib.metrics.criticalpath;
-import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.Comparators;
import com.google.common.collect.ImmutableList;
@@ -25,6 +24,7 @@
import com.google.common.flogger.StackSize;
import com.google.devtools.build.lib.actions.Action;
import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionChangePrunedEvent;
import com.google.devtools.build.lib.actions.ActionCompletionEvent;
import com.google.devtools.build.lib.actions.ActionKeyContext;
import com.google.devtools.build.lib.actions.ActionStartedEvent;
@@ -36,7 +36,7 @@
import com.google.devtools.build.lib.actions.SpawnExecutedEvent;
import com.google.devtools.build.lib.actions.SpawnMetrics;
import com.google.devtools.build.lib.actions.SpawnResult;
-import com.google.devtools.build.lib.analysis.FilesModifiedEvent;
+import com.google.devtools.build.lib.clock.BlazeClock;
import com.google.devtools.build.lib.skyframe.rewinding.ActionRewoundEvent;
import com.google.devtools.build.skyframe.WalkableGraph;
import java.time.Duration;
@@ -44,7 +44,6 @@
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.BinaryOperator;
@@ -82,8 +81,6 @@
private final ActionKeyContext actionKeyContext;
@Nullable private final WalkableGraph graph;
- private final AtomicBoolean queryGraph = new AtomicBoolean(false);
-
/** Maximum critical path found. */
private final AtomicReference<CriticalPathComponent> maxCriticalPath = new AtomicReference<>();
@@ -139,18 +136,6 @@
return outputArtifactToComponent;
}
- @VisibleForTesting
- void setQueryGraph(boolean queryGraph) {
- this.queryGraph.set(queryGraph);
- }
-
- @Subscribe
- public void onFilesModified(FilesModifiedEvent event) {
- // Only allow querying the graph if we have modified files from last build: only in this case
- // change-pruning could happen.
- queryGraph.set(event.numModifiedFiles() > 0);
- }
-
/** Changes the phase of the action */
@Subscribe
@AllowConcurrentEvents
@@ -331,6 +316,23 @@
event.getRelativeActionStartTimeNanos(), event.getFinishTimeNanos(), action, component, "");
}
+ @Subscribe
+ @AllowConcurrentEvents
+ public void actionChangePruned(ActionChangePrunedEvent event) throws InterruptedException {
+ if (graph == null) {
+ return;
+ }
+
+ var actionLookupData = event.actionLookupData();
+ if (!(Actions.getAction(graph, actionLookupData) instanceof Action action)) {
+ return;
+ }
+
+ var now = BlazeClock.nanoTime();
+ var component = tryAddComponent(createComponent(action, now));
+ finalizeActionStat(now, now, action, component, "change pruned");
+ }
+
/**
* Record that the failed rewound action is no longer running. The action may or may not start
* again later.
@@ -357,10 +359,9 @@
long finishTimeNanos,
Action action,
CriticalPathComponent component,
- String finalizeReason)
- throws InterruptedException {
+ String finalizeReason) {
for (Artifact input : action.getInputs().toList()) {
- addArtifactDependency(component, input, startTimeNanos, finishTimeNanos);
+ addArtifactDependency(component, input, finishTimeNanos);
}
if (Duration.ofNanos(finishTimeNanos - startTimeNanos).compareTo(Duration.ofMillis(-5)) < 0) {
// See note in {@link Clock#nanoTime} about non increasing subsequent #nanoTime calls.
@@ -374,23 +375,9 @@
/** If "input" is a generated artifact, link its critical path to the one we're building. */
private void addArtifactDependency(
- CriticalPathComponent actionStats,
- Artifact input,
- long componentStartNanos,
- long componentFinishNanos)
- throws InterruptedException {
+ CriticalPathComponent actionStats, Artifact input, long componentFinishNanos) {
CriticalPathComponent depComponent = outputArtifactToComponent.get(input);
- if (depComponent == null && !input.isSourceArtifact() && graph != null && queryGraph.get()) {
- // The generating action of the input is missing. It happens when the action was change
- // pruned in an incremental build. Query skyframe for the Action data.
- if (Actions.getGeneratingAction(graph, input) instanceof Action action) {
- depComponent = tryAddComponent(createComponent(action, componentStartNanos));
- finalizeActionStat(
- componentStartNanos, componentStartNanos, action, depComponent, "change pruning");
- }
- }
-
// Typically, the dep component should already be finished since its output was used as an input
// for a just-completed action. However, we tolerate it still running for (a) action rewinding
// and (b) the rare case that an action depending on a previously-cached shared action sees a
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 f99daa9..1a477a4 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
@@ -3292,6 +3292,13 @@
}
}
+ @Override
+ public void changePruned(SkyKey skyKey) {
+ if (executionProgressReceiver != null) {
+ executionProgressReceiver.changePruned(skyKey);
+ }
+ }
+
private void maybeDropGenQueryDep(SkyValue newValue, GroupedDeps directDeps) {
if (!(newValue instanceof RuleConfiguredTargetValue)) {
return;
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index e29e3c3..0ff0cae 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -357,7 +357,7 @@
.getProgressReceiver()
.evaluated(
skyKey,
- EvaluationState.get(valueMaybeWithMetadata, /* changed= */ false),
+ EvaluationState.get(valueMaybeWithMetadata, /* versionChanged= */ false),
/* newValue= */ null,
/* newError= */ null,
/* directDeps= */ null);
@@ -424,6 +424,9 @@
try {
evaluatorContext.getProgressReceiver().stateStarting(skyKey, NodeState.CHECK_DIRTY);
if (maybeHandleDirtyNode(nodeEntry) == DirtyOutcome.ALREADY_PROCESSED) {
+ if (nodeEntry.getLifecycleState() == LifecycleState.DONE) {
+ evaluatorContext.getProgressReceiver().changePruned(skyKey);
+ }
return;
}
} finally {
diff --git a/src/main/java/com/google/devtools/build/skyframe/CompoundEvaluationProgressReceiverBase.java b/src/main/java/com/google/devtools/build/skyframe/CompoundEvaluationProgressReceiverBase.java
index d24abbf..3d2219e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/CompoundEvaluationProgressReceiverBase.java
+++ b/src/main/java/com/google/devtools/build/skyframe/CompoundEvaluationProgressReceiverBase.java
@@ -75,4 +75,11 @@
receiver.evaluated(skyKey, state, newValue, newError, directDeps);
}
}
+
+ @Override
+ public void changePruned(SkyKey skyKey) {
+ for (EvaluationProgressReceiver receiver : receivers) {
+ receiver.changePruned(skyKey);
+ }
+ }
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyAndInflightTrackingProgressReceiver.java b/src/main/java/com/google/devtools/build/skyframe/DirtyAndInflightTrackingProgressReceiver.java
index 39d5c26..cc4a952 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyAndInflightTrackingProgressReceiver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyAndInflightTrackingProgressReceiver.java
@@ -81,6 +81,11 @@
}
}
+ @Override
+ public void changePruned(SkyKey skyKey) {
+ progressReceiver.changePruned(skyKey);
+ }
+
/**
* Called when a node was requested to be enqueued but wasn't because either an interrupt or an
* error (in nokeep_going mode) had occurred.
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java b/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java
index 109bc36..5e87b9d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluationProgressReceiver.java
@@ -140,4 +140,7 @@
@Nullable SkyValue newValue,
@Nullable ErrorInfo newError,
@Nullable GroupedDeps directDeps) {}
+
+ /** Notifies that the node for {@code skyKey} has been change pruned. */
+ default void changePruned(SkyKey skyKey) {}
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/InflightOnlyTrackingProgressReceiver.java b/src/main/java/com/google/devtools/build/skyframe/InflightOnlyTrackingProgressReceiver.java
index b240740..d7ee945 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InflightOnlyTrackingProgressReceiver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InflightOnlyTrackingProgressReceiver.java
@@ -92,6 +92,11 @@
inflightKeys.remove(skyKey);
}
+ @Override
+ public void changePruned(SkyKey skyKey) {
+ progressReceiver.changePruned(skyKey);
+ }
+
/** Returns if the key is enqueued for evaluation. */
@Override
public final boolean isInflight(SkyKey skyKey) {
diff --git a/src/test/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputerTest.java b/src/test/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputerTest.java
index 84903fe..890123b 100644
--- a/src/test/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/metrics/criticalpath/CriticalPathComputerTest.java
@@ -24,6 +24,7 @@
import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.actions.Action;
import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionChangePrunedEvent;
import com.google.devtools.build.lib.actions.ActionCompletionEvent;
import com.google.devtools.build.lib.actions.ActionKeyContext;
import com.google.devtools.build.lib.actions.ActionLookupData;
@@ -61,7 +62,6 @@
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.WalkableGraph;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
-import com.google.testing.junit.testparameterinjector.TestParameter;
import com.google.testing.junit.testparameterinjector.TestParameterInjector;
import java.time.Duration;
import java.time.Instant;
@@ -940,7 +940,7 @@
}
@Test
- public void testChangePruning(@TestParameter boolean queryGraph) throws Exception {
+ public void testChangePruning() throws Exception {
MockAction action1 =
new MockAction(ImmutableSet.of(), ImmutableSet.of(derivedArtifact("test/action1.out")));
MockAction action2 =
@@ -1021,7 +1021,6 @@
throw new UnsupportedOperationException();
}
});
- computer.setQueryGraph(queryGraph);
// Action 1 - 0s - 1s
long action1Start = clock.nanoTime();
@@ -1046,6 +1045,8 @@
new FakeActionInputFileCache(),
mock(ActionLookupData.class)));
// Action 3 - 3s - 3s, change pruned, no events
+ computer.actionChangePruned(
+ new ActionChangePrunedEvent(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA));
// Action 4 - 3s - 6s
long action4Start = clock.nanoTime();
computer.actionStarted(new ActionStartedEvent(action4, action4Start));
@@ -1058,44 +1059,24 @@
new FakeActionInputFileCache(),
mock(ActionLookupData.class)));
- if (queryGraph) {
- // The total run time should be 6s (Action 1 + Action 2 + Action 4) since Action 3 is
- // change-pruned.
- assertThat(computer.getMaxCriticalPath().getAggregatedElapsedTime())
- .isEqualTo(Duration.ofSeconds(6));
- AggregatedCriticalPath criticalPath = computer.aggregate();
- assertThat(criticalPath.components()).hasSize(4);
- // Action 4 has a run time of 3 seconds
- assertThat(criticalPath.components().get(0).prettyPrintAction()).contains("action4.out");
- assertThat(criticalPath.components().get(0).getElapsedTime())
- .isEqualTo(Duration.ofSeconds(3));
- // Action 3 has a run time of 0 seconds
- assertThat(criticalPath.components().get(1).prettyPrintAction()).contains("action3.out");
- assertThat(criticalPath.components().get(1).getElapsedTime()).isEqualTo(Duration.ZERO);
- // Action 2 has a run time of 2 seconds
- assertThat(criticalPath.components().get(2).prettyPrintAction()).contains("action2.out");
- assertThat(criticalPath.components().get(2).getElapsedTime())
- .isEqualTo(Duration.ofSeconds(2));
- // Action 1 has a run time of 1 seconds
- assertThat(criticalPath.components().get(3).prettyPrintAction()).contains("action1.out");
- assertThat(criticalPath.components().get(3).getElapsedTime())
- .isEqualTo(Duration.ofSeconds(1));
- } else {
- // The total run time should be 3s (Action 1 + Action 4) since Action 3 is change-pruned and
- // queryGraph is false.
- assertThat(computer.getMaxCriticalPath().getAggregatedElapsedTime())
- .isEqualTo(Duration.ofSeconds(4));
- AggregatedCriticalPath criticalPath = computer.aggregate();
- assertThat(criticalPath.components()).hasSize(2);
- // Action 4 has a run time of 3 seconds
- assertThat(criticalPath.components().get(0).prettyPrintAction()).contains("action4.out");
- assertThat(criticalPath.components().get(0).getElapsedTime())
- .isEqualTo(Duration.ofSeconds(3));
- // Action 1 has a run time of 1 seconds
- assertThat(criticalPath.components().get(1).prettyPrintAction()).contains("action1.out");
- assertThat(criticalPath.components().get(1).getElapsedTime())
- .isEqualTo(Duration.ofSeconds(1));
- }
+ // The total run time should be 6s (Action 1 + Action 2 + Action 4) since Action 3 is
+ // change-pruned.
+ assertThat(computer.getMaxCriticalPath().getAggregatedElapsedTime())
+ .isEqualTo(Duration.ofSeconds(6));
+ AggregatedCriticalPath criticalPath = computer.aggregate();
+ assertThat(criticalPath.components()).hasSize(4);
+ // Action 4 has a run time of 3 seconds
+ assertThat(criticalPath.components().get(0).prettyPrintAction()).contains("action4.out");
+ assertThat(criticalPath.components().get(0).getElapsedTime()).isEqualTo(Duration.ofSeconds(3));
+ // Action 3 has a run time of 0 seconds
+ assertThat(criticalPath.components().get(1).prettyPrintAction()).contains("action3.out");
+ assertThat(criticalPath.components().get(1).getElapsedTime()).isEqualTo(Duration.ZERO);
+ // Action 2 has a run time of 2 seconds
+ assertThat(criticalPath.components().get(2).prettyPrintAction()).contains("action2.out");
+ assertThat(criticalPath.components().get(2).getElapsedTime()).isEqualTo(Duration.ofSeconds(2));
+ // Action 1 has a run time of 1 seconds
+ assertThat(criticalPath.components().get(3).prettyPrintAction()).contains("action1.out");
+ assertThat(criticalPath.components().get(3).getElapsedTime()).isEqualTo(Duration.ofSeconds(1));
}
private void simulateActionExec(Action action, int totalTime) throws InterruptedException {
