Change priority_list_ into a std::priority_queue of ready edges

2 files changed, 92 insertions, 47 deletions

diff --git a/src/build.cc b/src/build.cc
index 5b6ad2f..76df857 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -75,6 +75,16 @@ bool DryRunCommandRunner::WaitForCommand(Result* result) {
 
 }  // namespace
 
+
+bool EdgeQueue::EdgePriorityCompare::operator()(const Edge* e1, const Edge* e2) const {
+  const uint64_t ct1 = e1->critical_time();
+  const uint64_t ct2 = e2->critical_time();
+  if (ct1 != ct2) {
+    return ct1 < ct2;
+  }
+  return e1->id_ < e2->id_;
+}
+
 Plan::Plan(Builder* builder)
   : builder_(builder)
   , command_edges_(0)
@@ -152,21 +162,7 @@ void Plan::EdgeWanted(const Edge* edge) {
 Edge* Plan::FindWork() {
   if (ready_.empty())
     return NULL;
-  std::set<Edge*>::iterator i = ready_.end();
-  for (std::list<Edge*>::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;
+  return ready_.pop();
 }
 
 void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
@@ -184,10 +180,12 @@ void Plan::ScheduleWork(map<Edge*, Want>::iterator want_e) {
   Pool* pool = edge->pool();
   if (pool->ShouldDelayEdge()) {
     pool->DelayEdge(edge);
-    pool->RetrieveReadyEdges(&ready_);
+    EdgeSet new_edges;
+    pool->RetrieveReadyEdges(&new_edges);
+    ready_.push(new_edges.begin(), new_edges.end());
   } else {
     pool->EdgeScheduled(*edge);
-    ready_.insert(edge);
+    ready_.push(edge);
   }
 }
 
@@ -199,7 +197,9 @@ 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);
-  edge->pool()->RetrieveReadyEdges(&ready_);
+  EdgeSet new_edges;
+  edge->pool()->RetrieveReadyEdges(&new_edges);
+  ready_.push(new_edges.begin(), new_edges.end());
 
   // The rest of this function only applies to successful commands.
   if (result != kEdgeSucceeded)
@@ -437,29 +437,32 @@ void Plan::UnmarkDependents(const Node* node, set<Node*>* dependents) {
 }
 
 namespace {
-bool EdgeCom(const Edge* lhs, const Edge* rhs) {
-  // Note: > to sort in decreasing order.
-  return lhs->critical_time() > rhs->critical_time();
-}
+
+struct SeenNodeBefore {
+  std::set<const Node*> *seen;
+
+  bool operator() (const Node* node) {
+    // Return true if the node has been seen before
+    return !seen->insert(node).second;
+  }
+};
+
 }  // namespace
 
-void Plan::ComputePriorityList(BuildLog* build_log) {
+void Plan::ComputeCriticalTime(BuildLog* build_log) {
 
   //testcase have no build_log
   if (!build_log)
     return;
 
   METRIC_RECORD("ComputePriorityList");
-  std::set<const Node*> dedup;
-  std::vector<const Node*> deduped;
-  for (std::vector<const Node*>::iterator it = targets_.begin(); it != targets_.end();
-       ++it) {
-    std::pair<std::set<const Node*>::iterator, bool> insert_result = dedup.insert(*it);
-    if (!insert_result.second)
-      continue;
-    deduped.push_back(*it);
+  // Remove duplicate targets
+  {
+    std::set<const Node*> seen;
+    targets_.erase(
+        std::remove_if(targets_.begin(), targets_.end(), SeenNodeBefore{&seen}),
+        targets_.end());
   }
-  targets_.swap(deduped);
 
 
   std::vector<Edge*> edges;
@@ -473,9 +476,8 @@ void Plan::ComputePriorityList(BuildLog* build_log) {
     std::set<Node*> 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) {
+      if (ins.insert(n).second) {
         num_out_edges[n]++;
-        ins.insert(n);
       }
     }
   }
@@ -509,7 +511,7 @@ void Plan::ComputePriorityList(BuildLog* build_log) {
     edge->run_time_ms_ = duration;
   }
 
-  // 1. Use backflow algorithm to compute critical times for all nodes, starting
+  // 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
@@ -530,9 +532,8 @@ void Plan::ComputePriorityList(BuildLog* build_log) {
       in->set_critical_time(
           std::max(std::max<uint64_t>(in->run_time_ms_, priority_weight),
               in->critical_time()));
-      if (done.count(in) == 0) {
+      if (done.insert(in).second) {
         edgesQ.push(in);
-        done.insert(in);
       }
     }
   }
@@ -566,17 +567,12 @@ void Plan::ComputePriorityList(BuildLog* build_log) {
          it != end; ++it) {
       num_out_edges[*it]--;
       if (Edge* in = (*it)->in_edge()) {
-        if (done.count(in) == 0) {
+        if (done.insert(in).second) {
           edgesQ.push(in);
-          done.insert(in);
         }
       }
     }
   }
-
-  // 2. Build priority list in decreasing order of critical times.
-  std::sort(edges.begin(), edges.end(), EdgeCom);
-  priority_list_.assign(edges.begin(), edges.end());
 }
 
 void Plan::Dump() const {
diff --git a/src/build.h b/src/build.h
index 5ee5650..ec6deea 100644
--- a/src/build.h
+++ b/src/build.h
@@ -16,7 +16,7 @@
 #define NINJA_BUILD_H_
 
 #include <cstdio>
-#include <list>
+#include <queue>
 #include <map>
 #include <memory>
 #include <queue>
@@ -36,6 +36,56 @@ struct Node;
 struct State;
 struct Status;
 
+
+// Set of ready edges, sorted by priority
+class EdgeQueue {
+  struct EdgePriorityCompare {
+    bool operator()(const Edge* e1, const Edge* e2) const;
+  };
+
+  std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityCompare> queue_;
+  // Set to ensure no duplicate entries in ready_
+  EdgeSet set_;
+
+public:
+
+  void push(Edge* edge) {
+    if (set_.insert(edge).second) {
+      queue_.push(edge);
+    }
+  }
+
+  template <typename It>
+  void push(It first, It last) {
+    for (; first != last; ++first) {
+      push(*first);
+    }
+  }
+
+  Edge* pop() {
+    Edge* ret = queue_.top();
+    queue_.pop();
+    set_.erase(ret);
+    return ret;
+  }
+
+  void clear() {
+    set_.clear();
+    while (!queue_.empty()) {
+      queue_.pop();
+    }
+  }
+
+  size_t size() const {
+    return queue_.size();
+  }
+
+  bool empty() const {
+    return queue_.empty();
+  }
+};
+
+
 /// Plan stores the state of a build plan: what we intend to build,
 /// which steps we're ready to execute.
 struct Plan {
@@ -76,7 +126,7 @@ struct Plan {
 
   /// Reset state.  Clears want and ready sets.
   void Reset();
-  void ComputePriorityList(BuildLog* build_log);
+  void ComputeCriticalTime(BuildLog* build_log);
 
   /// Update the build plan to account for modifications made to the graph
   /// by information loaded from a dyndep file.
@@ -121,12 +171,11 @@ private:
   /// we want for the edge.
   std::map<Edge*, Want> want_;
 
-  EdgeSet ready_;
+  EdgeQueue ready_;
 
   Builder* builder_;
   /// user provided targets in build order, earlier one have higher priority
   std::vector<const Node*> targets_;
-  std::list<Edge*> priority_list_;
 
   /// Total number of edges that have commands (not phony).
   int command_edges_;