Introduce a graph `LookupHint` to determine whether it is worthwhile to construct a list of keys to make a batch request.
For graphs that store nodes in memory, it is wasteful to construct a list just to make a single call to `getBatch()` because the keys can just be looked up individually.
PiperOrigin-RevId: 478068994
Change-Id: I6f9200f63eee63e5a9d6a7ec8a22723ed39d445a
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java
index a333a2c..9546129 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorWrappingWalkableGraph.java
@@ -38,6 +38,11 @@
}
@Override
+ public LookupHint getLookupHint(SkyKey key) {
+ return LookupHint.INDIVIDUAL;
+ }
+
+ @Override
public Map<SkyKey, ? extends NodeEntry> getBatchMap(
@Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys)
throws InterruptedException {
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 f9d87a3..e698e10 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
@@ -54,6 +54,11 @@
}
@Override
+ default LookupHint getLookupHint(SkyKey key) {
+ return LookupHint.INDIVIDUAL;
+ }
+
+ @Override
Map<SkyKey, ? extends NodeEntry> getBatchMap(
@Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys);
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
index 1a2824e..a58c8a2ca 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -61,6 +61,26 @@
return getBatchMap(requestor, reason, keys)::get;
}
+ /** A hint about the most efficient way to look up a key in the graph. */
+ enum LookupHint {
+ INDIVIDUAL,
+ BATCH
+ }
+
+ /**
+ * Hints to the caller about the most efficient way to look up a key in this graph.
+ *
+ * <p>A return of {@link LookupHint#INDIVIDUAL} indicates that the given key can efficiently be
+ * looked up by calling {@link #get}. In such a case, it is not worth the effort to aggregate the
+ * key into a collection with other keys for a {@link #getBatch} call.
+ *
+ * <p>A return of {@link LookupHint#BATCH} indicates that the given key should ideally be
+ * requested with other keys as part of a call to {@link #getBatch}. This may be the case if, for
+ * example, the corresponding node is stored remotely, and requesting keys in a single batch
+ * reduces trips to remote storage.
+ */
+ LookupHint getLookupHint(SkyKey key);
+
/**
* A version of {@link #getBatch} that returns an {@link InterruptibleSupplier} to possibly
* retrieve the results later.
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
index ef306099..938ab2b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -35,6 +35,7 @@
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
+import com.google.devtools.build.skyframe.QueryableGraph.LookupHint;
import com.google.devtools.build.skyframe.QueryableGraph.Reason;
import com.google.devtools.build.skyframe.proto.GraphInconsistency.Inconsistency;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
@@ -490,16 +491,13 @@
checkActive();
int sizeBeforeRequest = newlyRequestedDepsValues.size();
SkyValue depValue = lookupRequestedDep(depKey);
- if (depValue == null) {
+ if (depValue != null) {
+ processDepValue(depKey, depValue);
+ } else {
NodeEntry depEntry = evaluatorContext.getGraph().get(skyKey, Reason.DEP_REQUESTED, depKey);
- depValue = getValueOrNullMarker(depEntry);
- newlyRequestedDepsValues.put(depKey, depValue);
- if (depValue != NULL_MARKER) {
- maybeUpdateMaxTransitiveSourceVersion(depEntry);
- }
+ depValue = processDepEntry(depKey, depEntry);
}
endDepGroup(sizeBeforeRequest);
- processDepValue(depKey, depValue);
return unwrapOrThrow(
skyKey, depValue, exceptionClass1, exceptionClass2, exceptionClass3, exceptionClass4);
@@ -510,30 +508,37 @@
public SkyframeLookupResult getValuesAndExceptions(Iterable<? extends SkyKey> depKeys)
throws InterruptedException {
checkActive();
- List<SkyKey> missingKeys = new ArrayList<>();
+
+ // Lazily initialized when we encounter a missing key and the graph's lookup hint indicates that
+ // the key should be requested in a batch. If the graph supports efficient lookups of individual
+ // keys, we avoid constructing a list.
+ List<SkyKey> missingKeys = null;
int sizeBeforeRequest = newlyRequestedDepsValues.size();
for (SkyKey key : depKeys) {
SkyValue value = lookupRequestedDep(key);
- if (value == null) {
- missingKeys.add(key);
- } else if (value != PENDING_MARKER) {
+ if (value == PENDING_MARKER) {
+ continue; // Duplicate key in this request.
+ }
+ if (value != null) {
processDepValue(key, value);
+ } else if (evaluatorContext.getGraph().getLookupHint(key) == LookupHint.BATCH) {
+ if (missingKeys == null) {
+ missingKeys = new ArrayList<>();
+ }
+ missingKeys.add(key);
+ } else {
+ NodeEntry depEntry = evaluatorContext.getGraph().get(skyKey, Reason.DEP_REQUESTED, key);
+ processDepEntry(key, depEntry);
}
}
endDepGroup(sizeBeforeRequest);
- if (!missingKeys.isEmpty()) {
+ if (missingKeys != null) {
NodeBatch missingEntries =
evaluatorContext.getGraph().getBatch(skyKey, Reason.DEP_REQUESTED, missingKeys);
for (SkyKey key : missingKeys) {
- NodeEntry depEntry = missingEntries.get(key);
- SkyValue valueOrNullMarker = getValueOrNullMarker(depEntry);
- processDepValue(key, valueOrNullMarker);
- newlyRequestedDepsValues.put(key, valueOrNullMarker);
- if (valueOrNullMarker != NULL_MARKER) {
- maybeUpdateMaxTransitiveSourceVersion(depEntry);
- }
+ processDepEntry(key, missingEntries.get(key));
}
}
@@ -577,7 +582,19 @@
};
}
- private void processDepValue(SkyKey depKey, SkyValue depValue) throws InterruptedException {
+ @CanIgnoreReturnValue
+ private SkyValue processDepEntry(SkyKey depKey, @Nullable NodeEntry depEntry)
+ throws InterruptedException {
+ SkyValue valueOrNullMarker = getValueOrNullMarker(depEntry);
+ processDepValue(depKey, valueOrNullMarker);
+ newlyRequestedDepsValues.put(depKey, valueOrNullMarker);
+ if (valueOrNullMarker != NULL_MARKER) {
+ maybeUpdateMaxTransitiveSourceVersion(depEntry);
+ }
+ return valueOrNullMarker;
+ }
+
+ private void processDepValue(SkyKey depKey, SkyValue depValue) {
if (depValue == NULL_MARKER) {
valuesMissing = true;
return;
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 e7ddc37..f25d614 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
@@ -84,6 +84,11 @@
}
@Override
+ public LookupHint getLookupHint(SkyKey key) {
+ return delegate.getLookupHint(key);
+ }
+
+ @Override
public void remove(SkyKey key) {
delegate.remove(key);
}
