cc: Switch to vector based TaskGraph implementation.

cc/resources/task_graph_runner_perftest.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/resources/task_graph_runner.h"
 
 #include <vector>
 
 #include "base/time/time.h"
 #include "cc/base/completion_event.h"
@@ skipping 51 matching lines @@
                              int num_top_level_tasks,
                              int num_tasks,
                              int num_leaf_tasks) {
     PerfTaskImpl::Vector top_level_tasks;
     PerfTaskImpl::Vector tasks;
     PerfTaskImpl::Vector leaf_tasks;
     CreateTasks(num_top_level_tasks, &top_level_tasks);
     CreateTasks(num_tasks, &tasks);
     CreateTasks(num_leaf_tasks, &leaf_tasks);
 
+    // Avoid unnecessary heap allocations by reusing the same graph.
+    internal::TaskGraph graph;
+
     timer_.Reset();
     do {
-      internal::GraphNode::Map graph;
+      graph.Reset();
       BuildTaskGraph(top_level_tasks, tasks, leaf_tasks, &graph);
       timer_.NextLap();
     } while (!timer_.HasTimeLimitExpired());
 
     perf_test::PrintResult("build_task_graph",
                            "",
                            test_name,
                            timer_.LapsPerSecond(),
                            "runs/s",
                            true);
   }
 
   void RunScheduleTasksTest(const std::string& test_name,
                             int num_top_level_tasks,
                             int num_tasks,
                             int num_leaf_tasks) {
     PerfTaskImpl::Vector top_level_tasks;
     PerfTaskImpl::Vector tasks;
     PerfTaskImpl::Vector leaf_tasks;
     CreateTasks(num_top_level_tasks, &top_level_tasks);
     CreateTasks(num_tasks, &tasks);
     CreateTasks(num_leaf_tasks, &leaf_tasks);
 
+    // Avoid unnecessary heap allocations by reusing the same graph and
+    // completed tasks vector.
+    internal::TaskGraph graph;
+    internal::Task::Vector completed_tasks;
+
     timer_.Reset();
     do {
-      internal::GraphNode::Map graph;
+      graph.Reset();
       BuildTaskGraph(top_level_tasks, tasks, leaf_tasks, &graph);
       task_graph_runner_->SetTaskGraph(namespace_token_, &graph);
       // Shouldn't be any tasks to collect as we reschedule the same set
       // of tasks.
-      DCHECK_EQ(0u, CollectCompletedTasks());
+      DCHECK_EQ(0u, CollectCompletedTasks(&completed_tasks));
       timer_.NextLap();
     } while (!timer_.HasTimeLimitExpired());
 
-    internal::GraphNode::Map empty;
+    internal::TaskGraph empty;
     task_graph_runner_->SetTaskGraph(namespace_token_, &empty);
-    CollectCompletedTasks();
+    CollectCompletedTasks(&completed_tasks);
 
     perf_test::PrintResult("schedule_tasks",
                            "",
                            test_name,
                            timer_.LapsPerSecond(),
                            "runs/s",
                            true);
   }
 
   void RunScheduleAlternateTasksTest(const std::string& test_name,
                                      int num_top_level_tasks,
                                      int num_tasks,
                                      int num_leaf_tasks) {
     const int kNumVersions = 2;
     PerfTaskImpl::Vector top_level_tasks[kNumVersions];
     PerfTaskImpl::Vector tasks[kNumVersions];
     PerfTaskImpl::Vector leaf_tasks[kNumVersions];
     for (int i = 0; i < kNumVersions; ++i) {
       CreateTasks(num_top_level_tasks, &top_level_tasks[i]);
       CreateTasks(num_tasks, &tasks[i]);
       CreateTasks(num_leaf_tasks, &leaf_tasks[i]);
     }
 
+    // Avoid unnecessary heap allocations by reusing the same graph and
+    // completed tasks vector.
+    internal::TaskGraph graph;
+    internal::Task::Vector completed_tasks;
+
     int count = 0;
     timer_.Reset();
     do {
-      internal::GraphNode::Map graph;
+      graph.Reset();
       BuildTaskGraph(top_level_tasks[count % kNumVersions],
                      tasks[count % kNumVersions],
                      leaf_tasks[count % kNumVersions],
                      &graph);
       task_graph_runner_->SetTaskGraph(namespace_token_, &graph);
-      CollectCompletedTasks();
+      CollectCompletedTasks(&completed_tasks);
+      completed_tasks.clear();
       ++count;
       timer_.NextLap();
     } while (!timer_.HasTimeLimitExpired());
 
-    internal::GraphNode::Map empty;
+    internal::TaskGraph empty;
     task_graph_runner_->SetTaskGraph(namespace_token_, &empty);
-    CollectCompletedTasks();
+    CollectCompletedTasks(&completed_tasks);
 
     perf_test::PrintResult("schedule_alternate_tasks",
                            "",
                            test_name,
                            timer_.LapsPerSecond(),
                            "runs/s",
                            true);
   }
 
   void RunScheduleAndExecuteTasksTest(const std::string& test_name,
                                       int num_top_level_tasks,
                                       int num_tasks,
                                       int num_leaf_tasks) {
     PerfTaskImpl::Vector top_level_tasks;
     PerfTaskImpl::Vector tasks;
     PerfTaskImpl::Vector leaf_tasks;
     CreateTasks(num_top_level_tasks, &top_level_tasks);
     CreateTasks(num_tasks, &tasks);
     CreateTasks(num_leaf_tasks, &leaf_tasks);
 
+    // Avoid unnecessary heap allocations by reusing the same graph and
+    // completed tasks vector.
+    internal::TaskGraph graph;
+    internal::Task::Vector completed_tasks;
+
     timer_.Reset();
     do {
-      internal::GraphNode::Map graph;
+      graph.Reset();
       BuildTaskGraph(top_level_tasks, tasks, leaf_tasks, &graph);
       task_graph_runner_->SetTaskGraph(namespace_token_, &graph);
       while (task_graph_runner_->RunTaskForTesting())
         continue;
-      CollectCompletedTasks();
+      CollectCompletedTasks(&completed_tasks);
+      completed_tasks.clear();
       ResetTasks(&top_level_tasks);
       ResetTasks(&tasks);
       ResetTasks(&leaf_tasks);
       timer_.NextLap();
     } while (!timer_.HasTimeLimitExpired());
 
     perf_test::PrintResult(
         "execute_tasks", "", test_name, timer_.LapsPerSecond(), "runs/s", true);
   }
 
  private:
   void CreateTasks(int num_tasks, PerfTaskImpl::Vector* tasks) {
     for (int i = 0; i < num_tasks; ++i)
       tasks->push_back(make_scoped_refptr(new PerfTaskImpl));
   }
 
   void ResetTasks(PerfTaskImpl::Vector* tasks) {
     for (PerfTaskImpl::Vector::iterator it = tasks->begin(); it != tasks->end();
          ++it) {
       PerfTaskImpl* task = it->get();
       task->Reset();
     }
   }
 
   void BuildTaskGraph(const PerfTaskImpl::Vector& top_level_tasks,
                       const PerfTaskImpl::Vector& tasks,
                       const PerfTaskImpl::Vector& leaf_tasks,
-                      internal::GraphNode::Map* graph) {
-    typedef std::vector<internal::GraphNode*> NodeVector;
+                      internal::TaskGraph* graph) {
+    DCHECK(graph->nodes.empty());
+    DCHECK(graph->edges.empty());
 
-    NodeVector top_level_nodes;
-    top_level_nodes.reserve(top_level_tasks.size());
-    for (PerfTaskImpl::Vector::const_iterator it = top_level_tasks.begin();
-         it != top_level_tasks.end();
-         ++it) {
-      internal::Task* top_level_task = it->get();
-      scoped_ptr<internal::GraphNode> top_level_node(
-          new internal::GraphNode(top_level_task, 0u));
-
-      top_level_nodes.push_back(top_level_node.get());
-      graph->set(top_level_task, top_level_node.Pass());
-    }
-
-    NodeVector leaf_nodes;
-    leaf_nodes.reserve(leaf_tasks.size());
     for (PerfTaskImpl::Vector::const_iterator it = leaf_tasks.begin();
          it != leaf_tasks.end();
          ++it) {
-      internal::Task* leaf_task = it->get();
-      scoped_ptr<internal::GraphNode> leaf_node(
-          new internal::GraphNode(leaf_task, 0u));
-
-      leaf_nodes.push_back(leaf_node.get());
-      graph->set(leaf_task, leaf_node.Pass());
+      graph->nodes.push_back(internal::TaskGraph::Node(it->get(), 0u, 0u));
     }
 
     for (PerfTaskImpl::Vector::const_iterator it = tasks.begin();
          it != tasks.end();
          ++it) {
-      internal::Task* task = it->get();
-      scoped_ptr<internal::GraphNode> node(new internal::GraphNode(task, 0u));
+      graph->nodes.push_back(
+          internal::TaskGraph::Node(it->get(), 0u, leaf_tasks.size()));
 
-      for (NodeVector::iterator node_it = top_level_nodes.begin();
-           node_it != top_level_nodes.end();
-           ++node_it) {
-        internal::GraphNode* top_level_node = *node_it;
-        node->add_dependent(top_level_node);
-        top_level_node->add_dependency();
+      for (PerfTaskImpl::Vector::const_iterator leaf_it = leaf_tasks.begin();
+           leaf_it != leaf_tasks.end();
+           ++leaf_it) {
+        graph->edges.push_back(
+            internal::TaskGraph::Edge(leaf_it->get(), it->get()));
       }
 
-      for (NodeVector::iterator node_it = leaf_nodes.begin();
-           node_it != leaf_nodes.end();
-           ++node_it) {
-        internal::GraphNode* leaf_node = *node_it;
-        leaf_node->add_dependent(node.get());
-        node->add_dependency();
+      for (PerfTaskImpl::Vector::const_iterator top_level_it =
+               top_level_tasks.begin();
+           top_level_it != top_level_tasks.end();
+           ++top_level_it) {
+        graph->edges.push_back(
+            internal::TaskGraph::Edge(it->get(), top_level_it->get()));
       }
+    }
 
-      graph->set(task, node.Pass());
+    for (PerfTaskImpl::Vector::const_iterator it = top_level_tasks.begin();
+         it != top_level_tasks.end();
+         ++it) {
+      graph->nodes.push_back(
+          internal::TaskGraph::Node(it->get(), 0u, tasks.size()));
     }
   }
 
-  size_t CollectCompletedTasks() {
-    internal::Task::Vector completed_tasks;
+  size_t CollectCompletedTasks(internal::Task::Vector* completed_tasks) {
+    DCHECK(completed_tasks->empty());
     task_graph_runner_->CollectCompletedTasks(namespace_token_,
-                                              &completed_tasks);
-    return completed_tasks.size();
+                                              completed_tasks);
+    return completed_tasks->size();
   }
 
   scoped_ptr<internal::TaskGraphRunner> task_graph_runner_;
   internal::NamespaceToken namespace_token_;
   LapTimer timer_;
 };
 
 TEST_F(TaskGraphRunnerPerfTest, BuildTaskGraph) {
   RunBuildTaskGraphTest("0_1_0", 0, 1, 0);
   RunBuildTaskGraphTest("0_32_0", 0, 32, 0);
@@ skipping 25 matching lines @@
   RunScheduleAndExecuteTasksTest("0_1_0", 0, 1, 0);
   RunScheduleAndExecuteTasksTest("0_32_0", 0, 32, 0);
   RunScheduleAndExecuteTasksTest("2_1_0", 2, 1, 0);
   RunScheduleAndExecuteTasksTest("2_32_0", 2, 32, 0);
   RunScheduleAndExecuteTasksTest("2_1_1", 2, 1, 1);
   RunScheduleAndExecuteTasksTest("2_32_1", 2, 32, 1);
 }
 
 }  // namespace
 }  // namespace cc