From a8611647de41d52a05ee9e85a767e59d1c923ce6 Mon Sep 17 00:00:00 2001 From: Peter Bell Date: Mon, 7 Mar 2022 20:42:53 +0000 Subject: Improve comments and retrieve edges into ready_queue directly --- src/build.cc | 24 ++++++++++-------------- src/build.h | 4 ++-- src/graph.h | 23 ++++++++++++----------- src/graph_test.cc | 2 +- src/state.cc | 4 ++-- src/state.h | 2 +- 6 files changed, 28 insertions(+), 31 deletions(-) diff --git a/src/build.cc b/src/build.cc index d6be1c0..de62a62 100644 --- a/src/build.cc +++ b/src/build.cc @@ -173,9 +173,7 @@ void Plan::ScheduleWork(map::iterator want_e) { Pool* pool = edge->pool(); if (pool->ShouldDelayEdge()) { pool->DelayEdge(edge); - EdgeSet new_edges; - pool->RetrieveReadyEdges(&new_edges); - ready_.push_multiple(new_edges.begin(), new_edges.end()); + pool->RetrieveReadyEdges(&ready_); } else { pool->EdgeScheduled(*edge); ready_.push(edge); @@ -190,9 +188,7 @@ bool Plan::EdgeFinished(Edge* edge, EdgeResult result, string* err) { // See if this job frees up any delayed jobs. if (directly_wanted) edge->pool()->EdgeFinished(*edge); - EdgeSet new_edges; - edge->pool()->RetrieveReadyEdges(&new_edges); - ready_.push_multiple(new_edges.begin(), new_edges.end()); + edge->pool()->RetrieveReadyEdges(&ready_); // The rest of this function only applies to successful commands. if (result != kEdgeSucceeded) @@ -541,10 +537,10 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) { // Use backflow algorithm to compute critical times for all nodes, starting // from the destination nodes. // XXX: ignores pools - std::queue breadthFirstEdges; // Queue, for breadth-first traversal - std::set active_edges; // Set of in breadthFirstEdges + std::queue work_queue; // Queue, for breadth-first traversal + std::set active_edges; // Set of edges in work_queue SeenBefore seen_edge( - &active_edges); // Test for uniqueness in breadthFirstEdges + &active_edges); // Test for uniqueness in work_queue for (std::vector::reverse_iterator it = targets_.rbegin(), end = targets_.rend(); @@ -557,14 +553,14 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) { priority_weight + std::max(in->run_time_ms_, in->critical_time())); if (!seen_edge(in)) { - breadthFirstEdges.push(in); + work_queue.push(in); } } } - while (!breadthFirstEdges.empty()) { - Edge* e = breadthFirstEdges.front(); - breadthFirstEdges.pop(); + while (!work_queue.empty()) { + Edge* e = work_queue.front(); + work_queue.pop(); active_edges.erase(e); for (std::vector::iterator it = e->inputs_.begin(), @@ -579,7 +575,7 @@ void Plan::ComputeCriticalTime(BuildLog* build_log) { if (proposed_time > in->critical_time()) { in->set_critical_time(proposed_time); if (!seen_edge(in)) { - breadthFirstEdges.push(in); + work_queue.push(in); } } } diff --git a/src/build.h b/src/build.h index e91edbe..0d7c01a 100644 --- a/src/build.h +++ b/src/build.h @@ -22,7 +22,7 @@ #include #include "depfile_parser.h" -#include "graph.h" // XXX needed for DependencyScan; should rearrange. +#include "graph.h" #include "exit_status.h" #include "util.h" // int64_t @@ -120,7 +120,7 @@ private: /// we want for the edge. std::map want_; - EdgeQueue ready_; + EdgePriorityQueue ready_; Builder* builder_; /// user provided targets in build order, earlier one have higher priority diff --git a/src/graph.h b/src/graph.h index 0604ea7..4b45dad 100644 --- a/src/graph.h +++ b/src/graph.h @@ -197,7 +197,7 @@ struct Edge { void Dump(const char* prefix="") const; - // Critical time is the estimated exection time in ms of the edges + // 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 @@ -376,7 +376,13 @@ struct DependencyScan { DyndepLoader dyndep_loader_; }; -// Prioritize edges by largest critical time first +// Implements a less comarison for edges by priority, where highest +// 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. struct EdgePriorityCompare { bool operator()(const Edge* e1, const Edge* e2) const { const int64_t ct1 = e1->critical_time(); @@ -388,20 +394,15 @@ struct EdgePriorityCompare { } }; -// Set of ready edges, sorted by priority -class EdgeQueue: +// 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. +class EdgePriorityQueue: public std::priority_queue, EdgePriorityCompare>{ public: void clear() { c.clear(); } - - template - void push_multiple(It first, It last) { - for (; first != last; ++first) { - push(*first); - } - } }; #endif // NINJA_GRAPH_H_ diff --git a/src/graph_test.cc b/src/graph_test.cc index 97726ce..d657387 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -968,7 +968,7 @@ TEST_F(GraphTest, EdgeQueuePriority) { edges[i]->set_critical_time(i * 10); } - EdgeQueue queue; + EdgePriorityQueue queue; for (int i = 0; i < n_edges; ++i) { queue.push(edges[i]); } diff --git a/src/state.cc b/src/state.cc index 556b0d8..e194519 100644 --- a/src/state.cc +++ b/src/state.cc @@ -38,13 +38,13 @@ void Pool::DelayEdge(Edge* edge) { delayed_.insert(edge); } -void Pool::RetrieveReadyEdges(EdgeSet* ready_queue) { +void Pool::RetrieveReadyEdges(EdgePriorityQueue* ready_queue) { DelayedEdges::iterator it = delayed_.begin(); while (it != delayed_.end()) { Edge* edge = *it; if (current_use_ + edge->weight() > depth_) break; - ready_queue->insert(edge); + ready_queue->push(edge); EdgeScheduled(*edge); ++it; } diff --git a/src/state.h b/src/state.h index 878ac6d..2b0fa90 100644 --- a/src/state.h +++ b/src/state.h @@ -62,7 +62,7 @@ struct Pool { void DelayEdge(Edge* edge); /// Pool will add zero or more edges to the ready_queue - void RetrieveReadyEdges(EdgeSet* ready_queue); + void RetrieveReadyEdges(EdgePriorityQueue* ready_queue); /// Dump the Pool and its edges (useful for debugging). void Dump() const; -- cgit v0.12