Stop storing reverse deps to signal in BuildingState. Instead, re-use the reverseDepsToConsolidate field in InMemoryNodeEntry. As part of that, revamp our logic of how we store pending operations: store adds bare on initial evaluations, and checks bare on incremental evaluations and operations on done nodes.
This should improve performance in two ways: BuildingState loses two fields, saving working memory intra-build. Storing pending reverse dep operations bare also saves memory intra-build. Note that neither of these changes helps resting memory state, only while a node is still evaluating.
Because of this, we can simplify ReverseDepsUtil a bit, making ReverseDepsUtilImpl a static class, which it always wanted to be (what it really wants to be is a superclass of InMemoryNodeEntry, but I don't want to spend the object alignment bits).
Finally, this makes it pretty tempting to get rid of BuildingState altogether on initial evaluations. We'd still keep DirtyBuildingState, but we could save another ~24 bytes by storing BuildingState's one remaining field, signaledDeps, directly inside InMemoryNodeEntry.
--
PiperOrigin-RevId: 151048879
MOS_MIGRATED_REVID=151048879
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
new file mode 100644
index 0000000..0f93fa6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.java
@@ -0,0 +1,438 @@
+// Copyright 2014 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 com.google.common.base.MoreObjects;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.collect.CompactHashSet;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
+import com.google.devtools.build.skyframe.KeyToConsolidate.OpToStoreBare;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A utility class that allows us to keep the reverse dependencies as an array list instead of a
+ * set. This is more memory-efficient. At the same time it allows us to group the removals and
+ * uniqueness checks so that it also performs well.
+ *
+ * <p>We could simply make {@link InMemoryNodeEntry} extend this class, but we would be less
+ * memory-efficient since object memory alignment does not cross classes (you would have two memory
+ * alignments, one for the base class and one for the extended one). We could also merge this
+ * functionality directly into {@link InMemoryNodeEntry} at the cost of increasing its size and
+ * complexity even more.
+ *
+ * <p>The operations {@link #addReverseDeps}, {@link #checkReverseDep}, and {@link
+ * #removeReverseDep} here are optimized for a done entry. Done entries rarely have rdeps added and
+ * removed, but do have {@link Op#CHECK} operations performed frequently. As well, done node entries
+ * may never have their data forcibly consolidated, since their reverse deps will only be retrieved
+ * as a whole if they are marked dirty. Thus, we consolidate periodically.
+ *
+ * <p>{@link InMemoryNodeEntry} manages pending reverse dep operations on a marked-dirty or initally
+ * evaluating node itself, using similar logic tuned to those cases, and calls into {@link
+ * #consolidateDataAndReturnNewElements(InMemoryNodeEntry, OpToStoreBare)} when transitioning to
+ * done.
+ */
+abstract class ReverseDepsUtility {
+ private ReverseDepsUtility() {}
+
+ static final int MAYBE_CHECK_THRESHOLD = 10;
+
+ /**
+ * We can store one type of operation bare in order to save memory. For done nodes, most
+ * operations are CHECKS.
+ */
+ private static final OpToStoreBare DEFAULT_OP_TO_STORE_BARE = OpToStoreBare.CHECK;
+
+ private static void maybeDelayReverseDepOp(
+ InMemoryNodeEntry entry, Iterable<SkyKey> reverseDeps, Op op) {
+ List<Object> consolidations = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+ int currentReverseDepSize = getCurrentReverseDepSize(entry);
+ if (consolidations == null) {
+ consolidations = new ArrayList<>(currentReverseDepSize);
+ entry.setReverseDepsDataToConsolidateForReverseDepsUtil(consolidations);
+ }
+ for (SkyKey reverseDep : reverseDeps) {
+ consolidations.add(KeyToConsolidate.create(reverseDep, op, DEFAULT_OP_TO_STORE_BARE));
+ }
+ // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized.
+ if (consolidations.size() >= currentReverseDepSize) {
+ consolidateData(entry);
+ }
+ }
+
+ private static boolean isSingleReverseDep(InMemoryNodeEntry entry) {
+ return !(entry.getReverseDepsRawForReverseDepsUtil() instanceof List);
+ }
+
+ /**
+ * We only check if reverse deps is small and there are no delayed data to consolidate, since then
+ * presence or absence would not be known.
+ */
+ static void maybeCheckReverseDepNotPresent(InMemoryNodeEntry entry, SkyKey reverseDep) {
+ if (entry.getReverseDepsDataToConsolidateForReverseDepsUtil() != null) {
+ return;
+ }
+ if (isSingleReverseDep(entry)) {
+ Preconditions.checkState(
+ !entry.getReverseDepsRawForReverseDepsUtil().equals(reverseDep),
+ "Reverse dep %s already present in %s",
+ reverseDep,
+ entry);
+ return;
+ }
+ @SuppressWarnings("unchecked")
+ List<SkyKey> asList = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
+ if (asList.size() < MAYBE_CHECK_THRESHOLD) {
+ Preconditions.checkState(
+ !asList.contains(reverseDep),
+ "Reverse dep %s already present in %s for %s",
+ reverseDep,
+ asList,
+ entry);
+ }
+ }
+
+ @SuppressWarnings("unchecked") // Cast to list.
+ private static int getCurrentReverseDepSize(InMemoryNodeEntry entry) {
+ return isSingleReverseDep(entry)
+ ? 1
+ : ((List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil()).size();
+ }
+
+ /**
+ * We use a memory-efficient trick to keep reverseDeps memory usage low. Edges in Bazel are
+ * dominant over the number of nodes.
+ *
+ * <p>Most of the nodes have zero or one reverse dep. That is why we use immutable versions of the
+ * lists for those cases. In case of the size being > 1 we switch to an ArrayList. That is because
+ * we also have a decent number of nodes for which the reverseDeps are huge (for example almost
+ * everything depends on BuildInfo node).
+ *
+ * <p>We also optimize for the case where we have only one dependency. In that case we keep the
+ * object directly instead of a wrapper list.
+ */
+ @SuppressWarnings("unchecked") // Cast to SkyKey and List.
+ static void addReverseDeps(InMemoryNodeEntry entry, Collection<SkyKey> newReverseDeps) {
+ if (newReverseDeps.isEmpty()) {
+ return;
+ }
+ List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+ if (dataToConsolidate != null) {
+ maybeDelayReverseDepOp(entry, newReverseDeps, Op.ADD);
+ return;
+ }
+ Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
+ int reverseDepsSize = isSingleReverseDep(entry) ? 1 : ((List<SkyKey>) reverseDeps).size();
+ int newSize = reverseDepsSize + newReverseDeps.size();
+ if (newSize == 1) {
+ entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(newReverseDeps));
+ } else if (reverseDepsSize == 0) {
+ entry.setReverseDepsForReverseDepsUtil(Lists.newArrayList(newReverseDeps));
+ } else if (reverseDepsSize == 1) {
+ List<SkyKey> newList = Lists.newArrayListWithExpectedSize(newSize);
+ newList.add((SkyKey) reverseDeps);
+ newList.addAll(newReverseDeps);
+ entry.setReverseDepsForReverseDepsUtil(newList);
+ } else {
+ ((List<SkyKey>) reverseDeps).addAll(newReverseDeps);
+ }
+ }
+
+ static void checkReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) {
+ maybeDelayReverseDepOp(entry, ImmutableList.of(reverseDep), Op.CHECK);
+ }
+
+ /** See {@code addReverseDeps} method. */
+ static void removeReverseDep(InMemoryNodeEntry entry, SkyKey reverseDep) {
+ maybeDelayReverseDepOp(entry, ImmutableList.of(reverseDep), Op.REMOVE);
+ }
+
+ static ImmutableSet<SkyKey> getReverseDeps(InMemoryNodeEntry entry) {
+ consolidateData(entry);
+
+ // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
+ // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted,
+ // and we can't handle that right now.
+ if (isSingleReverseDep(entry)) {
+ return ImmutableSet.of((SkyKey) entry.getReverseDepsRawForReverseDepsUtil());
+ } else {
+ @SuppressWarnings("unchecked")
+ List<SkyKey> reverseDeps = (List<SkyKey>) entry.getReverseDepsRawForReverseDepsUtil();
+ ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
+ Preconditions.checkState(
+ set.size() == reverseDeps.size(),
+ "Duplicate reverse deps present in %s: %s",
+ reverseDeps,
+ entry);
+ return set;
+ }
+ }
+
+ static Set<SkyKey> returnNewElements(InMemoryNodeEntry entry, OpToStoreBare opToStoreBare) {
+ return consolidateDataAndReturnNewElements(entry, false, opToStoreBare);
+ }
+
+ @SuppressWarnings("unchecked") // List and bare SkyKey casts.
+ private static Set<SkyKey> consolidateDataAndReturnNewElements(
+ InMemoryNodeEntry entry, boolean mutateObject, OpToStoreBare opToStoreBare) {
+ List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+ if (dataToConsolidate == null) {
+ return ImmutableSet.of();
+ }
+ Set<SkyKey> reverseDepsAsSet;
+ Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
+ if (isSingleReverseDep(entry)) {
+ reverseDepsAsSet = CompactHashSet.create((SkyKey) reverseDeps);
+ } else {
+ List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+ reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);
+ }
+ Set<SkyKey> newData = CompactHashSet.create();
+ for (Object keyToConsolidate : dataToConsolidate) {
+ SkyKey key = KeyToConsolidate.key(keyToConsolidate);
+ switch (KeyToConsolidate.op(keyToConsolidate, opToStoreBare)) {
+ case CHECK:
+ Preconditions.checkState(
+ reverseDepsAsSet.contains(key),
+ "Reverse dep not present: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ newData,
+ dataToConsolidate,
+ entry);
+ Preconditions.checkState(
+ newData.add(key),
+ "Duplicate new reverse dep: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ newData,
+ dataToConsolidate,
+ entry);
+ break;
+ case REMOVE:
+ Preconditions.checkState(
+ reverseDepsAsSet.remove(key),
+ "Reverse dep to be removed not present: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ newData,
+ dataToConsolidate,
+ entry);
+ Preconditions.checkState(
+ newData.remove(key),
+ "Reverse dep to be removed not present: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ newData,
+ dataToConsolidate,
+ entry);
+ break;
+ case REMOVE_OLD:
+ Preconditions.checkState(
+ reverseDepsAsSet.remove(key),
+ "Reverse dep to be removed not present: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ newData,
+ dataToConsolidate,
+ entry);
+ Preconditions.checkState(
+ !newData.contains(key),
+ "Reverse dep shouldn't have been added to new: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ newData,
+ dataToConsolidate,
+ entry);
+ break;
+ case ADD:
+ Preconditions.checkState(
+ reverseDepsAsSet.add(key),
+ "Duplicate reverse deps: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDeps,
+ newData,
+ dataToConsolidate,
+ entry);
+ Preconditions.checkState(
+ newData.add(key),
+ "Duplicate new reverse deps: %s %s %s %s %s",
+ keyToConsolidate,
+ reverseDeps,
+ newData,
+ dataToConsolidate,
+ entry);
+ break;
+ default:
+ throw new IllegalStateException(
+ keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry);
+ }
+ }
+ if (mutateObject) {
+ entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
+ writeReverseDepsSet(entry, reverseDepsAsSet);
+ }
+ return newData;
+ }
+
+ static Set<SkyKey> consolidateDataAndReturnNewElements(
+ InMemoryNodeEntry entry, OpToStoreBare opToStoreBare) {
+ return consolidateDataAndReturnNewElements(entry, true, opToStoreBare);
+ }
+
+ @SuppressWarnings("unchecked") // Casts to SkyKey and List.
+ private static void consolidateData(InMemoryNodeEntry entry) {
+ List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
+ if (dataToConsolidate == null) {
+ return;
+ }
+ entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
+ Object reverseDeps = entry.getReverseDepsRawForReverseDepsUtil();
+ if (isSingleReverseDep(entry)) {
+ Preconditions.checkState(
+ dataToConsolidate.size() == 1,
+ "dataToConsolidate not size 1 even though only one rdep: %s %s %s",
+ dataToConsolidate,
+ reverseDeps,
+ entry);
+ Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate);
+ SkyKey key = KeyToConsolidate.key(keyToConsolidate);
+ switch (KeyToConsolidate.op(keyToConsolidate, DEFAULT_OP_TO_STORE_BARE)) {
+ case REMOVE:
+ entry.setReverseDepsForReverseDepsUtil(ImmutableList.<SkyKey>of());
+ // Fall through to check.
+ case CHECK:
+ Preconditions.checkState(
+ key.equals(reverseDeps), "%s %s %s", keyToConsolidate, reverseDeps, entry);
+ break;
+ case ADD:
+ throw new IllegalStateException(
+ "Shouldn't delay add if only one element: "
+ + keyToConsolidate
+ + ", "
+ + reverseDeps
+ + ", "
+ + entry);
+ case REMOVE_OLD:
+ throw new IllegalStateException(
+ "Shouldn't be removing old deps if node already done: "
+ + keyToConsolidate
+ + ", "
+ + reverseDeps
+ + ", "
+ + entry);
+ default:
+ throw new IllegalStateException(keyToConsolidate + ", " + reverseDeps + ", " + entry);
+ }
+ return;
+ }
+ List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+ Set<SkyKey> reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);
+
+ for (Object keyToConsolidate : dataToConsolidate) {
+ SkyKey key = KeyToConsolidate.key(keyToConsolidate);
+ switch (KeyToConsolidate.op(keyToConsolidate, DEFAULT_OP_TO_STORE_BARE)) {
+ case CHECK:
+ Preconditions.checkState(
+ reverseDepsAsSet.contains(key),
+ "%s %s %s %s",
+ keyToConsolidate,
+ reverseDepsAsSet,
+ dataToConsolidate,
+ entry);
+ break;
+ case REMOVE:
+ Preconditions.checkState(
+ reverseDepsAsSet.remove(key),
+ "%s %s %s %s",
+ keyToConsolidate,
+ reverseDeps,
+ dataToConsolidate,
+ entry);
+ break;
+ case ADD:
+ Preconditions.checkState(
+ reverseDepsAsSet.add(key),
+ "%s %s %s %s",
+ keyToConsolidate,
+ reverseDeps,
+ dataToConsolidate,
+ entry);
+ break;
+ case REMOVE_OLD:
+ throw new IllegalStateException(
+ "Shouldn't be removing old deps if node already done: "
+ + keyToConsolidate
+ + ", "
+ + reverseDeps
+ + ", "
+ + dataToConsolidate
+ + ", "
+ + entry);
+ default:
+ throw new IllegalStateException(
+ keyToConsolidate + ", " + reverseDepsAsSet + ", " + dataToConsolidate + ", " + entry);
+ }
+ }
+ writeReverseDepsSet(entry, reverseDepsAsSet);
+ }
+
+ private static void writeReverseDepsSet(InMemoryNodeEntry entry, Set<SkyKey> reverseDepsAsSet) {
+ if (reverseDepsAsSet.isEmpty()) {
+ entry.setReverseDepsForReverseDepsUtil(ImmutableList.<SkyKey>of());
+ } else if (reverseDepsAsSet.size() == 1) {
+ entry.setSingleReverseDepForReverseDepsUtil(Iterables.getOnlyElement(reverseDepsAsSet));
+ } else {
+ entry.setReverseDepsForReverseDepsUtil(new ArrayList<>(reverseDepsAsSet));
+ }
+ }
+
+ private static Set<SkyKey> getReverseDepsSet(
+ InMemoryNodeEntry entry, List<SkyKey> reverseDepsAsList) {
+ Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList);
+
+ if (reverseDepsAsSet.size() != reverseDepsAsList.size()) {
+ // We're about to crash. Try to print an informative error message.
+ Set<SkyKey> seen = new HashSet<>();
+ List<SkyKey> duplicates = new ArrayList<>();
+ for (SkyKey key : reverseDepsAsList) {
+ if (!seen.add(key)) {
+ duplicates.add(key);
+ }
+ }
+ throw new IllegalStateException(
+ (reverseDepsAsList.size() - reverseDepsAsSet.size())
+ + " duplicates: "
+ + duplicates
+ + " for "
+ + entry);
+ }
+ return reverseDepsAsSet;
+ }
+
+ static String toString(InMemoryNodeEntry entry) {
+ return MoreObjects.toStringHelper("ReverseDeps")
+ .add("reverseDeps", entry.getReverseDepsRawForReverseDepsUtil())
+ .add("singleReverseDep", isSingleReverseDep(entry))
+ .add("dataToConsolidate", entry.getReverseDepsDataToConsolidateForReverseDepsUtil())
+ .toString();
+ }
+}
