TaskGraphRunner Group support

cc/raster/task_graph_work_queue.h

 // 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.
 
 #ifndef CC_RASTER_TASK_GRAPH_WORK_QUEUE_H_
 #define CC_RASTER_TASK_GRAPH_WORK_QUEUE_H_
 
 #include <map>
 #include <vector>
 
 #include "cc/base/cc_export.h"
 #include "cc/raster/task_graph_runner.h"
 
 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 groups. Tasks from a single graph may
+// be put into different groups, each of which is prioritized independently
+// from the others. It is up to the implementation of TaskGraphRunner to
+// define the meaning of the groups and handle them appropriately.
 class CC_EXPORT TaskGraphWorkQueue {
  public:
+  // This value is chosen as the max needed at the moment.
+  enum : uint16_t { kMaxTaskGroups = 3 };

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

hm, not a huge fan of this. if this is going to be only 2 or 3 values then I'd
suggest we just use std::map as that would be consistent with how we handle
TaskNamespaces and it resulted in cleaner code that was actually performing a
bit better in the common case

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

ok - heh... I have that code 2 or 3 CLs back in the history :D - changed to this
as I worried about the cost of map doing dynamic allocations - but for 2 or 3
values this is probably fine.

+
   struct TaskNamespace;
 
   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 group,
+                    uint16_t priority)
+        : task(task),
+          task_namespace(task_namespace),
+          group(group),
+          priority(priority) {}
 
     Task* task;
     TaskNamespace* task_namespace;
-    size_t priority;
+    uint16_t group;
+    uint16_t priority;
   };
 
   // Helper classes and static methods used by dependent classes.
   struct TaskNamespace {
     typedef std::vector<TaskNamespace*> Vector;
 
     TaskNamespace();
     ~TaskNamespace();
 
     // Current task graph.
     TaskGraph graph;
 
-    // Ordered set of tasks that are ready to run.
-    PrioritizedTask::Vector ready_to_run_tasks;
+    // One ordered set of tasks that are ready to run for each group.
+    PrioritizedTask::Vector ready_to_run_tasks[kMaxTaskGroups];
 
     // Completed tasks not yet collected by origin thread.
     Task::Vector completed_tasks;
 
     // This set contains all currently running tasks.
     Task::Vector running_tasks;
   };
 
   TaskGraphWorkQueue();
   virtual ~TaskGraphWorkQueue();
 
   // Gets a NamespaceToken which is guaranteed to be unique within this
   // TaskGraphWorkQueue.
   NamespaceToken GetNamespaceToken();
 
   // Updates a TaskNamespace with a new TaskGraph to run. This cancels any
   // previous tasks in the graph being replaced.
   void ScheduleTasks(NamespaceToken token, TaskGraph* graph);
 
-  // Returns the next task to run paired with its namespace.
+  // Returns the next task to run. Treats group as a secondary priority (group
+  // 0 runs before group 1).
   PrioritizedTask GetNextTaskToRun();

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

Is this the only code in TaskGraphWorkQueue that treats group as a priority? In
that case I'd suggest we force the higher level TGR implementation to implement
it and leave this class completely free of interpreting the meaning of |group|.

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

sgtm

 
+  // Returns the next task to run for the given group.
+  PrioritizedTask GetNextTaskToRunForGroup(uint16_t group);
+
   // Marks a task as completed, adding it to its namespace's list of completed
   // tasks and updating the list of |ready_to_run_namespaces|.
   void CompleteTask(const PrioritizedTask& completed_task);
 
   // Helper which populates a vector of completed tasks from the provided
   // namespace.
   void CollectCompletedTasks(NamespaceToken token,
                              Task::Vector* completed_tasks);
 
   // Helper which returns the raw TaskNamespace* for the given token. Used to
   // allow callers to re-use a TaskNamespace*, reducing the number of lookups
   // needed.
   TaskNamespace* GetNamespaceForToken(NamespaceToken token) {
     auto it = namespaces_.find(token);
     if (it == namespaces_.end())
       return nullptr;
     return &it->second;
   }
 
   static bool HasFinishedRunningTasksInNamespace(
-      const TaskNamespace* task_namespace) {
-    return task_namespace->running_tasks.empty() &&
-           task_namespace->ready_to_run_tasks.empty();
+      const TaskNamespace* task_namespace);
+
+  bool HasReadyToRunTasks() const;
+
+  bool HasReadyToRunTasksForGroup(uint16_t group) const {
+    DCHECK(group < kMaxTaskGroups);
+    return ready_to_run_namespaces_[group].empty();
   }
 
-  bool HasReadyToRunTasks() const { return !ready_to_run_namespaces_.empty(); }
-
   bool HasAnyNamespaces() const { return !namespaces_.empty(); }
 
   bool HasFinishedRunningTasksInAllNamespaces() {
     return std::find_if(
                namespaces_.begin(), namespaces_.end(),
                [](const TaskNamespaceMap::value_type& entry) {
                  return !HasFinishedRunningTasksInNamespace(&entry.second);
                }) == namespaces_.end();
   }
 
   // Helper function which ensures that graph dependencies were correctly
   // configured.
   static bool DependencyMismatch(const TaskGraph* graph);
 
  private:
   // Helper class used to provide NamespaceToken comparison to TaskNamespaceMap.
   class CompareToken {
    public:
     bool operator()(const NamespaceToken& lhs,
                     const NamespaceToken& rhs) const {
       return lhs.id_ < rhs.id_;
     }
   };
 
-  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());
-  }
+  // Validates that no group in a graph exceeds |kMaxTaskGroups|.
+  static bool ValidateGroups(const TaskGraph* graph);
 
   using TaskNamespaceMap =
       std::map<NamespaceToken, TaskNamespace, CompareToken>;
 
   TaskNamespaceMap namespaces_;
-  TaskNamespace::Vector ready_to_run_namespaces_;
+
+  // A vector of ready to run namespaces for each group.
+  TaskNamespace::Vector ready_to_run_namespaces_[kMaxTaskGroups];
 
   // Provides a unique id to each NamespaceToken.
   int next_namespace_id_;
 };
 
 }  // namespace cc
 
 #endif  // CC_RASTER_TASK_GRAPH_WORK_QUEUE_H_