Integrate TieredPriorityExecutor under flag.
* Change is guarded behind the new flag
--experimental_use_priority_in_analysis.
* Adds a priority to DirtyBuildingState. The priority based on a
combination of a node's depth and how many times it has been
restarted. Previously, information about a node's priority would be lost
on restart and guessed from children.
* Adds `hasLowFanout` attribute to `SkyKey`, defaulting to true, and set false
for `ActionLookupKey`, which has been observed to have more than 10k
dependencies.
PiperOrigin-RevId: 509575949
Change-Id: I3061508e297be2b824b7ac2c4ab1d30350488b89
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupKey.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupKey.java
index 6c609d4..23f07b1 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupKey.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupKey.java
@@ -30,14 +30,14 @@
* are subclasses of {@link ActionLookupKey}. This allows callers to easily find the value key,
* while remaining agnostic to what action lookup values actually exist.
*/
-public interface ActionLookupKey extends ArtifactOwner, CPUHeavySkyKey {
+public abstract class ActionLookupKey implements ArtifactOwner, CPUHeavySkyKey {
/**
* Returns the {@link BuildConfigurationKey} for the configuration associated with this key, or
* {@code null} if this key has no associated configuration.
*/
@Nullable
- BuildConfigurationKey getConfigurationKey();
+ public abstract BuildConfigurationKey getConfigurationKey();
/**
* Returns {@code true} if this key <em>may</em> own shareable actions, as determined by {@link
@@ -50,7 +50,12 @@
* to determine whether the individual action can be shared - notably, for a test target,
* compilation actions are shareable, but test actions are not.
*/
- default boolean mayOwnShareableActions() {
+ public boolean mayOwnShareableActions() {
return getLabel() != null;
}
+
+ @Override
+ public boolean hasLowFanout() {
+ return false; // May have >10k deps.
+ }
}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
index f7cc396..77aa61d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
@@ -133,4 +133,18 @@
+ " be used. Example value: \"HOST_CPUS*0.5\".",
converter = CpuResourceConverter.class)
public int oomSensitiveSkyFunctionsSemaphoreSize;
+
+ @Option(
+ name = "experimental_use_priority_in_analysis",
+ defaultValue = "false",
+ documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
+ effectTags = {
+ OptionEffectTag.LOADING_AND_ANALYSIS,
+ OptionEffectTag.BAZEL_INTERNAL_CONFIGURATION
+ },
+ help =
+ "If true, runs the analysis phase with priority queuing for SkyFunctions, improving large"
+ + " build performance. This option is ignored unless"
+ + " experimental_skyframe_cpu_heavy_skykeys_thread_pool_size has a positive value.")
+ public boolean usePrioritization;
}
diff --git a/src/main/java/com/google/devtools/build/lib/concurrent/QuiescingExecutors.java b/src/main/java/com/google/devtools/build/lib/concurrent/QuiescingExecutors.java
index 240ba97..e3555ea 100644
--- a/src/main/java/com/google/devtools/build/lib/concurrent/QuiescingExecutors.java
+++ b/src/main/java/com/google/devtools/build/lib/concurrent/QuiescingExecutors.java
@@ -21,6 +21,8 @@
int globbingParallelism();
+ boolean usePrioritizationForAnalysis();
+
QuiescingExecutor getAnalysisExecutor();
QuiescingExecutor getExecutionExecutor();
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/QuiescingExecutorsImpl.java b/src/main/java/com/google/devtools/build/lib/runtime/QuiescingExecutorsImpl.java
index 4004db3..524e7af 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/QuiescingExecutorsImpl.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/QuiescingExecutorsImpl.java
@@ -23,6 +23,7 @@
import com.google.devtools.build.lib.concurrent.MultiExecutorQueueVisitor;
import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
import com.google.devtools.build.lib.concurrent.QuiescingExecutors;
+import com.google.devtools.build.lib.concurrent.TieredPriorityExecutor;
import com.google.devtools.build.lib.pkgcache.PackageOptions;
import com.google.devtools.build.skyframe.ParallelEvaluatorErrorClassifier;
import com.google.devtools.common.options.OptionsProvider;
@@ -51,13 +52,17 @@
*/
private int cpuHeavySkyKeysThreadPoolSize;
+ private boolean usePrioritizationForAnalysis;
+
@VisibleForTesting
public static QuiescingExecutors forTesting() {
return new QuiescingExecutorsImpl(
/* analysisParallelism= */ 6,
/* executionParallelism= */ 6,
/* globbingParallelism= */ 6,
- /* cpuHeavySkyKeysThreadPoolSize= */ 4);
+ /* cpuHeavySkyKeysThreadPoolSize= */ 4,
+ // Prioritization needs more test coverage.
+ /* usePrioritizationForAnalysis= */ true);
}
static QuiescingExecutorsImpl createDefault() {
@@ -65,18 +70,21 @@
/* analysisParallelism= */ 0,
/* executionParallelism= */ 0,
/* globbingParallelism= */ 0,
- /* cpuHeavySkyKeysThreadPoolSize= */ 0);
+ /* cpuHeavySkyKeysThreadPoolSize= */ 0,
+ /* usePrioritizationForAnalysis= */ false);
}
private QuiescingExecutorsImpl(
int analysisParallelism,
int executionParallelism,
int globbingParallelism,
- int cpuHeavySkyKeysThreadPoolSize) {
+ int cpuHeavySkyKeysThreadPoolSize,
+ boolean usePrioritizationForAnalysis) {
this.analysisParallelism = analysisParallelism;
this.executionParallelism = executionParallelism;
this.globbingParallelism = globbingParallelism;
this.cpuHeavySkyKeysThreadPoolSize = cpuHeavySkyKeysThreadPoolSize;
+ this.usePrioritizationForAnalysis = usePrioritizationForAnalysis;
}
void resetParameters(OptionsProvider options) {
@@ -97,6 +105,19 @@
var analysisOptions = options.getOptions(AnalysisOptions.class);
this.cpuHeavySkyKeysThreadPoolSize =
analysisOptions != null ? analysisOptions.cpuHeavySkyKeysThreadPoolSize : 0;
+ if (analysisOptions != null) {
+ this.cpuHeavySkyKeysThreadPoolSize = analysisOptions.cpuHeavySkyKeysThreadPoolSize;
+ if ((this.usePrioritizationForAnalysis = analysisOptions.usePrioritization)) {
+ if (cpuHeavySkyKeysThreadPoolSize > analysisParallelism) {
+ // The prioritizing executor requires the CPU heavy pool size to be no more than
+ // analysis parallelism.
+ this.cpuHeavySkyKeysThreadPoolSize = analysisParallelism;
+ }
+ }
+ } else {
+ this.cpuHeavySkyKeysThreadPoolSize = 0;
+ this.usePrioritizationForAnalysis = false;
+ }
}
@Override
@@ -115,9 +136,21 @@
}
@Override
+ public boolean usePrioritizationForAnalysis() {
+ return usePrioritizationForAnalysis;
+ }
+
+ @Override
public QuiescingExecutor getAnalysisExecutor() {
checkState(analysisParallelism > 0, "expected analysisParallelism > 0 : %s", this);
if (cpuHeavySkyKeysThreadPoolSize > 0) {
+ if (usePrioritizationForAnalysis) {
+ return new TieredPriorityExecutor(
+ "skyframe-evaluator",
+ analysisParallelism,
+ cpuHeavySkyKeysThreadPoolSize,
+ ParallelEvaluatorErrorClassifier.instance());
+ }
return MultiExecutorQueueVisitor.createWithExecutorServices(
newNamedPool(SKYFRAME_EVALUATOR, analysisParallelism),
AbstractQueueVisitor.createExecutorService(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
index 6f83aab..2298a07 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
@@ -36,7 +36,7 @@
/** Key for {@link ActionTemplateExpansionValue} nodes. */
@AutoCodec
- public static final class ActionTemplateExpansionKey implements ActionLookupKey {
+ public static final class ActionTemplateExpansionKey extends ActionLookupKey {
private static final Interner<ActionTemplateExpansionKey> interner =
BlazeInterners.newWeakInterner();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectKeyCreator.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectKeyCreator.java
index 2526999..fc34f04 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectKeyCreator.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectKeyCreator.java
@@ -60,7 +60,7 @@
}
/** Common superclass for {@link AspectKey} and {@link TopLevelAspectsKey}. */
- public abstract static class AspectBaseKey implements ActionLookupKey {
+ public abstract static class AspectBaseKey extends ActionLookupKey {
private final ConfiguredTargetKey baseConfiguredTargetKey;
private final int hashCode;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
index 9a98352..4c82613 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
@@ -57,7 +57,7 @@
/** Key for BuildInfoCollectionValues. */
@AutoCodec
- public static final class BuildInfoKeyAndConfig implements ActionLookupKey {
+ public static final class BuildInfoKeyAndConfig extends ActionLookupKey {
private static final Interner<BuildInfoKeyAndConfig> keyInterner =
BlazeInterners.newWeakInterner();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
index d52af1d..a4c504c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
@@ -58,7 +58,7 @@
* BuildConfigurationKey.
*/
@AutoCodec
-public class ConfiguredTargetKey implements ActionLookupKey {
+public class ConfiguredTargetKey extends ActionLookupKey {
/**
* Cache so that the number of ConfiguredTargetKey instances is {@code O(configured targets)} and
* not {@code O(edges between configured targets)}.
@@ -101,6 +101,7 @@
}
@Nullable
+ @Override
public final BuildConfigurationKey getConfigurationKey() {
return configurationKey;
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
index e7001df..fd474db 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
@@ -32,7 +32,7 @@
super(generatingActions);
}
- private static final class CoverageReportKey implements ActionLookupKey {
+ private static final class CoverageReportKey extends ActionLookupKey {
private CoverageReportKey() {}
@Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
index 653cc48..ceadba4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
@@ -54,7 +54,7 @@
}
/** {@link com.google.devtools.build.skyframe.SkyKey} for {@link WorkspaceStatusValue}. */
- public static final class BuildInfoKey implements ActionLookupKey {
+ public static final class BuildInfoKey extends ActionLookupKey {
private BuildInfoKey() {}
@Override
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 ca7f1ee..7b6b997 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -29,7 +29,6 @@
import com.google.common.graph.ImmutableGraph;
import com.google.common.graph.Traverser;
import com.google.common.util.concurrent.ListenableFuture;
-import com.google.devtools.build.lib.bugreport.BugReport;
import com.google.devtools.build.lib.clock.BlazeClock;
import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
import com.google.devtools.build.lib.concurrent.ComparableRunnable;
@@ -56,7 +55,6 @@
import java.util.Collection;
import java.util.List;
import java.util.Set;
-import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.atomic.AtomicInteger;
import javax.annotation.Nullable;
@@ -98,24 +96,16 @@
abstract class AbstractParallelEvaluator {
private static final GoogleLogger logger = GoogleLogger.forEnclosingClass();
- /**
- * The priority to use the first time a node is restarted.
- *
- * <p>This is designed to be higher than any value coming from {@link #globalEnqueuedIndex} so
- * that we get nodes that have previously started evaluation off our plate.
- */
- private static final int FIRST_RESTART_PRIORITY = Integer.MAX_VALUE / 2;
-
final ProcessableGraph graph;
final ParallelEvaluatorContext evaluatorContext;
protected final CycleDetector cycleDetector;
/**
- * Monotonically increasing counter designed to encourage depth-first graph exploration.
+ * A decreasing counter that results in FIFO priority tie-breaking for prioritization.
*
- * <p>It is expected that this never exceeds {@link #FIRST_RESTART_PRIORITY}.
+ * <p>FIFO is friendlier to priority queues.
*/
- private final AtomicInteger globalEnqueuedIndex = new AtomicInteger(Integer.MIN_VALUE);
+ private final AtomicInteger nextEvaluateId = new AtomicInteger(Integer.MAX_VALUE);
protected final Cache<SkyKey, SkyKeyComputeState> stateCache = Caffeine.newBuilder().build();
@@ -173,65 +163,40 @@
/**
* An action that evaluates a value.
*
- * <p>{@link Comparable} for use in priority queues. Experimentally, grouping enqueued evaluations
- * together by parent leads to fewer in-flight evaluations and thus lower peak memory usage. Thus
- * we store the {@link #evaluationPriority} (coming from the {@link #globalEnqueuedIndex} and use
- * it for comparisons: later enqueuings should be evaluated earlier, to do a depth-first search,
- * except for re-enqueued nodes, which always get top priority.
- *
- * <p>This is not applicable when using a {@link ForkJoinPool}, since it does not allow for easy
- * work prioritization.
+ * <p>{@link Comparable} for use in priority queues.
*/
private final class Evaluate implements ComparableRunnable {
private final SkyKey skyKey;
- private final int evaluationPriority;
+ private final long priority;
- private Evaluate(SkyKey skyKey, int evaluationPriority) {
+ private Evaluate(SkyKey skyKey, int partialPriority) {
this.skyKey = skyKey;
- this.evaluationPriority = evaluationPriority;
+
+ // LIFO could be more robust here. In the absence of other prioritization, LIFO exploits the
+ // fact that later arriving requests tend to be deeper in the graph. However, LIFO is not a
+ // good access pattern for priority queues as it increases reader / writer contention.
+ // Measurements show FIFO is faster with existing prioritization.
+ this.priority = (((long) partialPriority) << 32) | nextEvaluateId.getAndDecrement();
+ }
+
+ @Override
+ public boolean isCpuHeavy() {
+ return skyKey instanceof CPUHeavySkyKey;
}
@Override
public int compareTo(ComparableRunnable other) {
- // Put other one first, so larger values come first in priority queue.
- return Integer.compare(((Evaluate) other).evaluationPriority, this.evaluationPriority);
- }
-
- private int determineChildPriority() {
- // If this evaluation is already running at a high priority, its children should be evaluated
- // at an even higher priority - they are blocking a high priority node.
- if (evaluationPriority >= FIRST_RESTART_PRIORITY) {
- return evenHigherPriority();
- }
-
- int nextPriority = globalEnqueuedIndex.incrementAndGet();
- if (nextPriority == FIRST_RESTART_PRIORITY) {
- BugReport.sendBugReport(
- new ArithmeticException("Child priority has reached restart priority"));
- }
- return nextPriority;
- }
-
- private int determineRestartPriority() {
- // Each time a node is restarted, its priority increases so that it doesn't get lost behind
- // other restarted nodes.
- return evaluationPriority >= FIRST_RESTART_PRIORITY
- ? evenHigherPriority()
- : FIRST_RESTART_PRIORITY;
- }
-
- private int evenHigherPriority() {
- if (evaluationPriority == Integer.MAX_VALUE) {
- BugReport.sendBugReport(new ArithmeticException("Priority has reached Integer.MAX_VALUE"));
- return Integer.MAX_VALUE;
- }
- return evaluationPriority + 1;
+ // Compares in reverse order so that keys with high priority are evaluated first.
+ return Long.compare(((Evaluate) other).priority, priority);
}
/**
* Notes the rdep from the parent to the child, and then does the appropriate thing with the
* child or the parent, returning whether the parent has both been signalled and also is ready
* for evaluation.
+ *
+ * @param childDepth this should match {@code entry.getChildDepth()} but that performs some
+ * computation and this is often called in a loop with the same {@code entry}.
*/
@CanIgnoreReturnValue
private boolean enqueueChild(
@@ -240,7 +205,7 @@
SkyKey child,
NodeEntry childEntry,
boolean depAlreadyExists,
- int childEvaluationPriority,
+ int childDepth,
boolean enqueueParentIfReady,
@Nullable SkyFunctionEnvironment environmentIfEnqueuing)
throws InterruptedException {
@@ -255,13 +220,12 @@
// Add some more context regarding crashes.
throw new IllegalStateException("child key: " + child + " error: " + e.getMessage(), e);
}
+ childEntry.updateDepthIfGreater(childDepth);
switch (dependencyState) {
case DONE:
if (entry.signalDep(childEntry.getVersion(), child)) {
if (enqueueParentIfReady) {
- evaluatorContext
- .getVisitor()
- .enqueueEvaluation(skyKey, determineRestartPriority(), child);
+ evaluatorContext.getVisitor().enqueueEvaluation(skyKey, entry.getPriority(), child);
}
return true;
} else {
@@ -271,16 +235,14 @@
// If a dep was observed not-done by its parent when the parent tried to read its
// value, but that dep is now done, then this is the only chance the parent has to be
// signalled by that dep.
- evaluatorContext
- .getVisitor()
- .enqueueEvaluation(skyKey, determineRestartPriority(), child);
+ evaluatorContext.getVisitor().enqueueEvaluation(skyKey, entry.getPriority(), child);
}
}
break;
case ALREADY_EVALUATING:
break;
case NEEDS_SCHEDULING:
- evaluatorContext.getVisitor().enqueueEvaluation(child, childEvaluationPriority, null);
+ evaluatorContext.getVisitor().enqueueEvaluation(child, childEntry.getPriority(), null);
break;
}
return false;
@@ -401,7 +363,6 @@
unknownStatusDeps,
entriesToCheck,
nodeEntry,
- determineChildPriority(),
/* enqueueParentIfReady= */ false,
/* environmentIfEnqueuing= */ null);
if (!parentIsSignalledAndReady
@@ -438,7 +399,7 @@
throw SchedulerException.ofError(nodeEntry.getErrorInfo(), skyKey, rDepsToSignal);
}
evaluatorContext.signalParentsAndEnqueueIfReady(
- skyKey, rDepsToSignal, nodeEntry.getVersion(), determineRestartPriority());
+ skyKey, rDepsToSignal, nodeEntry.getVersion());
return DirtyOutcome.ALREADY_PROCESSED;
case NEEDS_REBUILDING:
nodeEntry.markRebuilding();
@@ -460,11 +421,11 @@
Collection<SkyKey> knownChildren,
NodeBatch oldChildren,
NodeEntry nodeEntry,
- int childEvaluationPriority,
boolean enqueueParentIfReady,
@Nullable SkyFunctionEnvironment environmentIfEnqueuing)
throws InterruptedException {
boolean parentIsSignalledAndReady = false;
+ int childDepth = nodeEntry.getChildDepth();
for (SkyKey directDep : knownChildren) {
NodeEntry directDepEntry =
checkNotNull(
@@ -480,7 +441,7 @@
directDep,
directDepEntry,
/* depAlreadyExists= */ true,
- childEvaluationPriority,
+ childDepth,
enqueueParentIfReady,
environmentIfEnqueuing);
}
@@ -549,6 +510,7 @@
ProfilerTask.SKYFUNCTION,
skyKey.functionName().getName());
}
+ nodeEntry.incrementEvaluationCount();
}
} catch (final SkyFunctionException builderException) {
// TODO(b/261604460): invalidating the state cache here appears to be load-bearing for
@@ -619,7 +581,7 @@
throw SchedulerException.ofError(errorInfo, skyKey, rdepsToBubbleUpTo);
}
evaluatorContext.signalParentsAndEnqueueIfReady(
- skyKey, rdepsToBubbleUpTo, nodeEntry.getVersion(), determineRestartPriority());
+ skyKey, rdepsToBubbleUpTo, nodeEntry.getVersion());
return;
}
} catch (RuntimeException re) {
@@ -642,7 +604,7 @@
dirtyRewindGraphAndResetEntry(skyKey, nodeEntry, (Restart) value);
stateCache.invalidate(skyKey);
cancelExternalDeps(env);
- evaluatorContext.getVisitor().enqueueEvaluation(skyKey, determineRestartPriority(), null);
+ evaluatorContext.getVisitor().enqueueEvaluation(skyKey, nodeEntry.getPriority(), null);
return;
}
@@ -681,7 +643,7 @@
env.setValue(value);
Set<SkyKey> reverseDeps = env.commitAndGetParents(nodeEntry);
evaluatorContext.signalParentsAndEnqueueIfReady(
- skyKey, reverseDeps, nodeEntry.getVersion(), determineRestartPriority());
+ skyKey, reverseDeps, nodeEntry.getVersion());
} finally {
evaluatorContext.getProgressReceiver().stateEnding(skyKey, NodeState.COMMIT);
}
@@ -782,7 +744,7 @@
// invariants either.
Set<SkyKey> reverseDeps = env.commitAndGetParents(nodeEntry);
evaluatorContext.signalParentsAndEnqueueIfReady(
- skyKey, reverseDeps, nodeEntry.getVersion(), determineRestartPriority());
+ skyKey, reverseDeps, nodeEntry.getVersion());
return;
}
@@ -809,7 +771,6 @@
newDepsThatWereInTheLastEvaluation = Sets.intersection(newDeps, oldDeps);
}
- int childEvaluationPriority = determineChildPriority();
InterruptibleSupplier<NodeBatch> newDepsThatWerentInTheLastEvaluationNodes =
graph.createIfAbsentBatchAsync(
skyKey, Reason.RDEP_ADDITION, newDepsThatWerentInTheLastEvaluation);
@@ -817,7 +778,6 @@
newDepsThatWereInTheLastEvaluation,
graph.getBatch(skyKey, Reason.ENQUEUING_CHILD, newDepsThatWereInTheLastEvaluation),
nodeEntry,
- childEvaluationPriority,
/* enqueueParentIfReady= */ true,
env);
@@ -825,6 +785,7 @@
// all 'new' children of this node are already done. Therefore, there should not be any code
// after this loop, as it would potentially race with the re-evaluation in another thread.
NodeBatch newNodes = newDepsThatWerentInTheLastEvaluationNodes.get();
+ int childDepth = nodeEntry.getChildDepth();
for (SkyKey newDirectDep : newDepsThatWerentInTheLastEvaluation) {
enqueueChild(
skyKey,
@@ -832,7 +793,7 @@
newDirectDep,
newNodes.get(newDirectDep),
/* depAlreadyExists= */ false,
- childEvaluationPriority,
+ childDepth,
/* enqueueParentIfReady= */ true,
env);
}
@@ -843,7 +804,7 @@
// re-enqueueing of the current node in the above loop if externalDeps != null.
evaluatorContext
.getVisitor()
- .registerExternalDeps(skyKey, nodeEntry, externalDeps, determineRestartPriority());
+ .registerExternalDeps(skyKey, nodeEntry, externalDeps, nodeEntry.getPriority());
}
// Do not put any code here! Any code here can race with a re-evaluation of this same node
// in another thread.
@@ -865,7 +826,7 @@
// If a previously requested dep is no longer done, restart this node from scratch.
stateCache.invalidate(skyKey);
resetEntry(skyKey, nodeEntry);
- evaluatorContext.getVisitor().enqueueEvaluation(skyKey, determineRestartPriority(), null);
+ evaluatorContext.getVisitor().enqueueEvaluation(skyKey, nodeEntry.getPriority(), null);
}
private void cancelExternalDeps(SkyFunctionEnvironment env) {
@@ -1198,7 +1159,8 @@
.noteInconsistencyAndMaybeThrow(
skyKey, ImmutableList.of(depKey), Inconsistency.BUILDING_PARENT_FOUND_UNDONE_CHILD);
if (triState == DependencyState.NEEDS_SCHEDULING) {
- evaluatorContext.getVisitor().enqueueEvaluation(depKey, FIRST_RESTART_PRIORITY, null);
+ depEntry.updateDepthIfGreater(entry.getChildDepth());
+ evaluatorContext.getVisitor().enqueueEvaluation(depKey, depEntry.getPriority(), null);
}
return MaybeHandleUndoneDepResult.DEP_NOT_DONE;
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index dd977a4..b2741e6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -224,4 +224,24 @@
public void addExternalDep() {
getDelegate().addExternalDep();
}
+
+ @Override
+ public int getPriority() {
+ return getDelegate().getPriority();
+ }
+
+ @Override
+ public int depth() {
+ return getDelegate().depth();
+ }
+
+ @Override
+ public void updateDepthIfGreater(int proposedDepth) {
+ getDelegate().updateDepthIfGreater(proposedDepth);
+ }
+
+ @Override
+ public void incrementEvaluationCount() {
+ getDelegate().incrementEvaluationCount();
+ }
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
index cb0ddcf..ee53e2f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -14,14 +14,18 @@
package com.google.devtools.build.skyframe;
import static com.google.common.base.Preconditions.checkState;
+import static java.lang.Math.min;
+import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.unsafe.UnsafeProvider;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
import com.google.devtools.build.skyframe.NodeEntry.DirtyType;
import javax.annotation.Nullable;
+import sun.misc.Unsafe;
/**
* State for a node that has been dirtied, and will be checked to see if it needs re-evaluation, and
@@ -30,16 +34,19 @@
* <p>This class is public only for the benefit of alternative graph implementations outside of the
* package.
*/
-public abstract class DirtyBuildingState {
+public abstract class DirtyBuildingState implements PriorityTracker {
private static final int NOT_EVALUATING_SENTINEL = -1;
static DirtyBuildingState create(
- DirtyType dirtyType, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
- return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue);
+ DirtyType dirtyType,
+ GroupedList<SkyKey> lastBuildDirectDeps,
+ SkyValue lastBuildValue,
+ boolean hasLowFanout) {
+ return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue, hasLowFanout);
}
- static DirtyBuildingState createNew() {
- return new FullDirtyBuildingState(DirtyType.CHANGE, null, null);
+ static DirtyBuildingState createNew(boolean hasLowFanout) {
+ return new FullDirtyBuildingState(DirtyType.CHANGE, null, null, hasLowFanout);
}
/**
@@ -88,6 +95,22 @@
private int externalDeps;
/**
+ * Priority information packed into 32-bits.
+ *
+ * <p>Packing is used because Java lacks support for native short operations and masking
+ * operations are needed to fit 1-bit of information about whether the {@link SkyKey} has low
+ * fanout. This field has the following layout.
+ *
+ * <ol>
+ * <li><i>Has Low Fanout</i> (1-bit) - 1 if {@link SkyKey#hasLowFanout} is true for the
+ * underlying key.
+ * <li><i>Depth</i> (15-bits) - the current estimated depth.
+ * <li><i>Restart Count</i> (16-bits, unsigned) - incremented when this node restarts.
+ * </ol>
+ */
+ private volatile int priority = HAS_LOW_FANOUT_MASK;
+
+ /**
* The dependencies requested (with group markers) last time the node was built (and below, the
* value last time the node was built). They will be compared to dependencies requested on this
* build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null,
@@ -123,11 +146,20 @@
*/
protected int dirtyDirectDepIndex;
- protected DirtyBuildingState(DirtyType dirtyType) {
+ /**
+ * Constructor.
+ *
+ * @param hasLowFanout indicates that this node is not expected to have high dependency fanout.
+ * Satisfied by by {@link SkyKey#hasLowFanout}.
+ */
+ protected DirtyBuildingState(DirtyType dirtyType, boolean hasLowFanout) {
dirtyState = dirtyType.getInitialDirtyState();
// We need to iterate through the deps to see if they have changed, or to remove them if one
// has. Initialize the iterating index.
dirtyDirectDepIndex = 0;
+ if (!hasLowFanout) {
+ this.priority = 0;
+ }
}
/** Returns true if this state does have information about a previously built version. */
@@ -296,6 +328,13 @@
signaledDeps = 0;
externalDeps = 0;
dirtyDirectDepIndex = 0;
+
+ // Resets the evaluation count.
+ int snapshot;
+ do {
+ snapshot = priority;
+ } while (!UNSAFE.compareAndSwapInt(
+ this, PRIORITY_OFFSET, snapshot, snapshot & ~EVALUATION_COUNT_MASK));
}
protected void markRebuilding() {
@@ -326,12 +365,71 @@
return signaledDeps == numDirectDeps + externalDeps;
}
+ /**
+ * A bound on depth to avoid overflow.
+ *
+ * <p>The maximum observed depth in our benchmark is ~150.
+ */
+ @VisibleForTesting static final int DEPTH_SATURATION_BOUND = 512;
+
+ /**
+ * A bound on evaluation count to avoid overflow.
+ *
+ * <p>The maximum observed evaluation count in our benchmark is 4.
+ */
+ @VisibleForTesting static final int EVALUATION_COUNT_SATURATION_BOUND = 32;
+
+ @Override
+ public int getPriority() {
+ int snapshot = priority;
+
+ // Fanout occupies the top-most bit. Shifts it over one bit so later computations don't need to
+ // consider negative priority values. Since this is the highest set bit, low-fanout nodes
+ // always have higher priority than high-fanout nodes.
+ int fanoutAdjustment = (snapshot & HAS_LOW_FANOUT_MASK) >>> 1;
+ int depth = min((snapshot & DEPTH_MASK) >> DEPTH_BIT_OFFSET, DEPTH_SATURATION_BOUND);
+ int evaluationCount = min(snapshot & EVALUATION_COUNT_MASK, EVALUATION_COUNT_SATURATION_BOUND);
+
+ // This formula was found to produce good results in our benchmark. There's no deep rationale
+ // behind it. It's likely possible to improve it, but iterating is slow.
+ return fanoutAdjustment + depth + evaluationCount * evaluationCount;
+ }
+
+ @Override
+ public int depth() {
+ return (priority & DEPTH_MASK) >> DEPTH_BIT_OFFSET;
+ }
+
+ @Override
+ public void updateDepthIfGreater(int proposedDepth) {
+ // Shifts the input for comparison instead of the snapshot, which might otherwise need to be
+ // shifted repeatedly.
+ proposedDepth = (proposedDepth << DEPTH_BIT_OFFSET) & DEPTH_MASK;
+ int snapshot;
+ do {
+ snapshot = priority;
+ if (proposedDepth <= (snapshot & DEPTH_MASK)) {
+ return;
+ }
+ } while (!UNSAFE.compareAndSwapInt(
+ this, PRIORITY_OFFSET, snapshot, (snapshot & ~DEPTH_MASK) | proposedDepth));
+ }
+
+ @Override
+ public void incrementEvaluationCount() {
+ UNSAFE.getAndAddInt(this, PRIORITY_OFFSET, ONE_EVALUATION);
+ }
+
protected MoreObjects.ToStringHelper getStringHelper() {
+ int snapshot = priority;
return MoreObjects.toStringHelper(this)
.add("dirtyState", dirtyState)
.add("signaledDeps", signaledDeps)
.add("externalDeps", externalDeps)
- .add("dirtyDirectDepIndex", dirtyDirectDepIndex);
+ .add("dirtyDirectDepIndex", dirtyDirectDepIndex)
+ .add("has low fanout", (snapshot & HAS_LOW_FANOUT_MASK) != 0)
+ .add("depth", (snapshot & DEPTH_MASK) >> DEPTH_BIT_OFFSET)
+ .add("evaluation count", (snapshot & EVALUATION_COUNT_MASK));
}
@Override
@@ -344,8 +442,11 @@
private final SkyValue lastBuildValue;
private FullDirtyBuildingState(
- DirtyType dirtyType, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
- super(dirtyType);
+ DirtyType dirtyType,
+ GroupedList<SkyKey> lastBuildDirectDeps,
+ SkyValue lastBuildValue,
+ boolean hasLowFanout) {
+ super(dirtyType, hasLowFanout);
this.lastBuildDirectDeps = lastBuildDirectDeps;
checkState(
!dirtyType.equals(DirtyType.DIRTY) || getNumOfGroupsInLastBuildDirectDeps() > 0,
@@ -386,4 +487,33 @@
.add("lastBuildValue", lastBuildValue);
}
}
+
+ // Masks for `priority`.
+ private static final int HAS_LOW_FANOUT_MASK = 0x8000_0000;
+
+ private static final int DEPTH_MASK = 0x7FFF_0000;
+ private static final int DEPTH_BIT_OFFSET = 16;
+
+ private static final int EVALUATION_COUNT_MASK = 0xFFFF;
+ private static final int ONE_EVALUATION = 1;
+
+ static {
+ checkState(Integer.numberOfTrailingZeros(DEPTH_MASK) == DEPTH_BIT_OFFSET);
+ checkState(
+ Integer.numberOfTrailingZeros(EVALUATION_COUNT_MASK)
+ == Integer.numberOfTrailingZeros(ONE_EVALUATION));
+ }
+
+ private static final Unsafe UNSAFE = UnsafeProvider.unsafe();
+
+ private static final long PRIORITY_OFFSET;
+
+ static {
+ try {
+ PRIORITY_OFFSET =
+ UNSAFE.objectFieldOffset(DirtyBuildingState.class.getDeclaredField("priority"));
+ } catch (ReflectiveOperationException e) {
+ throw new ExceptionInInitializerError(e);
+ }
+ }
}
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 22f1486..b06cb64 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -307,7 +307,7 @@
synchronized (this) {
boolean done = isDone();
if (!done && dirtyBuildingState == null) {
- dirtyBuildingState = DirtyBuildingState.createNew();
+ dirtyBuildingState = DirtyBuildingState.createNew(key.hasLowFanout());
}
if (reverseDep != null) {
if (done) {
@@ -439,7 +439,7 @@
@ForOverride
protected DirtyBuildingState createDirtyBuildingStateForDoneNode(
DirtyType dirtyType, GroupedList<SkyKey> directDeps, SkyValue value) {
- return DirtyBuildingState.create(dirtyType, directDeps, value);
+ return DirtyBuildingState.create(dirtyType, directDeps, value, key.hasLowFanout());
}
private static final GroupedList<SkyKey> EMPTY_LIST = new GroupedList<>();
@@ -659,6 +659,42 @@
checkGroupSizes(!it.hasNext(), deps, groupSizes);
}
+ @Override
+ public int getPriority() {
+ var snapshot = dirtyBuildingState;
+ if (snapshot == null) {
+ return Integer.MAX_VALUE;
+ }
+ return snapshot.getPriority();
+ }
+
+ @Override
+ public int depth() {
+ var snapshot = dirtyBuildingState;
+ if (snapshot == null) {
+ return 0;
+ }
+ return snapshot.depth();
+ }
+
+ @Override
+ public void updateDepthIfGreater(int proposedDepth) {
+ var snapshot = dirtyBuildingState;
+ if (snapshot == null) {
+ return;
+ }
+ snapshot.updateDepthIfGreater(proposedDepth);
+ }
+
+ @Override
+ public void incrementEvaluationCount() {
+ var snapshot = dirtyBuildingState;
+ if (snapshot == null) {
+ return;
+ }
+ snapshot.incrementEvaluationCount();
+ }
+
private static void checkGroupSizes(
boolean condition, Set<SkyKey> deps, List<Integer> groupSizes) {
checkArgument(
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 b785e53..b9bfd66 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -31,7 +31,7 @@
* <p>Certain graph implementations' node entries can throw {@link InterruptedException} on various
* accesses. Such exceptions should not be caught locally -- they should be allowed to propagate up.
*/
-public interface NodeEntry {
+public interface NodeEntry extends PriorityTracker {
/**
* Return code for {@link #addReverseDepAndCheckIfDone} and {@link
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 5818143..a83ccc2 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -143,9 +143,7 @@
// in order to be thread-safe.
switch (entry.addReverseDepAndCheckIfDone(null)) {
case NEEDS_SCHEDULING:
- // Low priority because this node is not needed by any other currently evaluating node.
- // So keep it at the back of the queue as long as there's other useful work to be done.
- evaluatorContext.getVisitor().enqueueEvaluation(skyKey, Integer.MIN_VALUE, null);
+ evaluatorContext.getVisitor().enqueueEvaluation(skyKey, entry.getPriority(), null);
break;
case DONE:
informProgressReceiverThatValueIsDone(skyKey, entry);
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
index 8893897..5957586 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
@@ -59,13 +59,13 @@
private final Supplier<NodeEntryVisitor> visitorSupplier;
/**
- * Returns a {@link Runnable} given a {@code key} to evaluate and an {@code evaluationPriority}
- * indicating whether it should be scheduled for evaluation soon (higher is better). The returned
- * {@link Runnable} is a {@link ComparableRunnable} so that it can be ordered by {@code
- * evaluationPriority} in a priority queue if needed.
+ * Returns a {@link Runnable} given a {@code key} to evaluate.
+ *
+ * <p>The returned {@link Runnable} is a {@link ComparableRunnable} so that it can be ordered by a
+ * priority queue.
*/
interface RunnableMaker {
- ComparableRunnable make(SkyKey key, int evaluationPriority);
+ ComparableRunnable make(SkyKey key, int priority);
}
public ParallelEvaluatorContext(
@@ -117,19 +117,15 @@
}
}
- /**
- * Signals all parents that this node is finished and enqueues any parents that are ready at the
- * given evaluation priority.
- */
- void signalParentsAndEnqueueIfReady(
- SkyKey skyKey, Set<SkyKey> parents, Version version, int evaluationPriority)
+ /** Signals all parents that this node is finished and enqueues any parents that are ready. */
+ void signalParentsAndEnqueueIfReady(SkyKey skyKey, Set<SkyKey> parents, Version version)
throws InterruptedException {
NodeBatch batch = graph.getBatch(skyKey, Reason.SIGNAL_DEP, parents);
for (SkyKey parent : parents) {
NodeEntry entry = checkNotNull(batch.get(parent), parent);
boolean evaluationRequired = entry.signalDep(version, skyKey);
if (evaluationRequired || parent.supportsPartialReevaluation()) {
- getVisitor().enqueueEvaluation(parent, evaluationPriority, skyKey);
+ getVisitor().enqueueEvaluation(parent, entry.getPriority(), skyKey);
}
}
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/PriorityTracker.java b/src/main/java/com/google/devtools/build/skyframe/PriorityTracker.java
new file mode 100644
index 0000000..1d93283
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/PriorityTracker.java
@@ -0,0 +1,73 @@
+// Copyright 2023 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.skyframe;
+
+/**
+ * Tracks the priority of node evaluations.
+ *
+ * <p>Prioritization has two goals: decrease the total walltime and minimize the number of inflight
+ * nodes. The build graph has uneven depth. When the build is less CPU-bound due to available
+ * parallelism, long sequential dependencies should be prioritized first so that they do not become
+ * long poles in walltime.
+ *
+ * <p>Minimizing inflight nodes is desirable because they contribute to memory pressure. A high
+ * inflight node count increases work done by the garbage collector and triggers cache clearing.
+ * Assigning higher priority to nodes with a higher likelihood of completing, without further
+ * fanout, helps to avoid these causes of poor performance.
+ *
+ * <p>Prioritization uses two runtime signals.
+ *
+ * <ul>
+ * <li><i>depth</i>: the deeper a node, the more likely it is to be one that could be on a long
+ * critical path of computations and the closer to leaf-level and the less likely it is to
+ * cause further fanout.
+ * <li><i>evaluationCount</i>: {@link SkyFunction}s are written to minimize restarts and they are
+ * usually bounded for any node. The higher the evaluation count, the more likely the next
+ * restart completes the node, reducing memory pressure.
+ * </ul>
+ *
+ * <p>Prioritization also uses statically determined information. Certain types of nodes have high
+ * fanout by design. These may be annotated using the {@link SkyKey#hasLowFanout} method.
+ */
+interface PriorityTracker {
+ /** The priority with higher meaning more urgent. */
+ int getPriority();
+
+ /**
+ * Current estimated depth.
+ *
+ * <p>Depth is initialized by adding one to parent depth. For heavy computations to prioritize
+ * correctly, their reverse dependencies under transitive closure (excluding the root) should also
+ * track depth.
+ *
+ * <p>8-bits is likely enough for this. It's an {@code int} because Java doesn't support
+ * arithmetic operations on narrower types.
+ */
+ int depth();
+
+ /**
+ * Attempts to update the depth.
+ *
+ * <p>During evaluation, parent nodes initialize priority as one more than their own priority.
+ * Since a node may have multiple parents, depth may increase during evaluation.
+ */
+ void updateDepthIfGreater(int proposedDepth);
+
+ /** Adds one to the evaluation count component of priority. */
+ void incrementEvaluationCount();
+
+ default int getChildDepth() {
+ return depth() + 1;
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyKey.java b/src/main/java/com/google/devtools/build/skyframe/SkyKey.java
index 6d4eaf6..f22db75 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyKey.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyKey.java
@@ -166,4 +166,13 @@
internerAsMap.remove(sample);
}
}
+
+ /**
+ * A hint to schedulers that evaluating this key shouldn't cause high fanout.
+ *
+ * <p>Keys with high fan-out create memory pressure and are assigned low priority.
+ */
+ default boolean hasLowFanout() {
+ return false;
+ }
}
diff --git a/src/test/java/com/google/devtools/build/lib/actions/util/InjectedActionLookupKey.java b/src/test/java/com/google/devtools/build/lib/actions/util/InjectedActionLookupKey.java
index c0ffa28..68b2e9f 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/util/InjectedActionLookupKey.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/util/InjectedActionLookupKey.java
@@ -24,7 +24,7 @@
* An {@link ActionLookupKey} with a non-hermetic {@link SkyFunctionName} so that its value can be
* directly injected during tests.
*/
-public final class InjectedActionLookupKey implements ActionLookupKey {
+public final class InjectedActionLookupKey extends ActionLookupKey {
public static final SkyFunctionName INJECTED_ACTION_LOOKUP =
SkyFunctionName.createNonHermetic("INJECTED_ACTION_LOOKUP");
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
index 9bbb4bf..9486060 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
@@ -155,7 +155,7 @@
assertThat(Iterables.getOnlyElement(eventCollector).getKind()).isEqualTo(EventKind.ERROR);
}
- private static final class SimpleActionLookupKey implements ActionLookupKey {
+ private static final class SimpleActionLookupKey extends ActionLookupKey {
private final String name;
SimpleActionLookupKey(String name) {
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
index 36c95ae..d31e3f8 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
@@ -80,13 +80,16 @@
@Override
public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key)
throws InterruptedException {
+ var node = delegate.get(requestor, reason, key);
// Maintains behavior for tests written when all DEP_REQUESTED calls were made as batch
// requests. Now there are optimizations in SkyFunctionEnvironment for looking up deps
// individually, but older tests may be written to listen for a GET_BATCH event.
if (reason == Reason.DEP_REQUESTED) {
notifyingHelper.graphListener.accept(key, EventType.GET_BATCH, Order.BEFORE, reason);
+ } else if (reason == Reason.EVALUATION) {
+ notifyingHelper.graphListener.accept(key, EventType.EVALUATE, Order.BEFORE, node);
}
- return notifyingHelper.wrapEntry(key, delegate.get(requestor, reason, key));
+ return notifyingHelper.wrapEntry(key, node);
}
@Override
@@ -134,6 +137,7 @@
*/
public enum EventType {
CREATE_IF_ABSENT,
+ EVALUATE,
ADD_REVERSE_DEP,
ADD_EXTERNAL_DEP,
REMOVE_REVERSE_DEP,
diff --git a/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java b/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java
new file mode 100644
index 0000000..1b5f19f
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java
@@ -0,0 +1,428 @@
+// Copyright 2023 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.skyframe;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.skyframe.DirtyBuildingState.DEPTH_SATURATION_BOUND;
+import static com.google.devtools.build.skyframe.DirtyBuildingState.EVALUATION_COUNT_SATURATION_BOUND;
+import static com.google.devtools.build.skyframe.NotifyingHelper.makeNotifyingTransformer;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.concurrent.TieredPriorityExecutor;
+import com.google.devtools.build.lib.events.StoredEventHandler;
+import com.google.devtools.build.skyframe.EvaluationContext.UnnecessaryTemporaryStateDropperReceiver;
+import com.google.devtools.build.skyframe.GraphTester.StringValue;
+import com.google.devtools.build.skyframe.NotifyingHelper.Listener;
+import com.google.testing.junit.testparameterinjector.TestParameter;
+import com.google.testing.junit.testparameterinjector.TestParameterInjector;
+import java.util.ArrayList;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.atomic.AtomicReference;
+import javax.annotation.Nullable;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+@RunWith(TestParameterInjector.class)
+public final class PriorityTest {
+ private static final long POLL_MS = 100;
+
+ /** Low fanout occupies the highest bit that can be set without creating a negative number. */
+ private static final int LOW_FANOUT_PRIORITY = 0x4000_0000;
+
+ private final ProcessableGraph graph = new InMemoryGraphImpl();
+ private final GraphTester tester = new GraphTester();
+
+ private final StoredEventHandler reportedEvents = new StoredEventHandler();
+ private final DirtyTrackingProgressReceiver revalidationReceiver =
+ new DirtyTrackingProgressReceiver(null);
+
+ private static final Version VERSION = IntVersion.of(0);
+
+ // TODO(shahan): consider factoring this boilerplate out to a common location.
+ private <T extends SkyValue> EvaluationResult<T> eval(SkyKey root, Listener listener)
+ throws InterruptedException {
+ return new ParallelEvaluator(
+ makeNotifyingTransformer(listener).transform(graph),
+ VERSION,
+ Version.minimal(),
+ tester.getSkyFunctionMap(),
+ reportedEvents,
+ new NestedSetVisitor.VisitedState(),
+ EventFilter.FULL_STORAGE,
+ ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
+ /* keepGoing= */ false,
+ revalidationReceiver,
+ GraphInconsistencyReceiver.THROWING,
+ new TieredPriorityExecutor(
+ "test-pool", 6, 3, ParallelEvaluatorErrorClassifier.instance()),
+ new SimpleCycleDetector(),
+ /* mergingSkyframeAnalysisExecutionPhases= */ false,
+ UnnecessaryTemporaryStateDropperReceiver.NULL)
+ .eval(ImmutableList.of(root));
+ }
+
+ // Some predefined values for use in the tests.
+ private static final SkyValue VALUE_A1 = new StringValue("A1");
+ private static final SkyValue VALUE_A2 = new StringValue("A2");
+ private static final SkyValue VALUE_B1 = new StringValue("B1");
+ private static final SkyValue DONE_VALUE = new StringValue("DONE");
+
+ @AutoValue
+ abstract static class PriorityInfo {
+ private static PriorityInfo fromNode(NodeEntry node) {
+ return new AutoValue_PriorityTest_PriorityInfo(node.getPriority(), node.depth());
+ }
+
+ private static PriorityInfo of(boolean hasLowFanout, int depth, int evaluationCount) {
+ int priority = depth + evaluationCount * evaluationCount;
+ if (hasLowFanout) {
+ priority += LOW_FANOUT_PRIORITY;
+ }
+ return new AutoValue_PriorityTest_PriorityInfo(priority, depth);
+ }
+
+ abstract int priority();
+
+ abstract int depth();
+ }
+
+ @Test
+ public void evaluate_incrementsChildDepthAndParentEvaluationCount() throws InterruptedException {
+ CPUHeavySkyKey rootKey = Key.create("root");
+ CPUHeavySkyKey depKey = Key.create("a");
+
+ tester.getOrCreate(depKey).setConstantValue(VALUE_A1);
+
+ tester
+ .getOrCreate(rootKey)
+ .setBuilder(
+ (unusedKey, env) -> {
+ var value = env.getValue(depKey);
+ if (value == null) {
+ return null;
+ }
+ assertThat(value).isEqualTo(VALUE_A1);
+ return DONE_VALUE;
+ });
+
+ var listener = new EvaluationPriorityListener();
+ assertThat(eval(rootKey, listener).get(rootKey)).isEqualTo(DONE_VALUE);
+
+ assertThat(listener.priorities())
+ .containsExactly(
+ rootKey,
+ ImmutableList.of(
+ PriorityInfo.of(
+ /* hasLowFanout= */ false, /* depth= */ 0, /* evaluationCount= */ 0),
+ PriorityInfo.of(
+ /* hasLowFanout= */ false, /* depth= */ 0, /* evaluationCount= */ 1)),
+ depKey,
+ ImmutableList.of(
+ PriorityInfo.of(
+ /* hasLowFanout= */ false, /* depth= */ 1, /* evaluationCount= */ 0)));
+ }
+
+ private static class EvaluationPriorityListener implements Listener {
+ private final ConcurrentHashMap<SkyKey, ArrayList<PriorityInfo>> priorities =
+ new ConcurrentHashMap<>();
+
+ @Override
+ public void accept(
+ SkyKey key,
+ NotifyingHelper.EventType type,
+ NotifyingHelper.Order order,
+ @Nullable Object context) {
+ if (type != NotifyingHelper.EventType.EVALUATE) {
+ return;
+ }
+ priorities
+ .computeIfAbsent(key, unusedKey -> new ArrayList<>())
+ .add(PriorityInfo.fromNode((NodeEntry) context));
+ }
+
+ ConcurrentHashMap<SkyKey, ArrayList<PriorityInfo>> priorities() {
+ return priorities;
+ }
+ }
+
+ @Test
+ public void enqueuingChildFromDeeperParent_incrementsDepth() throws InterruptedException {
+ CPUHeavySkyKey rootKey = Key.create("root");
+ // Both a1 and a2 are children of root. a2 requests a1 again to increase its depth.
+ CPUHeavySkyKey a1 = Key.create("a1");
+ CPUHeavySkyKey a2 = Key.create("a2");
+
+ // b1 is a child of a1 that causes a1 to restart. b1's SkyFunction holds until a2 has had a
+ // chance to re-request a1, so a1's increased depth at re-evaluation can be observed.
+ CPUHeavySkyKey b1 = Key.createWithLowFanout("b1");
+
+ var nodeA1 = new AtomicReference<NodeEntry>();
+
+ var listener =
+ new EvaluationPriorityListener() {
+ @Override
+ public void accept(
+ SkyKey key,
+ NotifyingHelper.EventType type,
+ NotifyingHelper.Order order,
+ @Nullable Object context) {
+ super.accept(key, type, order, context);
+ // Captures a1's node in addition to priority information.
+ if (key == a1 && type == NotifyingHelper.EventType.EVALUATE) {
+ nodeA1.compareAndSet(/* expectedValue= */ null, (NodeEntry) context);
+ }
+ }
+ };
+
+ tester
+ .getOrCreate(b1)
+ .setBuilder(
+ (key, env) -> {
+ // To ensure that a1 only re-enqueues after a2 has requested it, waits until a1's
+ // depth becomes 2.
+ while (nodeA1.get().depth() < 2) {
+ try {
+ Thread.sleep(POLL_MS);
+ } catch (InterruptedException e) {
+ throw new AssertionError("Unexpected interruption");
+ }
+ }
+ return VALUE_B1;
+ });
+
+ tester
+ .getOrCreate(a1)
+ .setBuilder(
+ (key, env) -> {
+ var value = env.getValue(b1);
+ if (value == null) {
+ return null;
+ }
+ assertThat(value).isEqualTo(VALUE_B1);
+ return VALUE_A1;
+ });
+
+ tester
+ .getOrCreate(a2)
+ .setBuilder(
+ (key, env) -> {
+ var value = env.getValue(a1);
+ if (value == null) {
+ return null;
+ }
+ assertThat(value).isEqualTo(VALUE_A1);
+ return VALUE_A2;
+ });
+
+ tester
+ .getOrCreate(rootKey)
+ .setBuilder(
+ (key, env) -> {
+ var value1 = env.getValue(a1);
+ var value2 = env.getValue(a2);
+ if (value1 == null || value2 == null) {
+ return null;
+ }
+ assertThat(value1).isEqualTo(VALUE_A1);
+ assertThat(value2).isEqualTo(VALUE_A2);
+ return DONE_VALUE;
+ });
+
+ assertThat(eval(rootKey, listener).get(rootKey)).isEqualTo(DONE_VALUE);
+
+ var priorities = listener.priorities();
+ assertThat(priorities.keySet()).containsExactly(rootKey, a1, a2, b1);
+
+ assertThat(priorities.get(rootKey))
+ .containsExactly(
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 0, /* evaluationCount= */ 0),
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 0, /* evaluationCount= */ 1))
+ .inOrder();
+ assertThat(priorities.get(a1)).hasSize(2);
+ assertThat(priorities.get(a1).get(0))
+ .isAnyOf(
+ // The common case where a1 starts evaluating before a2 requests it.
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 1, /* evaluationCount= */ 0),
+ // Sometimes a2 requests a1 before a1 starts evaluating.
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 2, /* evaluationCount= */ 0));
+ assertThat(priorities.get(a1).get(1))
+ .isEqualTo(
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 2, /* evaluationCount= */ 1));
+ assertThat(priorities.get(a2))
+ .containsExactly(
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 1, /* evaluationCount= */ 0),
+ PriorityInfo.of(/* hasLowFanout= */ false, /* depth= */ 1, /* evaluationCount= */ 1))
+ .inOrder();
+ assertThat(priorities.get(b1))
+ .containsAnyOf(
+ // If a1 requests b1 first.
+ PriorityInfo.of(/* hasLowFanout= */ true, /* depth= */ 2, /* evaluationCount= */ 0),
+ // If a2 requests a1 first.
+ PriorityInfo.of(/* hasLowFanout= */ true, /* depth= */ 3, /* evaluationCount= */ 0));
+ }
+
+ @Test
+ public void basicPriorityCalculation(@TestParameter boolean hasLowFanout)
+ throws InterruptedException {
+ var state = DirtyBuildingState.createNew(hasLowFanout);
+ state.updateDepthIfGreater(5);
+ state.incrementEvaluationCount();
+ state.incrementEvaluationCount();
+
+ assertThat(state.depth()).isEqualTo(5);
+ assertThat(state.getPriority())
+ .isEqualTo(
+ PriorityInfo.of(hasLowFanout, /* depth= */ 5, /* evaluationCount= */ 2).priority());
+ }
+
+ private static final int MAX_DEPTH = 0x7FFF;
+
+ private enum DepthTestCases {
+ NEGATIVE_NUMBER(-1, MAX_DEPTH, DEPTH_SATURATION_BOUND),
+ OVERFLOWING_VALUE(0xFFFF, MAX_DEPTH, DEPTH_SATURATION_BOUND),
+ NON_INTERSECTING_VALUE(0x1_0000, 0, 0);
+
+ private final int proposedDepth;
+ private final int resultingDepth;
+ private final int priority;
+
+ private DepthTestCases(int proposedDepth, int resultingDepth, int priority) {
+ this.proposedDepth = proposedDepth;
+ this.resultingDepth = resultingDepth;
+ this.priority = priority;
+ }
+
+ private int proposedDepth() {
+ return proposedDepth;
+ }
+
+ private int resultingDepth() {
+ return resultingDepth;
+ }
+
+ private int priority() {
+ return priority;
+ }
+ }
+
+ @Test
+ public void updateDepth(@TestParameter DepthTestCases testCase) {
+ var state = DirtyBuildingState.createNew(/* hasLowFanout= */ false);
+
+ state.updateDepthIfGreater(testCase.proposedDepth());
+ assertThat(state.depth()).isEqualTo(testCase.resultingDepth());
+ assertThat(state.getPriority()).isEqualTo(testCase.priority());
+ }
+
+ private static final int MAX_EVALUATION_COUNT = 0xFFFF;
+
+ private enum EvaluationCountTestCases {
+ SIMPLE(4, 16),
+ SATURATING(64, EVALUATION_COUNT_SATURATION_BOUND * EVALUATION_COUNT_SATURATION_BOUND),
+ MAXIMUM(
+ MAX_EVALUATION_COUNT,
+ EVALUATION_COUNT_SATURATION_BOUND * EVALUATION_COUNT_SATURATION_BOUND),
+ // If there are somehow over MAX_EVALUATION_COUNT evaluations, it overflows into depth. The
+ // only known scenario where this could happen is with partial re-evaluation. There it would
+ // make more sense to not mark the corresponding key CPUHeavy to avoid going through the
+ // priority queue thousands of times. In that case, its children may receive a small increase
+ // in depth per MAX_EVALUATION_COUNT iterations as an unintended side effect.
+ OVERFLOW(MAX_EVALUATION_COUNT + 1, 1);
+
+ private final int evaluationCount;
+ private final int priority;
+
+ private EvaluationCountTestCases(int evaluationCount, int priority) {
+ this.evaluationCount = evaluationCount;
+ this.priority = priority;
+ }
+
+ private int evaluationCount() {
+ return evaluationCount;
+ }
+
+ private int priority() {
+ return priority;
+ }
+ }
+
+ @Test
+ public void updateEvaluationCount(@TestParameter EvaluationCountTestCases testCase) {
+ var state = DirtyBuildingState.createNew(/* hasLowFanout= */ false);
+
+ for (int i = 0; i < testCase.evaluationCount(); ++i) {
+ state.incrementEvaluationCount();
+ }
+ assertThat(state.getPriority()).isEqualTo(testCase.priority());
+ }
+
+ private static class Key implements CPUHeavySkyKey {
+ private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+ private final String arg;
+ private final boolean hasLowFanout;
+
+ static Key create(String arg) {
+ return interner.intern(new Key(arg, /* hasLowFanout= */ false));
+ }
+
+ static Key createWithLowFanout(String arg) {
+ return interner.intern(new Key(arg, /* hasLowFanout= */ true));
+ }
+
+ private Key(String arg, boolean hasLowFanout) {
+ this.arg = arg;
+ this.hasLowFanout = hasLowFanout;
+ }
+
+ @Override
+ public SkyFunctionName functionName() {
+ return SkyFunctionName.FOR_TESTING;
+ }
+
+ @Override
+ public String argument() {
+ return arg;
+ }
+
+ @Override
+ public boolean hasLowFanout() {
+ return hasLowFanout;
+ }
+
+ @Override
+ public int hashCode() {
+ return 31 * functionName().hashCode() + arg.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof Key)) {
+ return false;
+ }
+ Key that = (Key) obj;
+ return arg.equals(that.arg) && hasLowFanout == that.hasLowFanout;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("arg", arg).add("hasLowFanout", hasLowFanout).toString();
+ }
+ }
+}
