From 6ae05b419922193c4c253e51c9a5e483e4f947fa Mon Sep 17 00:00:00 2001
From: janakr <janakr@google.com>
Date: Mon, 13 Aug 2018 16:13:42 -0700
Subject: Order Skyframe evaluations in a priority queue, with all children of
 a given node having the same priority, later enqueueings having higher
 priority, re-enqueued nodes having highest priority, and new root nodes
 having lowest priority. Experimentally, this can save significant RAM (1.4G
 in some builds!) while not affecting speed.

Also do a semi-drive-by deleting ExecutorFactory parameter to AbstractQueueVisitor, since it was always AbstractQueueVisitor.EXECUTOR_FACTORY.

PiperOrigin-RevId: 208560889
---
 .../devtools/build/skyframe/NodeEntryVisitor.java  | 31 ++++++++++++++++------
 1 file changed, 23 insertions(+), 8 deletions(-)

(limited to 'src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java')

diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
index 5d1cd5f26b..46672db153 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
@@ -14,12 +14,12 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Function;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.ErrorClassifier;
 import com.google.devtools.build.lib.concurrent.ForkJoinQuiescingExecutor;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
+import com.google.devtools.build.skyframe.ParallelEvaluatorContext.RunnableMaker;
 import java.util.Collection;
 import java.util.Set;
 import java.util.concurrent.CountDownLatch;
@@ -58,12 +58,12 @@ class NodeEntryVisitor {
    * Function that allows this visitor to execute the appropriate {@link Runnable} when given a
    * {@link SkyKey} to evaluate.
    */
-  private final Function<SkyKey, Runnable> runnableMaker;
+  private final RunnableMaker runnableMaker;
 
   NodeEntryVisitor(
       ForkJoinPool forkJoinPool,
       DirtyTrackingProgressReceiver progressReceiver,
-      Function<SkyKey, Runnable> runnableMaker) {
+      RunnableMaker runnableMaker) {
     this.quiescingExecutor = ForkJoinQuiescingExecutor.newBuilder()
         .withOwnershipOf(forkJoinPool)
         .setErrorClassifier(NODE_ENTRY_VISITOR_ERROR_CLASSIFIER)
@@ -75,15 +75,14 @@ class NodeEntryVisitor {
   NodeEntryVisitor(
       int threadCount,
       DirtyTrackingProgressReceiver progressReceiver,
-      Function<SkyKey, Runnable> runnableMaker) {
+      RunnableMaker runnableMaker) {
     quiescingExecutor =
-        new AbstractQueueVisitor(
+        AbstractQueueVisitor.createWithPriorityQueue(
             threadCount,
             /*keepAliveTime=*/ 1,
             TimeUnit.SECONDS,
             /*failFastOnException*/ true,
             "skyframe-evaluator",
-            AbstractQueueVisitor.EXECUTOR_FACTORY,
             NODE_ENTRY_VISITOR_ERROR_CLASSIFIER);
     this.progressReceiver = progressReceiver;
     this.runnableMaker = runnableMaker;
@@ -93,7 +92,23 @@ class NodeEntryVisitor {
     quiescingExecutor.awaitQuiescence(/*interruptWorkers=*/ true);
   }
 
-  void enqueueEvaluation(SkyKey key) {
+  /**
+   * Enqueue {@code key} for evaluation, at {@code evaluationPriority} if this visitor is using a
+   * priority queue.
+   *
+   * <p>{@code evaluationPriority} is used to minimize evaluation "sprawl": inefficiencies coming
+   * from incompletely evaluating many nodes, versus focusing on finishing the evaluation of nodes
+   * that have already started evaluating. Sprawl can be expensive because an incompletely evaluated
+   * node keeps state in Skyframe, and often in external caches, that uses memory.
+   *
+   * <p>In general, {@code evaluationPriority} should be maximal ({@link Integer#MAX_VALUE}) when
+   * restarting a node that has already started evaluation, and minimal when enqueueing a node that
+   * no other tasks depend on. Setting {@code evaluationPriority} to the same value for all children
+   * of a parent has good results experimentally, since it prioritizes batches of work that can be
+   * used together. Similarly, prioritizing deeper nodes (depth-first search of the evaluation
+   * graph) also has good results experimentally, since it minimizes sprawl.
+   */
+  void enqueueEvaluation(SkyKey key, int evaluationPriority) {
     if (preventNewEvaluations.get()) {
       // If an error happens in nokeep_going mode, we still want to mark these nodes as inflight,
       // otherwise cleanup will not happen properly.
@@ -101,7 +116,7 @@ class NodeEntryVisitor {
       return;
     }
     progressReceiver.enqueueing(key);
-    quiescingExecutor.execute(runnableMaker.apply(key));
+    quiescingExecutor.execute(runnableMaker.make(key, evaluationPriority));
   }
 
   /**
-- 
cgit v1.2.3