Simplify scheduler to not use build log/execution time

5 files changed, 51 insertions, 235 deletions

diff --git a/src/build.cc b/src/build.cc
index 9ace8c9..c3dc558 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -450,89 +450,16 @@ struct SeenBefore {
   }
 };
 
-// Assign run_time_ms for all wanted edges, and returns total time for all edges
-// For phony edges, 0 cost.
-// For edges with a build history, use the last build time.
-// For edges without history, use the 75th percentile time for edges with history.
-// Or, if there is no history at all just use 1
-int64_t AssignEdgeRuntime(BuildLog* build_log,
-                          const std::map<Edge*, Plan::Want>& want) {
-  bool missing_durations = false;
-  std::vector<int64_t> durations;
-  int64_t total_time = 0;
-  const int64_t kUnknownRunTime = -1; // marker value for the two loops below.
-
-  for (std::map<Edge*, Plan::Want>::const_iterator it = want.begin(),
-                                                   end = want.end();
-       it != end; ++it) {
-    Edge* edge = it->first;
-    if (edge->is_phony()) {
-      continue;
-    }
-    BuildLog::LogEntry* entry =
-        build_log->LookupByOutput(edge->outputs_[0]->path());
-    if (!entry) {
-      missing_durations = true;
-      edge->set_run_time_ms(kUnknownRunTime);  // mark as needing filled in
-      continue;
-    }
-    const int64_t duration = entry->end_time - entry->start_time;
-    edge->set_run_time_ms(duration);
-    total_time += duration;
-    durations.push_back(duration);
-  }
-
-  if (!missing_durations) {
-    return total_time;
-  }
-
-  // Heuristic: for unknown edges, take the 75th percentile time.
-  // This allows the known-slowest jobs to run first, but isn't so
-  // small that it is always the lowest priority. Which for slow jobs,
-  // might bottleneck the build.
-  int64_t p75_time = 1;
-  int64_t num_durations = static_cast<int64_t>(durations.size());
-  if (num_durations > 0) {
-    size_t p75_idx = (num_durations - 1) - num_durations / 4;
-    std::vector<int64_t>::iterator p75_it = durations.begin() + p75_idx;
-    std::nth_element(durations.begin(), p75_it, durations.end());
-    p75_time = *p75_it;
-  }
-
-  for (std::map<Edge*, Plan::Want>::const_iterator it = want.begin(),
-                                                   end = want.end();
-       it != end; ++it) {
-    Edge* edge = it->first;
-    if (edge->run_time_ms() != kUnknownRunTime) {
-      continue;
-    }
-    edge->set_run_time_ms(p75_time);
-    total_time += p75_time;
-  }
-  return total_time;
-}
-
-int64_t AssignDefaultEdgeRuntime(std::map<Edge*, Plan::Want> &want) {
-  int64_t total_time = 0;
-
-  for (std::map<Edge*, Plan::Want>::const_iterator it = want.begin(),
-           end = want.end();
-       it != end; ++it) {
-    Edge* edge = it->first;
-    if (edge->is_phony()) {
-      continue;
-    }
-
-    edge->set_run_time_ms(1);
-    ++total_time;
-  }
-  return total_time;
+// Heuristic for edge priority weighting.
+// Phony edges are free (0 cost), all other edges are weighted equally.
+int64_t EdgeWeightHeuristic(Edge *edge) {
+  return edge->is_phony() ? 0 : 1;
 }
 
 }  // namespace
 
