| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "cc/raster/task_graph_work_queue.h" | 5 #include "cc/raster/task_graph_work_queue.h" |
| 6 | 6 |
| 7 #include <stddef.h> | 7 #include <stddef.h> |
| 8 #include <stdint.h> | 8 #include <stdint.h> |
| 9 | 9 |
| 10 #include <algorithm> | 10 #include <algorithm> |
| (...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 90 | 90 |
| 91 // Task is not ready to run if dependencies are not yet satisfied. | 91 // Task is not ready to run if dependencies are not yet satisfied. |
| 92 if (node.dependencies) | 92 if (node.dependencies) |
| 93 continue; | 93 continue; |
| 94 | 94 |
| 95 // Skip if already finished running task. | 95 // Skip if already finished running task. |
| 96 if (node.task->HasFinishedRunning()) | 96 if (node.task->HasFinishedRunning()) |
| 97 continue; | 97 continue; |
| 98 | 98 |
| 99 // Skip if already running. | 99 // Skip if already running. |
| 100 const auto& running_tasks_for_category = | 100 if (std::find(task_namespace.running_tasks.begin(), |
| 101 task_namespace.running_tasks.find(node.category); | 101 task_namespace.running_tasks.end(), |
| 102 if (running_tasks_for_category != task_namespace.running_tasks.cend() && | 102 node.task) != task_namespace.running_tasks.end()) |
| 103 std::find(running_tasks_for_category->second.cbegin(), | |
| 104 running_tasks_for_category->second.cend(), | |
| 105 node.task) != running_tasks_for_category->second.cend()) | |
| 106 continue; | 103 continue; |
| 107 | 104 |
| 108 task_namespace.ready_to_run_tasks[node.category].push_back(PrioritizedTask( | 105 task_namespace.ready_to_run_tasks[node.category].push_back(PrioritizedTask( |
| 109 node.task, &task_namespace, node.category, node.priority)); | 106 node.task, &task_namespace, node.category, node.priority)); |
| 110 } | 107 } |
| 111 | 108 |
| 112 // Rearrange the elements in each vector within |ready_to_run_tasks| in such a | 109 // Rearrange the elements in each vector within |ready_to_run_tasks| in such a |
| 113 // way that they form a heap. | 110 // way that they form a heap. |
| 114 for (auto& it : task_namespace.ready_to_run_tasks) { | 111 for (auto& it : task_namespace.ready_to_run_tasks) { |
| 115 auto& ready_to_run_tasks = it.second; | 112 auto& ready_to_run_tasks = it.second; |
| 116 std::make_heap(ready_to_run_tasks.begin(), ready_to_run_tasks.end(), | 113 std::make_heap(ready_to_run_tasks.begin(), ready_to_run_tasks.end(), |
| 117 CompareTaskPriority); | 114 CompareTaskPriority); |
| 118 } | 115 } |
| 119 | 116 |
| 120 // Swap task graph. | 117 // Swap task graph. |
| 121 task_namespace.graph.Swap(graph); | 118 task_namespace.graph.Swap(graph); |
| 122 | 119 |
| 123 // Determine what tasks in old graph need to be canceled. | 120 // Determine what tasks in old graph need to be canceled. |
| 124 for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin(); | 121 for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin(); |
| 125 it != graph->nodes.end(); ++it) { | 122 it != graph->nodes.end(); ++it) { |
| 126 TaskGraph::Node& node = *it; | 123 TaskGraph::Node& node = *it; |
| 127 | 124 |
| 128 // Skip if already finished running task. | 125 // Skip if already finished running task. |
| 129 if (node.task->HasFinishedRunning()) | 126 if (node.task->HasFinishedRunning()) |
| 130 continue; | 127 continue; |
| 131 | 128 |
| 132 // Skip if already running. | 129 // Skip if already running. |
| 133 const auto& running_tasks_for_category = | 130 if (std::find(task_namespace.running_tasks.begin(), |
| 134 task_namespace.running_tasks.find(node.category); | 131 task_namespace.running_tasks.end(), |
| 135 if (running_tasks_for_category != task_namespace.running_tasks.cend() && | 132 node.task) != task_namespace.running_tasks.end()) |
| 136 std::find(running_tasks_for_category->second.cbegin(), | |
| 137 running_tasks_for_category->second.cend(), | |
| 138 node.task) != running_tasks_for_category->second.cend()) | |
| 139 continue; | 133 continue; |
| 140 | 134 |
| 141 DCHECK(std::find(task_namespace.completed_tasks.begin(), | 135 DCHECK(std::find(task_namespace.completed_tasks.begin(), |
| 142 task_namespace.completed_tasks.end(), | 136 task_namespace.completed_tasks.end(), |
| 143 node.task) == task_namespace.completed_tasks.end()); | 137 node.task) == task_namespace.completed_tasks.end()); |
| 144 task_namespace.completed_tasks.push_back(node.task); | 138 task_namespace.completed_tasks.push_back(node.task); |
| 145 } | 139 } |
| 146 | 140 |
| 147 // Build new "ready to run" task namespaces queue. | 141 // Build new "ready to run" task namespaces queue. |
| 148 for (auto& ready_to_run_namespaces_it : ready_to_run_namespaces_) { | 142 for (auto& ready_to_run_namespaces_it : ready_to_run_namespaces_) { |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 194 // Add task namespace back to |ready_to_run_namespaces| if not empty after | 188 // Add task namespace back to |ready_to_run_namespaces| if not empty after |
| 195 // taking top priority task. | 189 // taking top priority task. |
| 196 if (!ready_to_run_tasks.empty()) { | 190 if (!ready_to_run_tasks.empty()) { |
| 197 ready_to_run_namespaces.push_back(task_namespace); | 191 ready_to_run_namespaces.push_back(task_namespace); |
| 198 std::push_heap(ready_to_run_namespaces.begin(), | 192 std::push_heap(ready_to_run_namespaces.begin(), |
| 199 ready_to_run_namespaces.end(), | 193 ready_to_run_namespaces.end(), |
| 200 CompareTaskNamespacePriority(category)); | 194 CompareTaskNamespacePriority(category)); |
| 201 } | 195 } |
| 202 | 196 |
| 203 // Add task to |running_tasks|. | 197 // Add task to |running_tasks|. |
| 204 task_namespace->running_tasks[category].push_back(task.task); | 198 task_namespace->running_tasks.push_back(task.task); |
| 205 | 199 |
| 206 return task; | 200 return task; |
| 207 } | 201 } |
| 208 | 202 |
| 209 void TaskGraphWorkQueue::CompleteTask(const PrioritizedTask& completed_task) { | 203 void TaskGraphWorkQueue::CompleteTask(const PrioritizedTask& completed_task) { |
| 210 TaskNamespace* task_namespace = completed_task.task_namespace; | 204 TaskNamespace* task_namespace = completed_task.task_namespace; |
| 211 scoped_refptr<Task> task(completed_task.task); | 205 scoped_refptr<Task> task(completed_task.task); |
| 212 uint16_t category = completed_task.category; | |
| 213 | 206 |
| 214 // Remove task from |running_tasks|. | 207 // Remove task from |running_tasks|. |
| 215 auto& running_tasks_for_category = task_namespace->running_tasks[category]; | 208 auto it = std::find(task_namespace->running_tasks.begin(), |
| 216 auto it = std::find(running_tasks_for_category.begin(), | 209 task_namespace->running_tasks.end(), task); |
| 217 running_tasks_for_category.end(), task); | 210 DCHECK(it != task_namespace->running_tasks.end()); |
| 218 DCHECK(it != running_tasks_for_category.end()); | 211 std::swap(*it, task_namespace->running_tasks.back()); |
| 219 std::swap(*it, running_tasks_for_category.back()); | 212 task_namespace->running_tasks.pop_back(); |
| 220 running_tasks_for_category.pop_back(); | |
| 221 | 213 |
| 222 // Now iterate over all dependents to decrement dependencies and check if they | 214 // Now iterate over all dependents to decrement dependencies and check if they |
| 223 // are ready to run. | 215 // are ready to run. |
| 224 bool ready_to_run_namespaces_has_heap_properties = true; | 216 bool ready_to_run_namespaces_has_heap_properties = true; |
| 225 for (DependentIterator it(&task_namespace->graph, task.get()); it; ++it) { | 217 for (DependentIterator it(&task_namespace->graph, task.get()); it; ++it) { |
| 226 TaskGraph::Node& dependent_node = *it; | 218 TaskGraph::Node& dependent_node = *it; |
| 227 | 219 |
| 228 DCHECK_LT(0u, dependent_node.dependencies); | 220 DCHECK_LT(0u, dependent_node.dependencies); |
| 229 dependent_node.dependencies--; | 221 dependent_node.dependencies--; |
| 230 // Task is ready if it has no dependencies. Add it to |ready_to_run_tasks_|. | 222 // Task is ready if it has no dependencies. Add it to |ready_to_run_tasks_|. |
| (...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 278 | 270 |
| 279 TaskNamespace& task_namespace = it->second; | 271 TaskNamespace& task_namespace = it->second; |
| 280 | 272 |
| 281 DCHECK_EQ(0u, completed_tasks->size()); | 273 DCHECK_EQ(0u, completed_tasks->size()); |
| 282 completed_tasks->swap(task_namespace.completed_tasks); | 274 completed_tasks->swap(task_namespace.completed_tasks); |
| 283 if (!HasFinishedRunningTasksInNamespace(&task_namespace)) | 275 if (!HasFinishedRunningTasksInNamespace(&task_namespace)) |
| 284 return; | 276 return; |
| 285 | 277 |
| 286 // Remove namespace if finished running tasks. | 278 // Remove namespace if finished running tasks. |
| 287 DCHECK_EQ(0u, task_namespace.completed_tasks.size()); | 279 DCHECK_EQ(0u, task_namespace.completed_tasks.size()); |
| 288 DCHECK(HasFinishedRunningTasksInNamespace(&task_namespace)); | 280 DCHECK(!HasReadyToRunTasksInNamespace(&task_namespace)); |
| 281 DCHECK_EQ(0u, task_namespace.running_tasks.size()); |
| 289 namespaces_.erase(it); | 282 namespaces_.erase(it); |
| 290 } | 283 } |
| 291 | 284 |
| 292 bool TaskGraphWorkQueue::DependencyMismatch(const TaskGraph* graph) { | 285 bool TaskGraphWorkQueue::DependencyMismatch(const TaskGraph* graph) { |
| 293 // Value storage will be 0-initialized. | 286 // Value storage will be 0-initialized. |
| 294 std::unordered_map<const Task*, size_t> dependents; | 287 std::unordered_map<const Task*, size_t> dependents; |
| 295 for (const TaskGraph::Edge& edge : graph->edges) | 288 for (const TaskGraph::Edge& edge : graph->edges) |
| 296 dependents[edge.dependent]++; | 289 dependents[edge.dependent]++; |
| 297 | 290 |
| 298 for (const TaskGraph::Node& node : graph->nodes) { | 291 for (const TaskGraph::Node& node : graph->nodes) { |
| 299 if (dependents[node.task] != node.dependencies) | 292 if (dependents[node.task] != node.dependencies) |
| 300 return true; | 293 return true; |
| 301 } | 294 } |
| 302 | 295 |
| 303 return false; | 296 return false; |
| 304 } | 297 } |
| 305 | 298 |
| 306 } // namespace cc | 299 } // namespace cc |
| OLD | NEW |