Optimize GC usage of iterating over all elements of GroupedLists when we don't care about the group structure, and simplify the logic for prefetching old deps. PiperOrigin-RevId: 187681887
diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java index 11bef3f..3bf690a 100644 --- a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java +++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
@@ -20,6 +20,7 @@ import com.google.common.collect.Iterables; import com.google.common.collect.Lists; import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet; +import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; @@ -196,7 +197,7 @@ @SuppressWarnings("unchecked") public Set<T> toSet() { - ImmutableSet.Builder<T> builder = ImmutableSet.builder(); + ImmutableSet.Builder<T> builder = ImmutableSet.builderWithExpectedSize(numElements()); for (Object obj : elements) { if (obj instanceof List) { builder.addAll((List<T>) obj); @@ -262,6 +263,43 @@ return first.equals(second) || CompactHashSet.create(first).containsAll(second); } + /** An iterator that loops through every element in each group. */ + private class UngroupedIterator implements Iterator<T> { + private final Iterator<Object> iter = elements.iterator(); + int counter = 0; + List<T> currentGroup; + int listCounter = 0; + + @Override + public boolean hasNext() { + return counter < size; + } + + @SuppressWarnings("unchecked") // Cast of Object to List<T> or T. + @Override + public T next() { + counter++; + if (currentGroup != null && listCounter < currentGroup.size()) { + return currentGroup.get(listCounter++); + } + Object nextGroup = iter.next(); + if (nextGroup instanceof List) { + currentGroup = (List<T>) nextGroup; + listCounter = 1; + // GroupedLists shouldn't have empty lists stored. + return currentGroup.get(0); + } else { + currentGroup = null; + return (T) nextGroup; + } + } + } + + @ThreadHostile + public Iterable<T> getAllElementsAsIterable() { + return UngroupedIterator::new; + } + @Override public boolean equals(Object other) { if (other == null) { @@ -326,11 +364,6 @@ } return ImmutableList.of((T) obj); } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } } @Override
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 76e8100..24dfeab 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -18,7 +18,6 @@ import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Iterables; import com.google.devtools.build.lib.util.GroupedList; import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; import com.google.devtools.build.skyframe.KeyToConsolidate.Op; @@ -220,7 +219,7 @@ @Override public synchronized Iterable<SkyKey> getDirectDeps() { - return getGroupedDirectDeps().toSet(); + return getGroupedDirectDeps().getAllElementsAsIterable(); } /** @@ -520,7 +519,7 @@ throws InterruptedException { Preconditions.checkState(!isDone(), this); if (!isDirty()) { - return Iterables.concat(getTemporaryDirectDeps()); + return getTemporaryDirectDeps().getAllElementsAsIterable(); } else { // There may be duplicates here. Make sure everything is unique. ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
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 26422dd..8c5af09 100644 --- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -50,6 +50,15 @@ throws InterruptedException; /** + * A prefetch call may be used to hint to the graph that we may call {@link #getBatch} on the + * specified keys later. + */ + default void prefetchBatch( + @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) { + // Do nothing. + } + + /** * Examines all the given keys. Returns an iterable of keys whose corresponding nodes are * currently available to be fetched. *
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 9646b07..d8c8f7a 100644 --- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java +++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -20,8 +20,6 @@ import com.google.common.base.Preconditions; import com.google.common.base.Predicates; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableMap; -import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; import com.google.common.collect.Maps; import com.google.common.collect.Sets; @@ -151,20 +149,26 @@ boolean assertDone, SkyKey keyForDebugging) throws InterruptedException { - Iterable<SkyKey> depKeysAsIterable = Iterables.concat(depKeys); - Iterable<SkyKey> keysToPrefetch = depKeysAsIterable; + Set<SkyKey> depKeysAsSet = null; if (PREFETCH_OLD_DEPS) { - ImmutableSet.Builder<SkyKey> keysToPrefetchBuilder = ImmutableSet.builder(); - keysToPrefetchBuilder.addAll(depKeysAsIterable).addAll(oldDeps); - keysToPrefetch = keysToPrefetchBuilder.build(); + if (!oldDeps.isEmpty()) { + // Create a set here so that filtering the old deps below is fast. Once we create this set, + // we may as well use it for the call to evaluatorContext#getBatchValues since we've + // precomputed the size. + depKeysAsSet = depKeys.toSet(); + evaluatorContext + .getGraph() + .prefetchBatch( + requestor, + Reason.PREFETCH, + Iterables.filter(oldDeps, Predicates.not(Predicates.in(depKeysAsSet)))); + } } Map<SkyKey, ? extends NodeEntry> batchMap = - evaluatorContext.getBatchValues(requestor, Reason.PREFETCH, keysToPrefetch); - if (PREFETCH_OLD_DEPS) { - batchMap = - ImmutableMap.<SkyKey, NodeEntry>copyOf( - Maps.filterKeys(batchMap, Predicates.in(ImmutableSet.copyOf(depKeysAsIterable)))); - } + evaluatorContext.getBatchValues( + requestor, + Reason.PREFETCH, + depKeysAsSet == null ? depKeys.getAllElementsAsIterable() : depKeysAsSet); if (batchMap.size() != depKeys.numElements()) { throw new IllegalStateException( "Missing keys for " @@ -316,7 +320,7 @@ keySize - directDeps.size() - (bubbleErrorInfo == null ? 0 : bubbleErrorInfo.size()), 0); ArrayList<SkyKey> missingKeys = new ArrayList<>(expectedMissingKeySize); - for (SkyKey key : Iterables.concat(depKeys)) { + for (SkyKey key : depKeys.getAllElementsAsIterable()) { SkyValue value = maybeGetValueFromErrorOrDeps(key); if (value == null) { missingKeys.add(key);
diff --git a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java index 63c99cc..fd5938e 100644 --- a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java +++ b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
@@ -154,6 +154,9 @@ assertElementsEqual(compressed, allElts); assertElementsEqualInGroups(GroupedList.<String>create(compressed), elements); assertElementsEqualInGroups(groupedList, elements); + assertThat(groupedList.getAllElementsAsIterable()) + .containsExactlyElementsIn(Iterables.concat(groupedList)) + .inOrder(); } @Test @@ -186,6 +189,9 @@ elements.remove(1); assertElementsEqualInGroups(GroupedList.<String>create(compressed), elements); assertElementsEqualInGroups(groupedList, elements); + assertThat(groupedList.getAllElementsAsIterable()) + .containsExactlyElementsIn(Iterables.concat(groupedList)) + .inOrder(); } @Test