From 29fe3ef1faefa554bc9490716071e969e84774db Mon Sep 17 00:00:00 2001 From: Peter Bell Date: Wed, 10 Aug 2022 17:29:50 +0100 Subject: Simplify scheduler to not use build log/execution time --- src/build.cc | 123 +++++++++--------------------------------------------- src/build.h | 6 +-- src/build_test.cc | 108 ++++------------------------------------------- src/graph.h | 45 ++++++++------------ src/graph_test.cc | 4 +- 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& want) { - bool missing_durations = false; - std::vector durations; - int64_t total_time = 0; - const int64_t kUnknownRunTime = -1; // marker value for the two loops below. - - for (std::map::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(durations.size()); - if (num_durations > 0) { - size_t p75_idx = (num_durations - 1) - num_durations / 4; - std::vector::iterator p75_it = durations.begin() + p75_idx; - std::nth_element(durations.begin(), p75_it, durations.end()); - p75_time = *p75_it; - } - - for (std::map::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 &want) { - int64_t total_time = 0; - - for (std::map::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 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 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(in->run_time_ms(), in->critical_time_ms())); + int64_t edge_weight = EdgeWeightHeuristic(in); + in->set_critical_path_weight( + std::max(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* dependents); bool AddSubTarget(const Node* node, const Node* dependent, std::string* err, std::set* 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* 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, 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]); -- cgit v0.12