cc: Use priority_queue for worker_pool's ready to run tasks

This changes std::map to be a priority queue with an underlying vector.

BUG=253968

Review URL: https://chromiumcodereview.appspot.com/17605004

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@208549 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 21 insertions, 15 deletions

diff --git a/cc/resources/worker_pool.cc b/cc/resources/worker_pool.cc
index 9b7e824..a1d64a3 100644
--- a/cc/resources/worker_pool.cc
+++ b/cc/resources/worker_pool.cc
@@ -9,7 +9,8 @@
 #include <sys/resource.h>
 #endif
 
-#include <map>
+#include <algorithm>
+#include <queue>
 
 #include "base/bind.h"
 #include "base/containers/hash_tables.h"
@@ -88,6 +89,15 @@ class WorkerPool::Inner : public base::DelegateSimpleThread::Delegate {
   void CollectCompletedTasks(TaskDeque* completed_tasks);
 
  private:
+  class PriorityComparator {
+   public:
+    bool operator()(const GraphNode* a,
+                    const GraphNode* b) {
+      // In this system, numerically lower priority is run first.
+      return a->priority() > b->priority();
+    }
+  };
+
   // Overridden from base::DelegateSimpleThread:
   virtual void Run() OVERRIDE;
 
@@ -112,9 +122,10 @@ class WorkerPool::Inner : public base::DelegateSimpleThread::Delegate {
   GraphNodeMap pending_tasks_;
 
   // Ordered set of tasks that are ready to run.
-  // TODO(reveman): priority_queue might be more efficient.
-  typedef std::map<unsigned, internal::WorkerPoolTask*> TaskMap;
-  TaskMap ready_to_run_tasks_;
+  typedef std::priority_queue<GraphNode*,
+                              std::vector<GraphNode*>,
+                              PriorityComparator> TaskQueue;
+  TaskQueue ready_to_run_tasks_;
 
   // This set contains all currently running tasks.
   GraphNodeMap running_tasks_;
@@ -186,7 +197,7 @@ void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) {
 
   GraphNodeMap new_pending_tasks;
   GraphNodeMap new_running_tasks;
-  TaskMap new_ready_to_run_tasks;
+  TaskQueue new_ready_to_run_tasks;
 
   new_pending_tasks.swap(*graph);
 
@@ -245,16 +256,15 @@ void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) {
       // Note: This is only for debugging purposes.
       task->DidSchedule();
 
-      DCHECK_EQ(0u, new_ready_to_run_tasks.count(node->priority()));
       if (!node->num_dependencies())
-        new_ready_to_run_tasks[node->priority()] = task;
+        new_ready_to_run_tasks.push(node);
     }
 
     // Swap task sets.
     // Note: old tasks are intentionally destroyed after releasing |lock_|.
     pending_tasks_.swap(new_pending_tasks);
     running_tasks_.swap(new_running_tasks);
-    ready_to_run_tasks_.swap(new_ready_to_run_tasks);
+    std::swap(ready_to_run_tasks_, new_ready_to_run_tasks);
 
     // If |ready_to_run_tasks_| is empty, it means we either have
     // running tasks, or we have no pending tasks.
@@ -299,8 +309,8 @@ void WorkerPool::Inner::Run() {
 
     // Take top priority task from |ready_to_run_tasks_|.
     scoped_refptr<internal::WorkerPoolTask> task(
-        ready_to_run_tasks_.begin()->second);
-    ready_to_run_tasks_.erase(ready_to_run_tasks_.begin());
+        ready_to_run_tasks_.top()->task());
+    ready_to_run_tasks_.pop();
 
     // Move task from |pending_tasks_| to |running_tasks_|.
     DCHECK(pending_tasks_.contains(task.get()));
@@ -336,11 +346,7 @@ void WorkerPool::Inner::Run() {
           continue;
 
         // Task is ready. Add it to |ready_to_run_tasks_|.
-        DCHECK(!ready_to_run_tasks_.count(dependent_node->priority()) ||
-               ready_to_run_tasks_[dependent_node->priority()] ==
-               dependent_node->task());
-        ready_to_run_tasks_[dependent_node->priority()] =
-            dependent_node->task();
+        ready_to_run_tasks_.push(dependent_node);
       }
     }