diff options
author | nharmata <nharmata@google.com> | 2018-02-28 13:03:12 -0800 |
---|---|---|
committer | Copybara-Service <copybara-piper@google.com> | 2018-02-28 13:05:31 -0800 |
commit | 23319fc23fd334a98e610edcfca4a1f255908e14 (patch) | |
tree | f3de277759a03634c3793a80749ef6e72c857a4f /src/main/java/com/google/devtools/build | |
parent | 614fe0dfb9e6bed90c361e4b6bfff37c11a4775f (diff) |
Introduce an Extrema aggregator.
RELNOTES: None
PiperOrigin-RevId: 187370833
Diffstat (limited to 'src/main/java/com/google/devtools/build')
6 files changed, 138 insertions, 44 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); } |