During change pruning, when a parent node notices all its children are done, finish processing that parent node intra-thread rather than enqueue it and have it be processed in the future by a different Skyframe thread.
I discovered this room for improvement myself by running benchmarks with a Blaze binary instrumented with a ton of log statements in the Skyframe engine codebase. I was excited to go work on this commit. But when I started editing the code, I was surprised and happy to see that @ericfelly curiously had added a TODO for exactly this in passing in commit e97bba1 in 2016!
For highly parallel change pruning situations (e.g. N parent nodes each with a single common child node, such that N >> num_skyframe_threads >= num_cores), this avoids the contention of enqueueing each parent node and also is just plain faster since we process the parent node now rather than in the future. On a benchmark of a particularly extreme incremental build situation internally at Google, this increased the change pruning rate by ~175% and decreased overall wall time by ~60%.
The contention mentioned above is between busy Skyframe threads enqueueing more work units (PriorityBlockingQueue#offer) and idle Skyframe threads picking up a work unit (PriorityBlockingQueue#take). It's something that's been on my radar for ~years, and I even have a pending CL to completely remove it. I've never prioritized pushing that CL through because I've never been able to show the contention is obviously causing real problems, and my fix is to implement a low-contention priority queue data structure. Well, this CL here reduces the impact of that contention even more, so maybe I'll never get around to mailing out my new queue code ¯\_(ツ)_/¯
RELNOTES: None
PiperOrigin-RevId: 339337198
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 2ebd793..aa7a8f1 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -160,13 +160,19 @@
return Integer.compare(((Evaluate) other).evaluationPriority, this.evaluationPriority);
}
- private void enqueueChild(
+ /**
+ * 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 (but wasn't enqueued).
+ */
+ private boolean enqueueChild(
SkyKey skyKey,
NodeEntry entry,
SkyKey child,
NodeEntry childEntry,
boolean depAlreadyExists,
- int childEvaluationPriority)
+ int childEvaluationPriority,
+ EnqueueParentBehavior enqueueParent)
throws InterruptedException {
Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry);
DependencyState dependencyState;
@@ -181,11 +187,18 @@
}
switch (dependencyState) {
case DONE:
- if (entry.signalDep(childEntry.getVersion(), child)) {
- // This can only happen if there are no more children to be added.
- // Maximum priority, since this node has already started evaluation before, and we want
- // it off our plate.
- evaluatorContext.getVisitor().enqueueEvaluation(skyKey, Integer.MAX_VALUE);
+ switch (enqueueParent) {
+ case SIGNAL:
+ return entry.signalDep(childEntry.getVersion(), child);
+ case ENQUEUE:
+ if (entry.signalDep(childEntry.getVersion(), child)) {
+ // Maximum priority, since this node has already started evaluation before, and we
+ // want it off our plate.
+ evaluatorContext.getVisitor().enqueueEvaluation(skyKey, Integer.MAX_VALUE);
+ }
+ break;
+ case NO_ACTION:
+ break;
}
break;
case ALREADY_EVALUATING:
@@ -194,6 +207,7 @@
evaluatorContext.getVisitor().enqueueEvaluation(child, childEvaluationPriority);
break;
}
+ return false;
}
/**
@@ -307,9 +321,22 @@
if (entriesToCheck == null || depsReport.hasInformation()) {
entriesToCheck = graph.getBatch(skyKey, Reason.ENQUEUING_CHILD, unknownStatusDeps);
}
- handleKnownChildrenForDirtyNode(
- unknownStatusDeps, entriesToCheck, state, globalEnqueuedIndex.incrementAndGet());
- return DirtyOutcome.ALREADY_PROCESSED;
+ boolean parentIsSignalledAndReady =
+ handleKnownChildrenForDirtyNode(
+ unknownStatusDeps,
+ entriesToCheck,
+ state,
+ globalEnqueuedIndex.incrementAndGet(),
+ EnqueueParentBehavior.SIGNAL);
+ if (!parentIsSignalledAndReady
+ || evaluatorContext.getVisitor().shouldPreventNewEvaluations()) {
+ return DirtyOutcome.ALREADY_PROCESSED;
+ }
+ // If we're here, then we may proceed to the rest of the method and continue processing
+ // the node intra-thread. This is a performance optimization: By not enqueuing the node,
+ // we avoid contention on the queue data structure (between concurrent threads
+ // enqueueing and dequeueing), and we also save wall time since the node gets processed
+ // now rather than at some point in the future.
}
switch (state.getDirtyState()) {
case VERIFIED_CLEAN:
@@ -347,12 +374,18 @@
}
}
- private void handleKnownChildrenForDirtyNode(
+ /**
+ * Returns whether the parent has been both been signalled and also is ready for evaluation (but
+ * wasn't enqueued).
+ */
+ private boolean handleKnownChildrenForDirtyNode(
Collection<SkyKey> knownChildren,
Map<SkyKey, ? extends NodeEntry> oldChildren,
NodeEntry state,
- int childEvaluationPriority)
+ int childEvaluationPriority,
+ EnqueueParentBehavior enqueueParent)
throws InterruptedException {
+ boolean parentIsSignalledAndReady = false;
if (oldChildren.size() != knownChildren.size()) {
GraphInconsistencyReceiver inconsistencyReceiver =
evaluatorContext.getGraphInconsistencyReceiver();
@@ -365,28 +398,31 @@
Map<SkyKey, ? extends NodeEntry> recreatedEntries =
graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, missingChildren);
for (Map.Entry<SkyKey, ? extends NodeEntry> recreatedEntry : recreatedEntries.entrySet()) {
- enqueueChild(
- skyKey,
- state,
- recreatedEntry.getKey(),
- recreatedEntry.getValue(),
- /*depAlreadyExists=*/ false,
- childEvaluationPriority);
+ parentIsSignalledAndReady |=
+ enqueueChild(
+ skyKey,
+ state,
+ recreatedEntry.getKey(),
+ recreatedEntry.getValue(),
+ /*depAlreadyExists=*/ false,
+ childEvaluationPriority,
+ enqueueParent);
}
}
for (Map.Entry<SkyKey, ? extends NodeEntry> e : oldChildren.entrySet()) {
SkyKey directDep = e.getKey();
NodeEntry directDepEntry = e.getValue();
- // TODO(bazel-team): If this signals the current node and makes it ready, consider
- // evaluating it in this thread instead of scheduling a new evaluation.
- enqueueChild(
- skyKey,
- state,
- directDep,
- directDepEntry,
- /*depAlreadyExists=*/ true,
- childEvaluationPriority);
+ parentIsSignalledAndReady |=
+ enqueueChild(
+ skyKey,
+ state,
+ directDep,
+ directDepEntry,
+ /*depAlreadyExists=*/ true,
+ childEvaluationPriority,
+ enqueueParent);
}
+ return parentIsSignalledAndReady;
}
@Override
@@ -686,7 +722,8 @@
newDepsThatWereInTheLastEvaluation,
graph.getBatch(skyKey, Reason.ENQUEUING_CHILD, newDepsThatWereInTheLastEvaluation),
state,
- childEvaluationPriority);
+ childEvaluationPriority,
+ EnqueueParentBehavior.ENQUEUE);
// Due to multi-threading, this can potentially cause the current node to be re-enqueued if
// all 'new' children of this node are already done. Therefore, there should not be any
@@ -702,7 +739,8 @@
newDirectDep,
newDirectDepEntry,
/*depAlreadyExists=*/ false,
- childEvaluationPriority);
+ childEvaluationPriority,
+ EnqueueParentBehavior.ENQUEUE);
}
if (externalDeps != null) {
// This can cause the current node to be re-enqueued if all futures are already done.
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
index d0ecefe..109d4f1 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
@@ -90,7 +90,7 @@
* graph) also has good results experimentally, since it minimizes sprawl.
*/
void enqueueEvaluation(SkyKey key, int evaluationPriority) {
- if (preventNewEvaluations.get()) {
+ if (shouldPreventNewEvaluations()) {
// If an error happens in nokeep_going mode, we still want to mark these nodes as inflight,
// otherwise cleanup will not happen properly.
progressReceiver.enqueueAfterError(key);
@@ -126,6 +126,16 @@
}
/**
+ * Returns whether any new evaluations should be prevented.
+ *
+ * <p>If called from within node evaluation, the caller may use the return value to determine
+ * whether it is responsible for throwing an exception to halt evaluation at the executor level.
+ */
+ boolean shouldPreventNewEvaluations() {
+ return preventNewEvaluations.get();
+ }
+
+ /**
* Stop any new evaluations from being enqueued. Returns whether this was the first thread to
* request a halt.
*
