From a39a562850bc17182d2ee0d86177457f27453bef Mon Sep 17 00:00:00 2001 From: janakr Date: Wed, 24 Jan 2018 08:43:35 -0800 Subject: Introduce a wrapper around the ImmutableSortedSet> set of Fragment classes that is part of the BuildConfigurationValue.Key. This class allows us to compute a fingerprint of the wrapped ImmutableSortedSet, making equality comparisons fast. The number of additional wrapper objects is the number of distinct sets of fragment classes, so 1. (In fact, we don't even need to compute a fingerprint, since reference equality does the job for us here, but we do it just to be conservative.) This CL has a performance benefit for Bazel currently, but has a bigger performance benefit in the following changes, where there are more BuildConfigurationValue.Key objects to compare. PiperOrigin-RevId: 183090122 --- .../devtools/build/lib/analysis/BuildView.java | 11 ++- .../build/lib/analysis/DependencyResolver.java | 5 +- .../lib/analysis/config/BuildConfiguration.java | 12 +-- .../lib/analysis/config/ConfigurationResolver.java | 15 ++-- .../lib/analysis/config/FragmentClassSet.java | 98 ++++++++++++++++++++++ .../lib/skyframe/BuildConfigurationValue.java | 28 ++++--- .../build/lib/skyframe/SkyframeBuildView.java | 9 +- .../lib/skyframe/SkyframeDependencyResolver.java | 5 +- .../build/lib/skyframe/SkyframeExecutor.java | 3 +- .../build/lib/analysis/DependencyResolverTest.java | 5 +- .../analysis/config/BuildConfigurationTest.java | 6 +- 11 files changed, 152 insertions(+), 45 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/lib/analysis/config/FragmentClassSet.java diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java index ab9981b93d..4a1bd249f7 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java @@ -26,7 +26,6 @@ import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableMultimap; import com.google.common.collect.ImmutableSet; -import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Iterables; import com.google.common.collect.Lists; import com.google.common.collect.Multimap; @@ -45,6 +44,7 @@ import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollectio import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; import com.google.devtools.build.lib.analysis.config.ConfigurationResolver; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.analysis.config.transitions.NoTransition; import com.google.devtools.build.lib.analysis.config.transitions.PatchTransition; @@ -954,9 +954,12 @@ public class BuildView { @Override protected List getConfigurations( - ImmutableSortedSet> fragments, - Iterable buildOptions) { - Preconditions.checkArgument(ct.getConfiguration().fragmentClasses().equals(fragments)); + FragmentClassSet fragments, Iterable buildOptions) { + Preconditions.checkArgument( + ct.getConfiguration().fragmentClasses().equals(fragments), + "Mismatch: %s %s", + ct, + fragments); Dependency asDep = Dependency.withTransitionAndAspects(ct.getLabel(), NoTransition.INSTANCE, AspectCollection.EMPTY); ImmutableList.Builder builder = ImmutableList.builder(); diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java index c87ca9b03a..ea542dfffa 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java @@ -18,12 +18,12 @@ import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableSet; -import com.google.common.collect.ImmutableSortedSet; import com.google.devtools.build.lib.analysis.AspectCollection.AspectCycleOnPathException; import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; import com.google.devtools.build.lib.analysis.config.DynamicTransitionMapper; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.analysis.config.HostTransition; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.analysis.config.TransitionResolver; @@ -875,8 +875,7 @@ public abstract class DependencyResolver { */ @Nullable protected abstract List getConfigurations( - ImmutableSortedSet> fragments, - Iterable buildOptions) + FragmentClassSet fragments, Iterable buildOptions) throws InvalidConfigurationException, InterruptedException; /** diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java index 10daadda48..3b54a8b17c 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java @@ -26,7 +26,6 @@ import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableSet; import com.google.common.collect.ImmutableSortedMap; -import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Interner; import com.google.common.collect.Interners; import com.google.common.collect.Iterables; @@ -1112,6 +1111,7 @@ public class BuildConfiguration implements BuildEvent { private final String checksum; private final ImmutableSortedMap, Fragment> fragments; + private final FragmentClassSet fragmentClassSet; private final ImmutableMap> skylarkVisibleFragments; private final String repositoryName; @@ -1390,6 +1390,7 @@ public class BuildConfiguration implements BuildEvent { String repositoryName) { this.directories = directories; this.fragments = makeFragmentsMap(fragmentsMap); + this.fragmentClassSet = FragmentClassSet.of(this.fragments.keySet()); this.skylarkVisibleFragments = buildIndexOfSkylarkVisibleFragments(); this.repositoryName = repositoryName; @@ -1475,12 +1476,11 @@ public class BuildConfiguration implements BuildEvent { * configuration is assumed to have). */ public BuildConfiguration clone( - Set> fragmentClasses, - RuleClassProvider ruleClassProvider) { + FragmentClassSet fragmentClasses, RuleClassProvider ruleClassProvider) { ClassToInstanceMap fragmentsMap = MutableClassToInstanceMap.create(); for (Fragment fragment : fragments.values()) { - if (fragmentClasses.contains(fragment.getClass())) { + if (fragmentClasses.fragmentClasses().contains(fragment.getClass())) { fragmentsMap.put(fragment.getClass(), fragment); } } @@ -1847,8 +1847,8 @@ public class BuildConfiguration implements BuildEvent { } /** Which fragments does this configuration contain? */ - public ImmutableSortedSet> fragmentClasses() { - return fragments.keySet(); + public FragmentClassSet fragmentClasses() { + return fragmentClassSet; } /** diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java index 249ac0c5e4..57cf02b1f1 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java @@ -19,7 +19,6 @@ import com.google.common.base.Joiner; import com.google.common.base.Verify; import com.google.common.base.VerifyException; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Iterables; import com.google.common.collect.LinkedHashMultimap; import com.google.common.collect.LinkedListMultimap; @@ -123,8 +122,7 @@ public final class ConfigurationResolver { Map> transitionsMap = new LinkedHashMap<>(); // The fragments used by the current target's configuration. - ImmutableSortedSet> ctgFragments = - ctgValue.getConfiguration().fragmentClasses(); + FragmentClassSet ctgFragments = ctgValue.getConfiguration().fragmentClasses(); BuildOptions ctgOptions = ctgValue.getConfiguration().getOptions(); // Stores the configuration-resolved versions of each dependency. This method must preserve the @@ -183,7 +181,7 @@ public final class ConfigurationResolver { depFragments); } - boolean sameFragments = depFragments.equals(ctgFragments); + boolean sameFragments = depFragments.equals(ctgFragments.fragmentClasses()); Transition transition = dep.getTransition(); if (sameFragments) { @@ -233,9 +231,12 @@ public final class ConfigurationResolver { // If we get here, we have to get the configuration from Skyframe. for (BuildOptions options : toOptions) { - keysToEntries.put( - BuildConfigurationValue.key(sameFragments ? ctgFragments : depFragments, options), - depsEntry); + if (sameFragments) { + keysToEntries.put(BuildConfigurationValue.key(ctgFragments, options), depsEntry); + + } else { + keysToEntries.put(BuildConfigurationValue.key(depFragments, options), depsEntry); + } } } diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/FragmentClassSet.java b/src/main/java/com/google/devtools/build/lib/analysis/config/FragmentClassSet.java new file mode 100644 index 0000000000..a419224b7e --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/analysis/config/FragmentClassSet.java @@ -0,0 +1,98 @@ +// Copyright 2018 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.config; + +import com.google.common.collect.ImmutableSortedSet; +import com.google.common.collect.Interner; +import com.google.devtools.build.lib.concurrent.BlazeInterners; +import com.google.devtools.build.lib.util.Fingerprint; +import java.util.Arrays; +import javax.annotation.Nullable; + +/** + * A wrapper class for an {@code ImmutableSortedSet>} + * object. Interning these objects allows us to do cheap reference equality checks when these sets + * are in frequently used keys. For good measure, we also compute a fingerprint. + */ +public class FragmentClassSet { + private final ImmutableSortedSet> fragments; + + // Lazily initialized. + @Nullable private volatile byte[] fingerprint; + private volatile int hashCode; + + private FragmentClassSet( + ImmutableSortedSet> fragments) { + this.fragments = fragments; + } + + private static final Interner interner = BlazeInterners.newWeakInterner(); + + public static FragmentClassSet of( + ImmutableSortedSet> fragments) { + return interner.intern(new FragmentClassSet(fragments)); + } + + public ImmutableSortedSet> fragmentClasses() { + return fragments; + } + + /** + * Lazily initialize {@link #fingerprint} and {@link #hashCode}. Keeps computation off critical + * path of build, while still avoiding expensive computation for equality and hash code each time. + * + *

We check for nullity of {@link #fingerprint} to see if this method has already been called. + * Using {@link #hashCode} after this method is called is safe because it is set here before + * {@link #fingerprint} is set, so if {@link #fingerprint} is non-null then {@link #hashCode} is + * definitely set. + */ + private void maybeInitializeFingerprintAndHashCode() { + if (fingerprint != null) { + return; + } + synchronized (this) { + if (fingerprint != null) { + return; + } + Fingerprint fingerprint = new Fingerprint(); + for (Class fragment : fragments) { + fingerprint.addString(fragment.getName()); + } + byte[] computedFingerprint = fingerprint.digestAndReset(); + hashCode = Arrays.hashCode(computedFingerprint); + this.fingerprint = computedFingerprint; + } + } + + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } else if (!(other instanceof FragmentClassSet)) { + return false; + } else { + maybeInitializeFingerprintAndHashCode(); + FragmentClassSet that = (FragmentClassSet) other; + that.maybeInitializeFingerprintAndHashCode(); + return Arrays.equals(this.fingerprint, that.fingerprint); + } + } + + @Override + public int hashCode() { + maybeInitializeFingerprintAndHashCode(); + return hashCode; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java index c42539aace..df86614495 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildConfigurationValue.java @@ -17,8 +17,8 @@ import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Interner; import com.google.devtools.build.lib.analysis.config.BuildConfiguration; -import com.google.devtools.build.lib.analysis.config.BuildConfiguration.Fragment; import com.google.devtools.build.lib.analysis.config.BuildOptions; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.concurrent.BlazeInterners; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import com.google.devtools.build.lib.skyframe.serialization.InjectingObjectCodec; @@ -67,28 +67,29 @@ public class BuildConfigurationValue implements SkyValue { @ThreadSafe public static Key key( Set> fragments, BuildOptions buildOptions) { - return keyInterner.intern( - new Key( - ImmutableSortedSet.copyOf(BuildConfiguration.lexicalFragmentSorter, fragments), - buildOptions)); + return key( + FragmentClassSet.of( + ImmutableSortedSet.copyOf(BuildConfiguration.lexicalFragmentSorter, fragments)), + buildOptions); } - static final class Key implements SkyKey, Serializable { - static final ObjectCodec CODEC = new Codec(); + public static Key key(FragmentClassSet fragmentClassSet, BuildOptions buildOptions) { + return keyInterner.intern(new Key(fragmentClassSet, buildOptions)); + } - private final ImmutableSortedSet> fragments; + static final class Key implements SkyKey, Serializable { + private final FragmentClassSet fragments; private final BuildOptions buildOptions; // If hashCode really is -1, we'll recompute it from scratch each time. Oh well. private volatile int hashCode = -1; - private Key( - ImmutableSortedSet> fragments, BuildOptions buildOptions) { + private Key(FragmentClassSet fragments, BuildOptions buildOptions) { this.fragments = fragments; this.buildOptions = Preconditions.checkNotNull(buildOptions); } ImmutableSortedSet> getFragments() { - return fragments; + return fragments.fragmentClasses(); } BuildOptions getBuildOptions() { @@ -131,8 +132,9 @@ public class BuildConfigurationValue implements SkyValue { public void serialize(Key obj, CodedOutputStream codedOut) throws SerializationException, IOException { BuildOptions.CODEC.serialize(obj.buildOptions, codedOut); - codedOut.writeInt32NoTag(obj.fragments.size()); - for (Class fragment : obj.fragments) { + codedOut.writeInt32NoTag(obj.fragments.fragmentClasses().size()); + for (Class fragment : + obj.fragments.fragmentClasses()) { StringCodecs.asciiOptimized().serialize(fragment.getName(), codedOut); } } diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java index 5d4e24aad7..118a636294 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java @@ -47,6 +47,7 @@ import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory.BuildIn import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; import com.google.devtools.build.lib.events.Event; @@ -112,8 +113,8 @@ public final class SkyframeBuildView { private BuildConfiguration topLevelHostConfiguration; // Fragment-limited versions of the host configuration. It's faster to create/cache these here // than to store them in Skyframe. - private Map>, BuildConfiguration> - hostConfigurationCache = Maps.newConcurrentMap(); + private Map hostConfigurationCache = + Maps.newConcurrentMap(); private BuildConfigurationCollection configurations; @@ -545,10 +546,10 @@ public final class SkyframeBuildView { // trims a host configuration to the same scope as a target configuration. Since their options // are different, the host instance may actually be able to produce the fragment. So it's // wrong and potentially dangerous to unilaterally exclude it. - Set> fragmentClasses = + FragmentClassSet fragmentClasses = config.trimConfigurations() ? config.fragmentClasses() - : ruleClassProvider.getAllFragments(); + : FragmentClassSet.of(ruleClassProvider.getAllFragments()); BuildConfiguration hostConfig = hostConfigurationCache.get(fragmentClasses); if (hostConfig != null) { return hostConfig; diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java index 4c5a674f33..e627332dab 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java @@ -14,12 +14,12 @@ package com.google.devtools.build.lib.skyframe; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSortedSet; import com.google.devtools.build.lib.analysis.DependencyResolver; import com.google.devtools.build.lib.analysis.TargetAndConfiguration; import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.DynamicTransitionMapper; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; @@ -126,8 +126,7 @@ public final class SkyframeDependencyResolver extends DependencyResolver { @Nullable @Override protected List getConfigurations( - ImmutableSortedSet> fragments, - Iterable buildOptions) + FragmentClassSet fragments, Iterable buildOptions) throws InvalidConfigurationException, InterruptedException { List keys = new ArrayList<>(); for (BuildOptions options : buildOptions) { diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java index cca618a403..d7da8c0778 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java @@ -71,6 +71,7 @@ import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollectio import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigurationFragmentFactory; import com.google.devtools.build.lib.analysis.config.ConfigurationResolver; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.analysis.config.HostTransition; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.analysis.config.transitions.ConfigurationTransitionProxy; @@ -1623,7 +1624,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory { @VisibleForTesting public BuildConfiguration getConfigurationForTesting( ExtendedEventHandler eventHandler, - ImmutableSortedSet> fragments, + FragmentClassSet fragments, BuildOptions options) throws InterruptedException { SkyKey key = BuildConfigurationValue.key(fragments, options); diff --git a/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java b/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java index 4251210d95..fc44c70cbd 100644 --- a/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java +++ b/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java @@ -17,10 +17,10 @@ import static com.google.common.truth.Truth.assertThat; import static com.google.common.truth.Truth.assertWithMessage; import com.google.common.collect.ImmutableMap; -import com.google.common.collect.ImmutableSortedSet; import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; +import com.google.devtools.build.lib.analysis.config.FragmentClassSet; import com.google.devtools.build.lib.analysis.util.AnalysisTestCase; import com.google.devtools.build.lib.analysis.util.TestAspects; import com.google.devtools.build.lib.cmdline.Label; @@ -91,8 +91,7 @@ public class DependencyResolverTest extends AnalysisTestCase { @Nullable @Override protected List getConfigurations( - ImmutableSortedSet> fragments, - Iterable buildOptions) { + FragmentClassSet fragments, Iterable buildOptions) { throw new UnsupportedOperationException( "this functionality is covered by analysis-phase integration tests"); } diff --git a/src/test/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationTest.java b/src/test/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationTest.java index 8501af640c..2bc20c343a 100644 --- a/src/test/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationTest.java +++ b/src/test/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationTest.java @@ -18,6 +18,7 @@ import static org.junit.Assert.fail; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; +import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Iterables; import com.google.devtools.build.lib.analysis.config.BuildConfiguration.Fragment; import com.google.devtools.build.lib.analysis.util.ConfigurationTestCase; @@ -283,7 +284,10 @@ public class BuildConfigurationTest extends ConfigurationTestCase { BuildConfiguration config = create(); BuildConfiguration trimmedConfig = config.clone( - ImmutableSet.>of(CppConfiguration.class), + FragmentClassSet.of( + ImmutableSortedSet.orderedBy(BuildConfiguration.lexicalFragmentSorter) + .add(CppConfiguration.class) + .build()), analysisMock.createRuleClassProvider()); BuildConfiguration hostConfig = createHost(); -- cgit v1.2.3