From 6c8c1fb881492c5b6739d60db6f4a7815f8de084 Mon Sep 17 00:00:00 2001 From: "reveman@chromium.org" Date: Tue, 18 Jun 2013 10:58:59 +0000 Subject: cc: Use run count instead of linear scan through dependencies to detect ready to run tasks. This improves SetTaskGraph() and general task execution performance. It's also a critical step towards implementing more efficient graph construction in derived RasterWorkerPool class. BUG=247677 Review URL: https://chromiumcodereview.appspot.com/17269002 git-svn-id: svn://svn.chromium.org/chrome/trunk/src@206927 0039d316-1c4b-4281-b951-d872f2087c98 --- cc/resources/worker_pool.cc | 110 +++++++++++++++++++++++--------------------- cc/resources/worker_pool.h | 33 +++++++++---- 2 files changed, 82 insertions(+), 61 deletions(-) (limited to 'cc') diff --git a/cc/resources/worker_pool.cc b/cc/resources/worker_pool.cc index ea66e4b0..98237e2 100644 --- a/cc/resources/worker_pool.cc +++ b/cc/resources/worker_pool.cc @@ -63,17 +63,6 @@ void WorkerPoolTask::DidComplete() { did_complete_ = true; } -bool WorkerPoolTask::IsReadyToRun() const { - // TODO(reveman): Use counter to improve performance. - for (TaskVector::const_reverse_iterator it = dependencies_.rbegin(); - it != dependencies_.rend(); ++it) { - WorkerPoolTask* dependency = it->get(); - if (!dependency->HasFinishedRunning()) - return false; - } - return true; -} - bool WorkerPoolTask::HasFinishedRunning() const { return did_run_; } @@ -211,11 +200,20 @@ void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) { { base::AutoLock lock(lock_); - // First remove all completed tasks from |new_pending_tasks|. + // First remove all completed tasks from |new_pending_tasks| and + // adjust number of dependencies. for (TaskDeque::iterator it = completed_tasks_.begin(); it != completed_tasks_.end(); ++it) { internal::WorkerPoolTask* task = it->get(); - new_pending_tasks.take_and_erase(task); + + scoped_ptr node = new_pending_tasks.take_and_erase(task); + if (node) { + for (GraphNode::Vector::const_iterator it = node->dependents().begin(); + it != node->dependents().end(); ++it) { + GraphNode* dependent_node = *it; + dependent_node->remove_dependency(); + } + } } // Move tasks not present in |new_pending_tasks| to |completed_tasks_|. @@ -240,9 +238,11 @@ void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) { } // Build new "ready to run" tasks queue. + // TODO(reveman): Create this queue when building the task graph instead. for (GraphNodeMap::iterator it = new_pending_tasks.begin(); it != new_pending_tasks.end(); ++it) { internal::WorkerPoolTask* task = it->first; + GraphNode* node = it->second; // Completed tasks should not exist in |new_pending_tasks|. DCHECK(!task->HasFinishedRunning()); @@ -251,9 +251,9 @@ void WorkerPool::Inner::SetTaskGraph(TaskGraph* graph) { // Note: This is only for debugging purposes. task->DidSchedule(); - DCHECK_EQ(0u, new_ready_to_run_tasks.count(it->second->priority())); - if (task->IsReadyToRun()) - new_ready_to_run_tasks[it->second->priority()] = task; + DCHECK_EQ(0u, new_ready_to_run_tasks.count(node->priority())); + if (!node->num_dependencies()) + new_ready_to_run_tasks[node->priority()] = task; } // Swap task sets. @@ -323,25 +323,25 @@ void WorkerPool::Inner::Run() { // This will mark task as finished running. task->DidRun(); - // Now iterate over all dependents to check if they are ready to run. + // Now iterate over all dependents to remove dependency and check + // if they are ready to run. scoped_ptr node = running_tasks_.take_and_erase(task.get()); if (node) { - typedef GraphNode::TaskVector TaskVector; - for (TaskVector::const_iterator it = node->dependents().begin(); + for (GraphNode::Vector::const_iterator it = node->dependents().begin(); it != node->dependents().end(); ++it) { - GraphNodeMap::iterator dependent_it = pending_tasks_.find(*it); - DCHECK(dependent_it != pending_tasks_.end()); + GraphNode* dependent_node = *it; - internal::WorkerPoolTask* dependent = dependent_it->first; - if (!dependent->IsReadyToRun()) + dependent_node->remove_dependency(); + // Dependent is not ready unless number of dependencies are 0. + if (dependent_node->num_dependencies()) continue; // Task is ready. Add it to |ready_to_run_tasks_|. - GraphNode* dependent_node = dependent_it->second; - unsigned priority = dependent_node->priority(); - DCHECK(!ready_to_run_tasks_.count(priority) || - ready_to_run_tasks_[priority] == dependent); - ready_to_run_tasks_[priority] = dependent; + DCHECK(!ready_to_run_tasks_.count(dependent_node->priority()) || + ready_to_run_tasks_[dependent_node->priority()] == + dependent_node->task()); + ready_to_run_tasks_[dependent_node->priority()] = + dependent_node->task(); } } @@ -354,21 +354,15 @@ void WorkerPool::Inner::Run() { has_ready_to_run_tasks_cv_.Signal(); } -WorkerPool::GraphNode::GraphNode( - internal::WorkerPoolTask* dependent, unsigned priority) - : priority_(priority) { - if (dependent) - dependents_.push_back(dependent); +WorkerPool::GraphNode::GraphNode(internal::WorkerPoolTask* task) + : task_(task), + priority_(0), + num_dependencies_(0) { } WorkerPool::GraphNode::~GraphNode() { } -void WorkerPool::GraphNode::AddDependent(internal::WorkerPoolTask* dependent) { - DCHECK(dependent); - dependents_.push_back(dependent); -} - WorkerPool::WorkerPool(size_t num_threads, const std::string& thread_name_prefix) : in_dispatch_completion_callbacks_(false), @@ -425,37 +419,49 @@ void WorkerPool::SetTaskGraph(TaskGraph* graph) { // static unsigned WorkerPool::BuildTaskGraphRecursive( internal::WorkerPoolTask* task, - internal::WorkerPoolTask* dependent, + GraphNode* dependent, unsigned priority, - TaskGraph* tasks) { - // Skip sub-tree if task has already completed. - if (task->HasCompleted()) - return priority; - - GraphNodeMap::iterator it = tasks->find(task); - if (it != tasks->end()) { - it->second->AddDependent(dependent); + TaskGraph* graph) { + GraphNodeMap::iterator it = graph->find(task); + if (it != graph->end()) { + GraphNode* node = it->second; + node->add_dependent(dependent); return priority; } + scoped_ptr node(new GraphNode(task)); + typedef internal::WorkerPoolTask::TaskVector TaskVector; for (TaskVector::iterator dependency_it = task->dependencies().begin(); dependency_it != task->dependencies().end(); ++dependency_it) { internal::WorkerPoolTask* dependency = dependency_it->get(); - priority = BuildTaskGraphRecursive(dependency, task, priority, tasks); + // Skip sub-tree if task has already completed. + if (dependency->HasCompleted()) + continue; + + node->add_dependency(); + + priority = BuildTaskGraphRecursive(dependency, + node.get(), + priority, + graph); } - tasks->set(task, make_scoped_ptr(new GraphNode(dependent, priority))); + node->set_priority(priority); + if (dependent) + node->add_dependent(dependent); + + graph->set(task, node.Pass()); return priority + 1; } // static void WorkerPool::BuildTaskGraph( - internal::WorkerPoolTask* root, TaskGraph* tasks) { + internal::WorkerPoolTask* root, TaskGraph* graph) { const unsigned kBasePriority = 0u; - if (root) - BuildTaskGraphRecursive(root, NULL, kBasePriority, tasks); + if (root && !root->HasCompleted()) + BuildTaskGraphRecursive(root, NULL, kBasePriority, graph); } } // namespace cc diff --git a/cc/resources/worker_pool.h b/cc/resources/worker_pool.h index 4f53203..cfa6302 100644 --- a/cc/resources/worker_pool.h +++ b/cc/resources/worker_pool.h @@ -33,7 +33,6 @@ class CC_EXPORT WorkerPoolTask void DidRun(); void DidComplete(); - bool IsReadyToRun() const; bool HasFinishedRunning() const; bool HasCompleted() const; @@ -84,21 +83,37 @@ class CC_EXPORT WorkerPool { protected: class CC_EXPORT GraphNode { public: - typedef std::vector TaskVector; + typedef std::vector Vector; - GraphNode(internal::WorkerPoolTask* dependent, unsigned priority); + explicit GraphNode(internal::WorkerPoolTask* task); ~GraphNode(); - void AddDependent(internal::WorkerPoolTask* dependent); + internal::WorkerPoolTask* task() { return task_; } - const TaskVector& dependents() const { + void add_dependent(GraphNode* dependent) { + dependents_.push_back(dependent); + } + const Vector& dependents() const { return dependents_; } + + void set_priority(unsigned priority) { priority_ = priority; } unsigned priority() const { return priority_; } + unsigned num_dependencies() const { + return num_dependencies_; + } + void add_dependency() { ++num_dependencies_; } + void remove_dependency() { + DCHECK(num_dependencies_); + --num_dependencies_; + } + private: - TaskVector dependents_; + internal::WorkerPoolTask* task_; + Vector dependents_; unsigned priority_; + unsigned num_dependencies_; DISALLOW_COPY_AND_ASSIGN(GraphNode); }; @@ -131,11 +146,11 @@ class CC_EXPORT WorkerPool { // "ready to run" tasks. static unsigned BuildTaskGraphRecursive( internal::WorkerPoolTask* task, - internal::WorkerPoolTask* dependent, + GraphNode* dependent, unsigned priority, - TaskGraph* tasks); + TaskGraph* graph); static void BuildTaskGraph( - internal::WorkerPoolTask* root, TaskGraph* tasks); + internal::WorkerPoolTask* root, TaskGraph* graph); private: class Inner; -- cgit v1.1