diff options
8 files changed, 224 insertions, 45 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/collect/Extrema.java b/src/main/java/com/google/devtools/build/lib/collect/Extrema.java new file mode 100644 index 0000000000..6f0b9cfbe3 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/Extrema.java @@ -0,0 +1,95 @@ +// 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.collect; + +import com.google.common.collect.ImmutableList; +import java.util.Comparator; +import java.util.PriorityQueue; + +/** + * A stream aggregator that, given a {@code k}, aggregates a sequence of elements into the {@code k} + * most extreme. + */ +public class Extrema<T extends Comparable<T>> { + private final int k; + private final Comparator<T> extremaComparator; + private final PriorityQueue<T> priorityQueue; + + /** + * Creates an {@link Extrema} that aggregates a sequence of elements into the {@code k} smallest. + */ + public static <T extends Comparable<T>> Extrema<T> min(int k) { + return new Extrema<>(k, Comparator.<T>naturalOrder()); + } + + /** + * Creates an {@link Extrema} that aggregates a sequence of elements into the {@code k} largest. + */ + public static <T extends Comparable<T>> Extrema<T> max(int k) { + return new Extrema<>(k, Comparator.<T>naturalOrder().reversed()); + } + + /** + * @param k the number of extreme elements to compute + * @param extremaComparator a comparator such that {@code extremaComparator(a, b) < 0} iff + * {@code a} is more extreme than {@code b} + */ + private Extrema(int k, Comparator<T> extremaComparator) { + this.k = k; + this.extremaComparator = extremaComparator; + this.priorityQueue = new PriorityQueue<>( + /*initialCapacity=*/ k, + // Our implementation strategy is to keep a priority queue of the k most extreme elements + // encountered, ordered backwards; this way we have constant-time access to the least + // extreme among these elements. + extremaComparator.reversed()); + } + + /** + * Aggregates the given element. + * + * <p>See {@link #getExtremeElements()}. + */ + public void aggregate(T element) { + if (priorityQueue.size() < k) { + priorityQueue.add(element); + } else { + if (extremaComparator.compare(element, priorityQueue.peek()) < 0) { + // Suppose the least extreme of the current k most extreme elements is e. If the new element + // is more extreme than e, then (i) it must be among the new k most extreme among the (2) e + // must not be. + priorityQueue.remove(); + priorityQueue.add(element); + } + } + } + + /** + * For an {@link Extrema} created with {@code k} and with {@code n} calls to {@link #aggregate} + * since the most recent call to {@link #clear}, returns the min(k, n) most extreme elements + * {@link #aggregate}'ed since the most recent call to {@link #clear}. + */ + public ImmutableList<T> getExtremeElements() { + return ImmutableList.sortedCopyOf(extremaComparator, priorityQueue); + } + + /** + * Disregards all the elements {@link #aggregate}'ed already. + * + * <p>See {@link #getExtremeElements()}. + */ + public void clear() { + priorityQueue.clear(); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java index 04307006fd..7a8b121ae8 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/Package.java +++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java @@ -721,7 +721,7 @@ public class Package { */ public static class Builder { - public static interface Helper { + public interface Helper { /** * Returns a fresh {@link Package} instance that a {@link Builder} will internally mutate * during package loading. Called by {@link PackageFactory}. @@ -730,10 +730,13 @@ public class Package { /** * Called after {@link com.google.devtools.build.lib.skyframe.PackageFunction} is completely - * done loading the given {@link Package}. {@code skylarkSemantics} are the semantics used to - * evaluate the build. + * done loading the given {@link Package}. + * + * @param pkg the loaded {@link Package} + * @param skylarkSemantics are the semantics used to load the package + * @param loadTimeMs the wall time, in ms, that it took to load the package */ - void onLoadingComplete(Package pkg, SkylarkSemantics skylarkSemantics); + void onLoadingComplete(Package pkg, SkylarkSemantics skylarkSemantics, long loadTimeMs); } /** {@link Helper} that simply calls the {@link Package} constructor. */ @@ -749,7 +752,8 @@ public class Package { } @Override - public void onLoadingComplete(Package pkg, SkylarkSemantics skylarkSemantics) { + public void onLoadingComplete( + Package pkg, SkylarkSemantics skylarkSemantics, long loadTimeMs) { } } diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java index daf3dfe247..3f3ad09cb1 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java +++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java @@ -390,7 +390,7 @@ public final class PackageFactory { * Constructs a {@code PackageFactory} instance with a specific glob path translator * and rule factory. * - * <p>Only intended to be called by BlazeRuntime or {@link FactoryForTesting#create}. + * <p>Only intended to be called by BlazeRuntime or {@link BuilderForTesting#build}. * * <p>Do not call this constructor directly in tests; please use * TestConstants#PACKAGE_FACTORY_BUILDER_FACTORY_FOR_TESTING instead. @@ -1617,8 +1617,9 @@ public final class PackageFactory { * Called by a caller of {@link #createPackageFromAst} after this caller has fully * loaded the package. */ - public void afterDoneLoadingPackage(Package pkg, SkylarkSemantics skylarkSemantics) { - packageBuilderHelper.onLoadingComplete(pkg, skylarkSemantics); + public void afterDoneLoadingPackage( + Package pkg, SkylarkSemantics skylarkSemantics, long loadTimeNanos) { + packageBuilderHelper.onLoadingComplete(pkg, skylarkSemantics, loadTimeNanos); } /** diff --git a/src/main/java/com/google/devtools/build/lib/profiler/BUILD b/src/main/java/com/google/devtools/build/lib/profiler/BUILD index bb1231e064..e0a8dfb7b6 100644 --- a/src/main/java/com/google/devtools/build/lib/profiler/BUILD +++ b/src/main/java/com/google/devtools/build/lib/profiler/BUILD @@ -16,6 +16,7 @@ java_library( "//src/main/java/com/google/devtools/build/lib:base-util", "//src/main/java/com/google/devtools/build/lib:os_util", "//src/main/java/com/google/devtools/build/lib/clock", + "//src/main/java/com/google/devtools/build/lib/collect", "//src/main/java/com/google/devtools/build/lib/concurrent", "//src/main/java/com/google/devtools/build/lib/shell", "//src/main/java/com/google/devtools/common/options", diff --git a/src/main/java/com/google/devtools/build/lib/profiler/Profiler.java b/src/main/java/com/google/devtools/build/lib/profiler/Profiler.java index d453967041..b58c21d9c2 100644 --- a/src/main/java/com/google/devtools/build/lib/profiler/Profiler.java +++ b/src/main/java/com/google/devtools/build/lib/profiler/Profiler.java @@ -20,6 +20,7 @@ import com.google.common.base.Predicate; import com.google.common.collect.ImmutableList; import com.google.common.collect.Iterables; import com.google.devtools.build.lib.clock.Clock; +import com.google.devtools.build.lib.collect.Extrema; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import com.google.devtools.build.lib.profiler.PredicateBasedStatRecorder.RecorderAndPredicate; @@ -36,7 +37,6 @@ import java.util.IdentityHashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; -import java.util.PriorityQueue; import java.util.Queue; import java.util.Timer; import java.util.TimerTask; @@ -332,51 +332,40 @@ public final class Profiler { /** * Aggregator class that keeps track of the slowest tasks of the specified type. * - * <p><code>priorityQueues</p> is sharded so that all threads need not compete for the same - * lock if they do the same operation at the same time. Access to the individual queues is - * synchronized on the queue objects themselves. + * <p><code>extremaAggregators</p> is sharded so that all threads need not compete for the same + * lock if they do the same operation at the same time. Access to an individual {@link Extrema} + * is synchronized on the {@link Extrema} instance itself. */ private static final class SlowestTaskAggregator { private static final int SHARDS = 16; private final int size; @SuppressWarnings({"unchecked", "rawtypes"}) - private final PriorityQueue<SlowTask>[] priorityQueues = new PriorityQueue[SHARDS]; + private final Extrema<SlowTask>[] extremaAggregators = new Extrema[SHARDS]; SlowestTaskAggregator(int size) { this.size = size; for (int i = 0; i < SHARDS; i++) { - priorityQueues[i] = new PriorityQueue<>(size + 1); + extremaAggregators[i] = Extrema.max(size); } } // @ThreadSafe void add(TaskData taskData) { - PriorityQueue<SlowTask> queue = - priorityQueues[(int) (Thread.currentThread().getId() % SHARDS)]; - synchronized (queue) { - if (queue.size() == size) { - // Optimization: check if we are faster than the fastest element. If we are, we would - // be the ones to fall off the end of the queue, therefore, we can safely return early. - if (queue.peek().getDurationNanos() > taskData.duration) { - return; - } - - queue.add(new SlowTask(taskData)); - queue.remove(); - } else { - queue.add(new SlowTask(taskData)); - } + Extrema<SlowTask> extrema = + extremaAggregators[(int) (Thread.currentThread().getId() % SHARDS)]; + synchronized (extrema) { + extrema.aggregate(new SlowTask(taskData)); } } // @ThreadSafe void clear() { for (int i = 0; i < SHARDS; i++) { - PriorityQueue<SlowTask> queue = priorityQueues[i]; - synchronized (queue) { - queue.clear(); + Extrema<SlowTask> extrema = extremaAggregators[i]; + synchronized (extrema) { + extrema.clear(); } } } @@ -384,19 +373,16 @@ public final class Profiler { // @ThreadSafe Iterable<SlowTask> getSlowestTasks() { // This is slow, but since it only happens during the end of the invocation, it's OK - PriorityQueue<SlowTask> merged = new PriorityQueue<>(size * SHARDS); + Extrema mergedExtrema = Extrema.max(size * SHARDS); for (int i = 0; i < SHARDS; i++) { - PriorityQueue<SlowTask> queue = priorityQueues[i]; - synchronized (queue) { - merged.addAll(queue); + Extrema<SlowTask> extrema = extremaAggregators[i]; + synchronized (extrema) { + for (SlowTask task : extrema.getExtremeElements()) { + mergedExtrema.aggregate(task); + } } } - - while (merged.size() > size) { - merged.remove(); - } - - return merged; + return mergedExtrema.getExtremeElements(); } } diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java index af54d080c5..bfc2a35e72 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java @@ -25,6 +25,7 @@ import com.google.common.collect.Iterables; import com.google.common.collect.Lists; import com.google.common.collect.Maps; import com.google.common.collect.Sets; +import com.google.devtools.build.lib.clock.BlazeClock; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.cmdline.LabelSyntaxException; import com.google.devtools.build.lib.cmdline.PackageIdentifier; @@ -472,7 +473,11 @@ public class PackageFunction implements SkyFunction { } if (packageFactory != null) { - packageFactory.afterDoneLoadingPackage(pkg, skylarkSemantics); + packageFactory.afterDoneLoadingPackage( + pkg, + skylarkSemantics, + // This is a lie. + /*loadTimeNanos=*/0L); } return new PackageValue(pkg); } @@ -576,6 +581,7 @@ public class PackageFunction implements SkyFunction { List<Statement> preludeStatements = astLookupValue.lookupSuccessful() ? astLookupValue.getAST().getStatements() : ImmutableList.<Statement>of(); + long startTimeNanos = BlazeClock.nanoTime(); BuilderAndGlobDeps packageBuilderAndGlobDeps = loadPackage( workspaceName, @@ -588,6 +594,7 @@ public class PackageFunction implements SkyFunction { preludeStatements, packageLookupValue.getRoot(), env); + long loadTimeNanos = Math.max(BlazeClock.nanoTime() - startTimeNanos, 0L); if (packageBuilderAndGlobDeps == null) { return null; } @@ -642,7 +649,7 @@ public class PackageFunction implements SkyFunction { // We know this SkyFunction will not be called again, so we can remove the cache entry. packageFunctionCache.invalidate(packageId); - packageFactory.afterDoneLoadingPackage(pkg, skylarkSemantics); + packageFactory.afterDoneLoadingPackage(pkg, skylarkSemantics, loadTimeNanos); return new PackageValue(pkg); } diff --git a/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java b/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java new file mode 100644 index 0000000000..1f86a042fe --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java @@ -0,0 +1,84 @@ +// 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.collect; + +import static com.google.common.truth.Truth.assertThat; + +import com.google.common.collect.ImmutableList; +import java.util.Collections; +import java.util.List; +import java.util.stream.Collectors; +import java.util.stream.IntStream; +import java.util.stream.Stream; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +/** Tests for {@link Extrema}. */ +@RunWith(JUnit4.class) +public class ExtremaTest { + @Test + public void handlesDupes() { + Extrema<Integer> extrema = Extrema.min(3); + extrema.aggregate(4); + extrema.aggregate(3); + extrema.aggregate(1); + extrema.aggregate(2); + extrema.aggregate(1); + extrema.aggregate(3); + extrema.aggregate(1); + assertThat(extrema.getExtremeElements()).containsExactly(1, 1, 1); + } + + @Test + public void minExtremaSmallK() { + runRangeTest(Extrema.min(5), 1, 100, ImmutableList.of(1, 2, 3, 4, 5)); + } + + @Test + public void minExtremaLargeK() { + runRangeTest(Extrema.min(10), 1, 5, ImmutableList.of(1, 2, 3, 4, 5)); + } + + @Test + public void maxExtremaSmallK() { + runRangeTest(Extrema.max(5), 1, 100, ImmutableList.of(100, 99, 98, 97, 96)); + } + + @Test + public void maxExtremaLargeK() { + runRangeTest(Extrema.max(10), 1, 5, ImmutableList.of(5, 4, 3, 2, 1)); + } + + private void runRangeTest( + Extrema<Integer> extrema, + int leftEndpointInclusive, + int rightEndpointInclusive, + ImmutableList<Integer> expected) { + assertThat(extrema.getExtremeElements()).isEmpty(); + closedRangeShuffled(leftEndpointInclusive, rightEndpointInclusive).forEach(extrema::aggregate); + assertThat(extrema.getExtremeElements()).containsExactlyElementsIn(expected).inOrder(); + extrema.clear(); + assertThat(extrema.getExtremeElements()).isEmpty(); + } + + private static Stream<Integer> closedRangeShuffled( + int leftEndpointInclusive, int rightEndpointInclusive) { + List<Integer> list = + IntStream.rangeClosed(leftEndpointInclusive, rightEndpointInclusive).boxed().collect( + Collectors.toList()); + Collections.shuffle(list); + return list.stream(); + } +} diff --git a/src/test/java/com/google/devtools/build/lib/testutil/BazelPackageBuilderHelperForTesting.java b/src/test/java/com/google/devtools/build/lib/testutil/BazelPackageBuilderHelperForTesting.java index b5522a0007..2bd6cf6d8e 100644 --- a/src/test/java/com/google/devtools/build/lib/testutil/BazelPackageBuilderHelperForTesting.java +++ b/src/test/java/com/google/devtools/build/lib/testutil/BazelPackageBuilderHelperForTesting.java @@ -47,7 +47,8 @@ public class BazelPackageBuilderHelperForTesting implements Package.Builder.Help } @Override - public void onLoadingComplete(Package pkg, SkylarkSemantics skylarkSemantics) { + public void onLoadingComplete( + Package pkg, SkylarkSemantics skylarkSemantics, long loadTimeNanos) { sanityCheckBazelPackageLoader(pkg, ruleClassProvider, skylarkSemantics); } |