cc: Improve worker pool performance by using std:make_heap instead of std:priority_queue.

cc/resources/worker_pool.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/resources/worker_pool.h"
 
 #include <algorithm>
-#include <queue>
 
 #include "base/bind.h"
 #include "base/containers/hash_tables.h"
 #include "base/debug/trace_event.h"
 #include "base/strings/stringprintf.h"
 #include "base/synchronization/condition_variable.h"
 #include "base/threading/simple_thread.h"
 #include "base/threading/thread_restrictions.h"
 #include "cc/base/scoped_ptr_deque.h"
 
@@ skipping 72 matching lines @@
   // tasks are moved to |completed_tasks_| without being run. The result
   // is that once scheduled, a task is guaranteed to end up in the
   // |completed_tasks_| queue even if they later get canceled by another
   // call to SetTaskGraph().
   void SetTaskGraph(TaskGraph* graph);
 
   // Collect all completed tasks in |completed_tasks|.
   void CollectCompletedTasks(TaskVector* completed_tasks);
 
  private:
-  class PriorityComparator {
-   public:
-    bool operator()(const internal::GraphNode* a,
-                    const internal::GraphNode* b) {
-      // In this system, numerically lower priority is run first.
-      if (a->priority() != b->priority())
-        return a->priority() > b->priority();
+  static bool CompareTaskPriority(const internal::GraphNode* a,
+                                  const internal::GraphNode* b) {
+    // In this system, numerically lower priority is run first.
+    if (a->priority() != b->priority())
+      return a->priority() > b->priority();
 
-      // Run task with most dependents first when priority is the same.
-      return a->dependents().size() < b->dependents().size();
-    }
-  };
+    // Run task with most dependents first when priority is the same.
+    return a->dependents().size() < b->dependents().size();
+  }
 
   // Overridden from base::DelegateSimpleThread:
   virtual void Run() OVERRIDE;
 
   // This lock protects all members of this class except
   // |worker_pool_on_origin_thread_|. Do not read or modify anything
   // without holding this lock. Do not block while holding this lock.
   mutable base::Lock lock_;
 
   // Condition variable that is waited on by worker threads until new
   // tasks are ready to run or shutdown starts.
   base::ConditionVariable has_ready_to_run_tasks_cv_;
 
   // Provides each running thread loop with a unique index. First thread
   // loop index is 0.
   unsigned next_thread_index_;
 
   // Set during shutdown. Tells workers to exit when no more tasks
   // are pending.
   bool shutdown_;
 
   // This set contains all pending tasks.
   GraphNodeMap pending_tasks_;
 
-  // Ordered set of tasks that are ready to run.
-  typedef std::priority_queue<internal::GraphNode*,
-                              std::vector<internal::GraphNode*>,
-                              PriorityComparator> TaskQueue;
-  TaskQueue ready_to_run_tasks_;
+  // Priority queue containing tasks that are ready to run.
+  internal::GraphNode::Vector ready_to_run_tasks_;
 
   // This set contains all currently running tasks.
   GraphNodeMap running_tasks_;
 
   // Completed tasks not yet collected by origin thread.
   TaskVector completed_tasks_;
 
   ScopedPtrDeque<base::DelegateSimpleThread> workers_;
 
   DISALLOW_COPY_AND_ASSIGN(Inner);
