cc: Add TaskGraphRunner sub-namespaces with task concurrency limits.

cc/resources/task_graph_runner.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_RESOURCES_TASK_GRAPH_RUNNER_H_
 #define CC_RESOURCES_TASK_GRAPH_RUNNER_H_
 
+#include <array>
 #include <map>
 #include <vector>
 
 #include "base/logging.h"
 #include "base/memory/ref_counted.h"
 #include "base/synchronization/condition_variable.h"
 #include "cc/base/cc_export.h"
 
 namespace cc {
 
@@ skipping 28 matching lines @@
       explicit TaskComparator(const Task* task) : task_(task) {}
 
       bool operator()(const Node& node) const { return node.task == task_; }
 
      private:
       const Task* task_;
     };
 
     typedef std::vector<Node> Vector;
 
-    Node(Task* task, unsigned priority, size_t dependencies)
-        : task(task), priority(priority), dependencies(dependencies) {}
+    Node(Task* task,
+         unsigned priority,

[danakj, 2015/02/23 18:45:01]

did git cl format do this? it seems to have disabled bin packing in this
scenario now..? :(

+         size_t dependencies,
+         int sub_namespace,
+         int max_concurrent_tasks)
+        : task(task),
+          priority(priority),
+          dependencies(dependencies),
+          sub_namespace(sub_namespace),
+          max_concurrent_tasks(max_concurrent_tasks) {}
 
     Task* task;
     unsigned priority;
     size_t dependencies;
+    int sub_namespace;
+    int max_concurrent_tasks;
   };
 
   struct Edge {
     typedef std::vector<Edge> Vector;
 
     Edge(const Task* task, Task* dependent)
         : task(task), dependent(dependent) {}
 
     const Task* task;
     Task* dependent;
@@ skipping 62 matching lines @@
 
   // Signals the Run method to return when it becomes idle. It will continue to
   // process tasks and future tasks as long as they are scheduled.
   // Warning: if the TaskGraphRunner remains busy, it may never quit.
   void Shutdown();
 
  private:
   struct PrioritizedTask {
     typedef std::vector<PrioritizedTask> Vector;
 
-    PrioritizedTask(Task* task, unsigned priority)
-        : task(task), priority(priority) {}
+    PrioritizedTask(Task* task, unsigned priority, int max_concurrent_tasks)
+        : task(task),
+          priority(priority),
+          max_concurrent_tasks(max_concurrent_tasks) {}
 
     Task* task;
     unsigned priority;
+    int max_concurrent_tasks;
   };
 
   typedef std::vector<const Task*> TaskVector;
 
+  struct TaskNamespace;
+
+  struct TaskSubNamespace {
+    typedef std::vector<TaskSubNamespace*> Vector;

[danakj, 2015/02/23 18:45:01]

prefer using instead of typedef 

+
+    TaskSubNamespace();
+    ~TaskSubNamespace();
+    bool IsReadyToRun() const;
+
+    // Task namespace this belongs to.
+    TaskNamespace* task_namespace;
+
+    bool is_in_ready_sub_namespaces;
+
+    // Number of currently running tasks in this sub namespace.
+    int running_task_count;
+
+    // Ordered set of tasks that are ready to run.
+    PrioritizedTask::Vector ready_to_run_tasks;
+  };
+
   struct TaskNamespace {
     typedef std::vector<TaskNamespace*> Vector;
 
+    static const int kNumberOfSubNamespaces = 2;

[danakj, 2015/02/23 18:45:01]

this 2 looks pretty magical here, is it possible to have an enum of
subnamespaces or something so it can be tied to the declaration of them?

+    static const int kDefaultSubNamespace = 0;

[danakj, 2015/02/23 18:45:01]

There's at least 2 constants with this name in this CL, in different class
namespaces. This seems.. complicated? Can things be consolidated somehow?

+
     TaskNamespace();
     ~TaskNamespace();
 
     // Current task graph.
     TaskGraph graph;
 
-    // Ordered set of tasks that are ready to run.
-    PrioritizedTask::Vector ready_to_run_tasks;
+    typedef std::array<TaskSubNamespace, kNumberOfSubNamespaces>

[danakj, 2015/02/23 18:45:01]

std::array is c++11 library feature no? (ie can't be used yet)

[danakj, 2015/02/23 18:45:01]

using

+        SubNamespaceArray;
+    SubNamespaceArray sub_namespaces;
 
     // Completed tasks not yet collected by origin thread.
     Task::Vector completed_tasks;
 
     // This set contains all currently running tasks.
     TaskVector running_tasks;
   };
 
   typedef std::map<int, TaskNamespace> TaskNamespaceMap;
 
   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) {
+  static bool CompareTaskSubNamespacePriority(const TaskSubNamespace* a,
+                                              const TaskSubNamespace* 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());
   }
 
   static bool HasFinishedRunningTasksInNamespace(
       const TaskNamespace* task_namespace) {
-    return task_namespace->running_tasks.empty() &&
-           task_namespace->ready_to_run_tasks.empty();
+    if (!task_namespace->running_tasks.empty())
+      return false;
+    for (const TaskSubNamespace& sub_namespace :
+         task_namespace->sub_namespaces) {
+      if (!sub_namespace.ready_to_run_tasks.empty())
+        return false;
+    }
+    return true;
   }
 
   // Run next task. Caller must acquire |lock_| prior to calling this function
   // and make sure at least one task is ready to run.
   void RunTaskWithLockAcquired();
 
   // This lock protects all members of this class. Do not read or modify
   // anything without holding this lock. Do not block while holding this lock.
   mutable base::Lock lock_;
 
   // Condition variable that is waited on by Run() until new tasks are ready to
   // run or shutdown starts.
   base::ConditionVariable has_ready_to_run_tasks_cv_;
 
   // Condition variable that is waited on by origin threads until a namespace
   // has finished running all associated tasks.
   base::ConditionVariable has_namespaces_with_finished_running_tasks_cv_;
 
   // Provides a unique id to each NamespaceToken.
   int next_namespace_id_;
 
   // This set contains all namespaces with pending, running or completed tasks
   // not yet collected.
   TaskNamespaceMap namespaces_;
 
-  // Ordered set of task namespaces that have ready to run tasks.
-  TaskNamespace::Vector ready_to_run_namespaces_;
+  // Ordered set of task sub namespaces that have ready to run tasks.
+  TaskSubNamespace::Vector ready_to_run_sub_namespaces_;
 
   // Set during shutdown. Tells Run() to return when no more tasks are pending.
   bool shutdown_;
 
   DISALLOW_COPY_AND_ASSIGN(TaskGraphRunner);
 };
 
 }  // namespace cc
 
 #endif  // CC_RESOURCES_TASK_GRAPH_RUNNER_H_