TaskGraphRunner Group support

cc/raster/task_graph_work_queue.h

Index: cc/raster/task_graph_work_queue.h
diff --git a/cc/raster/task_graph_work_queue.h b/cc/raster/task_graph_work_queue.h
index 8a461232cbfbc536016a620317bef4e6f235ebb8..601a2c6fc159cfcd152bfd821cc3030df93e2601 100644
--- a/cc/raster/task_graph_work_queue.h
+++ b/cc/raster/task_graph_work_queue.h
@@ -16,6 +16,11 @@ namespace cc {
 // Implements a queue of incoming TaskGraph work. Designed for use by
 // implementations of TaskGraphRunner. Not thread safe, so the caller is
 // responsible for all necessary locking.
+//
+// Tasks in the queue are divided into categories. Tasks from a single graph may
+// be put into different categories, each of which is prioritized independently
+// from the others. It is up to the implementation of TaskGraphRunner to
+// define the meaning of the categories and handle them appropriately.
 class CC_EXPORT TaskGraphWorkQueue {
  public:
   struct TaskNamespace;
@@ -23,12 +28,19 @@ class CC_EXPORT TaskGraphWorkQueue {
   struct PrioritizedTask {
     typedef std::vector<PrioritizedTask> Vector;
 
-    PrioritizedTask(Task* task, TaskNamespace* task_namespace, size_t priority)
-        : task(task), task_namespace(task_namespace), priority(priority) {}
+    PrioritizedTask(Task* task,
+                    TaskNamespace* task_namespace,
+                    uint16_t category,
+                    uint16_t priority)
+        : task(task),
+          task_namespace(task_namespace),
+          category(category),
+          priority(priority) {}
 
     Task* task;
     TaskNamespace* task_namespace;
-    size_t priority;
+    uint16_t category;
+    uint16_t priority;
   };
 
   // Helper classes and static methods used by dependent classes.
@@ -41,8 +53,9 @@ class CC_EXPORT TaskGraphWorkQueue {
     // Current task graph.
     TaskGraph graph;
 
-    // Ordered set of tasks that are ready to run.
-    PrioritizedTask::Vector ready_to_run_tasks;
+    // Map from category to a vector of tasks that are ready to run for that
+    // category.
+    std::map<uint16_t, PrioritizedTask::Vector> ready_to_run_tasks;
 
     // Completed tasks not yet collected by origin thread.
     Task::Vector completed_tasks;
@@ -62,8 +75,8 @@ class CC_EXPORT TaskGraphWorkQueue {
   // previous tasks in the graph being replaced.
   void ScheduleTasks(NamespaceToken token, TaskGraph* graph);
 
-  // Returns the next task to run paired with its namespace.
-  PrioritizedTask GetNextTaskToRun();
+  // Returns the next task to run for the given category.
+  PrioritizedTask GetNextTaskToRun(uint16_t category);
 
   // Marks a task as completed, adding it to its namespace's list of completed
   // tasks and updating the list of |ready_to_run_namespaces|.
@@ -92,6 +105,10 @@ class CC_EXPORT TaskGraphWorkQueue {
 
   bool HasReadyToRunTasks() const { return !ready_to_run_namespaces_.empty(); }
 
+  bool HasReadyToRunTasksForCategory(uint16_t category) const {
+    return ready_to_run_namespaces_.count(category) > 0;

[reveman, 2015/12/04 20:55:51]

nit: ready_to_run_namespaces_.find(category)?

[ericrk, 2015/12/09 22:56:44]

now that a category can be empty (but still exist), restructured this.

+  }
+
   bool HasAnyNamespaces() const { return !namespaces_.empty(); }
 
   bool HasFinishedRunningTasksInAllNamespaces() {
@@ -106,6 +123,11 @@ class CC_EXPORT TaskGraphWorkQueue {
   // configured.
   static bool DependencyMismatch(const TaskGraph* graph);
 
+  // Certain TaskGraphRunners may wish to ignore categories - in these cases, we
+  // provide a utility function which strips categories from a TaskGraph,
+  // assigning all tasks to group 0.
+  static void UncategorizeTaskGraph(TaskGraph* graph);

[reveman, 2015/12/04 20:55:51]

I don't think we should modify the task graph in any other way than what Swap
does. ie. TaskGraph::nodes should be const from the TaskGraphRunners
perspective.

Would it be possible to instead create or schedule tasks in the work queue using
a category rewrite filter of some sort that would map category to 0 without
modifying the nodes?

or maybe it's fine to just run all tasks by category in the single threaded
case? I would prefer that if possible

[ericrk, 2015/12/09 22:56:43]

Re-worked things per our discussion on fri.

+
  private:
   // Helper class used to provide NamespaceToken comparison to TaskNamespaceMap.
   class CompareToken {
@@ -116,29 +138,13 @@ class CC_EXPORT TaskGraphWorkQueue {
     }
   };
 
-  static bool CompareTaskPriority(const PrioritizedTask& a,
-                                  const PrioritizedTask& b) {
-    // In this system, numerically lower priority is run first.
-    return a.priority > b.priority;
-  }
-
-  static bool CompareTaskNamespacePriority(const TaskNamespace* a,
-                                           const TaskNamespace* b) {
-    DCHECK(!a->ready_to_run_tasks.empty());
-    DCHECK(!b->ready_to_run_tasks.empty());
-
-    // Compare based on task priority of the ready_to_run_tasks heap .front()
-    // will hold the max element of the heap, except after pop_heap, when max
-    // element is moved to .back().
-    return CompareTaskPriority(a->ready_to_run_tasks.front(),
-                               b->ready_to_run_tasks.front());
-  }
-
   using TaskNamespaceMap =
       std::map<NamespaceToken, TaskNamespace, CompareToken>;
 
   TaskNamespaceMap namespaces_;
-  TaskNamespace::Vector ready_to_run_namespaces_;
+
+  // Map from category to a vector of ready to run namespaces for that category.
+  std::map<uint16_t, TaskNamespace::Vector> ready_to_run_namespaces_;
 
   // Provides a unique id to each NamespaceToken.
   int next_namespace_id_;