TaskGraphRunner Group support

cc/raster/task_graph_work_queue.cc

 // Copyright 2014 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/raster/task_graph_work_queue.h"
 
 #include <algorithm>
 #include <utility>
 
 #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() {}
 
 TaskGraphWorkQueue::TaskNamespace::~TaskNamespace() {}
 
 TaskGraphWorkQueue::TaskGraphWorkQueue() : next_namespace_id_(1) {}
 TaskGraphWorkQueue::~TaskGraphWorkQueue() {}
 
 NamespaceToken TaskGraphWorkQueue::GetNamespaceToken() {
   NamespaceToken token(next_namespace_id_++);
   DCHECK(namespaces_.find(token) == namespaces_.end());
   return token;
 }
 
 void TaskGraphWorkQueue::ScheduleTasks(NamespaceToken token, TaskGraph* graph) {
+  DCHECK(ValidateGroups(graph));
+
   TaskNamespace& task_namespace = namespaces_[token];
 
   // First adjust number of dependencies to reflect completed tasks.
   for (const scoped_refptr<Task>& task : task_namespace.completed_tasks) {
     for (DependentIterator node_it(graph, task.get()); node_it; ++node_it) {
       TaskGraph::Node& node = *node_it;
       DCHECK_LT(0u, node.dependencies);
       node.dependencies--;
     }
   }
 
   // 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,
     // which we use below to determine what tasks need to be canceled.
     TaskGraph::Node::Vector::iterator old_it = std::find_if(
         task_namespace.graph.nodes.begin(), task_namespace.graph.nodes.end(),
         [node](const TaskGraph::Node& other) {
           return node.task == other.task;
         });
     if (old_it != task_namespace.graph.nodes.end()) {
       std::swap(*old_it, task_namespace.graph.nodes.back());
       task_namespace.graph.nodes.pop_back();
     }
 
     // Task is not ready to run if dependencies are not yet satisfied.
     if (node.dependencies)
       continue;
 
     // Skip if already finished running task.
     if (node.task->HasFinishedRunning())
       continue;
 
     // Skip if already running.
     if (std::find(task_namespace.running_tasks.begin(),
                   task_namespace.running_tasks.end(),
                   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);
 
   // Determine what tasks in old graph need to be canceled.
   for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin();
        it != graph->nodes.end(); ++it) {
     TaskGraph::Node& node = *it;
 
     // Skip if already finished running task.
     if (node.task->HasFinishedRunning())
       continue;
 
     // Skip if already running.
     if (std::find(task_namespace.running_tasks.begin(),
                   task_namespace.running_tasks.end(),
                   node.task) != task_namespace.running_tasks.end())
       continue;
 
     DCHECK(std::find(task_namespace.completed_tasks.begin(),
                      task_namespace.completed_tasks.end(),
                      node.task) == task_namespace.completed_tasks.end());
     task_namespace.completed_tasks.push_back(node.task);
   }
 
   // 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());
+TaskGraphWorkQueue::PrioritizedTask
+TaskGraphWorkQueue::GetNextTaskToRunForGroup(uint16_t group) {
+  DCHECK(group < kMaxTaskGroups);
 
-  // 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());
+  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 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();
+  // 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();
 
-  // Add task namespace back to |ready_to_run_namespaces_| if not empty after
+  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|.
   task_namespace->running_tasks.push_back(task.task);
 
   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);
 
   // Remove task from |running_tasks|.
   auto it = std::find(task_namespace->running_tasks.begin(),
                       task_namespace->running_tasks.end(), task);
   DCHECK(it != task_namespace->running_tasks.end());
   std::swap(*it, task_namespace->running_tasks.back());
   task_namespace->running_tasks.pop_back();
 
   // Now iterate over all dependents to decrement dependencies and check if they
   // are ready to run.
   bool ready_to_run_namespaces_has_heap_properties = true;
   for (DependentIterator it(&task_namespace->graph, task.get()); it; ++it) {
     TaskGraph::Node& dependent_node = *it;
 
     DCHECK_LT(0u, dependent_node.dependencies);
     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;
     }
   }
 
   // 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_|.
   task_namespace->completed_tasks.push_back(task);
 }
 
 void TaskGraphWorkQueue::CollectCompletedTasks(NamespaceToken token,
                                                Task::Vector* completed_tasks) {
   TaskNamespaceMap::iterator it = namespaces_.find(token);
   if (it == namespaces_.end())
     return;
 
   TaskNamespace& task_namespace = it->second;
 
   DCHECK_EQ(0u, completed_tasks->size());
   completed_tasks->swap(task_namespace.completed_tasks);
   if (!HasFinishedRunningTasksInNamespace(&task_namespace))
     return;
 
   // 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;
   for (const TaskGraph::Edge& edge : graph->edges)
     dependents[edge.dependent]++;
 
   for (const TaskGraph::Node& node : graph->nodes) {
     if (dependents[node.task] != node.dependencies)
       return true;
   }
 
   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