-void Plan::ComputeCriticalTime(BuildLog* build_log) {
-  METRIC_RECORD("ComputeCriticalTime");
+void Plan::ComputeCriticalPath() {
+  METRIC_RECORD("ComputeCriticalPath");
   // Remove duplicate targets
   {
     std::set<const Node*> seen;
@@ -541,16 +468,8 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
                    targets_.end());
   }
 
-  // total time if building all edges in serial. This value is big
-  // enough to ensure higher priority target's initial critical time
-  // is always bigger than lower ones
-  const int64_t total_time = build_log ?
-      AssignEdgeRuntime(build_log, want_) :
-      AssignDefaultEdgeRuntime(want_);  // Plan tests have no build_log
-
-
-  // Use backflow algorithm to compute critical times for all nodes, starting
-  // from the destination nodes.
+  // Use backflow algorithm to compute the critical path for all
+  // nodes, starting from the destination nodes.
   // XXX: ignores pools
   std::queue<Edge*> work_queue;        // Queue, for breadth-first traversal
   // The set of edges currently in work_queue, to avoid duplicates.
@@ -560,12 +479,9 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
   for (size_t i = 0; i < targets_.size(); ++i) {
     const Node* target = targets_[i];
     if (Edge* in = target->in_edge()) {
-      // Add a bias to ensure that targets that appear first in |targets_| have a larger critical time than
-      // those that follow them. E.g. for 3 targets: [2*total_time, total_time, 0].
-      int64_t priority_weight = (targets_.size() - i - 1) * total_time;
-      in->set_critical_time_ms(
-          priority_weight +
-          std::max<int64_t>(in->run_time_ms(), in->critical_time_ms()));
+      int64_t edge_weight = EdgeWeightHeuristic(in);
+      in->set_critical_path_weight(
+          std::max<int64_t>(edge_weight, in->critical_path_weight()));
       if (!seen_edge(in)) {
         work_queue.push(in);
       }
@@ -575,7 +491,7 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
   while (!work_queue.empty()) {
     Edge* e = work_queue.front();
     work_queue.pop();
-    // If the critical time of any dependent edges is updated, this
+    // If the critical path of any dependent edges is updated, this
     // edge may need to be processed again. So re-allow insertion.
     active_edges.erase(e);
 
@@ -586,10 +502,11 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) {
       if (!in) {
         continue;
       }
-      // Only process edge if this node offers a higher critical time
-      const int64_t proposed_time = e->critical_time_ms() + in->run_time_ms();
-      if (proposed_time > in->critical_time_ms()) {
-        in->set_critical_time_ms(proposed_time);
+      // Only process edge if this node offers a higher weighted path
+      const int64_t edge_weight = EdgeWeightHeuristic(in);
+      const int64_t proposed_weight = e->critical_path_weight() + edge_weight;
+      if (proposed_weight > in->critical_path_weight()) {
+        in->set_critical_path_weight(proposed_weight);
         if (!seen_edge(in)) {
           work_queue.push(in);
         }
@@ -629,8 +546,8 @@ void Plan::ScheduleInitialEdges() {
   }
 }
 
-void Plan::PrepareQueue(BuildLog* build_log) {
-  ComputeCriticalTime(build_log);
+void Plan::PrepareQueue() {
+  ComputeCriticalPath();
   ScheduleInitialEdges();
 }
 
@@ -803,7 +720,7 @@ bool Builder::AlreadyUpToDate() const {
 
 bool Builder::Build(string* err) {
   assert(!AlreadyUpToDate());
-  plan_.PrepareQueue(scan_.build_log());
+  plan_.PrepareQueue();
 
   status_->PlanHasTotalEdges(plan_.command_edge_count());
   int pending_commands = 0;
diff --git a/src/build.h b/src/build.h
index e8b7c39..63d0682 100644
--- a/src/build.h
+++ b/src/build.h
@@ -76,7 +76,7 @@ struct Plan {
   void Reset();
 
   // After all targets have been added, prepares the ready queue for find work.
-  void PrepareQueue(BuildLog* build_log);
+  void PrepareQueue();
 
   /// Update the build plan to account for modifications made to the graph
   /// by information loaded from a dyndep file.
@@ -97,14 +97,14 @@ struct Plan {
   };
 
 private:
-  void ComputeCriticalTime(BuildLog* build_log);
+  void ComputeCriticalPath();
   bool RefreshDyndepDependents(DependencyScan* scan, const Node* node, std::string* err);
   void UnmarkDependents(const Node* node, std::set<Node*>* dependents);
   bool AddSubTarget(const Node* node, const Node* dependent, std::string* err,
                     std::set<Edge*>* dyndep_walk);
 
   // Add edges that kWantToStart into the ready queue
-  // Must be called after ComputeCriticalTime and before FindWork
+  // Must be called after ComputeCriticalPath and before FindWork
   void ScheduleInitialEdges();
 
   /// Update plan with knowledge that the given node is up to date.
diff --git a/src/build_test.cc b/src/build_test.cc
index 4c274e6..176f1a3 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -54,7 +54,7 @@ struct PlanTest : public StateTestWithBuiltinRules {
     string err;
     EXPECT_TRUE(plan_.AddTarget(GetNode(node), &err));
     ASSERT_EQ("", err);
-    plan_.PrepareQueue(log);
+    plan_.PrepareQueue();
     ASSERT_TRUE(plan_.more_to_do());
   }
 
@@ -207,7 +207,7 @@ void PlanTest::TestPoolWithDepthOne(const char* test_case) {
   ASSERT_EQ("", err);
   EXPECT_TRUE(plan_.AddTarget(GetNode("out2"), &err));
   ASSERT_EQ("", err);
-  plan_.PrepareQueue(NULL);
+  plan_.PrepareQueue();
   ASSERT_TRUE(plan_.more_to_do());
 
   Edge* edge = plan_.FindWork();
@@ -434,7 +434,7 @@ TEST_F(PlanTest, PoolWithFailingEdge) {
   ASSERT_EQ("", err);
   EXPECT_TRUE(plan_.AddTarget(GetNode("out2"), &err));
   ASSERT_EQ("", err);
-  plan_.PrepareQueue(NULL);
+  plan_.PrepareQueue();
   ASSERT_TRUE(plan_.more_to_do());
 
   Edge* edge = plan_.FindWork();
@@ -491,11 +491,11 @@ TEST_F(PlanTest, PriorityWithoutBuildLog) {
   BuildLog log;
   PrepareForTarget("out", &log);
 
-  EXPECT_EQ(GetNode("out")->in_edge()->critical_time_ms(), 1);
-  EXPECT_EQ(GetNode("a0")->in_edge()->critical_time_ms(), 2);
-  EXPECT_EQ(GetNode("b0")->in_edge()->critical_time_ms(), 2);
-  EXPECT_EQ(GetNode("c0")->in_edge()->critical_time_ms(), 2);
-  EXPECT_EQ(GetNode("a1")->in_edge()->critical_time_ms(), 3);
+  EXPECT_EQ(GetNode("out")->in_edge()->critical_path_weight(), 1);
+  EXPECT_EQ(GetNode("a0")->in_edge()->critical_path_weight(), 2);
+  EXPECT_EQ(GetNode("b0")->in_edge()->critical_path_weight(), 2);
+  EXPECT_EQ(GetNode("c0")->in_edge()->critical_path_weight(), 2);
+  EXPECT_EQ(GetNode("a1")->in_edge()->critical_path_weight(), 3);
 
   const int n_edges = 5;
   const char *expected_order[n_edges] = {
@@ -513,98 +513,6 @@ TEST_F(PlanTest, PriorityWithoutBuildLog) {
   EXPECT_FALSE(plan_.FindWork());
 }
 
-TEST_F(PlanTest, PriorityWithBuildLog) {
-  // With a build log, the critical time is longest weighted path.
-  // Test with the following graph:
-  //   a2
-  //   |
-  //   a1  b1
-  //   |  |  |
-  //   a0 b0 c0
-  //    \ | /
-  //     out
-
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-    "rule r\n"
-    "  command = unused\n"
-    "build out: r a0 b0 c0\n"
-    "build a0: r a1\n"
-    "build a1: r a2\n"
-    "build b0: r b1\n"
-    "build c0: r b1\n"
-  ));
-  GetNode("a1")->MarkDirty();
-  GetNode("a0")->MarkDirty();
-  GetNode("b0")->MarkDirty();
-  GetNode("c0")->MarkDirty();
-  GetNode("out")->MarkDirty();
-
-  BuildLog log;
-  log.RecordCommand(GetNode("out")->in_edge(), 0, 100); // time = 100
-  log.RecordCommand(GetNode("a0")->in_edge(), 10, 20); // time = 10
-  log.RecordCommand(GetNode("a1")->in_edge(), 20, 40); // time = 20
-  log.RecordCommand(GetNode("b0")->in_edge(), 10, 30); // time = 20
-  log.RecordCommand(GetNode("c0")->in_edge(), 20, 70); // time = 50
-
-  PrepareForTarget("out", &log);
-
-  EXPECT_EQ(GetNode("out")->in_edge()->critical_time_ms(), 100);
-  EXPECT_EQ(GetNode("a0")->in_edge()->critical_time_ms(), 110);
-  EXPECT_EQ(GetNode("b0")->in_edge()->critical_time_ms(), 120);
-  EXPECT_EQ(GetNode("c0")->in_edge()->critical_time_ms(), 150);
-  EXPECT_EQ(GetNode("a1")->in_edge()->critical_time_ms(), 130);
-
-  const int n_edges = 5;
-  const char *expected_order[n_edges] = {
-    "c0", "a1", "b0", "a0", "out"};
-  for (int i = 0; i < n_edges; ++i) {
-    Edge* edge = plan_.FindWork();
-    ASSERT_NE(edge, NULL);
-    EXPECT_EQ(expected_order[i], edge->outputs_[0]->path());
-
-    std::string err;
-    ASSERT_TRUE(plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, &err));
-    EXPECT_EQ(err, "");
-  }
-  EXPECT_FALSE(plan_.FindWork());
-}
-
-TEST_F(PlanTest, RuntimePartialBuildLog) {
-  // Test the edge->run_time_ms() estimate when no build log is available
-
-  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
-    "rule r\n"
-    "  command = unused\n"
-    "build out: r a0 b0 c0 d0\n"
-    "build a0: r a1\n"
-    "build b0: r b1\n"
-    "build c0: r c1\n"
-    "build d0: r d1\n"
-  ));
-  GetNode("a0")->MarkDirty();
-  GetNode("b0")->MarkDirty();
-  GetNode("c0")->MarkDirty();
-  GetNode("d0")->MarkDirty();
-  GetNode("out")->MarkDirty();
-
-  BuildLog log;
-  log.RecordCommand(GetNode("out")->in_edge(), 0, 100); // time = 40
-  log.RecordCommand(GetNode("a0")->in_edge(), 10, 20); // time = 10
-  log.RecordCommand(GetNode("b0")->in_edge(), 20, 40); // time = 20
-  log.RecordCommand(GetNode("c0")->in_edge(), 10, 40); // time = 30
-
-  PrepareForTarget("out", &log);
-
-  // These edges times are read from the build log
-  EXPECT_EQ(GetNode("out")->in_edge()->run_time_ms(), 100);
-  EXPECT_EQ(GetNode("a0")->in_edge()->run_time_ms(), 10);
-  EXPECT_EQ(GetNode("b0")->in_edge()->run_time_ms(), 20);
-  EXPECT_EQ(GetNode("c0")->in_edge()->run_time_ms(), 30);
-
-  // The missing data is taken from the 3rd quintile of known data
-  EXPECT_EQ(GetNode("d0")->in_edge()->run_time_ms(), 30);
-}
-
 /// Fake implementation of CommandRunner, useful for tests.
 struct FakeCommandRunner : public CommandRunner {
   explicit FakeCommandRunner(VirtualFileSystem* fs) :
diff --git a/src/graph.h b/src/graph.h
index db82bc5..c7304a6 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -174,7 +174,7 @@ struct Edge {
         id_(0), outputs_ready_(false), deps_loaded_(false),
         deps_missing_(false), generated_by_dep_loader_(false),
         command_start_time_(0), implicit_deps_(0), order_only_deps_(0),
-        run_time_ms_(0), critical_time_ms_(-1), implicit_outs_(0) {}
+        critical_path_weight_(-1), implicit_outs_(0) {}
 
   /// Return true if all inputs' in-edges are ready.
   bool AllInputsReady() const;
@@ -200,21 +200,13 @@ struct Edge {
   // Append all edge explicit inputs to |*out|. Possibly with shell escaping.
   void CollectInputs(bool shell_escape, std::vector<std::string>* out) const;
 
-  // Critical time is the estimated execution time in ms of the edges
-  // forming the longest time-weighted path to the target output.
-  // This quantity is used as a priority during build scheduling.
-  // NOTE: Defaults to -1 as a marker smaller than any valid time
-  int64_t critical_time_ms() const { return critical_time_ms_; }
-  void set_critical_time_ms(int64_t critical_time_ms) {
-    critical_time_ms_ = critical_time_ms;
-  }
-
-  // Run time in ms for this edge's command.
-  // Taken from the build log if present, or estimated otherwise.
-  // Default initialized to 0.
-  int64_t run_time_ms() const { return run_time_ms_; }
-  void set_run_time_ms(int64_t run_time_ms) {
-    run_time_ms_ = run_time_ms;
+  // critical_path_weight is the priority during build scheduling. The
+  // "critical path" between this edge's inputs and any target node is
+  // the path which maximises the sum oof weights along that path.
+  // NOTE: Defaults to -1 as a marker smaller than any valid weight
+  int64_t critical_path_weight() const { return critical_path_weight_; }
+  void set_critical_path_weight(int64_t critical_path_weight) {
+    critical_path_weight_ = critical_path_weight;
   }
 
   const Rule* rule_;
@@ -226,8 +218,7 @@ struct Edge {
   BindingEnv* env_;
   VisitMark mark_;
   size_t id_;
-  int64_t run_time_ms_;
-  int64_t critical_time_ms_;
+  int64_t critical_path_weight_;
   bool outputs_ready_;
   bool deps_loaded_;
   bool deps_missing_;
@@ -392,15 +383,15 @@ struct DependencyScan {
 // priority is defined lexicographically first by largest critical
 // time, then lowest ID.
 //
-// Including ID means that wherever the critical times are the same,
-// the edges are executed in ascending ID order which was historically
-// how all tasks were scheduled.
+// Including ID means that wherever the critical path weights are the
+// same, the edges are executed in ascending ID order which was
+// historically how all tasks were scheduled.
 struct EdgePriorityLess {
   bool operator()(const Edge* e1, const Edge* e2) const {
-    const int64_t ct1 = e1->critical_time_ms();
-    const int64_t ct2 = e2->critical_time_ms();
-    if (ct1 != ct2) {
-      return ct1 < ct2;
+    const int64_t cw1 = e1->critical_path_weight();
+    const int64_t cw2 = e2->critical_path_weight();
+    if (cw1 != cw2) {
+      return cw1 < cw2;
     }
     return e1->id_ > e2->id_;
   }
@@ -414,8 +405,8 @@ struct EdgePriorityGreater {
 };
 
 // A priority queue holding non-owning Edge pointers. top() will
-// return the edge with the largest critical time, and lowest ID if
-// more than one edge has the same critical time.
+// return the edge with the largest critical path weight, and lowest
+// ID if more than one edge has the same critical path weight.
 class EdgePriorityQueue:
   public std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityLess>{
 public:
diff --git a/src/graph_test.cc b/src/graph_test.cc
index 67dad53..fb0513c 100644
--- a/src/graph_test.cc
+++ b/src/graph_test.cc
@@ -998,7 +998,7 @@ TEST_F(GraphTest, EdgeQueuePriority) {
 
   // Output is largest critical time to smallest
   for (int i = 0; i < n_edges; ++i) {
-    edges[i]->set_critical_time_ms(i * 10);
+    edges[i]->set_critical_path_weight(i * 10);
   }
 
   EdgePriorityQueue queue;
@@ -1015,7 +1015,7 @@ TEST_F(GraphTest, EdgeQueuePriority) {
 
   // When there is ambiguity, the lowest edge id comes first
   for (int i = 0; i < n_edges; ++i) {
-    edges[i]->set_critical_time_ms(0);
+    edges[i]->set_critical_path_weight(0);
   }
 
   queue.push(edges[1]);