Make top-N computation in CriticalPathComputer more efficient. It is not
necessary to sort the entire list just to compute the top-N. This can easily
give a 10x speed improvement if there are many components.
RELNOTES: None.
package com.google.devtools.build.lib.runtime;
-import static com.google.common.collect.ImmutableList.toImmutableList;
-import static java.util.Comparator.comparingLong;
-
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Maps;
+import com.google.common.collect.Ordering;
import com.google.common.eventbus.AllowConcurrentEvents;
import com.google.common.eventbus.Subscribe;
import com.google.devtools.build.lib.actions.Action;
@@ -36,6 +34,7 @@ import com.google.devtools.build.lib.actions.SpawnMetrics;
import com.google.devtools.build.lib.actions.SpawnResult;
import com.google.devtools.build.lib.clock.Clock;
import java.time.Duration;
+import java.util.Comparator;
import java.util.Objects;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicInteger;
@@ -178,38 +177,27 @@ public class CriticalPathComputer {
/** Returns the list of components using the most memory. */
public ImmutableList<CriticalPathComponent> getLargestMemoryComponents() {
- return outputArtifactToComponent
- .values()
- .stream()
- .sorted(
- comparingLong((CriticalPathComponent a) -> a.getSpawnMetrics().memoryEstimate())
- .reversed())
- .limit(LARGEST_MEMORY_COMPONENTS_SIZE)
- .collect(toImmutableList());
+ return ImmutableList.copyOf(
+ Ordering.from(
+ Comparator.comparingLong(
+ (CriticalPathComponent c) -> c.getSpawnMetrics().memoryEstimate()))
+ .greatestOf(outputArtifactToComponent.values(), LARGEST_MEMORY_COMPONENTS_SIZE));
}
/** Returns the list of components with the largest input sizes. */
public ImmutableList<CriticalPathComponent> getLargestInputSizeComponents() {
- return outputArtifactToComponent
- .values()
- .stream()
- .sorted(
- comparingLong((CriticalPathComponent a) -> a.getSpawnMetrics().inputBytes())
- .reversed())
- .limit(LARGEST_INPUT_SIZE_COMPONENTS_SIZE)
- .collect(toImmutableList());
+ return ImmutableList.copyOf(
+ Ordering.from(
+ Comparator.comparingLong(
+ (CriticalPathComponent c) -> c.getSpawnMetrics().inputBytes()))
+ .greatestOf(outputArtifactToComponent.values(), LARGEST_INPUT_SIZE_COMPONENTS_SIZE));
}
/** Returns the list of slowest components. */
public ImmutableList<CriticalPathComponent> getSlowestComponents() {
- return outputArtifactToComponent
- .values()
- .stream()
- .sorted(
- comparingLong((CriticalPathComponent a) -> a.getElapsedTimeNanos())
- .reversed())
- .limit(SLOWEST_COMPONENTS_SIZE)
- .collect(toImmutableList());
+ return ImmutableList.copyOf(
+ Ordering.from(Comparator.comparingLong(CriticalPathComponent::getElapsedTimeNanos))
+ .greatestOf(outputArtifactToComponent.values(), SLOWEST_COMPONENTS_SIZE));
}
/**
