Optimize TransitiveInfoMap memory consumption.
Instead of using ImmutableMap, we share the keys between all provider maps with an identical key set.
PiperOrigin-RevId: 155432135
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
index dc74887..be92473 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
@@ -36,7 +36,6 @@
import com.google.devtools.build.lib.syntax.EvalException;
import com.google.devtools.build.lib.util.Preconditions;
import java.util.Arrays;
-import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
@@ -46,20 +45,19 @@
* Extra information about a configured target computed on request of a dependent.
*
* <p>Analogous to {@link ConfiguredTarget}: contains a bunch of transitive info providers, which
- * are merged with the providers of the associated configured target before they are passed to
- * the configured target factories that depend on the configured target to which this aspect is
- * added.
+ * are merged with the providers of the associated configured target before they are passed to the
+ * configured target factories that depend on the configured target to which this aspect is added.
*
* <p>Aspects are created alongside configured targets on request from dependents.
*
- * <p>For more information about aspects, see
- * {@link com.google.devtools.build.lib.packages.AspectClass}.
+ * <p>For more information about aspects, see {@link
+ * com.google.devtools.build.lib.packages.AspectClass}.
*
* @see com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory
* @see com.google.devtools.build.lib.packages.AspectClass
*/
@Immutable
-public final class ConfiguredAspect implements Iterable<TransitiveInfoProvider> {
+public final class ConfiguredAspect {
private final TransitiveInfoProviderMap providers;
private final AspectDescriptor descriptor;
@@ -119,12 +117,6 @@
: null;
}
-
- @Override
- public Iterator<TransitiveInfoProvider> iterator() {
- return providers.values().iterator();
- }
-
public static ConfiguredAspect forAlias(ConfiguredAspect real) {
return new ConfiguredAspect(real.descriptor, real.getProviders());
}
@@ -188,9 +180,10 @@
/** Adds providers to the aspect. */
public Builder addProviders(TransitiveInfoProviderMap providers) {
- for (Map.Entry<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> entry :
- providers.entries()) {
- addProvider(entry.getKey(), entry.getKey().cast(entry.getValue()));
+ for (int i = 0; i < providers.getProviderCount(); ++i) {
+ Class<? extends TransitiveInfoProvider> providerClass = providers.getProviderClassAt(i);
+ TransitiveInfoProvider provider = providers.getProviderAt(i);
+ addProvider(providerClass, providerClass.cast(provider));
}
return this;
}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java
index 10f5cae..a9079ad 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java
@@ -17,7 +17,6 @@
import com.google.common.collect.Iterables;
import java.util.ArrayList;
import java.util.List;
-import java.util.Map;
/**
* A single dependency with its configured target and aspects merged together.
@@ -90,9 +89,9 @@
}
for (ConfiguredAspect aspect : aspects) {
- for (Map.Entry<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> entry :
- aspect.getProviders().entries()) {
- Class<? extends TransitiveInfoProvider> providerClass = entry.getKey();
+ TransitiveInfoProviderMap providers = aspect.getProviders();
+ for (int i = 0; i < providers.getProviderCount(); ++i) {
+ Class<? extends TransitiveInfoProvider> providerClass = providers.getProviderClassAt(i);
if (OutputGroupProvider.class.equals(providerClass)
|| SkylarkProviders.class.equals(providerClass)
|| ExtraActionArtifactsProvider.class.equals(providerClass)) {
@@ -103,7 +102,7 @@
throw new IllegalStateException("Provider " + providerClass + " provided twice");
}
- aspectProviders.add(entry.getValue());
+ aspectProviders.add(providers.getProviderAt(i));
}
}
return new MergedConfiguredTarget(base, aspectProviders.build());
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
index 8fa2c4e..84fa027 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
@@ -146,11 +146,11 @@
/** Adds skylark providers from a skylark provider registry, and checks for collisions. */
private void addRegisteredProvidersToSkylarkProviders(TransitiveInfoProviderMap providers) {
Map<String, Object> nativeSkylarkProviders = new HashMap<>();
- for (Map.Entry<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> entry :
- providers.entries()) {
- if (ruleContext.getSkylarkProviderRegistry().containsValue(entry.getKey())) {
- String skylarkName = ruleContext.getSkylarkProviderRegistry().inverse().get(entry.getKey());
- nativeSkylarkProviders.put(skylarkName, entry.getValue());
+ for (int i = 0; i < providers.getProviderCount(); ++i) {
+ Class<? extends TransitiveInfoProvider> providerClass = providers.getProviderClassAt(i);
+ if (ruleContext.getSkylarkProviderRegistry().containsValue(providerClass)) {
+ String skylarkName = ruleContext.getSkylarkProviderRegistry().inverse().get(providerClass);
+ nativeSkylarkProviders.put(skylarkName, providers.getProviderAt(i));
}
}
try {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java
index b824bb2..96f9cb7 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java
@@ -14,7 +14,6 @@
package com.google.devtools.build.lib.analysis;
-import java.util.Map;
import javax.annotation.Nullable;
import javax.annotation.concurrent.Immutable;
@@ -25,7 +24,9 @@
@Nullable
<P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass);
- Iterable<Map.Entry<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>> entries();
+ int getProviderCount();
- Iterable<TransitiveInfoProvider> values();
+ Class<? extends TransitiveInfoProvider> getProviderClassAt(int i);
+
+ TransitiveInfoProvider getProviderAt(int i);
}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java
index ac68e3b..06a7726 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java
@@ -55,7 +55,10 @@
}
public TransitiveInfoProviderMapBuilder addAll(TransitiveInfoProviderMap providers) {
- return addAll(providers.values());
+ for (int i = 0; i < providers.getProviderCount(); ++i) {
+ add(providers.getProviderAt(i));
+ }
+ return this;
}
public TransitiveInfoProviderMapBuilder addAll(Iterable<TransitiveInfoProvider> providers) {
@@ -71,6 +74,6 @@
}
public TransitiveInfoProviderMap build() {
- return new TransitiveInfoProviderMapImmutableMapBased(ImmutableMap.copyOf(providers));
+ return new TransitiveInfoProviderMapOffsetBased(ImmutableMap.copyOf(providers));
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImmutableMapBased.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImmutableMapBased.java
deleted file mode 100644
index f87ca57..0000000
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImmutableMapBased.java
+++ /dev/null
@@ -1,50 +0,0 @@
-// 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.lib.analysis;
-
-import com.google.common.collect.ImmutableMap;
-import java.util.Map;
-import javax.annotation.Nullable;
-import javax.annotation.concurrent.Immutable;
-
-/** Provides a mapping between a TransitiveInfoProvider class and an instance. */
-@Immutable
-final class TransitiveInfoProviderMapImmutableMapBased implements TransitiveInfoProviderMap {
-
- private final ImmutableMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> map;
-
- TransitiveInfoProviderMapImmutableMapBased(
- ImmutableMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> map) {
- this.map = map;
- }
-
- /** Returns the instance for the provided providerClass, or <tt>null</tt> if not present. */
- @Override
- @Nullable
- public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
- return (P) map.get(TransitiveInfoProviderEffectiveClassHelper.get(providerClass));
- }
-
- @Override
- public Iterable<Map.Entry<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>>
- entries() {
- return map.entrySet();
- }
-
- @Override
- public Iterable<TransitiveInfoProvider> values() {
- return map.values();
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapOffsetBased.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapOffsetBased.java
new file mode 100644
index 0000000..a36a3e1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapOffsetBased.java
@@ -0,0 +1,127 @@
+// Copyright 2017 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.lib.analysis;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import java.util.Arrays;
+import java.util.Map.Entry;
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.Immutable;
+
+/**
+ * Provides a mapping between a TransitiveInfoProvider class and an instance.
+ *
+ * <p>This class implements a map where it is expected that a lot of the key sets will be the same.
+ * These key sets are shared and an offset table of indices is computed. Each provider map instance
+ * thus contains only a reference to the shared offset table, and a plain array of providers.
+ */
+@Immutable
+final class TransitiveInfoProviderMapOffsetBased implements TransitiveInfoProviderMap {
+ private static final Interner<OffsetTable> offsetTables = BlazeInterners.newWeakInterner();
+
+ private final OffsetTable offsetTable;
+ private final TransitiveInfoProvider[] providers;
+
+ private static final class OffsetTable {
+ private final Class<? extends TransitiveInfoProvider>[] providerClasses;
+ // Keep a map around to speed up get lookups for larger maps.
+ // We make this value lazy to avoid computing for values that end up being thrown away
+ // during interning anyway (the majority).
+ private volatile ImmutableMap<Class<? extends TransitiveInfoProvider>, Integer> indexMap;
+
+ OffsetTable(Class<? extends TransitiveInfoProvider>[] providerClasses) {
+ this.providerClasses = providerClasses;
+ }
+
+ private ImmutableMap<Class<? extends TransitiveInfoProvider>, Integer> getIndexMap() {
+ if (indexMap == null) {
+ synchronized (this) {
+ if (indexMap == null) {
+ ImmutableMap.Builder<Class<? extends TransitiveInfoProvider>, Integer> builder =
+ ImmutableMap.builder();
+ for (int i = 0; i < providerClasses.length; ++i) {
+ builder.put(providerClasses[i], i);
+ }
+ this.indexMap = builder.build();
+ }
+ }
+ }
+ return indexMap;
+ }
+
+ int getOffsetForClass(Class effectiveClass) {
+ return getIndexMap().getOrDefault(effectiveClass, -1);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (!(o instanceof OffsetTable)) {
+ return false;
+ }
+ OffsetTable that = (OffsetTable) o;
+ return Arrays.equals(this.providerClasses, that.providerClasses);
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(providerClasses);
+ }
+ }
+
+ TransitiveInfoProviderMapOffsetBased(
+ ImmutableMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> map) {
+ int count = map.size();
+ Class<? extends TransitiveInfoProvider>[] providerClasses = new Class[count];
+ this.providers = new TransitiveInfoProvider[count];
+ int i = 0;
+ for (Entry<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> entry :
+ map.entrySet()) {
+ providerClasses[i] = entry.getKey();
+ providers[i] = entry.getValue();
+ ++i;
+ }
+ OffsetTable offsetTable = new OffsetTable(providerClasses);
+ this.offsetTable = offsetTables.intern(offsetTable);
+ }
+
+ /** Returns the instance for the provided providerClass, or <tt>null</tt> if not present. */
+ @Override
+ @Nullable
+ public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
+ Class effectiveClass = TransitiveInfoProviderEffectiveClassHelper.get(providerClass);
+ int offset = offsetTable.getOffsetForClass(effectiveClass);
+ return offset >= 0 ? (P) providers[offset] : null;
+ }
+
+ @Override
+ public int getProviderCount() {
+ return providers.length;
+ }
+
+ @Override
+ public Class<? extends TransitiveInfoProvider> getProviderClassAt(int i) {
+ return offsetTable.providerClasses[i];
+ }
+
+ @Override
+ public TransitiveInfoProvider getProviderAt(int i) {
+ return providers[i];
+ }
+}
