Replace EvaluableGraph#createIfAbsent with the potentially more efficient EvaluableGraph#createIfAbsentBatch.
--
MOS_MIGRATED_REVID=104534858
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
index a61de6e..7527146 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
@@ -15,6 +15,8 @@
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import java.util.Map;
+
/**
* Interface between a single version of the graph and the evaluator. Supports mutation of that
* single version of the graph.
@@ -22,8 +24,8 @@
@ThreadSafe
interface EvaluableGraph extends QueryableGraph {
/**
- * Creates a new node with the specified key if it does not exist yet. Returns the node entry
- * (either the existing one or the one just created), never {@code null}.
+ * Like {@link QueryableGraph#getBatch}, except it creates a new node for each key not already
+ * present in the graph. Thus, the returned map will have an entry for each key in {@code keys}.
*/
- NodeEntry createIfAbsent(SkyKey key);
+ Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys);
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
index f2faaef..5a589ba 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
@@ -69,13 +69,21 @@
return builder.build();
}
- @Override
- public NodeEntry createIfAbsent(SkyKey key) {
+ protected NodeEntry createIfAbsent(SkyKey key) {
NodeEntry newval = keepEdges ? new InMemoryNodeEntry() : new EdgelessInMemoryNodeEntry();
NodeEntry oldval = nodeMap.putIfAbsent(key, newval);
return oldval == null ? newval : oldval;
}
+ @Override
+ public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
+ ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder();
+ for (SkyKey key : keys) {
+ builder.put(key, createIfAbsent(key));
+ }
+ return builder.build();
+ }
+
/** Only done nodes exist to the outside world. */
private static final Predicate<NodeEntry> NODE_DONE_PREDICATE =
new Predicate<NodeEntry>() {
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
index 5fa80a0..d7bfb95 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -222,10 +222,7 @@
if (valuesToInject.isEmpty()) {
return;
}
- for (Entry<SkyKey, SkyValue> entry : valuesToInject.entrySet()) {
- ParallelEvaluator.injectValue(
- entry.getKey(), entry.getValue(), version, graph, dirtyKeyTracker);
- }
+ ParallelEvaluator.injectValues(valuesToInject, version, graph, dirtyKeyTracker);
// Start with a new map to avoid bloat since clear() does not downsize the map.
valuesToInject = new HashMap<>();
}
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 7cc430b..1e555e8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -680,17 +680,16 @@
this.skyKey = skyKey;
}
- private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child, boolean dirtyParent) {
+ private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child, NodeEntry childEntry,
+ boolean dirtyParent) {
Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry);
-
- NodeEntry depEntry = graph.createIfAbsent(child);
DependencyState dependencyState =
dirtyParent
- ? depEntry.checkIfDoneForDirtyReverseDep(skyKey)
- : depEntry.addReverseDepAndCheckIfDone(skyKey);
+ ? childEntry.checkIfDoneForDirtyReverseDep(skyKey)
+ : childEntry.addReverseDepAndCheckIfDone(skyKey);
switch (dependencyState) {
case DONE:
- if (entry.signalDep(depEntry.getVersion())) {
+ if (entry.signalDep(childEntry.getVersion())) {
// This can only happen if there are no more children to be added.
visitor.enqueueEvaluation(skyKey);
}
@@ -786,8 +785,11 @@
// than this node, so we are going to mark it clean (since the error transience node is
// always the last dep).
state.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck));
- for (SkyKey directDep : directDepsToCheck) {
- enqueueChild(skyKey, state, directDep, /*dirtyParent=*/ true);
+ for (Map.Entry<SkyKey, NodeEntry> e
+ : graph.createIfAbsentBatch(directDepsToCheck).entrySet()) {
+ SkyKey directDep = e.getKey();
+ NodeEntry directDepEntry = e.getValue();
+ enqueueChild(skyKey, state, directDep, directDepEntry, /*dirtyParent=*/ true);
}
return DirtyOutcome.ALREADY_PROCESSED;
case VERIFIED_CLEAN:
@@ -958,8 +960,10 @@
return;
}
- for (SkyKey newDirectDep : newDirectDeps) {
- enqueueChild(skyKey, state, newDirectDep, /*dirtyParent=*/ false);
+ for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(newDirectDeps).entrySet()) {
+ SkyKey newDirectDep = e.getKey();
+ NodeEntry newDirectDepEntry = e.getValue();
+ enqueueChild(skyKey, state, newDirectDep, newDirectDepEntry, /*dirtyParent=*/ false);
}
// It is critical that there is no code below this point.
}
@@ -1129,17 +1133,19 @@
// We unconditionally add the ErrorTransienceValue here, to ensure that it will be created, and
// in the graph, by the time that it is needed. Creating it on demand in a parallel context sets
// up a race condition, because there is no way to atomically create a node and set its value.
- NodeEntry errorTransienceEntry = graph.createIfAbsent(ErrorTransienceValue.key());
+ SkyKey errorTransienceKey = ErrorTransienceValue.key();
+ NodeEntry errorTransienceEntry = Iterables.getOnlyElement(
+ graph.createIfAbsentBatch(ImmutableList.of(errorTransienceKey)).values());
if (!errorTransienceEntry.isDone()) {
- injectValue(
- ErrorTransienceValue.key(),
- new ErrorTransienceValue(),
+ injectValues(
+ ImmutableMap.of(errorTransienceKey, (SkyValue) new ErrorTransienceValue()),
graphVersion,
graph,
dirtyKeyTracker);
}
- for (SkyKey skyKey : skyKeys) {
- NodeEntry entry = graph.createIfAbsent(skyKey);
+ for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(skyKeys).entrySet()) {
+ SkyKey skyKey = e.getKey();
+ NodeEntry entry = e.getValue();
// This must be equivalent to the code in enqueueChild above, in order to be thread-safe.
switch (entry.addReverseDepAndCheckIfDone(null)) {
case NEEDS_SCHEDULING:
@@ -1753,38 +1759,42 @@
return entry != null && entry.isDone();
}
- static void injectValue(
- SkyKey key,
- SkyValue value,
+ static void injectValues(
+ Map<SkyKey, SkyValue> injectionMap,
Version version,
EvaluableGraph graph,
DirtyKeyTracker dirtyKeyTracker) {
- Preconditions.checkNotNull(value, key);
- NodeEntry prevEntry = graph.createIfAbsent(key);
- DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null);
- Preconditions.checkState(
- newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry);
- if (prevEntry.isDirty()) {
+ Map<SkyKey, NodeEntry> prevNodeEntries = graph.createIfAbsentBatch(injectionMap.keySet());
+ for (Map.Entry<SkyKey, SkyValue> injectionEntry : injectionMap.entrySet()) {
+ SkyKey key = injectionEntry.getKey();
+ SkyValue value = injectionEntry.getValue();
+ NodeEntry prevEntry = prevNodeEntries.get(key);
+ DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null);
Preconditions.checkState(
- newState == DependencyState.NEEDS_SCHEDULING, "%s %s", key, prevEntry);
- // There was an existing entry for this key in the graph.
- // Get the node in the state where it is able to accept a value.
+ newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry);
+ if (prevEntry.isDirty()) {
+ Preconditions.checkState(
+ newState == DependencyState.NEEDS_SCHEDULING, "%s %s", key, prevEntry);
+ // There was an existing entry for this key in the graph.
+ // Get the node in the state where it is able to accept a value.
- // Check that the previous node has no dependencies. Overwriting a value with deps with an
- // injected value (which is by definition deps-free) needs a little additional bookkeeping
- // (removing reverse deps from the dependencies), but more importantly it's something that
- // we want to avoid, because it indicates confusion of input values and derived values.
- Preconditions.checkState(
- prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry);
- // Put the node into a "rebuilding" state and verify that there were no dirty deps remaining.
- Preconditions.checkState(
- prevEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps().isEmpty(),
- "%s %s",
- key,
- prevEntry);
+ // Check that the previous node has no dependencies. Overwriting a value with deps with an
+ // injected value (which is by definition deps-free) needs a little additional bookkeeping
+ // (removing reverse deps from the dependencies), but more importantly it's something that
+ // we want to avoid, because it indicates confusion of input values and derived values.
+ Preconditions.checkState(
+ prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry);
+ // Put the node into a "rebuilding" state and verify that there were no dirty deps
+ // remaining.
+ Preconditions.checkState(
+ prevEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps().isEmpty(),
+ "%s %s",
+ key,
+ prevEntry);
+ }
+ prevEntry.setValue(value, version);
+ // Now that this key's injected value is set, it is no longer dirty.
+ dirtyKeyTracker.notDirty(key);
}
- prevEntry.setValue(value, version);
- // Now that this key's injected value is set, it is no longer dirty.
- dirtyKeyTracker.notDirty(key);
}
}