@@ skipping 54 matching lines @@
     worker->Join();
   }
 }
 
 void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) {
   // It is OK to call SetTaskGraph() after shutdown if |graph| is empty.
   DCHECK(graph->empty() || !shutdown_);
 
   GraphNodeMap new_pending_tasks;
   GraphNodeMap new_running_tasks;
-  TaskQueue new_ready_to_run_tasks;
 
   new_pending_tasks.swap(*graph);
 
   {
     base::AutoLock lock(lock_);
 
     // First remove all completed tasks from |new_pending_tasks| and
     // adjust number of dependencies.
     for (TaskVector::iterator it = completed_tasks_.begin();
          it != completed_tasks_.end(); ++it) {
@@ skipping 16 matching lines @@
          it != running_tasks_.end(); ++it) {
       internal::WorkerPoolTask* task = it->first;
       // Transfer scheduled task value from |new_pending_tasks| to
       // |new_running_tasks| if currently running. Value must be set to
       // NULL if |new_pending_tasks| doesn't contain task. This does
       // the right in both cases.
       new_running_tasks.set(task, new_pending_tasks.take_and_erase(task));
     }
 
     // Build new "ready to run" tasks queue.
-    // TODO(reveman): Create this queue when building the task graph instead.
+    ready_to_run_tasks_.clear();
     for (GraphNodeMap::iterator it = new_pending_tasks.begin();
          it != new_pending_tasks.end(); ++it) {
       internal::WorkerPoolTask* task = it->first;
       DCHECK(task);
       internal::GraphNode* node = it->second;
 
       // Completed tasks should not exist in |new_pending_tasks|.
       DCHECK(!task->HasFinishedRunning());
 
       // Call DidSchedule() to indicate that this task has been scheduled.
       // Note: This is only for debugging purposes.
       task->DidSchedule();
 
       if (!node->num_dependencies())
-        new_ready_to_run_tasks.push(node);
+        ready_to_run_tasks_.push_back(node);
 
       // Erase the task from old pending tasks.
       pending_tasks_.erase(task);
     }
 
+    // Rearrange the elements in |ready_to_run_tasks_| in such a way that
+    // they form a heap.
+    std::make_heap(ready_to_run_tasks_.begin(),
+                   ready_to_run_tasks_.end(),
+                   CompareTaskPriority);
+
     completed_tasks_.reserve(completed_tasks_.size() + pending_tasks_.size());
 
     // The items left in |pending_tasks_| need to be canceled.
     for (GraphNodeMap::const_iterator it = pending_tasks_.begin();
          it != pending_tasks_.end();
          ++it) {
       completed_tasks_.push_back(it->first);
     }
 
     // Swap task sets.
     // Note: old tasks are intentionally destroyed after releasing |lock_|.
     pending_tasks_.swap(new_pending_tasks);
     running_tasks_.swap(new_running_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.
     DCHECK(!ready_to_run_tasks_.empty() ||
            (pending_tasks_.empty() || !running_tasks_.empty()));
 
     // If there is more work available, wake up worker thread.
     if (!ready_to_run_tasks_.empty())
       has_ready_to_run_tasks_cv_.Signal();
   }
@@ skipping 17 matching lines @@
       // Exit when shutdown is set and no more tasks are pending.
       if (shutdown_ && pending_tasks_.empty())
         break;
 
       // Wait for more tasks.
       has_ready_to_run_tasks_cv_.Wait();
       continue;
     }
 
     // Take top priority task from |ready_to_run_tasks_|.
+    std::pop_heap(ready_to_run_tasks_.begin(),
+                  ready_to_run_tasks_.end(),
+                  CompareTaskPriority);
     scoped_refptr<internal::WorkerPoolTask> task(
-        ready_to_run_tasks_.top()->task());
-    ready_to_run_tasks_.pop();
+        ready_to_run_tasks_.back()->task());
+    ready_to_run_tasks_.pop_back();
 
     // Move task from |pending_tasks_| to |running_tasks_|.
     DCHECK(pending_tasks_.contains(task.get()));
     DCHECK(!running_tasks_.contains(task.get()));
     running_tasks_.set(task.get(), pending_tasks_.take_and_erase(task.get()));
 
     // There may be more work available, so wake up another worker thread.
     has_ready_to_run_tasks_cv_.Signal();
 
     // Call WillRun() before releasing |lock_| and running task.
@@ skipping 14 matching lines @@
         task.get());
     if (node) {
       for (internal::GraphNode::Vector::const_iterator it =
                node->dependents().begin();
            it != node->dependents().end(); ++it) {
         internal::GraphNode* dependent_node = *it;
 
         dependent_node->remove_dependency();
         // Task is ready if it has no dependencies. Add it to
         // |ready_to_run_tasks_|.
-        if (!dependent_node->num_dependencies())
-          ready_to_run_tasks_.push(dependent_node);
+        if (!dependent_node->num_dependencies()) {
+          ready_to_run_tasks_.push_back(dependent_node);
+          std::push_heap(ready_to_run_tasks_.begin(),
+                         ready_to_run_tasks_.end(),
+                         CompareTaskPriority);
+        }
       }
     }
 
     // Finally add task to |completed_tasks_|.
     completed_tasks_.push_back(task);
   }
 
   // We noticed we should exit. Wake up the next worker so it knows it should
   // exit as well (because the Shutdown() code only signals once).
   has_ready_to_run_tasks_cv_.Signal();
@@ skipping 50 matching lines @@
 void WorkerPool::SetTaskGraph(TaskGraph* graph) {
   TRACE_EVENT1("cc", "WorkerPool::SetTaskGraph",
                "num_tasks", graph->size());
 
   DCHECK(!in_dispatch_completion_callbacks_);
 
   inner_->SetTaskGraph(graph);
 }
 
 }  // namespace cc