diff options
author | Treehugger Robot <treehugger-gerrit@google.com> | 2023-03-15 10:03:19 +0000 |
---|---|---|
committer | Gerrit Code Review <noreply-gerritcodereview@google.com> | 2023-03-15 10:03:19 +0000 |
commit | a6b76d1e577f3bf3d3956d1b135d130e8083af69 (patch) | |
tree | 298d8d25ea9b419b6bb40f00274cf56aa82cbafc | |
parent | cdd5c80b94f89be8282b8bd43760239516c1c5ac (diff) | |
parent | 85feab1d7308ac61770ffde92d21aa935bda2d09 (diff) | |
download | ninja-a6b76d1e577f3bf3d3956d1b135d130e8083af69.tar.gz |
Merge "Add usesweightlist option"
-rw-r--r-- | src/build.cc | 111 | ||||
-rw-r--r-- | src/build.h | 16 | ||||
-rw-r--r-- | src/graph.h | 14 | ||||
-rw-r--r-- | src/ninja.cc | 9 | ||||
-rw-r--r-- | src/status.cc | 3 |
5 files changed, 149 insertions, 4 deletions
diff --git a/src/build.cc b/src/build.cc index f152317..26a6cda 100644 --- a/src/build.cc +++ b/src/build.cc @@ -16,11 +16,15 @@ #include <assert.h> #include <errno.h> +#include <fstream> #include <functional> #include <set> #include <sstream> #include <stdio.h> #include <stdlib.h> +#include <unordered_map> +#include <unordered_set> +#include <variant> #include <vector> #ifdef _WIN32 @@ -40,6 +44,7 @@ #include "disk_interface.h" #include "graph.h" #include "metrics.h" +#include "parallel_map.h" #include "state.h" #include "status.h" #include "subprocess.h" @@ -79,6 +84,23 @@ bool DryRunCommandRunner::WaitForCommand(Result* result) { return true; } +typedef std::unordered_map<HashedStrView, int64_t> WeightDataSource; + +// Get weight from data source, it isn't related to Edge.weight because +// Edge.weight is used for task distribution across pools which we don't +// want to do that in this context. +int64_t GetWeight(const WeightDataSource& data_source, Edge* edge) { + if (!edge || edge->outputs_ready()) { + return 0; + } + if (edge->is_phony()) { + return 1; + } + if (auto it = data_source.find(edge->outputs_[0]->globalPath().h); it != data_source.end()) { + return it->second; + } + return 1; +} } // namespace Plan::Plan(Builder* builder) @@ -590,11 +612,100 @@ Node* Builder::AddTarget(const string& name, string* err) { return node; } +void Builder::RefreshPriority(const std::vector<Node*>& start_nodes) { + METRIC_RECORD("RefreshPriority"); + WeightDataSource data_source; + // To keep HashedStrView in WeightDataSource valid. + std::vector<HashedStr> paths; + if (config_.weight_list_path) { + std::ifstream file(config_.weight_list_path.value()); + std::string line; + while (std::getline(file, line)) { + if (auto pos = line.find_first_of(','); pos != string::npos) { + auto path = line.substr(0, pos); + auto raw_weight = line.substr(pos + 1); + char* idx; + int64_t weight = std::strtoll(raw_weight.c_str(), &idx, 10); + if (idx != nullptr) { + data_source[paths.emplace_back(path)] = weight; + } + } + } + } else { + Fatal("data_source should exist here."); + } + std::vector<std::pair<Edge*, int64_t>> todos; + std::unique_ptr<ThreadPool> thread_pool = CreateThreadPool(); + for (auto* node: start_nodes) { + if (node && node->in_edge()) { + todos.emplace_back(std::make_pair(node->in_edge(), 0)); + } + } + while (!todos.empty()) { + // Traverse edges in BFS manner, and update each edge's critical path based priority from + // accumulated weight. + const auto& result = ParallelMap(thread_pool.get(), todos, [&data_source] (auto& p) { + // the pair is composed of a visiting edge and accumulated critical path based priority. + auto* e = p.first; + auto acc = p.second; + + if (!e) { + return std::unordered_map<Edge*, int64_t>(); + } + auto run = GetWeight(data_source, e); + auto new_priority = run + acc; + // Skip if priority isn't updated + if (new_priority <= e->priority()) { + return std::unordered_map<Edge*, int64_t>(); + } + e->priority_ = new_priority; + + std::set<Edge*, EdgeCmp> next_edges; + for (auto* next_node : e->inputs_) { + if (!next_node) { + continue; + } + auto* next_e = next_node->in_edge(); + if (next_e) { + next_edges.insert(next_e); + } + } + + std::unordered_map<Edge*, int64_t> next_todo_map; + for (auto* ne : next_edges) { + auto next_run = GetWeight(data_source, ne); + if (next_run + e->priority() > ne->priority()) { + next_todo_map.try_emplace(ne, e->priority()); + } + } + return next_todo_map; + }); + todos.clear(); + + std::unordered_map<Edge*, int64_t> next_todo_map_total; + for (const auto& todo_map : result) { + for (const auto& [k, v] : todo_map) { + auto [it, inserted] = next_todo_map_total.try_emplace(k, v); + if (!inserted) { + it->second = std::max(it->second, v); + } + } + } + for (const auto& [key, value] : next_todo_map_total) { + todos.emplace_back(key, value); + } + } +} + bool Builder::AddTargets(const std::vector<Node*> &nodes, string* err) { std::vector<Node*> validation_nodes; if (!scan_.RecomputeNodesDirty(nodes, &validation_nodes, err)) return false; + if (config_.weight_list_path) { + RefreshPriority(nodes); + } + for (Node* node : nodes) { std::string plan_err; if (!plan_.AddTarget(node, &plan_err)) { diff --git a/src/build.h b/src/build.h index b335a7d..1283ee8 100644 --- a/src/build.h +++ b/src/build.h @@ -18,6 +18,7 @@ #include <cstdio> #include <map> #include <memory> +#include <optional> #include <queue> #include <string> #include <vector> @@ -172,7 +173,8 @@ struct BuildConfig { output_directory_should_err(false), missing_output_file_should_err(false), old_output_should_err(false), - pre_remove_output_files(false) {} + pre_remove_output_files(false), + weight_list_path(std::nullopt) {} enum Verbosity { NORMAL, @@ -221,6 +223,16 @@ struct BuildConfig { /// Whether to remove outputs before executing rule commands bool pre_remove_output_files; + + /// A file path which includes a weight list for modules. + /// A priority list is a csv file format and it has two fields, output global path and weight. + /// Weight is proportional to execution time of an edge for a node. + /// And it is used to set a priority of edges by a critical path based on weight. + /// For example, + /// out/lib/foo.so,2 + /// out/bin/bar,5 + /// Note that the default weight is 1 for a module which isn't included in the list. + std::optional<std::string> weight_list_path; }; /// Builder wraps the build process: starting commands, updating status. @@ -277,6 +289,8 @@ struct Builder { const string& deps_prefix, vector<Node*>* deps_nodes, string* err); + void RefreshPriority(const std::vector<Node*>& nodes); + /// Map of running edge to time the edge started running. typedef map<Edge*, int> RunningEdgeMap; RunningEdgeMap running_edges_; diff --git a/src/graph.h b/src/graph.h index 001b68d..85e9326 100644 --- a/src/graph.h +++ b/src/graph.h @@ -464,6 +464,7 @@ public: VisitMark mark_ = VisitNone; bool precomputed_dirtiness_ = false; size_t id_ = 0; + int64_t priority_ = 0; bool outputs_ready_ = false; bool deps_loaded_ = false; bool deps_missing_ = false; @@ -474,6 +475,11 @@ public: const Rule& rule() const { return *rule_; } Pool* pool() const { return pool_; } int weight() const { return 1; } + // Priority is a value used to determine which modules should be built earlier than others. + // The default value is 1 and can be updated by a priority list file. + // After that, it is also updated from dependents. + // The final priority would be the sum of the critical path between this edge and the target edge. + int64_t priority() const { return priority_; } bool outputs_ready() const { return outputs_ready_; } // There are three types of inputs. @@ -521,7 +527,13 @@ public: struct EdgeCmp { bool operator()(const Edge* a, const Edge* b) const { - return a->id_ < b->id_; + if (a->priority() == b->priority()) { + // Order by id ascending to preserve the original behavior if they have + // the same priority. + return a->id_ < b->id_; + } + // Order by priority descending to run prioritized edges earlier. + return a->priority() > b->priority(); } }; diff --git a/src/ninja.cc b/src/ninja.cc index 00372eb..19fc605 100644 --- a/src/ninja.cc +++ b/src/ninja.cc @@ -1307,7 +1307,8 @@ bool OptionEnable(const string& name, Options* options, BuildConfig* config) { " usessymlinkoutputs={yes,no} whether the generate uses 'symlink_outputs' so \n" " that these warnings work:\n" " undeclaredsymlinkoutputs\n" -" preremoveoutputs={yes,no} whether to remove outputs before running rule\n"); +" preremoveoutputs={yes,no} whether to remove outputs before running rule\n" +" usesweightlist={<file path>,no} whether to prioritize some rules based on weight list from file\n"); return false; } else if (name == "usesphonyoutputs=yes") { config->uses_phony_outputs = true; @@ -1327,6 +1328,12 @@ bool OptionEnable(const string& name, Options* options, BuildConfig* config) { } else if (name == "preremoveoutputs=no") { config->pre_remove_output_files = false; return true; + } else if (name == "usesweightlist=no") { + config->weight_list_path = std::nullopt; + return true; + } else if (auto n = name.find("usesweightlist=") != std::string::npos) { + config->weight_list_path = name.substr(n + strlen("usesweightlist=" ) - 1); + return true; } else { const char* suggestion = SpellcheckString(name.c_str(), diff --git a/src/status.cc b/src/status.cc index 4f8a5eb..1049312 100644 --- a/src/status.cc +++ b/src/status.cc @@ -345,7 +345,8 @@ void StatusSerializer::BuildEdgeStarted(Edge* edge, int64_t start_time_millis) { edge_started->add_outputs((*it)->globalPath().h.data()); } - edge_started->set_desc(edge->GetBinding("description")); + const auto& proirity_suffix = config_.weight_list_path ? (" (priority: " + std::to_string(edge->priority()) + ")") : ""; + edge_started->set_desc(edge->GetBinding("description") + proirity_suffix); edge_started->set_command(edge->GetBinding("command")); |