cc: Move task graph construction to RasterWorkerPool classes.

This removes the need to construct a temporary graph by
RasterWorkerPool classes. It reduces the number of tasks
created and eliminates the need for a dependencies vector
as part of the internal::WorkerPoolTask class.

This is also a prerequisite to implementing a "ready to activate"
signal as that requires as task graph structure that is not a tree.

BUG=247677

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

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

14 files changed, 550 insertions, 383 deletions

diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index 0a57347..de989d5 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp
@@ -232,6 +232,7 @@
         'cc_test_support',
       ],
       'sources': [
+        'resources/raster_worker_pool_perftest.cc',
         'resources/worker_pool_perftest.cc',
         'test/cc_test_suite.cc',
         'test/run_all_unittests.cc',
diff --git a/cc/resources/image_raster_worker_pool.cc b/cc/resources/image_raster_worker_pool.cc
index c34ed2e..c2fe395 100644
--- a/cc/resources/image_raster_worker_pool.cc
+++ b/cc/resources/image_raster_worker_pool.cc
@@ -17,12 +17,10 @@ class ImageWorkerPoolTaskImpl : public internal::WorkerPoolTask {
   typedef base::Callback<void(bool was_canceled)> Reply;
 
   ImageWorkerPoolTaskImpl(internal::RasterWorkerPoolTask* task,
-                          TaskVector* dependencies,
                           uint8_t* buffer,
                           int stride,
                           const Reply& reply)
-      : internal::WorkerPoolTask(dependencies),
-        task_(task),
+      : task_(task),
         buffer_(buffer),
         stride_(stride),
         reply_(reply) {
@@ -68,27 +66,20 @@ ImageRasterWorkerPool::~ImageRasterWorkerPool() {
   DCHECK_EQ(0u, image_tasks_.size());
 }
 
-void ImageRasterWorkerPool::Shutdown() {
-  RasterWorkerPool::Shutdown();
-  ScheduleRasterTasks(RootTask());
-}
-
 void ImageRasterWorkerPool::ScheduleTasks(RasterTask::Queue* queue) {
   TRACE_EVENT0("cc", "ImageRasterWorkerPool::ScheduleTasks");
 
-  internal::WorkerPoolTask::TaskVector tasks;
-
   RasterWorkerPool::SetRasterTasks(queue);
 
-  for (RasterTask::Queue::TaskVector::const_iterator it =
-           raster_tasks().begin();
+  RasterTaskGraph graph;
+  for (RasterTaskVector::const_iterator it = raster_tasks().begin();
        it != raster_tasks().end(); ++it) {
     internal::RasterWorkerPoolTask* task = it->get();
 
     TaskMap::iterator image_it = image_tasks_.find(task);
     if (image_it != image_tasks_.end()) {
       internal::WorkerPoolTask* image_task = image_it->second.get();
-      tasks.push_back(image_task);
+      graph.InsertRasterTask(image_task, task->dependencies());
       continue;
     }
 
@@ -99,29 +90,19 @@ void ImageRasterWorkerPool::ScheduleTasks(RasterTask::Queue* queue) {
     uint8* buffer = resource_provider()->MapImage(task->resource()->id());
     int stride = resource_provider()->GetImageStride(task->resource()->id());
 
-    // TODO(reveman): Avoid having to make a copy of dependencies.
-    internal::WorkerPoolTask::TaskVector dependencies = task->dependencies();
     scoped_refptr<internal::WorkerPoolTask> new_image_task(
         new ImageWorkerPoolTaskImpl(
             task,
-            &dependencies,
             buffer,
             stride,
             base::Bind(&ImageRasterWorkerPool::OnRasterTaskCompleted,
                        base::Unretained(this),
                        make_scoped_refptr(task))));
-
     image_tasks_[task] = new_image_task;
-    tasks.push_back(new_image_task);
-  }
-
-  if (tasks.empty()) {
-    ScheduleRasterTasks(RootTask());
-    return;
+    graph.InsertRasterTask(new_image_task.get(), task->dependencies());
   }
 
-  RootTask root(&tasks);
-  ScheduleRasterTasks(root);
+  SetRasterTaskGraph(&graph);
 }
 
 void ImageRasterWorkerPool::OnRasterTaskCompleted(
diff --git a/cc/resources/image_raster_worker_pool.h b/cc/resources/image_raster_worker_pool.h
index 19b8f93..453b3a3 100644
--- a/cc/resources/image_raster_worker_pool.h
+++ b/cc/resources/image_raster_worker_pool.h
@@ -20,7 +20,6 @@ class CC_EXPORT ImageRasterWorkerPool : public RasterWorkerPool {
   }
 
   // Overridden from RasterWorkerPool:
-  virtual void Shutdown() OVERRIDE;
   virtual void ScheduleTasks(RasterTask::Queue* queue) OVERRIDE;
 
  private:
diff --git a/cc/resources/pixel_buffer_raster_worker_pool.cc b/cc/resources/pixel_buffer_raster_worker_pool.cc
index 5b43c0c..2f3e4d2 100644
--- a/cc/resources/pixel_buffer_raster_worker_pool.cc
+++ b/cc/resources/pixel_buffer_raster_worker_pool.cc
@@ -17,11 +17,9 @@ class PixelBufferWorkerPoolTaskImpl : public internal::WorkerPoolTask {
   typedef base::Callback<void(bool was_canceled, bool needs_upload)> Reply;
 
   PixelBufferWorkerPoolTaskImpl(internal::RasterWorkerPoolTask* task,
-                                TaskVector* dependencies,
                                 uint8_t* buffer,
                                 const Reply& reply)
-      : internal::WorkerPoolTask(dependencies),
-        task_(task),
+      : task_(task),
         buffer_(buffer),
         reply_(reply),
         needs_upload_(false) {
@@ -90,9 +88,7 @@ PixelBufferRasterWorkerPool::PixelBufferRasterWorkerPool(
                           shutdown_(false),
                           bytes_pending_upload_(0),
                           has_performed_uploads_since_last_flush_(false),
-                          check_for_completed_raster_tasks_pending_(false),
-                          weak_ptr_factory_(this),
-                          schedule_more_tasks_count_(0) {
+                          check_for_completed_raster_tasks_pending_(false) {
 }
 
 PixelBufferRasterWorkerPool::~PixelBufferRasterWorkerPool() {
@@ -118,8 +114,6 @@ void PixelBufferRasterWorkerPool::Shutdown() {
       completed_tasks_.push_back(task);
     }
   }
-  // Cancel any pending OnRasterFinished callback.
-  weak_ptr_factory_.InvalidateWeakPtrs();
 }
 
 void PixelBufferRasterWorkerPool::ScheduleTasks(RasterTask::Queue* queue) {
@@ -129,8 +123,7 @@ void PixelBufferRasterWorkerPool::ScheduleTasks(RasterTask::Queue* queue) {
 
   // Build new pixel buffer task set.
   TaskMap new_pixel_buffer_tasks;
-  for (RasterTask::Queue::TaskVector::const_iterator it =
-           raster_tasks().begin();
+  for (RasterTaskVector::const_iterator it = raster_tasks().begin();
        it != raster_tasks().end(); ++it) {
     internal::RasterWorkerPoolTask* task = it->get();
     DCHECK(new_pixel_buffer_tasks.find(task) == new_pixel_buffer_tasks.end());
@@ -196,6 +189,13 @@ void PixelBufferRasterWorkerPool::CheckForCompletedTasks() {
   }
 }
 
+void PixelBufferRasterWorkerPool::OnRasterTasksFinished() {
+  // Call CheckForCompletedTasks() when we've finished running all raster
+  // tasks needed since last time ScheduleMoreTasks() was called. This
+  // reduces latency when processing only a small number of raster tasks.
+  CheckForCompletedRasterTasks();
+}
+
 void PixelBufferRasterWorkerPool::FlushUploads() {
   if (!has_performed_uploads_since_last_flush_)
     return;
@@ -306,10 +306,8 @@ void PixelBufferRasterWorkerPool::ScheduleMoreTasks() {
   size_t bytes_pending_upload = bytes_pending_upload_;
   size_t bytes_pending_raster = 0;
 
-  internal::WorkerPoolTask::TaskVector tasks;
-
-  for (RasterTask::Queue::TaskVector::const_iterator it =
-           raster_tasks().begin();
+  RasterTaskGraph graph;
+  for (RasterTaskVector::const_iterator it = raster_tasks().begin();
        it != raster_tasks().end(); ++it) {
     internal::RasterWorkerPoolTask* task = it->get();
 
@@ -354,8 +352,7 @@ void PixelBufferRasterWorkerPool::ScheduleMoreTasks() {
 
     // Use existing pixel buffer task if available.
     if (pixel_buffer_task) {
-      DCHECK(!pixel_buffer_task->HasCompleted());
-      tasks.push_back(pixel_buffer_task);
+      graph.InsertRasterTask(pixel_buffer_task, task->dependencies());
       continue;
     }
 
@@ -368,44 +365,24 @@ void PixelBufferRasterWorkerPool::ScheduleMoreTasks() {
     uint8* buffer = resource_provider()->MapPixelBuffer(
         task->resource()->id());
 
-    // TODO(reveman): Avoid having to make a copy of dependencies.
-    internal::WorkerPoolTask::TaskVector dependencies = task->dependencies();
     scoped_refptr<internal::WorkerPoolTask> new_pixel_buffer_task(
         new PixelBufferWorkerPoolTaskImpl(
             task,
-            &dependencies,
             buffer,
             base::Bind(&PixelBufferRasterWorkerPool::OnRasterTaskCompleted,
                        base::Unretained(this),
                        make_scoped_refptr(task))));
-
     pixel_buffer_tasks_[task] = new_pixel_buffer_task;
-    tasks.push_back(new_pixel_buffer_task);
-  }
-
-  ++schedule_more_tasks_count_;
-
-  // We need to make sure not to schedule a check for completed raster
-  // tasks when |tasks| is empty as that would cause us to never stop
-  // checking.
-  if (tasks.empty()) {
-    ScheduleRasterTasks(RootTask());
-    return;
+    graph.InsertRasterTask(new_pixel_buffer_task.get(), task->dependencies());
   }
 
-  RootTask root(
-      base::Bind(&PixelBufferRasterWorkerPool::RunRasterFinishedTask,
-                 base::MessageLoopProxy::current(),
-                 base::Bind(&PixelBufferRasterWorkerPool::OnRasterFinished,
-                            weak_ptr_factory_.GetWeakPtr(),
-                            schedule_more_tasks_count_)),
-                &tasks);
-  ScheduleRasterTasks(root);
+  SetRasterTaskGraph(&graph);
 
   // At least one task that could need an upload is now pending, schedule
   // a check for completed raster tasks to ensure this upload is dispatched
   // without too much latency.
-  ScheduleCheckForCompletedRasterTasks();
+  if (bytes_pending_raster)
+    ScheduleCheckForCompletedRasterTasks();
 }
 
 void PixelBufferRasterWorkerPool::OnRasterTaskCompleted(
@@ -438,25 +415,4 @@ void PixelBufferRasterWorkerPool::OnRasterTaskCompleted(
   tasks_with_pending_upload_.push_back(task);
 }
 
-void PixelBufferRasterWorkerPool::OnRasterFinished(
-    int64 schedule_more_tasks_count) {
-  TRACE_EVENT1("cc",
-               "PixelBufferRasterWorkerPool::OnRasterFinishedTasks",
-               "schedule_more_tasks_count", schedule_more_tasks_count);
-  DCHECK_GE(schedule_more_tasks_count_, schedule_more_tasks_count);
-  // Call CheckForCompletedTasks() when we've finished running all raster
-  // tasks needed since last time ScheduleMoreTasks() was called. This
-  // reduces latency when processing only a small number of raster tasks.
-  if (schedule_more_tasks_count_ == schedule_more_tasks_count)
-    CheckForCompletedRasterTasks();
-}
-
-// static
-void PixelBufferRasterWorkerPool::RunRasterFinishedTask(
-    scoped_refptr<base::MessageLoopProxy> origin_loop,
-    const base::Closure& on_raster_finished_callback) {
-  TRACE_EVENT0("cc", "RasterWorkerPool::RunRasterFinishedTask");
-  origin_loop->PostTask(FROM_HERE, on_raster_finished_callback);
-}
-
 }  // namespace cc
diff --git a/cc/resources/pixel_buffer_raster_worker_pool.h b/cc/resources/pixel_buffer_raster_worker_pool.h
index 2a89d4b..be609a8 100644
--- a/cc/resources/pixel_buffer_raster_worker_pool.h
+++ b/cc/resources/pixel_buffer_raster_worker_pool.h
@@ -33,6 +33,9 @@ class CC_EXPORT PixelBufferRasterWorkerPool : public RasterWorkerPool {
   PixelBufferRasterWorkerPool(ResourceProvider* resource_provider,
                               size_t num_threads);
 
+  // Overridden from RasterWorkerPool:
+  virtual void OnRasterTasksFinished() OVERRIDE;
+
   void FlushUploads();
   void CheckForCompletedUploads();
   void ScheduleCheckForCompletedRasterTasks();
@@ -43,11 +46,6 @@ class CC_EXPORT PixelBufferRasterWorkerPool : public RasterWorkerPool {
       bool was_canceled,
       bool needs_upload);
   void DidCompleteRasterTask(internal::RasterWorkerPoolTask* task);
-  void OnRasterFinished(int64 schedule_more_tasks_count);
-
-  static void RunRasterFinishedTask(
-      scoped_refptr<base::MessageLoopProxy> origin_loop,
-      const base::Closure& on_raster_finished_callback);
 
   bool shutdown_;
 
@@ -62,9 +60,6 @@ class CC_EXPORT PixelBufferRasterWorkerPool : public RasterWorkerPool {
   base::CancelableClosure check_for_completed_raster_tasks_callback_;
   bool check_for_completed_raster_tasks_pending_;
 
-  base::WeakPtrFactory<PixelBufferRasterWorkerPool> weak_ptr_factory_;
-  int64 schedule_more_tasks_count_;
-
   DISALLOW_COPY_AND_ASSIGN(PixelBufferRasterWorkerPool);
 };
 
diff --git a/cc/resources/raster_worker_pool.cc b/cc/resources/raster_worker_pool.cc
index a4b4a50..5f356e5 100644
--- a/cc/resources/raster_worker_pool.cc
+++ b/cc/resources/raster_worker_pool.cc
@@ -29,43 +29,6 @@ class DisableLCDTextFilter : public SkDrawFilter {
   }
 };
 
-void Noop() {}
-
-class RootWorkerPoolTaskImpl : public internal::WorkerPoolTask {
- public:
-  RootWorkerPoolTaskImpl(const base::Closure& callback,
-                         const base::Closure& reply)
-      : callback_(callback), reply_(reply) {}
-
-  explicit RootWorkerPoolTaskImpl(
-      internal::WorkerPoolTask::TaskVector* dependencies)
-      : internal::WorkerPoolTask(dependencies),
-        callback_(base::Bind(&Noop)),
-        reply_(base::Bind(&Noop)) {}
-
-  RootWorkerPoolTaskImpl(const base::Closure& callback,
-                         internal::WorkerPoolTask::TaskVector* dependencies)
-      : internal::WorkerPoolTask(dependencies),
-        callback_(callback),
-        reply_(base::Bind(&Noop)) {}
-
-  // Overridden from internal::WorkerPoolTask:
-  virtual void RunOnThread(unsigned thread_index) OVERRIDE {
-    callback_.Run();
-  }
-  virtual void DispatchCompletionCallback() OVERRIDE {
-    reply_.Run();
-  }
-
- private:
-  virtual ~RootWorkerPoolTaskImpl() {}
-
-  const base::Closure callback_;
-  const base::Closure reply_;
-
-  DISALLOW_COPY_AND_ASSIGN(RootWorkerPoolTaskImpl);
-};
-
 class RasterWorkerPoolTaskImpl : public internal::RasterWorkerPoolTask {
  public:
   RasterWorkerPoolTaskImpl(const Resource* resource,
@@ -77,7 +40,7 @@ class RasterWorkerPoolTaskImpl : public internal::RasterWorkerPoolTask {
                            const RasterTaskMetadata& metadata,
                            RenderingStatsInstrumentation* rendering_stats,
                            const RasterWorkerPool::RasterTask::Reply& reply,
-                           internal::WorkerPoolTask::TaskVector* dependencies)
+                           TaskVector* dependencies)
       : internal::RasterWorkerPoolTask(resource, dependencies),
         picture_pile_(picture_pile),
         content_rect_(content_rect),
@@ -237,6 +200,32 @@ class ImageDecodeWorkerPoolTaskImpl : public internal::WorkerPoolTask {
   DISALLOW_COPY_AND_ASSIGN(ImageDecodeWorkerPoolTaskImpl);
 };
 
+class RasterFinishedWorkerPoolTaskImpl : public internal::WorkerPoolTask {
+ public:
+  RasterFinishedWorkerPoolTaskImpl(
+      base::MessageLoopProxy* origin_loop,
+      const base::Closure& on_raster_finished_callback)
+      : origin_loop_(origin_loop),
+        on_raster_finished_callback_(on_raster_finished_callback) {
+  }
+
+  // Overridden from internal::WorkerPoolTask:
+  virtual void RunOnThread(unsigned thread_index) OVERRIDE {
+    origin_loop_->PostTask(FROM_HERE, on_raster_finished_callback_);
+  }
+  virtual void DispatchCompletionCallback() OVERRIDE {}
+
+ private:
+  virtual ~RasterFinishedWorkerPoolTaskImpl() {}
+
+  scoped_refptr<base::MessageLoopProxy> origin_loop_;
+  const base::Closure on_raster_finished_callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(RasterFinishedWorkerPoolTaskImpl);
+};
+
+void Noop() {}
+
 const char* kWorkerThreadNamePrefix = "CompositorRaster";
 
 }  // namespace
@@ -244,8 +233,7 @@ const char* kWorkerThreadNamePrefix = "CompositorRaster";
 namespace internal {
 
 RasterWorkerPoolTask::RasterWorkerPoolTask(
-    const Resource* resource,
-    WorkerPoolTask::TaskVector* dependencies)
+    const Resource* resource, TaskVector* dependencies)
     : did_run_(false),
       did_complete_(false),
       was_canceled_(false),
@@ -345,21 +333,54 @@ void RasterWorkerPool::RasterTask::Reset() {
 RasterWorkerPool::RasterTask::~RasterTask() {
 }
 
-RasterWorkerPool::RootTask::RootTask() {
+RasterWorkerPool::RasterTaskGraph::RasterTaskGraph()
+    : raster_finished_node_(new GraphNode),
+      next_priority_(1u) {
 }
 
-RasterWorkerPool::RootTask::RootTask(
-    internal::WorkerPoolTask::TaskVector* dependencies)
-    : internal_(new RootWorkerPoolTaskImpl(dependencies)) {
+RasterWorkerPool::RasterTaskGraph::~RasterTaskGraph() {
 }
 
-RasterWorkerPool::RootTask::RootTask(
-    const base::Closure& callback,
-    internal::WorkerPoolTask::TaskVector* dependencies)
-    : internal_(new RootWorkerPoolTaskImpl(callback, dependencies)) {
-}
+void RasterWorkerPool::RasterTaskGraph::InsertRasterTask(
+    internal::WorkerPoolTask* raster_task,
+    const TaskVector& decode_tasks) {
+  DCHECK(!raster_task->HasCompleted());
+  DCHECK(graph_.find(raster_task) == graph_.end());
+
+  scoped_ptr<GraphNode> raster_node(new GraphNode);
+  raster_node->set_task(raster_task);
+  raster_node->set_priority(next_priority_++);
+
+  // Insert image decode tasks.
+  for (TaskVector::const_iterator it = decode_tasks.begin();
+       it != decode_tasks.end(); ++it) {
+    internal::WorkerPoolTask* decode_task = it->get();
+
+    // Skip if already decoded.
+    if (decode_task->HasCompleted())
+      continue;
+
+    raster_node->add_dependency();
 
-RasterWorkerPool::RootTask::~RootTask() {
+    // Check if decode task already exists in graph.
+    GraphNodeMap::iterator decode_it = graph_.find(decode_task);
+    if (decode_it != graph_.end()) {
+      GraphNode* decode_node = decode_it->second;
+      decode_node->add_dependent(raster_node.get());
+      continue;
+    }
+
+    scoped_ptr<GraphNode> decode_node(new GraphNode);
+    decode_node->set_task(decode_task);
+    decode_node->set_priority(next_priority_++);
+    decode_node->add_dependent(raster_node.get());
+    graph_.set(decode_task, decode_node.Pass());
+  }
+
+  raster_finished_node_->add_dependency();
+  raster_node->add_dependent(raster_finished_node_.get());
+
+  graph_.set(raster_task, raster_node.Pass());
 }
 
 // static
@@ -373,7 +394,7 @@ RasterWorkerPool::RasterTask RasterWorkerPool::CreateRasterTask(
     const RasterTaskMetadata& metadata,
     RenderingStatsInstrumentation* rendering_stats,
     const RasterTask::Reply& reply,
-    Task::Set& dependencies) {
+    Task::Set* dependencies) {
   return RasterTask(new RasterWorkerPoolTaskImpl(resource,
                                                  picture_pile,
                                                  content_rect,
@@ -383,7 +404,7 @@ RasterWorkerPool::RasterTask RasterWorkerPool::CreateRasterTask(
                                                  metadata,
                                                  rendering_stats,
                                                  reply,
-                                                 &dependencies.tasks_));
+                                                 &dependencies->tasks_));
 }
 
 // static
@@ -402,7 +423,9 @@ RasterWorkerPool::RasterWorkerPool(ResourceProvider* resource_provider,
                                    size_t num_threads)
     : WorkerPool(num_threads, kWorkerThreadNamePrefix),
       client_(NULL),
-      resource_provider_(resource_provider) {
+      resource_provider_(resource_provider),
+      weak_ptr_factory_(this),
+      schedule_raster_tasks_count_(0) {
 }
 
 RasterWorkerPool::~RasterWorkerPool() {
@@ -413,8 +436,12 @@ void RasterWorkerPool::SetClient(RasterWorkerPoolClient* client) {
 }
 
 void RasterWorkerPool::Shutdown() {
-  raster_tasks_.clear();
+  TaskGraph empty;
+  SetTaskGraph(&empty);
   WorkerPool::Shutdown();
+  raster_tasks_.clear();
+  // Cancel any pending OnRasterFinished callback.
+  weak_ptr_factory_.InvalidateWeakPtrs();
 }
 
 void RasterWorkerPool::SetRasterTasks(RasterTask::Queue* queue) {
@@ -423,14 +450,31 @@ void RasterWorkerPool::SetRasterTasks(RasterTask::Queue* queue) {
       queue->tasks_required_for_activation_);
 }
 
-void RasterWorkerPool::ScheduleRasterTasks(const RootTask& root) {
-  scoped_refptr<internal::WorkerPoolTask> new_root(root.internal_);
+void RasterWorkerPool::SetRasterTaskGraph(RasterTaskGraph* graph) {
+  scoped_ptr<GraphNode> raster_finished_node(
+      graph->raster_finished_node_.Pass());
+  TaskGraph new_graph;
+  new_graph.swap(graph->graph_);
+
+  if (new_graph.empty()) {
+    SetTaskGraph(&new_graph);
+    raster_finished_task_ = NULL;
+    return;
+  }
 
-  TaskGraph graph;
-  BuildTaskGraph(new_root.get(), &graph);
-  WorkerPool::SetTaskGraph(&graph);
+  ++schedule_raster_tasks_count_;
 
-  root_.swap(new_root);
+  scoped_refptr<internal::WorkerPoolTask> new_raster_finished_task(
+      new RasterFinishedWorkerPoolTaskImpl(
+          base::MessageLoopProxy::current(),
+          base::Bind(&RasterWorkerPool::OnRasterFinished,
+                     weak_ptr_factory_.GetWeakPtr(),
+                     schedule_raster_tasks_count_)));
+  raster_finished_node->set_task(new_raster_finished_task.get());
+  // Insert "raster finished" task before switching to new graph.
+  new_graph.set(new_raster_finished_task.get(), raster_finished_node.Pass());
+  SetTaskGraph(&new_graph);
+  raster_finished_task_.swap(new_raster_finished_task);
 }
 
 bool RasterWorkerPool::IsRasterTaskRequiredForActivation(
@@ -440,4 +484,14 @@ bool RasterWorkerPool::IsRasterTaskRequiredForActivation(
       raster_tasks_required_for_activation_.end();
 }
 
+void RasterWorkerPool::OnRasterFinished(int64 schedule_raster_tasks_count) {
+  TRACE_EVENT1("cc", "RasterWorkerPool::OnRasterFinished",
+               "schedule_raster_tasks_count", schedule_raster_tasks_count);
+  DCHECK_GE(schedule_raster_tasks_count_, schedule_raster_tasks_count);
+  // Call OnRasterTasksFinished() when we've finished running all raster
+  // tasks needed since last time SetRasterTaskGraph() was called.
+  if (schedule_raster_tasks_count_ == schedule_raster_tasks_count)
+    OnRasterTasksFinished();
+}
+
 }  // namespace cc
diff --git a/cc/resources/raster_worker_pool.h b/cc/resources/raster_worker_pool.h
index f168cbc..c868be7 100644
--- a/cc/resources/raster_worker_pool.h
+++ b/cc/resources/raster_worker_pool.h
@@ -30,7 +30,7 @@ namespace internal {
 class CC_EXPORT RasterWorkerPoolTask
     : public base::RefCounted<RasterWorkerPoolTask> {
  public:
-  typedef std::vector<scoped_refptr<RasterWorkerPoolTask> > TaskVector;
+  typedef std::vector<scoped_refptr<WorkerPoolTask> > TaskVector;
 
   // Returns true if |device| was written to. False indicate that
   // the content of |device| is undefined and the resource doesn't
@@ -45,15 +45,12 @@ class CC_EXPORT RasterWorkerPoolTask
   bool HasCompleted() const;
 
   const Resource* resource() const { return resource_; }
-  const WorkerPoolTask::TaskVector& dependencies() const {
-    return dependencies_;
-  }
+  const TaskVector& dependencies() const { return dependencies_; }
 
  protected:
   friend class base::RefCounted<RasterWorkerPoolTask>;
 
-  RasterWorkerPoolTask(const Resource* resource,
-                       WorkerPoolTask::TaskVector* dependencies);
+  RasterWorkerPoolTask(const Resource* resource, TaskVector* dependencies);
   virtual ~RasterWorkerPoolTask();
 
  private:
@@ -61,7 +58,7 @@ class CC_EXPORT RasterWorkerPoolTask
   bool did_complete_;
   bool was_canceled_;
   const Resource* resource_;
-  WorkerPoolTask::TaskVector dependencies_;
+  TaskVector dependencies_;
 };
 
 }  // namespace internal
@@ -128,7 +125,7 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
       friend class RasterWorkerPool;
       friend class RasterWorkerPoolTest;
 
-      typedef internal::WorkerPoolTask::TaskVector TaskVector;
+      typedef internal::RasterWorkerPoolTask::TaskVector TaskVector;
       TaskVector tasks_;
     };
 
@@ -157,8 +154,6 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
 
     class CC_EXPORT Queue {
      public:
-      typedef internal::RasterWorkerPoolTask::TaskVector TaskVector;
-
       Queue();
       ~Queue();
 
@@ -167,6 +162,8 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
      private:
       friend class RasterWorkerPool;
 
+      typedef std::vector<scoped_refptr<internal::RasterWorkerPoolTask> >
+          TaskVector;
       TaskVector tasks_;
       typedef base::hash_set<internal::RasterWorkerPoolTask*> TaskSet;
       TaskSet tasks_required_for_activation_;
@@ -182,7 +179,6 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
     void Reset();
 
    protected:
-    friend class PixelBufferRasterWorkerPool;
     friend class RasterWorkerPool;
     friend class RasterWorkerPoolTest;
 
@@ -217,7 +213,7 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
       const RasterTaskMetadata& metadata,
       RenderingStatsInstrumentation* rendering_stats,
       const RasterTask::Reply& reply,
-      Task::Set& dependencies);
+      Task::Set* dependencies);
 
   static Task CreateImageDecodeTask(
       skia::LazyPixelRef* pixel_ref,
@@ -226,28 +222,38 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
       const Task::Reply& reply);
 
  protected:
-  class RootTask {
+  typedef std::vector<scoped_refptr<internal::WorkerPoolTask> > TaskVector;
+  typedef std::vector<scoped_refptr<internal::RasterWorkerPoolTask> >
+      RasterTaskVector;
+  typedef internal::RasterWorkerPoolTask* TaskMapKey;
+  typedef base::hash_map<TaskMapKey,
+                         scoped_refptr<internal::WorkerPoolTask> > TaskMap;
+
+  class CC_EXPORT RasterTaskGraph {
    public:
-    RootTask();
-    explicit RootTask(internal::WorkerPoolTask::TaskVector* dependencies);
-    RootTask(const base::Closure& callback,
-             internal::WorkerPoolTask::TaskVector* dependencies);
-    ~RootTask();
+    RasterTaskGraph();
+    ~RasterTaskGraph();
 
-   protected:
+    void InsertRasterTask(internal::WorkerPoolTask* raster_task,
+                          const TaskVector& decode_tasks);
+
+   private:
     friend class RasterWorkerPool;
 
-    scoped_refptr<internal::WorkerPoolTask> internal_;
-  };
+    TaskGraph graph_;
+    scoped_refptr<internal::WorkerPoolTask> raster_finished_task_;
+    scoped_ptr<GraphNode> raster_finished_node_;
+    unsigned next_priority_;
 
-  typedef internal::RasterWorkerPoolTask* TaskMapKey;
-  typedef base::hash_map<TaskMapKey,
-                         scoped_refptr<internal::WorkerPoolTask> > TaskMap;
+    DISALLOW_COPY_AND_ASSIGN(RasterTaskGraph);
+  };
 
   RasterWorkerPool(ResourceProvider* resource_provider, size_t num_threads);
 
+  virtual void OnRasterTasksFinished() {}
+
   void SetRasterTasks(RasterTask::Queue* queue);
-  void ScheduleRasterTasks(const RootTask& root);
+  void SetRasterTaskGraph(RasterTaskGraph* graph);
   bool IsRasterTaskRequiredForActivation(
       internal::RasterWorkerPoolTask* task) const;
 
@@ -258,13 +264,16 @@ class CC_EXPORT RasterWorkerPool : public WorkerPool {
   }
 
  private:
+  void OnRasterFinished(int64 schedule_raster_tasks_count);
+
   RasterWorkerPoolClient* client_;
   ResourceProvider* resource_provider_;
   RasterTask::Queue::TaskVector raster_tasks_;
   RasterTask::Queue::TaskSet raster_tasks_required_for_activation_;
 
-  // The root task that is a dependent of all other tasks.
-  scoped_refptr<internal::WorkerPoolTask> root_;
+  base::WeakPtrFactory<RasterWorkerPool> weak_ptr_factory_;
+  scoped_refptr<internal::WorkerPoolTask> raster_finished_task_;
+  int64 schedule_raster_tasks_count_;
 };
 
 }  // namespace cc
diff --git a/cc/resources/raster_worker_pool_perftest.cc b/cc/resources/raster_worker_pool_perftest.cc
new file mode 100644
index 0000000..44cc2c9
--- /dev/null
+++ b/cc/resources/raster_worker_pool_perftest.cc
@@ -0,0 +1,200 @@
+// 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/raster_worker_pool.h"
+
+#include "base/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+
+namespace {
+
+static const int kTimeLimitMillis = 2000;
+static const int kWarmupRuns = 5;
+static const int kTimeCheckInterval = 10;
+
+class PerfWorkerPoolTaskImpl : public internal::WorkerPoolTask {
+ public:
+  // Overridden from internal::WorkerPoolTask:
+  virtual void RunOnThread(unsigned thread_index) OVERRIDE {}
+  virtual void DispatchCompletionCallback() OVERRIDE {}
+
+ private:
+  virtual ~PerfWorkerPoolTaskImpl() {}
+};
+
+class PerfRasterWorkerPool : public RasterWorkerPool {
+ public:
+  PerfRasterWorkerPool() : RasterWorkerPool(NULL, 1) {}
+  virtual ~PerfRasterWorkerPool() {}
+
+  static scoped_ptr<PerfRasterWorkerPool> Create() {
+    return make_scoped_ptr(new PerfRasterWorkerPool);
+  }
+
+  // Overridden from RasterWorkerPool:
+  virtual void ScheduleTasks(RasterTask::Queue* queue) OVERRIDE {
+    NOTREACHED();
+  }
+
+  void SetRasterTasks(RasterTask::Queue* queue) {
+    RasterWorkerPool::SetRasterTasks(queue);
+
+    TaskMap perf_tasks;
+    for (RasterTaskVector::const_iterator it = raster_tasks().begin();
+         it != raster_tasks().end(); ++it) {
+      internal::RasterWorkerPoolTask* task = it->get();
+
+      scoped_refptr<internal::WorkerPoolTask> new_perf_task(
+          new PerfWorkerPoolTaskImpl);
+      perf_tasks[task] = new_perf_task;
+    }
+
+    perf_tasks_.swap(perf_tasks);
+  }
+
+  void BuildTaskGraph() {
+    RasterTaskGraph graph;
+
+    for (RasterTaskVector::const_iterator it = raster_tasks().begin();
+         it != raster_tasks().end(); ++it) {
+      internal::RasterWorkerPoolTask* task = it->get();
+
+      TaskMap::iterator perf_it = perf_tasks_.find(task);
+      DCHECK(perf_it != perf_tasks_.end());
+      if (perf_it != perf_tasks_.end()) {
+        internal::WorkerPoolTask* perf_task = perf_it->second.get();
+        graph.InsertRasterTask(perf_task, task->dependencies());
+      }
+    }
+  }
+
+ private:
+  TaskMap perf_tasks_;
+
+  DISALLOW_COPY_AND_ASSIGN(PerfRasterWorkerPool);
+};
+
+class RasterWorkerPoolPerfTest : public testing::Test {
+ public:
+  RasterWorkerPoolPerfTest() : num_runs_(0) {}
+
+  // Overridden from testing::Test:
+  virtual void SetUp() OVERRIDE {
+    raster_worker_pool_ = PerfRasterWorkerPool::Create();
+  }
+  virtual void TearDown() OVERRIDE {
+    raster_worker_pool_->Shutdown();
+  }
+
+  void EndTest() {
+    elapsed_ = base::TimeTicks::HighResNow() - start_time_;
+  }
+
+  void AfterTest(const std::string test_name) {
+    // Format matches chrome/test/perf/perf_test.h:PrintResult
+    printf("*RESULT %s: %.2f runs/s\n",
+           test_name.c_str(),
+           num_runs_ / elapsed_.InSecondsF());
+  }
+
+  bool DidRun() {
+    ++num_runs_;
+    if (num_runs_ == kWarmupRuns)
+      start_time_ = base::TimeTicks::HighResNow();
+
+    if (!start_time_.is_null() && (num_runs_ % kTimeCheckInterval) == 0) {
+      base::TimeDelta elapsed = base::TimeTicks::HighResNow() - start_time_;
+      if (elapsed >= base::TimeDelta::FromMilliseconds(kTimeLimitMillis)) {
+        elapsed_ = elapsed;
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  void CreateTasks(RasterWorkerPool::RasterTask::Queue* tasks,
+                   unsigned num_raster_tasks,
+                   unsigned num_image_decode_tasks) {
+    typedef std::vector<RasterWorkerPool::Task> TaskVector;
+    TaskVector image_decode_tasks;
+
+    for (unsigned i = 0; i < num_image_decode_tasks; ++i) {
+      image_decode_tasks.push_back(
+          RasterWorkerPool::CreateImageDecodeTask(
+              NULL,
+              0,
+              NULL,
+              base::Bind(
+                  &RasterWorkerPoolPerfTest::OnImageDecodeTaskCompleted)));
+    }
+
+    for (unsigned i = 0; i < num_raster_tasks; ++i) {
+      RasterWorkerPool::Task::Set decode_tasks;
+      for (TaskVector::iterator it = image_decode_tasks.begin();
+           it != image_decode_tasks.end(); ++it)
+        decode_tasks.Insert(*it);
+
+      tasks->Append(
+          RasterWorkerPool::CreateRasterTask(
+              NULL,
+              NULL,
+              gfx::Rect(),
+              1.0,
+              HIGH_QUALITY_RASTER_MODE,
+              false,
+              RasterTaskMetadata(),
+              NULL,
+              base::Bind(&RasterWorkerPoolPerfTest::OnRasterTaskCompleted),
+              &decode_tasks),
+          false);
+    }
+  }
+
+  void RunBuildTaskGraphTest(const std::string test_name,
+                             unsigned num_raster_tasks,
+                             unsigned num_image_decode_tasks) {
+    start_time_ = base::TimeTicks();
+    num_runs_ = 0;
+    RasterWorkerPool::RasterTask::Queue tasks;
+    CreateTasks(&tasks, num_raster_tasks, num_image_decode_tasks);
+    raster_worker_pool_->SetRasterTasks(&tasks);
+    do {
+      raster_worker_pool_->BuildTaskGraph();
+    } while (DidRun());
+
+    AfterTest(test_name);
+  }
+
+ protected:
+  static void OnRasterTaskCompleted(const PicturePileImpl::Analysis& analysis,
+                                    bool was_canceled) {}
+  static void OnImageDecodeTaskCompleted(bool was_canceled) {}
+
+  scoped_ptr<PerfRasterWorkerPool> raster_worker_pool_;
+  base::TimeTicks start_time_;
+  base::TimeDelta elapsed_;
+  int num_runs_;
+};
+
+TEST_F(RasterWorkerPoolPerfTest, BuildTaskGraph) {
+  RunBuildTaskGraphTest("build_task_graph_10_0", 10, 0);
+  RunBuildTaskGraphTest("build_task_graph_100_0", 100, 0);
+  RunBuildTaskGraphTest("build_task_graph_1000_0", 1000, 0);
+  RunBuildTaskGraphTest("build_task_graph_10_1", 10, 1);
+  RunBuildTaskGraphTest("build_task_graph_100_1", 100, 1);
+  RunBuildTaskGraphTest("build_task_graph_1000_1", 1000, 1);
+  RunBuildTaskGraphTest("build_task_graph_10_4", 10, 4);
+  RunBuildTaskGraphTest("build_task_graph_100_4", 100, 4);
+  RunBuildTaskGraphTest("build_task_graph_1000_4", 1000, 4);
+  RunBuildTaskGraphTest("build_task_graph_10_16", 10, 16);
+  RunBuildTaskGraphTest("build_task_graph_100_16", 100, 16);
+  RunBuildTaskGraphTest("build_task_graph_1000_16", 1000, 16);
+}
+
+}  // namespace
+
+}  // namespace cc
diff --git a/cc/resources/raster_worker_pool_unittest.cc b/cc/resources/raster_worker_pool_unittest.cc
index e35518c..ed98e48 100644
--- a/cc/resources/raster_worker_pool_unittest.cc
+++ b/cc/resources/raster_worker_pool_unittest.cc
@@ -26,11 +26,12 @@ class TestRasterWorkerPoolTaskImpl : public internal::RasterWorkerPoolTask {
   TestRasterWorkerPoolTaskImpl(
       const Resource* resource,
       const Reply& reply,
-      internal::WorkerPoolTask::TaskVector* dependencies)
+      TaskVector* dependencies)
       : internal::RasterWorkerPoolTask(resource, dependencies),
         reply_(reply),
         did_raster_(false) {}
 
+  // Overridden from internal::WorkerPoolTask:
   virtual bool RunOnThread(SkDevice* device, unsigned thread_index) OVERRIDE {
     did_raster_ = true;
     return true;
@@ -45,6 +46,8 @@ class TestRasterWorkerPoolTaskImpl : public internal::RasterWorkerPoolTask {
  private:
   const Reply reply_;
   bool did_raster_;
+
+  DISALLOW_COPY_AND_ASSIGN(TestRasterWorkerPoolTaskImpl);
 };
 
 class RasterWorkerPoolTest : public testing::Test,
diff --git a/cc/resources/tile_manager.cc b/cc/resources/tile_manager.cc
index 48cb31f..ab53cfd 100644
--- a/cc/resources/tile_manager.cc
+++ b/cc/resources/tile_manager.cc
@@ -726,7 +726,7 @@ RasterWorkerPool::RasterTask TileManager::CreateRasterTask(Tile* tile) {
                  make_scoped_refptr(tile),
                  base::Passed(&resource),
                  mts.raster_mode),
-      decode_tasks);
+      &decode_tasks);
 }
 
 void TileManager::OnImageDecodeTaskCompleted(
diff --git a/cc/resources/worker_pool.cc b/cc/resources/worker_pool.cc
index 09aa1aa..9b7e824 100644
--- a/cc/resources/worker_pool.cc
+++ b/cc/resources/worker_pool.cc
@@ -29,13 +29,6 @@ WorkerPoolTask::WorkerPoolTask()
       did_complete_(false) {
 }
 
-WorkerPoolTask::WorkerPoolTask(TaskVector* dependencies)
-    : did_schedule_(false),
-      did_run_(false),
-      did_complete_(false) {
-  dependencies_.swap(*dependencies);
-}
-
 WorkerPoolTask::~WorkerPoolTask() {
   DCHECK_EQ(did_schedule_, did_complete_);
   DCHECK(!did_run_ || did_schedule_);
@@ -242,6 +235,7 @@ void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) {
     for (GraphNodeMap::iterator it = new_pending_tasks.begin();
          it != new_pending_tasks.end(); ++it) {
       internal::WorkerPoolTask* task = it->first;
+      DCHECK(task);
       GraphNode* node = it->second;
 
       // Completed tasks should not exist in |new_pending_tasks|.
@@ -359,8 +353,8 @@ void WorkerPool::Inner::Run() {
   has_ready_to_run_tasks_cv_.Signal();
 }
 
-WorkerPool::GraphNode::GraphNode(internal::WorkerPoolTask* task)
-    : task_(task),
+WorkerPool::GraphNode::GraphNode()
+    : task_(NULL),
       priority_(0),
       num_dependencies_(0) {
 }
@@ -414,59 +408,12 @@ void WorkerPool::DispatchCompletionCallbacks(TaskDeque* completed_tasks) {
 }
 
 void WorkerPool::SetTaskGraph(TaskGraph* graph) {
-  TRACE_EVENT0("cc", "WorkerPool::SetTaskGraph");
+  TRACE_EVENT1("cc", "WorkerPool::SetTaskGraph",
+               "num_tasks", graph->size());
 
   DCHECK(!in_dispatch_completion_callbacks_);
 
   inner_->SetTaskGraph(graph);
 }
 
-// static
-unsigned WorkerPool::BuildTaskGraphRecursive(
-    internal::WorkerPoolTask* task,
-    GraphNode* dependent,
-    unsigned priority,
-    TaskGraph* graph) {
-  GraphNodeMap::iterator it = graph->find(task);
-  if (it != graph->end()) {
-    GraphNode* node = it->second;
-    node->add_dependent(dependent);
-    return priority;
-  }
-
-  scoped_ptr<GraphNode> node(new GraphNode(task));
-
-  typedef internal::WorkerPoolTask::TaskVector TaskVector;
-  for (TaskVector::iterator dependency_it = task->dependencies().begin();
-       dependency_it != task->dependencies().end(); ++dependency_it) {
-    internal::WorkerPoolTask* dependency = dependency_it->get();
-    // Skip sub-tree if task has already completed.
-    if (dependency->HasCompleted())
-      continue;
-
-    node->add_dependency();
-
-    priority = BuildTaskGraphRecursive(dependency,
-                                       node.get(),
-                                       priority,
-                                       graph);
-  }
-
-  node->set_priority(priority);
-  if (dependent)
-    node->add_dependent(dependent);
-
-  graph->set(task, node.Pass());
-
-  return priority + 1;
-}
-
-// static
-void WorkerPool::BuildTaskGraph(
-    internal::WorkerPoolTask* root, TaskGraph* graph) {
-  const unsigned kBasePriority = 0u;
-  if (root && !root->HasCompleted())
-    BuildTaskGraphRecursive(root, NULL, kBasePriority, graph);
-}
-
 }  // namespace cc
diff --git a/cc/resources/worker_pool.h b/cc/resources/worker_pool.h
index cfa6302..a8f27db 100644
--- a/cc/resources/worker_pool.h
+++ b/cc/resources/worker_pool.h
@@ -23,8 +23,6 @@ namespace internal {
 class CC_EXPORT WorkerPoolTask
     : public base::RefCountedThreadSafe<WorkerPoolTask> {
  public:
-  typedef std::vector<scoped_refptr<WorkerPoolTask> > TaskVector;
-
   virtual void RunOnThread(unsigned thread_index) = 0;
   virtual void DispatchCompletionCallback() = 0;
 
@@ -36,20 +34,16 @@ class CC_EXPORT WorkerPoolTask
   bool HasFinishedRunning() const;
   bool HasCompleted() const;
 
-  TaskVector& dependencies() { return dependencies_; }
-
  protected:
   friend class base::RefCountedThreadSafe<WorkerPoolTask>;
 
   WorkerPoolTask();
-  explicit WorkerPoolTask(TaskVector* dependencies);
   virtual ~WorkerPoolTask();
 
  private:
   bool did_schedule_;
   bool did_run_;
   bool did_complete_;
-  TaskVector dependencies_;
 };
 
 }  // namespace internal
@@ -85,12 +79,14 @@ class CC_EXPORT WorkerPool {
    public:
     typedef std::vector<GraphNode*> Vector;
 
-    explicit GraphNode(internal::WorkerPoolTask* task);
+    GraphNode();
     ~GraphNode();
 
+    void set_task(internal::WorkerPoolTask* task) { task_ = task; }
     internal::WorkerPoolTask* task() { return task_; }
 
     void add_dependent(GraphNode* dependent) {
+      DCHECK(dependent);
       dependents_.push_back(dependent);
     }
     const Vector& dependents() const {
@@ -117,6 +113,10 @@ class CC_EXPORT WorkerPool {
 
     DISALLOW_COPY_AND_ASSIGN(GraphNode);
   };
+  // A task graph contains a unique set of tasks with edges between
+  // dependencies pointing in the direction of the dependents. Each task
+  // need to be assigned a unique priority and a run count that matches
+  // the number of dependencies.
   typedef ScopedPtrHashMap<internal::WorkerPoolTask*, GraphNode> GraphNodeMap;
   typedef GraphNodeMap TaskGraph;
 
@@ -127,31 +127,6 @@ class CC_EXPORT WorkerPool {
   // but completion of them is still processed.
   void SetTaskGraph(TaskGraph* graph);
 
-  // BuildTaskGraph() takes a task tree as input and constructs a
-  // unique set of tasks with edges between dependencies pointing in
-  // the direction of the dependents. Each task is given a unique priority
-  // which is currently the same as the DFS traversal order.
-  //
-  // Input:             Output:
-  //
-  //       root               task4          Task | Priority (lower is better)
-  //     /      \           /       \      -------+---------------------------
-  //  task1    task2      task3    task2     root | 4
-  //    |        |          |        |      task1 | 2
-  //  task3      |        task1      |      task2 | 3
-  //    |        |           \      /       task3 | 1
-  //  task4    task4           root         task4 | 0
-  //
-  // The output can be used to efficiently maintain a queue of
-  // "ready to run" tasks.
-  static unsigned BuildTaskGraphRecursive(
-      internal::WorkerPoolTask* task,
-      GraphNode* dependent,
-      unsigned priority,
-      TaskGraph* graph);
-  static void BuildTaskGraph(
-      internal::WorkerPoolTask* root, TaskGraph* graph);
-
  private:
   class Inner;
   friend class Inner;
diff --git a/cc/resources/worker_pool_perftest.cc b/cc/resources/worker_pool_perftest.cc
index 9b52ae4..b7a1c4c 100644
--- a/cc/resources/worker_pool_perftest.cc
+++ b/cc/resources/worker_pool_perftest.cc
@@ -16,26 +16,20 @@ static const int kTimeLimitMillis = 2000;
 static const int kWarmupRuns = 5;
 static const int kTimeCheckInterval = 10;
 
-class PerfTaskImpl : public internal::WorkerPoolTask {
+class PerfWorkerPoolTaskImpl : public internal::WorkerPoolTask {
  public:
-  explicit PerfTaskImpl(internal::WorkerPoolTask::TaskVector* dependencies)
-      : internal::WorkerPoolTask(dependencies) {}
-
   // Overridden from internal::WorkerPoolTask:
   virtual void RunOnThread(unsigned thread_index) OVERRIDE {}
   virtual void DispatchCompletionCallback() OVERRIDE {}
 
  private:
-  virtual ~PerfTaskImpl() {}
+  virtual ~PerfWorkerPoolTaskImpl() {}
 };
 
-class PerfControlTaskImpl : public internal::WorkerPoolTask {
+class PerfControlWorkerPoolTaskImpl : public internal::WorkerPoolTask {
  public:
-  explicit PerfControlTaskImpl(
-      internal::WorkerPoolTask::TaskVector* dependencies)
-      : internal::WorkerPoolTask(dependencies),
-        did_start_(new CompletionEvent),
-        can_finish_(new CompletionEvent) {}
+  PerfControlWorkerPoolTaskImpl() : did_start_(new CompletionEvent),
+                                    can_finish_(new CompletionEvent) {}
 
   // Overridden from internal::WorkerPoolTask:
   virtual void RunOnThread(unsigned thread_index) OVERRIDE {
@@ -53,10 +47,12 @@ class PerfControlTaskImpl : public internal::WorkerPoolTask {
   }
 
  private:
-  virtual ~PerfControlTaskImpl() {}
+  virtual ~PerfControlWorkerPoolTaskImpl() {}
 
   scoped_ptr<CompletionEvent> did_start_;
   scoped_ptr<CompletionEvent> can_finish_;
+
+  DISALLOW_COPY_AND_ASSIGN(PerfControlWorkerPoolTaskImpl);
 };
 
 class PerfWorkerPool : public WorkerPool {
@@ -68,17 +64,97 @@ class PerfWorkerPool : public WorkerPool {
     return make_scoped_ptr(new PerfWorkerPool);
   }
 
-  void BuildTaskGraph(internal::WorkerPoolTask* root) {
-    graph_.clear();
-    WorkerPool::BuildTaskGraph(root, &graph_);
-  }
+  void ScheduleTasks(internal::WorkerPoolTask* root_task,
+                     internal::WorkerPoolTask* leaf_task,
+                     unsigned max_depth,
+                     unsigned num_children_per_node) {
+    TaskVector tasks;
+    unsigned priority = 0u;
+    TaskGraph graph;
+
+    scoped_ptr<GraphNode> root_node;
+    if (root_task) {
+      root_node = make_scoped_ptr(new GraphNode);
+      root_node->set_task(root_task);
+    }
+
+    scoped_ptr<GraphNode> leaf_node;
+    if (leaf_task) {
+      leaf_node = make_scoped_ptr(new GraphNode);
+      leaf_node->set_task(leaf_task);
+    }
 
-  void ScheduleTasks() {
-    SetTaskGraph(&graph_);
+    if (max_depth) {
+      priority = BuildTaskGraph(&tasks,
+                                &graph,
+                                root_node.get(),
+                                leaf_node.get(),
+                                priority,
+                                0,
+                                max_depth,
+                                num_children_per_node);
+    }
+
+    if (leaf_node) {
+      leaf_node->set_priority(priority++);
+      graph.set(leaf_task, leaf_node.Pass());
+    }
+
+    if (root_node) {
+      root_node->set_priority(priority++);
+      graph.set(root_task, root_node.Pass());
+    }
+
+    SetTaskGraph(&graph);
+
+    tasks_.swap(tasks);
   }
 
  private:
-  TaskGraph graph_;
+  typedef std::vector<scoped_refptr<internal::WorkerPoolTask> > TaskVector;
+
+  unsigned BuildTaskGraph(TaskVector* tasks,
+                          TaskGraph* graph,
+                          GraphNode* dependent_node,
+                          GraphNode* leaf_node,
+                          unsigned priority,
+                          unsigned current_depth,
+                          unsigned max_depth,
+                          unsigned num_children_per_node) {
+    scoped_refptr<PerfWorkerPoolTaskImpl> task(new PerfWorkerPoolTaskImpl);
+    scoped_ptr<GraphNode> node(new GraphNode);
+    node->set_task(task.get());
+
+    if (current_depth < max_depth) {
+      for (unsigned i = 0; i < num_children_per_node; ++i) {
+        priority = BuildTaskGraph(tasks,
+                                  graph,
+                                  node.get(),
+                                  leaf_node,
+                                  priority,
+                                  current_depth + 1,
+                                  max_depth,
+                                  num_children_per_node);
+      }
+    } else if (leaf_node) {
+      leaf_node->add_dependent(node.get());
+      node->add_dependency();
+    }
+
+    if (dependent_node) {
+      node->add_dependent(dependent_node);
+      dependent_node->add_dependency();
+    }
+    node->set_priority(priority);
+    graph->set(task.get(), node.Pass());
+    tasks->push_back(task.get());
+
+    return priority + 1;
+  }
+
+  TaskVector tasks_;
+
+  DISALLOW_COPY_AND_ASSIGN(PerfWorkerPool);
 };
 
 class WorkerPoolPerfTest : public testing::Test {
@@ -105,24 +181,6 @@ class WorkerPoolPerfTest : public testing::Test {
            num_runs_ / elapsed_.InSecondsF());
   }
 
-  void CreateTasks(internal::WorkerPoolTask::TaskVector* dependencies,
-                   unsigned current_depth,
-                   unsigned max_depth,
-                   unsigned num_children_per_node) {
-    internal::WorkerPoolTask::TaskVector children;
-    if (current_depth < max_depth) {
-      for (unsigned i = 0; i < num_children_per_node; ++i) {
-        CreateTasks(&children,
-                    current_depth + 1,
-                    max_depth,
-                    num_children_per_node);
-      }
-    } else if (leaf_task_.get()) {
-      children.push_back(leaf_task_);
-    }
-    dependencies->push_back(make_scoped_refptr(new PerfTaskImpl(&children)));
-  }
-
   bool DidRun() {
     ++num_runs_;
     if (num_runs_ == kWarmupRuns)
@@ -139,42 +197,20 @@ class WorkerPoolPerfTest : public testing::Test {
     return true;
   }
 
-  void RunBuildTaskGraphTest(const std::string test_name,
-                             unsigned max_depth,
-                             unsigned num_children_per_node) {
-    start_time_ = base::TimeTicks();
-    num_runs_ = 0;
-    internal::WorkerPoolTask::TaskVector children;
-    CreateTasks(&children, 0, max_depth, num_children_per_node);
-    scoped_refptr<PerfTaskImpl> root_task(
-        make_scoped_refptr(new PerfTaskImpl(&children)));
-    do {
-      worker_pool_->BuildTaskGraph(root_task.get());
-    } while (DidRun());
-
-    AfterTest(test_name);
-  }
-
   void RunScheduleTasksTest(const std::string test_name,
                             unsigned max_depth,
                             unsigned num_children_per_node) {
     start_time_ = base::TimeTicks();
     num_runs_ = 0;
     do {
-      internal::WorkerPoolTask::TaskVector empty;
-      leaf_task_ = make_scoped_refptr(new PerfControlTaskImpl(&empty));
-      internal::WorkerPoolTask::TaskVector children;
-      CreateTasks(&children, 0, max_depth, num_children_per_node);
-      scoped_refptr<PerfTaskImpl> root_task(
-          make_scoped_refptr(new PerfTaskImpl(&children)));
-
-      worker_pool_->BuildTaskGraph(root_task.get());
-      worker_pool_->ScheduleTasks();
-      leaf_task_->WaitForTaskToStartRunning();
-      worker_pool_->BuildTaskGraph(NULL);
-      worker_pool_->ScheduleTasks();
+      scoped_refptr<PerfControlWorkerPoolTaskImpl> leaf_task(
+          new PerfControlWorkerPoolTaskImpl);
+      worker_pool_->ScheduleTasks(
+          NULL, leaf_task.get(), max_depth, num_children_per_node);
+      leaf_task->WaitForTaskToStartRunning();
+      worker_pool_->ScheduleTasks(NULL, NULL, 0, 0);
       worker_pool_->CheckForCompletedTasks();
-      leaf_task_->AllowTaskToFinish();
+      leaf_task->AllowTaskToFinish();
     } while (DidRun());
 
     AfterTest(test_name);
@@ -186,13 +222,10 @@ class WorkerPoolPerfTest : public testing::Test {
     start_time_ = base::TimeTicks();
     num_runs_ = 0;
     do {
-      internal::WorkerPoolTask::TaskVector children;
-      CreateTasks(&children, 0, max_depth, num_children_per_node);
-      scoped_refptr<PerfControlTaskImpl> root_task(
-          make_scoped_refptr(new PerfControlTaskImpl(&children)));
-
-      worker_pool_->BuildTaskGraph(root_task.get());
-      worker_pool_->ScheduleTasks();
+      scoped_refptr<PerfControlWorkerPoolTaskImpl> root_task(
+          new PerfControlWorkerPoolTaskImpl);
+      worker_pool_->ScheduleTasks(
+          root_task.get(), NULL, max_depth, num_children_per_node);
       root_task->WaitForTaskToStartRunning();
       root_task->AllowTaskToFinish();
       worker_pool_->CheckForCompletedTasks();
@@ -203,22 +236,11 @@ class WorkerPoolPerfTest : public testing::Test {
 
  protected:
   scoped_ptr<PerfWorkerPool> worker_pool_;
-  scoped_refptr<PerfControlTaskImpl> leaf_task_;
   base::TimeTicks start_time_;
   base::TimeDelta elapsed_;
   int num_runs_;
 };
 
-TEST_F(WorkerPoolPerfTest, BuildTaskGraph) {
-  RunBuildTaskGraphTest("build_task_graph_1_10", 1, 10);
-  RunBuildTaskGraphTest("build_task_graph_1_1000", 1, 1000);
-  RunBuildTaskGraphTest("build_task_graph_2_10", 2, 10);
-  RunBuildTaskGraphTest("build_task_graph_5_5", 5, 5);
-  RunBuildTaskGraphTest("build_task_graph_10_2", 10, 2);
-  RunBuildTaskGraphTest("build_task_graph_1000_1", 1000, 1);
-  RunBuildTaskGraphTest("build_task_graph_10_1", 10, 1);
-}
-
 TEST_F(WorkerPoolPerfTest, ScheduleTasks) {
   RunScheduleTasksTest("schedule_tasks_1_10", 1, 10);
   RunScheduleTasksTest("schedule_tasks_1_1000", 1, 1000);
diff --git a/cc/resources/worker_pool_unittest.cc b/cc/resources/worker_pool_unittest.cc
index babf7fb..5c946e0 100644
--- a/cc/resources/worker_pool_unittest.cc
+++ b/cc/resources/worker_pool_unittest.cc
@@ -13,16 +13,10 @@ namespace cc {
 
 namespace {
 
-class FakeTaskImpl : public internal::WorkerPoolTask {
+class FakeWorkerPoolTaskImpl : public internal::WorkerPoolTask {
  public:
-  FakeTaskImpl(const base::Closure& callback,
-               const base::Closure& reply,
-               internal::WorkerPoolTask::TaskVector* dependencies)
-      : internal::WorkerPoolTask(dependencies),
-        callback_(callback),
-        reply_(reply) {
-  }
-  FakeTaskImpl(const base::Closure& callback, const base::Closure& reply)
+  FakeWorkerPoolTaskImpl(const base::Closure& callback,
+                         const base::Closure& reply)
       : callback_(callback),
         reply_(reply) {
   }
@@ -38,10 +32,12 @@ class FakeTaskImpl : public internal::WorkerPoolTask {
   }
 
  private:
-  virtual ~FakeTaskImpl() {}
+  virtual ~FakeWorkerPoolTaskImpl() {}
 
   const base::Closure callback_;
   const base::Closure reply_;
+
+  DISALLOW_COPY_AND_ASSIGN(FakeWorkerPoolTaskImpl);
 };
 
 class FakeWorkerPool : public WorkerPool {
@@ -57,26 +53,49 @@ class FakeWorkerPool : public WorkerPool {
                      const base::Closure& reply,
                      const base::Closure& dependency,
                      int count) {
-    scoped_refptr<FakeTaskImpl> dependency_task(
-        new FakeTaskImpl(dependency, base::Closure()));
+    unsigned priority = 0u;
+    TaskGraph graph;
+
+    scoped_refptr<FakeWorkerPoolTaskImpl> completion_task(
+        new FakeWorkerPoolTaskImpl(
+            base::Bind(&FakeWorkerPool::OnTasksCompleted,
+                       base::Unretained(this)),
+            base::Closure()));
+    scoped_ptr<GraphNode> completion_node(new GraphNode);
+    completion_node->set_task(completion_task.get());
+
+    scoped_refptr<FakeWorkerPoolTaskImpl> dependency_task(
+        new FakeWorkerPoolTaskImpl(dependency, base::Closure()));
+    scoped_ptr<GraphNode> dependency_node(new GraphNode);
+    dependency_node->set_task(dependency_task.get());
 
-    internal::WorkerPoolTask::TaskVector tasks;
+    TaskVector tasks;
     for (int i = 0; i < count; ++i) {
-      internal::WorkerPoolTask::TaskVector dependencies(1, dependency_task);
-      tasks.push_back(new FakeTaskImpl(callback, reply, &dependencies));
+      scoped_refptr<FakeWorkerPoolTaskImpl> task(
+          new FakeWorkerPoolTaskImpl(callback, reply));
+      scoped_ptr<GraphNode> node(new GraphNode);
+      node->set_task(task.get());
+      node->add_dependent(completion_node.get());
+      completion_node->add_dependency();
+      dependency_node->add_dependent(node.get());
+      node->add_dependency();
+      node->set_priority(priority++);
+      graph.set(task.get(), node.Pass());
+      tasks.push_back(task.get());
     }
-    scoped_refptr<FakeTaskImpl> completion_task(
-        new FakeTaskImpl(base::Bind(&FakeWorkerPool::OnTasksCompleted,
-                                    base::Unretained(this)),
-                         base::Closure(),
-                         &tasks));
+
+    completion_node->set_priority(priority++);
+    graph.set(completion_task.get(), completion_node.Pass());
+    dependency_node->set_priority(priority++);
+    graph.set(dependency_task.get(), dependency_node.Pass());
 
     scheduled_tasks_completion_.reset(new CompletionEvent);
 
-    TaskGraph graph;
-    BuildTaskGraph(completion_task.get(), &graph);
-    WorkerPool::SetTaskGraph(&graph);
-    root_.swap(completion_task);
+    SetTaskGraph(&graph);
+
+    tasks_.swap(tasks);
+    completion_task_.swap(completion_task);
+    dependency_task_.swap(dependency_task);
   }
 
   void WaitForTasksToComplete() {
@@ -85,13 +104,19 @@ class FakeWorkerPool : public WorkerPool {
   }
 
  private:
+  typedef std::vector<scoped_refptr<internal::WorkerPoolTask> > TaskVector;
+
   void OnTasksCompleted() {
     DCHECK(scheduled_tasks_completion_);
     scheduled_tasks_completion_->Signal();
   }
 
-  scoped_refptr<FakeTaskImpl> root_;
+  TaskVector tasks_;
+  scoped_refptr<FakeWorkerPoolTaskImpl> completion_task_;
+  scoped_refptr<FakeWorkerPoolTaskImpl> dependency_task_;
   scoped_ptr<CompletionEvent> scheduled_tasks_completion_;
+
+  DISALLOW_COPY_AND_ASSIGN(FakeWorkerPool);
 };
 
 class WorkerPoolTest : public testing::Test {