From 7ba939dfd5df48903929e9c14ebd0449656403e4 Mon Sep 17 00:00:00 2001 From: shreyax Date: Mon, 5 Mar 2018 16:19:35 -0800 Subject: Cache SkylarkLookupImportValues in memory so that we don't recompute them multiple times. PiperOrigin-RevId: 187941859 --- .../CachedSkylarkImportLookupValueAndDeps.java | 121 +++++++++++ .../lib/skyframe/SkylarkImportLookupFunction.java | 159 +++++++++++---- .../skyframe/RecordingSkyFunctionEnvironment.java | 223 +++++++++++++++++++++ 3 files changed, 460 insertions(+), 43 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java create mode 100644 src/main/java/com/google/devtools/build/skyframe/RecordingSkyFunctionEnvironment.java (limited to 'src/main/java') diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java b/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java new file mode 100644 index 0000000000..4cee4ba3df --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/skyframe/CachedSkylarkImportLookupValueAndDeps.java @@ -0,0 +1,121 @@ +// 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.skyframe; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.devtools.build.skyframe.SkyKey; +import com.google.errorprone.annotations.CanIgnoreReturnValue; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +class CachedSkylarkImportLookupValueAndDeps { + private final SkylarkImportLookupValue value; + // We store the deps separately so that we can let go of the value when the cache drops it. + final CachedSkylarkImportLookupFunctionDeps deps; + + private CachedSkylarkImportLookupValueAndDeps( + SkylarkImportLookupValue value, CachedSkylarkImportLookupFunctionDeps deps) { + this.value = value; + this.deps = deps; + } + + SkylarkImportLookupValue getValue() { + return value; + } + + static CachedSkylarkImportLookupValueAndDeps.Builder newBuilder() { + return new CachedSkylarkImportLookupValueAndDeps.Builder(); + } + + static class Builder { + private final CachedSkylarkImportLookupFunctionDeps.Builder depsBuilder = + CachedSkylarkImportLookupFunctionDeps.newBuilder(); + private SkylarkImportLookupValue value; + + @CanIgnoreReturnValue + Builder addDep(SkyKey key) { + depsBuilder.addDep(key); + return this; + } + + @CanIgnoreReturnValue + Builder addDeps(Iterable keys) { + depsBuilder.addDeps(keys); + return this; + } + + @CanIgnoreReturnValue + Builder addTransitiveDeps(CachedSkylarkImportLookupValueAndDeps transitiveDeps) { + depsBuilder.addTransitiveDeps(transitiveDeps.deps); + return this; + } + + @CanIgnoreReturnValue + Builder setValue(SkylarkImportLookupValue value) { + this.value = value; + return this; + } + + CachedSkylarkImportLookupValueAndDeps build() { + return new CachedSkylarkImportLookupValueAndDeps(value, depsBuilder.build()); + } + } + + static class CachedSkylarkImportLookupFunctionDeps implements Iterable> { + private final ImmutableList> deps; + + private CachedSkylarkImportLookupFunctionDeps(ImmutableList> deps) { + this.deps = deps; + } + + static CachedSkylarkImportLookupFunctionDeps.Builder newBuilder() { + return new CachedSkylarkImportLookupFunctionDeps.Builder(); + } + + @Override + public Iterator> iterator() { + return deps.iterator(); + } + + static class Builder { + private final List> deps = new ArrayList<>(); + + // We only add the ASTFileLookupFunction through this so we don't need to worry about memory + // optimizations by adding it raw. + @CanIgnoreReturnValue + Builder addDep(SkyKey key) { + deps.add(ImmutableList.of(key)); + return this; + } + + @CanIgnoreReturnValue + Builder addDeps(Iterable keys) { + deps.add(keys); + return this; + } + + @CanIgnoreReturnValue + Builder addTransitiveDeps(CachedSkylarkImportLookupFunctionDeps transitiveDeps) { + Iterables.addAll(deps, transitiveDeps); + return this; + } + + CachedSkylarkImportLookupFunctionDeps build() { + return new CachedSkylarkImportLookupFunctionDeps(ImmutableList.copyOf(deps)); + } + } + } +} diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java index ad4c5a9d74..cddbf485bf 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java @@ -15,6 +15,8 @@ package com.google.devtools.build.lib.skyframe; import com.google.common.base.Preconditions; import com.google.common.base.Predicates; +import com.google.common.cache.Cache; +import com.google.common.cache.CacheBuilder; import com.google.common.collect.ImmutableCollection; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; @@ -27,6 +29,7 @@ import com.google.common.collect.Multimap; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.cmdline.LabelSyntaxException; import com.google.devtools.build.lib.cmdline.PackageIdentifier; +import com.google.devtools.build.lib.concurrent.BlazeInterners; import com.google.devtools.build.lib.events.Event; import com.google.devtools.build.lib.events.EventHandler; import com.google.devtools.build.lib.events.ExtendedEventHandler.Postable; @@ -47,6 +50,7 @@ import com.google.devtools.build.lib.syntax.SkylarkImport; import com.google.devtools.build.lib.syntax.SkylarkSemantics; import com.google.devtools.build.lib.syntax.Statement; import com.google.devtools.build.lib.vfs.PathFragment; +import com.google.devtools.build.skyframe.RecordingSkyFunctionEnvironment; import com.google.devtools.build.skyframe.SkyFunction; import com.google.devtools.build.skyframe.SkyFunctionException; import com.google.devtools.build.skyframe.SkyFunctionException.Transience; @@ -57,22 +61,26 @@ import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; +import java.util.logging.Logger; import javax.annotation.Nullable; /** * A Skyframe function to look up and import a single Skylark extension. * - *

