TaskGraphRunner Group support

cc/raster/task_graph_work_queue.cc

Index: cc/raster/task_graph_work_queue.cc
diff --git a/cc/raster/task_graph_work_queue.cc b/cc/raster/task_graph_work_queue.cc
index 655a005b024804117fc9052a16ca20dd523868ca..dec9a4490c2eb6a429d07b3efa20b31514fc4db6 100644
--- a/cc/raster/task_graph_work_queue.cc
+++ b/cc/raster/task_graph_work_queue.cc
@@ -10,6 +10,52 @@
 #include "base/trace_event/trace_event.h"
 
 namespace cc {
+namespace {
+
+template <typename T>
+void ClearAllVectors(T* array_of_vectors) {

[reveman, 2015/12/04 02:30:53]

nit: remove vector specific references as T can be any type that you can iterate
and contains items that implement clear(). maybe rename to ClearEach or
ForEachClear..

[ericrk, 2015/12/04 19:14:31]

no longer needed when using map - but good point.

+  for (auto& vector : *array_of_vectors) {
+    vector.clear();
+  }
+}
+
+// Helper which checks if all sub arrays of a group are empty.
+template <typename T>
+bool AllVectorsEmpty(const T& array_of_vectors) {

[reveman, 2015/12/04 02:30:54]

ditto.

maybe std::for_each and std::find_if with lambdas are just as easy to read as
calls to these helper functions, don't know. just something to consider..

[ericrk, 2015/12/04 19:14:31]

Acknowledged.

+  for (const auto& vector : array_of_vectors) {
+    if (!vector.empty())
+      return false;
+  }
+  return true;
+}
+
+bool CompareTaskPriority(const TaskGraphWorkQueue::PrioritizedTask& a,
+                         const TaskGraphWorkQueue::PrioritizedTask& b) {
+  // In this system, numerically lower priority is run first.
+  return a.priority > b.priority;
+}
+
+class CompareTaskNamespacePriority {

[reveman, 2015/12/04 02:30:54]

nit: this code predates c++11 support in chromium. no need for a class anymore.
please change this to a CompareTaskNamespacePriority function and use a lambda
below when calling it. maybe you can even remove it completely and call
CompareTaskPriority directly in the lambda.

[ericrk, 2015/12/04 19:14:30]

Using a lambda directly is a lot more verbose at the call-site, and there are 4
call sites - I actually wrapped the original free-function in a class to clean
up the various uses.

Consider:

    std::make_heap(task_namespace.begin(), task_namespace.end(),
                   CompareTaskNamespacePriority(category));

Vs. the following with a free function:

    std::make_heap(task_namespace.begin(), task_namespace.end(),
                   [category](const TaskGraphWorkQueue::TaskNamespace* a,
                              const TaskGraphWorkQueue::TaskNamespace* b) {
                     CompareTaskNamespacePriority(category, a, b);
                   });

Or the following when calling directly:

    std::make_heap(task_namespace.begin(), task_namespace.end(),
                   [category](const TaskGraphWorkQueue::TaskNamespace* a,
                              const TaskGraphWorkQueue::TaskNamespace* b) {
                     return CompareTaskPriority(
                         a->ready_to_run_tasks.at(category_).front(),
                         b->ready_to_run_tasks.at(category_).front())
                   });

If it was just one case, I'd do the lambda, but at 4 uses the helper class
seemed cleaner? WDYT?

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

I think this would be OK with auto for arguments but it's perfectly fine to keep
the existing CompareTaskNamespacePriority class if you prefer that.
Yea, keeping the code in the current patch in this regard might be best.

+ public:
+  explicit CompareTaskNamespacePriority(uint16_t group) : group_(group) {}
+
+  bool operator()(const TaskGraphWorkQueue::TaskNamespace* a,
+                  const TaskGraphWorkQueue::TaskNamespace* b) {
+    DCHECK(group_ < TaskGraphWorkQueue::kMaxTaskGroups);
+    DCHECK(!a->ready_to_run_tasks[group_].empty());
+    DCHECK(!b->ready_to_run_tasks[group_].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[group_].front(),
+                               b->ready_to_run_tasks[group_].front());
+  }
+
+ private:
+  uint16_t group_;
+};
+}  // namespace
 
 TaskGraphWorkQueue::TaskNamespace::TaskNamespace() {}
 
@@ -25,6 +71,8 @@ NamespaceToken TaskGraphWorkQueue::GetNamespaceToken() {
 }
 
 void TaskGraphWorkQueue::ScheduleTasks(NamespaceToken token, TaskGraph* graph) {
+  DCHECK(ValidateGroups(graph));
+
   TaskNamespace& task_namespace = namespaces_[token];
 
   // First adjust number of dependencies to reflect completed tasks.
@@ -37,7 +85,7 @@ void TaskGraphWorkQueue::ScheduleTasks(NamespaceToken token, TaskGraph* graph) {
   }
 
   // Build new "ready to run" queue and remove nodes from old graph.
-  task_namespace.ready_to_run_tasks.clear();
+  ClearAllVectors(&task_namespace.ready_to_run_tasks);
   for (const TaskGraph::Node& node : graph->nodes) {
     // Remove any old nodes that are associated with this task. The result is
     // that the old graph is left with all nodes not present in this graph,
@@ -66,14 +114,15 @@ void TaskGraphWorkQueue::ScheduleTasks(NamespaceToken token, TaskGraph* graph) {
                   node.task) != task_namespace.running_tasks.end())
       continue;
 
-    task_namespace.ready_to_run_tasks.push_back(
-        PrioritizedTask(node.task, &task_namespace, node.priority));
+    task_namespace.ready_to_run_tasks[node.group].push_back(
+        PrioritizedTask(node.task, &task_namespace, node.group, node.priority));
   }
 
-  // Rearrange the elements in |ready_to_run_tasks| in such a way that they
-  // form a heap.
-  std::make_heap(task_namespace.ready_to_run_tasks.begin(),
-                 task_namespace.ready_to_run_tasks.end(), CompareTaskPriority);
+  // Rearrange the elements in each vector within |ready_to_run_tasks| in such a
+  // way that they form a heap.
+  for (auto& vector : task_namespace.ready_to_run_tasks) {

[reveman, 2015/12/04 02:30:54]

nit: s/vector/ready_to_run_tasks/ not a fan of naming variables based on the
container type as that makes it harder to change the container without making
the code confusing..

[ericrk, 2015/12/04 19:14:30]

Done.

+    std::make_heap(vector.begin(), vector.end(), CompareTaskPriority);
+  }
 
   // Swap task graph.
   task_namespace.graph.Swap(graph);
@@ -100,41 +149,52 @@ void TaskGraphWorkQueue::ScheduleTasks(NamespaceToken token, TaskGraph* graph) {
   }
 
   // Build new "ready to run" task namespaces queue.
-  ready_to_run_namespaces_.clear();
+  ClearAllVectors(&ready_to_run_namespaces_);
   for (auto& it : namespaces_) {

[reveman, 2015/12/04 02:30:53]

would be nice if this could be something like:

for (auto& namespace_it : namespaces_) {
  for (auto& ready_to_run_tasks_it : it.second.ready_to_run_tasks) {
    ...
  }
}

[ericrk, 2015/12/04 19:14:31]

Couldn't do that before (when  using an array), as we needed the group/category,
which we wouldn't get with range-based-for. Now when using map we have keys, so
this has been changed to that form.

-    if (!it.second.ready_to_run_tasks.empty())
-      ready_to_run_namespaces_.push_back(&it.second);
+    for (uint16_t group = 0; group < kMaxTaskGroups; ++group) {
+      if (!it.second.ready_to_run_tasks[group].empty())
+        ready_to_run_namespaces_[group].push_back(&it.second);
+    }
   }
 
   // Rearrange the task namespaces in |ready_to_run_namespaces| in such a
   // way that they form a heap.
-  std::make_heap(ready_to_run_namespaces_.begin(),
-                 ready_to_run_namespaces_.end(), CompareTaskNamespacePriority);
+  for (uint16_t group = 0; group < kMaxTaskGroups; ++group) {
+    std::make_heap(ready_to_run_namespaces_[group].begin(),
+                   ready_to_run_namespaces_[group].end(),
+                   CompareTaskNamespacePriority(group));
+  }
 }
 
