From 4af9fc5c51040944178b112e6defda8473d40105 Mon Sep 17 00:00:00 2001 From: Nico Weber Date: Sun, 21 Sep 2014 16:10:54 -0700 Subject: support explicit build order --- src/build.cc | 189 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- src/build.h | 5 ++ src/graph.h | 12 +++- 3 files changed, 200 insertions(+), 6 deletions(-) diff --git a/src/build.cc b/src/build.cc index cf07846..8f23e96 100644 --- a/src/build.cc +++ b/src/build.cc @@ -89,6 +89,7 @@ void Plan::Reset() { } bool Plan::AddTarget(const Node* target, string* err) { + targets_.push_back(target); return AddSubTarget(target, NULL, err, NULL); } @@ -151,9 +152,20 @@ void Plan::EdgeWanted(const Edge* edge) { Edge* Plan::FindWork() { if (ready_.empty()) return NULL; - EdgeSet::iterator e = ready_.begin(); - Edge* edge = *e; - ready_.erase(e); + set::iterator i = ready_.end(); + for (list::iterator it = priority_list_.begin(), + end = priority_list_.end(); + it != end; ++it) { + i = ready_.find(*it); + if (i != ready_.end()) { + priority_list_.erase(it); + break; + } + } + if (i == ready_.end()) + i = ready_.begin(); + Edge* edge = *i; + ready_.erase(i); return edge; } @@ -424,6 +436,175 @@ void Plan::UnmarkDependents(const Node* node, set* dependents) { } } +namespace { +bool EdgeCom(const Edge* lhs, const Edge* rhs) { + // Note: > to sort in decreasing order. + return lhs->critical_time() > rhs->critical_time(); +} +} // namespace + +void Plan::ComputePriorityList(BuildLog* build_log) { + + //testcase have no build_log + if (!build_log) + return; + + METRIC_RECORD("ComputePriorityList"); + set dedup; + vector deduped; + for (vector::iterator it = targets_.begin(); it != targets_.end(); + ++it) { + pair::iterator, bool> insert_result = dedup.insert(*it); + if (!insert_result.second) + continue; + deduped.push_back(*it); + } + targets_.swap(deduped); + + + vector edges; + map num_out_edges; + for (map::iterator it = want_.begin(), end = want_.end(); + it != end; ++it) { + if (it->second != kWantNothing) + continue; + Edge* e = it->first; + edges.push_back(e); + //printf("in\n"); + set ins; // protect against #308; also sanity + for (size_t nit = 0; nit < e->inputs_.size(); ++nit) { + Node* n = e->inputs_[nit]; + if (ins.count(n) == 0) { + //printf("%s %s\n", (*nit)->path().c_str(), e->rule().name().c_str()); + num_out_edges[n]++; + ins.insert(n); + } + } + //printf("\n"); + } + + if (false) { + for (map::iterator it = num_out_edges.begin(), + end = num_out_edges.end(); + it != end; ++it) { + printf("%s %d\n", it->first->path().c_str(), it->second); + } + } + + + + // this is total time if building all edges in serial, so this value is big + // enough to ensure higher priority target initial critical time always bigger + // than lower one + uint64_t total_time = 0; + // Critical path scheduling. + // 0. Assign costs to all edges, using: + // a) The time the edge needed last time, if available. + // b) The average time this edge type needed, if this edge hasn't run before. + // (not implemented .log entries is not grouped by rule type, and even + // similar rule type may not have same name , for example two compile rule + // with different compile flags) + // c) A fixed cost if this type of edge hasn't run before (0 for phony target, + // 1 for others) + // + for (vector::iterator it = edges.begin(), end = edges.end(); it != end; + total_time += (*it)->run_time_ms_, ++it) { + Edge* edge = *it; + if (edge->is_phony()) + continue; + BuildLog::LogEntry* entry = + build_log->LookupByOutput(edge->outputs_[0]->path()); + if (!entry) { + edge->run_time_ms_ = 1; + continue; + } + int duration = entry->end_time - entry->start_time; // XXX: + 1? + edge->run_time_ms_ = duration; + } + + + // Dump graph to stdout for debugging / prototyping. + if (false) { + for (vector::iterator it = edges.begin(), end = edges.end(); + it != end; ++it) { + Edge* edge = *it; + Node* input = edge->inputs_[0]; + Node* output = edge->outputs_[0]; + printf("%s %s %d\n", input->path().c_str(), output->path().c_str(), + edge->run_time_ms_); + } + } + + // 1. Use backflow algorithm to compute critical times for all nodes, starting + // from the destination nodes. use priority_weight = total_time * N as + // initial critical time to makes forward edgs of higher priority always + // get higher critical time value + // XXX: ignores pools + queue edgesQ; + + // Makes sure that each edge is added to the queue just once. This is needed + // for example if a binary is used to generate 50 source files, and all the + // source file cxx lines are added. Without this, the edge generating that + // binary would be added ot the queue 50 times. + set done; + + for (vector::reverse_iterator it = targets_.rbegin(), + end = targets_.rend(); + it != end; ++it) { + if (Edge* in = (*it)->in_edge()) { + uint64_t priority_weight = (it - targets_.rbegin()) * total_time; + in->set_critical_time( + max(max(in->run_time_ms_, priority_weight), + in->critical_time())); + if (done.count(in) == 0) { + edgesQ.push(in); + done.insert(in); + } + } + } + while (!edgesQ.empty()) { + Edge* e = edgesQ.front(); edgesQ.pop(); + bool all_nodes_ready = true; + uint64_t max_crit = 0; + for (vector::iterator it = e->outputs_.begin(), + end = e->outputs_.end(); + it != end; ++it) { + if (num_out_edges[*it] > 0) { + all_nodes_ready = false; + continue; + } + for (vector::const_iterator eit = (*it)->out_edges().begin(), + eend = (*it)->out_edges().end(); + eit != eend; ++eit) { + max_crit = max((*eit)->critical_time(), max_crit); + } + } + if (!all_nodes_ready) { + // To the back it goes. + // XXX: think about how often this can happen. + edgesQ.push(e); + continue; + } + e->set_critical_time(max(max_crit + e->run_time_ms_, e->critical_time())); + + for (vector::iterator it = e->inputs_.begin(), + end = e->inputs_.end(); + it != end; ++it) { + num_out_edges[*it]--; + if (Edge* in = (*it)->in_edge()) { + if (done.count(in) == 0) { + edgesQ.push(in); + done.insert(in); + } + } + } + } + + // 2. Build priority list in decreasing order of critical times. + sort(edges.begin(), edges.end(), EdgeCom); + priority_list_ = list(edges.begin(), edges.end()); +} + void Plan::Dump() const { printf("pending: %d\n", (int)want_.size()); for (map::const_iterator e = want_.begin(); e != want_.end(); ++e) { @@ -574,6 +755,8 @@ bool Builder::AlreadyUpToDate() const { bool Builder::Build(string* err) { assert(!AlreadyUpToDate()); + plan_.ComputePriorityList(scan_.build_log()); + status_->PlanHasTotalEdges(plan_.command_edge_count()); int pending_commands = 0; int failures_allowed = config_.failures_allowed; diff --git a/src/build.h b/src/build.h index d697dfb..11c87da 100644 --- a/src/build.h +++ b/src/build.h @@ -16,6 +16,7 @@ #define NINJA_BUILD_H_ #include +#include #include #include #include @@ -75,6 +76,7 @@ struct Plan { /// Reset state. Clears want and ready sets. void Reset(); + void ComputePriorityList(BuildLog* build_log); /// Update the build plan to account for modifications made to the graph /// by information loaded from a dyndep file. @@ -122,6 +124,9 @@ private: EdgeSet ready_; Builder* builder_; + /// user provided targets in build order, earlier one have higher priority + vector targets_; + list priority_list_; /// Total number of edges that have commands (not phony). int command_edges_; diff --git a/src/graph.h b/src/graph.h index bb4f10c..47a2e57 100644 --- a/src/graph.h +++ b/src/graph.h @@ -146,9 +146,10 @@ struct Edge { Edge() : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL), mark_(VisitNone), - id_(0), outputs_ready_(false), deps_loaded_(false), - deps_missing_(false), generated_by_dep_loader_(false), - implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {} + id_(0), run_time_ms_(0), critical_time_(0), outputs_ready_(false), + deps_loaded_(false), deps_missing_(false), + generated_by_dep_loader_(false), implicit_deps_(0), + order_only_deps_(0), implicit_outs_(0) {} /// Return true if all inputs' in-edges are ready. bool AllInputsReady() const; @@ -171,6 +172,9 @@ struct Edge { void Dump(const char* prefix="") const; + uint64_t critical_time() const { return critical_time_; } + void set_critical_time(uint64_t critical_time) { critical_time_ = critical_time; } + const Rule* rule_; Pool* pool_; std::vector inputs_; @@ -179,6 +183,8 @@ struct Edge { BindingEnv* env_; VisitMark mark_; size_t id_; + int run_time_ms_; + uint64_t critical_time_; bool outputs_ready_; bool deps_loaded_; bool deps_missing_; -- cgit v0.12