Given a {@link Label} referencing a Skylark file, attempts to locate the file and load it. - * The Label must be absolute, and must not reference the special {@code external} package. If - * loading is successful, returns a {@link SkylarkImportLookupValue} that encapsulates - * the loaded {@link Extension} and {@link SkylarkFileDependency} information. If loading is - * unsuccessful, throws a {@link SkylarkImportLookupFunctionException} that encapsulates the - * cause of the failure. + *

Given a {@link Label} referencing a Skylark file, attempts to locate the file and load it. The + * Label must be absolute, and must not reference the special {@code external} package. If loading + * is successful, returns a {@link SkylarkImportLookupValue} that encapsulates the loaded {@link + * Extension} and {@link SkylarkFileDependency} information. If loading is unsuccessful, throws a + * {@link SkylarkImportLookupFunctionException} that encapsulates the cause of the failure. */ public class SkylarkImportLookupFunction implements SkyFunction { private final RuleClassProvider ruleClassProvider; private final PackageFactory packageFactory; + private Cache skylarkImportLookupValueCache; + + private static final Logger logger = + Logger.getLogger(SkylarkImportLookupFunction.class.getName()); public SkylarkImportLookupFunction( RuleClassProvider ruleClassProvider, PackageFactory packageFactory) { @@ -81,11 +89,17 @@ public class SkylarkImportLookupFunction implements SkyFunction { } @Override - public SkyValue compute(SkyKey skyKey, Environment env) throws SkyFunctionException, - InterruptedException { + @Nullable + public SkyValue compute(SkyKey skyKey, Environment env) + throws SkyFunctionException, InterruptedException { SkylarkImportLookupKey key = (SkylarkImportLookupKey) skyKey.argument(); try { - return computeInternal(key.importLabel, key.inWorkspace, env, null); + return computeInternal( + key.importLabel, + key.inWorkspace, + env, + /*alreadyVisited=*/ null, + /*inlineCachedValueBuilder=*/ null); } catch (InconsistentFilesystemException e) { throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT); } catch (SkylarkImportFailedException e) { @@ -93,32 +107,88 @@ public class SkylarkImportLookupFunction implements SkyFunction { } } - SkyValue computeWithInlineCalls( + @Nullable + SkylarkImportLookupValue computeWithInlineCalls( SkyKey skyKey, Environment env, LinkedHashMap visited) throws InconsistentFilesystemException, SkylarkImportFailedException, InterruptedException { - return computeWithInlineCallsInternal(skyKey, env, visited); + CachedSkylarkImportLookupValueAndDeps cachedSkylarkImportLookupValueAndDeps = + computeWithInlineCallsInternal(skyKey, env, visited); + if (cachedSkylarkImportLookupValueAndDeps == null) { + return null; + } + for (Iterable depGroup : cachedSkylarkImportLookupValueAndDeps.deps) { + env.getValues(depGroup); + } + return cachedSkylarkImportLookupValueAndDeps.getValue(); } - private SkyValue computeWithInlineCallsInternal( + @Nullable + private CachedSkylarkImportLookupValueAndDeps computeWithInlineCallsInternal( SkyKey skyKey, Environment env, LinkedHashMap visited) throws InconsistentFilesystemException, SkylarkImportFailedException, InterruptedException { SkylarkImportLookupKey key = (SkylarkImportLookupKey) skyKey.argument(); SkylarkImportLookupValue precomputedResult = visited.get(key.importLabel); if (precomputedResult != null) { - return precomputedResult; - } - return computeInternal( - key.importLabel, - key.inWorkspace, - env, - Preconditions.checkNotNull(visited, key.importLabel)); + // We have already registered all the deps for this value. + return CachedSkylarkImportLookupValueAndDeps.newBuilder().setValue(precomputedResult).build(); + } + // Note that we can't block other threads on the computation of this value due to a potential + // deadlock on a cycle. Although we are repeating some work, it is possible we have an import + // cycle where one thread starts at one side of the cycle and the other thread starts at the + // other side, and they then wait forever on the results of each others computations. + CachedSkylarkImportLookupValueAndDeps cachedSkylarkImportLookupValueAndDeps = + skylarkImportLookupValueCache.getIfPresent(skyKey); + if (cachedSkylarkImportLookupValueAndDeps != null) { + return cachedSkylarkImportLookupValueAndDeps; + } + + CachedSkylarkImportLookupValueAndDeps.Builder inlineCachedValueBuilder = + CachedSkylarkImportLookupValueAndDeps.newBuilder(); + Preconditions.checkState( + !(env instanceof RecordingSkyFunctionEnvironment), + "Found nested RecordingSkyFunctionEnvironment but it should have been stripped: %s", + env); + RecordingSkyFunctionEnvironment recordingEnv = + new RecordingSkyFunctionEnvironment( + env, + addedKey -> inlineCachedValueBuilder.addDep(addedKey), + addedSkyKeys -> inlineCachedValueBuilder.addDeps(addedSkyKeys)); + SkylarkImportLookupValue value = + computeInternal( + key.importLabel, + key.inWorkspace, + recordingEnv, + Preconditions.checkNotNull(visited, key.importLabel), + inlineCachedValueBuilder); + if (value != null) { + inlineCachedValueBuilder.setValue(value); + cachedSkylarkImportLookupValueAndDeps = inlineCachedValueBuilder.build(); + skylarkImportLookupValueCache.put(skyKey, cachedSkylarkImportLookupValueAndDeps); + } + return cachedSkylarkImportLookupValueAndDeps; + } + + public void resetCache() { + if (skylarkImportLookupValueCache != null) { + logger.info( + "Skylark inlining cache stats from earlier build: " + + skylarkImportLookupValueCache.stats()); + } + skylarkImportLookupValueCache = + CacheBuilder.newBuilder() + .concurrencyLevel(BlazeInterners.concurrencyLevel()) + .maximumSize(10000) + .recordStats() + .build(); } - private SkyValue computeInternal( + @Nullable + private SkylarkImportLookupValue computeInternal( Label fileLabel, boolean inWorkspace, Environment env, - @Nullable LinkedHashMap alreadyVisited) + @Nullable LinkedHashMap alreadyVisited, + @Nullable CachedSkylarkImportLookupValueAndDeps.Builder inlineCachedValueBuilder) throws InconsistentFilesystemException, SkylarkImportFailedException, InterruptedException { PathFragment filePath = fileLabel.toPathFragment(); @@ -150,8 +220,6 @@ public class SkylarkImportLookupFunction implements SkyFunction { // Process the load statements in the file. ImmutableList imports = ast.getImports(); - Map extensionsForImports = Maps.newHashMapWithExpectedSize(imports.size()); - ImmutableList.Builder fileDependencies = ImmutableList.builder(); ImmutableMap labelsForImports; // Find the labels corresponding to the load statements. @@ -174,6 +242,9 @@ public class SkylarkImportLookupFunction implements SkyFunction { skylarkImportMap = env.getValues(importLookupKeys); valuesMissing = env.valuesMissing(); } else { + Preconditions.checkNotNull( + inlineCachedValueBuilder, + "Expected inline cached value builder to be not-null when inlining."); // Inlining calls to SkylarkImportLookupFunction. if (alreadyVisited.containsKey(fileLabel)) { ImmutableList