-TaskGraphWorkQueue::PrioritizedTask TaskGraphWorkQueue::GetNextTaskToRun() {
-  DCHECK(!ready_to_run_namespaces_.empty());
-
-  // Take top priority TaskNamespace from |ready_to_run_namespaces_|.
-  std::pop_heap(ready_to_run_namespaces_.begin(),
-                ready_to_run_namespaces_.end(), CompareTaskNamespacePriority);
-  TaskNamespace* task_namespace = ready_to_run_namespaces_.back();
-  ready_to_run_namespaces_.pop_back();
-  DCHECK(!task_namespace->ready_to_run_tasks.empty());
-
-  // Take top priority task from |ready_to_run_tasks|.
-  std::pop_heap(task_namespace->ready_to_run_tasks.begin(),
-                task_namespace->ready_to_run_tasks.end(), CompareTaskPriority);
-  PrioritizedTask task = task_namespace->ready_to_run_tasks.back();
-  task_namespace->ready_to_run_tasks.pop_back();
-
-  // Add task namespace back to |ready_to_run_namespaces_| if not empty after
+TaskGraphWorkQueue::PrioritizedTask
+TaskGraphWorkQueue::GetNextTaskToRunForGroup(uint16_t group) {
+  DCHECK(group < kMaxTaskGroups);
+
+  TaskNamespace::Vector& namespaces_for_group = ready_to_run_namespaces_[group];

[reveman, 2015/12/04 02:30:54]

nit: s/namespaces_for_group/ready_to_run_namespaces_for_group/ or maybe just
ready_to_run_namespaces

[ericrk, 2015/12/04 19:14:31]

Done.

+  DCHECK(!namespaces_for_group.empty());
+
+  // Take top priority TaskNamespace from |namespaces_for_group|.
+  std::pop_heap(namespaces_for_group.begin(), namespaces_for_group.end(),
+                CompareTaskNamespacePriority(group));
+  TaskNamespace* task_namespace = namespaces_for_group.back();
+  namespaces_for_group.pop_back();
+
+  PrioritizedTask::Vector& tasks_for_group =

[reveman, 2015/12/04 02:30:54]

nit: s/tasks_for_group/ready_to_run_tasks_for_group/ or maybe just
ready_to_run_tasks

[ericrk, 2015/12/04 19:14:30]

Done.

+      task_namespace->ready_to_run_tasks[group];
+  DCHECK(!tasks_for_group.empty());
+
+  // Take top priority task from |tasks_for_group|.
+  std::pop_heap(tasks_for_group.begin(), tasks_for_group.end(),
+                CompareTaskPriority);
+  PrioritizedTask task = tasks_for_group.back();
+  tasks_for_group.pop_back();
+
+  // Add task namespace back to |namespaces_for_group| if not empty after
   // taking top priority task.
-  if (!task_namespace->ready_to_run_tasks.empty()) {
-    ready_to_run_namespaces_.push_back(task_namespace);
-    std::push_heap(ready_to_run_namespaces_.begin(),
-                   ready_to_run_namespaces_.end(),
-                   CompareTaskNamespacePriority);
+  if (!tasks_for_group.empty()) {
+    namespaces_for_group.push_back(task_namespace);
+    std::push_heap(namespaces_for_group.begin(), namespaces_for_group.end(),
+                   CompareTaskNamespacePriority(group));
   }
 
   // Add task to |running_tasks|.
@@ -143,6 +203,18 @@ TaskGraphWorkQueue::PrioritizedTask TaskGraphWorkQueue::GetNextTaskToRun() {
   return task;
 }
 
+TaskGraphWorkQueue::PrioritizedTask TaskGraphWorkQueue::GetNextTaskToRun() {
+  for (uint16_t group = 0; group < kMaxTaskGroups; ++group) {
+    if (!ready_to_run_namespaces_[group].empty()) {
+      return GetNextTaskToRunForGroup(group);
+    }
+  }
+
+  // This function must only be called when there is at least one task to run.
+  NOTREACHED();
+  return GetNextTaskToRunForGroup(0);
+}
+
 void TaskGraphWorkQueue::CompleteTask(const PrioritizedTask& completed_task) {
   TaskNamespace* task_namespace = completed_task.task_namespace;
   scoped_refptr<Task> task(completed_task.task);
@@ -164,19 +236,26 @@ void TaskGraphWorkQueue::CompleteTask(const PrioritizedTask& completed_task) {
     dependent_node.dependencies--;
     // Task is ready if it has no dependencies. Add it to |ready_to_run_tasks_|.
     if (!dependent_node.dependencies) {
-      bool was_empty = task_namespace->ready_to_run_tasks.empty();
-      task_namespace->ready_to_run_tasks.push_back(PrioritizedTask(
-          dependent_node.task, task_namespace, dependent_node.priority));
-      std::push_heap(task_namespace->ready_to_run_tasks.begin(),
-                     task_namespace->ready_to_run_tasks.end(),
+      PrioritizedTask::Vector& tasks_for_group =

[reveman, 2015/12/04 02:30:53]

nit: same as above, ready_to_run_tasks_for_group or just ready_to_run_tasks

[ericrk, 2015/12/04 19:14:31]

Done.

+          task_namespace->ready_to_run_tasks[dependent_node.group];
+
+      bool was_empty = tasks_for_group.empty();
+      tasks_for_group.push_back(
+          PrioritizedTask(dependent_node.task, task_namespace,
+                          dependent_node.group, dependent_node.priority));
+      std::push_heap(tasks_for_group.begin(), tasks_for_group.end(),
                      CompareTaskPriority);
+
       // Task namespace is ready if it has at least one ready to run task. Add
       // it to |ready_to_run_namespaces_| if it just become ready.
       if (was_empty) {
-        DCHECK(std::find(ready_to_run_namespaces_.begin(),
-                         ready_to_run_namespaces_.end(),
-                         task_namespace) == ready_to_run_namespaces_.end());
-        ready_to_run_namespaces_.push_back(task_namespace);
+        TaskNamespace::Vector& namespaces_for_group =

[reveman, 2015/12/04 02:30:53]

ditto

[ericrk, 2015/12/04 19:14:31]

Done.

+            ready_to_run_namespaces_[dependent_node.group];
+
+        DCHECK(std::find(namespaces_for_group.begin(),
+                         namespaces_for_group.end(),
+                         task_namespace) == namespaces_for_group.end());
+        namespaces_for_group.push_back(task_namespace);
       }
       ready_to_run_namespaces_has_heap_properties = false;
     }
@@ -185,9 +264,11 @@ void TaskGraphWorkQueue::CompleteTask(const PrioritizedTask& completed_task) {
   // Rearrange the task namespaces in |ready_to_run_namespaces_| in such a way
   // that they yet again form a heap.
   if (!ready_to_run_namespaces_has_heap_properties) {
-    std::make_heap(ready_to_run_namespaces_.begin(),
-                   ready_to_run_namespaces_.end(),
-                   CompareTaskNamespacePriority);
+    for (uint16_t group = 0; group < kMaxTaskGroups; ++group) {
+      std::make_heap(ready_to_run_namespaces_[group].begin(),
+                     ready_to_run_namespaces_[group].end(),
+                     CompareTaskNamespacePriority(group));
+    }
   }
 
   // Finally add task to |completed_tasks_|.
@@ -209,11 +290,21 @@ void TaskGraphWorkQueue::CollectCompletedTasks(NamespaceToken token,
 
   // Remove namespace if finished running tasks.
   DCHECK_EQ(0u, task_namespace.completed_tasks.size());
-  DCHECK_EQ(0u, task_namespace.ready_to_run_tasks.size());
+  DCHECK(AllVectorsEmpty(task_namespace.ready_to_run_tasks));
   DCHECK_EQ(0u, task_namespace.running_tasks.size());
   namespaces_.erase(it);
 }
 
+bool TaskGraphWorkQueue::HasReadyToRunTasks() const {
+  return !AllVectorsEmpty(ready_to_run_namespaces_);
+}
+
+bool TaskGraphWorkQueue::HasFinishedRunningTasksInNamespace(
+    const TaskNamespace* task_namespace) {
+  return task_namespace->running_tasks.empty() &&
+         AllVectorsEmpty(task_namespace->ready_to_run_tasks);
+}
+
 bool TaskGraphWorkQueue::DependencyMismatch(const TaskGraph* graph) {
   // Value storage will be 0-initialized.
   base::hash_map<const Task*, size_t> dependents;
@@ -228,4 +319,12 @@ bool TaskGraphWorkQueue::DependencyMismatch(const TaskGraph* graph) {
   return false;
 }
 
+bool TaskGraphWorkQueue::ValidateGroups(const TaskGraph* graph) {
+  for (const TaskGraph::Node& node : graph->nodes) {
+    if (node.group >= kMaxTaskGroups)
+      return false;
+  }
+  return true;
+}
+
 }  // namespace cc