cc: Replace RasterTaskStateMap with a vector and brute force search instead of hash map lookups.

cc/resources/pixel_buffer_raster_worker_pool.cc

Index: cc/resources/pixel_buffer_raster_worker_pool.cc
diff --git a/cc/resources/pixel_buffer_raster_worker_pool.cc b/cc/resources/pixel_buffer_raster_worker_pool.cc
index f56242ccfe2c55d0d2f4af2f8d085c8b09958284..b2370139d39262523ea842429baaf8e258f8d79b 100644
--- a/cc/resources/pixel_buffer_raster_worker_pool.cc
+++ b/cc/resources/pixel_buffer_raster_worker_pool.cc
@@ -4,6 +4,8 @@
 
 #include "cc/resources/pixel_buffer_raster_worker_pool.h"
 
+#include <algorithm>
+
 #include "base/containers/stack_container.h"
 #include "base/debug/trace_event.h"
 #include "base/values.h"
@@ -71,15 +73,14 @@ void PixelBufferRasterWorkerPool::Shutdown() {
   weak_factory_.InvalidateWeakPtrs();
   check_for_completed_raster_tasks_pending_ = false;
 
-  for (RasterTaskStateMap::iterator it = raster_task_states_.begin();
+  for (RasterTaskState::Vector::iterator it = raster_task_states_.begin();
        it != raster_task_states_.end();
        ++it) {
-    internal::WorkerPoolTask* task = it->first;
-    RasterTaskState& state = it->second;
+    RasterTaskState& state = *it;
 
     // All unscheduled tasks need to be canceled.
     if (state.type == RasterTaskState::UNSCHEDULED) {
-      completed_raster_tasks_.push_back(task);
+      completed_raster_tasks_.push_back(state.task);
       state.type = RasterTaskState::COMPLETED;
     }
   }
@@ -103,22 +104,29 @@ void PixelBufferRasterWorkerPool::ScheduleTasks(RasterTaskQueue* queue) {
 
   raster_tasks_required_for_activation_count_ = 0u;
 
+  recycled_raster_task_states_.clear();
+
   // Build new raster task state map.
-  RasterTaskStateMap new_raster_task_states;
   for (RasterTaskQueue::Item::Vector::const_iterator it = queue->items.begin();
        it != queue->items.end();
        ++it) {
     const RasterTaskQueue::Item& item = *it;
     internal::WorkerPoolTask* task = item.task;
-    DCHECK(new_raster_task_states.find(task) == new_raster_task_states.end());
-
-    RasterTaskStateMap::iterator state_it = raster_task_states_.find(task);

[vmpstr, 2014/02/21 18:39:41]

Out of curiousity... The current approach will have to eventually perform worse
(ie, the more we schedule the more the overhead of a hash map will not matter as
much as a linear search through the vector). Do you know what that number is?
What I mean is how many items do I have to schedule at once before the vector
becomes slower than the hash map?

[reveman, 2014/02/22 11:32:01]

We get about the same performance when reaching ~1000 raster tasks with latest
patch.

[vmpstr, 2014/02/24 17:37:58]

Nice. Let's hope we don't schedule more than that too often (or ever :P)

+    DCHECK(std::find_if(recycled_raster_task_states_.begin(),
+                        recycled_raster_task_states_.end(),
+                        RasterTaskState::TaskComparator(task)) ==
+           recycled_raster_task_states_.end());
+
+    RasterTaskState::Vector::iterator state_it =
+        std::find_if(raster_task_states_.begin(),
+                     raster_task_states_.end(),
+                     RasterTaskState::TaskComparator(task));
     if (state_it != raster_task_states_.end()) {
-      const RasterTaskState& state = state_it->second;
+      RasterTaskState& state = *state_it;
 
-      new_raster_task_states[task] =
+      recycled_raster_task_states_.push_back(
           RasterTaskState(state)
-              .set_required_for_activation(item.required_for_activation);
+              .set_required_for_activation(item.required_for_activation));
       // |raster_tasks_required_for_activation_count| accounts for all tasks
       // that need to complete before we can send a "ready to activate" signal.
       // Tasks that have already completed should not be part of this count.
@@ -127,25 +135,28 @@ void PixelBufferRasterWorkerPool::ScheduleTasks(RasterTaskQueue* queue) {
             item.required_for_activation;
       }
 
-      raster_task_states_.erase(state_it);
+      std::swap(*state_it, raster_task_states_.back());

[vmpstr, 2014/02/21 18:39:41]

nit: s/\*state_it/state/

[reveman, 2014/02/22 11:32:01]

Done.

+      raster_task_states_.pop_back();
     } else {
       DCHECK(!task->HasBeenScheduled());
-      new_raster_task_states[task] =
-          RasterTaskState().set_required_for_activation(
-              item.required_for_activation);
+      recycled_raster_task_states_.push_back(
+          RasterTaskState(task, item.required_for_activation));
       raster_tasks_required_for_activation_count_ +=
           item.required_for_activation;
     }
   }
 
-  // Transfer old raster task state to |new_raster_task_states| and cancel all
-  // remaining unscheduled tasks.
-  for (RasterTaskStateMap::const_iterator it = raster_task_states_.begin();
+  // Transfer old raster task state to |recycled_raster_task_states_| and cancel
+  // all remaining unscheduled tasks.
+  for (RasterTaskState::Vector::const_iterator it = raster_task_states_.begin();
        it != raster_task_states_.end();
        ++it) {
-    internal::WorkerPoolTask* task = it->first;
-    const RasterTaskState& state = it->second;
-    DCHECK(new_raster_task_states.find(task) == new_raster_task_states.end());
+    const RasterTaskState& state = *it;
+    internal::WorkerPoolTask* task = state.task;
+    DCHECK(std::find_if(recycled_raster_task_states_.begin(),
+                        recycled_raster_task_states_.end(),
+                        RasterTaskState::TaskComparator(task)) ==
+           recycled_raster_task_states_.end());
 
     // Unscheduled task can be canceled.
     if (state.type == RasterTaskState::UNSCHEDULED) {
@@ -154,17 +165,18 @@ void PixelBufferRasterWorkerPool::ScheduleTasks(RasterTaskQueue* queue) {
                        completed_raster_tasks_.end(),
                        task) == completed_raster_tasks_.end());
       completed_raster_tasks_.push_back(task);
-      new_raster_task_states[task] = RasterTaskState(state).set_completed();
+      recycled_raster_task_states_.push_back(
+          RasterTaskState(state).set_completed());
       continue;
     }
 
-    // Move state to |new_raster_task_states|.
-    new_raster_task_states[task] =
-        RasterTaskState(state).set_required_for_activation(false);
+    // Move state to |recycled_raster_task_states_|.
+    recycled_raster_task_states_.push_back(
+        RasterTaskState(state).set_required_for_activation(false));
   }
 
   raster_tasks_.Swap(queue);
-  raster_task_states_.swap(new_raster_task_states);
+  raster_task_states_.swap(recycled_raster_task_states_);

[vmpstr, 2014/02/21 18:39:41]

Is there a better name for this vector? Recycled makes it seem that you're going
to reuse the states themselves, but it seems that you are only reusing the heap
memory. Maybe something like pending_raster_task_state_ or even
new_raster_task_states_

[reveman, 2014/02/22 11:32:01]

I figured out a faster way to do this that avoids the need for a second vector.
This gave another ~25% performance improvement and allows me to remove the set_
functions from RasterTaskState. PTAL.

 
   // Check for completed tasks when ScheduleTasks() is called as
   // priorities might have changed and this maximizes the number
@@ -205,34 +217,43 @@ void PixelBufferRasterWorkerPool::CheckForCompletedTasks() {
   CheckForCompletedUploads();
   FlushUploads();
 
-  while (!completed_image_decode_tasks_.empty()) {
-    internal::WorkerPoolTask* task =
-        completed_image_decode_tasks_.front().get();
-
+  for (TaskVector::iterator it = completed_image_decode_tasks_.begin();
+       it != completed_image_decode_tasks_.end();
+       ++it) {
+    internal::WorkerPoolTask* task = it->get();
     task->RunReplyOnOriginThread();
-
-    completed_image_decode_tasks_.pop_front();
   }
+  completed_image_decode_tasks_.clear();
 
-  while (!completed_raster_tasks_.empty()) {
-    internal::WorkerPoolTask* task = completed_raster_tasks_.front().get();
-    DCHECK(raster_task_states_.find(task) != raster_task_states_.end());
-    DCHECK_EQ(RasterTaskState::COMPLETED, raster_task_states_[task].type);
+  for (TaskVector::iterator it = completed_raster_tasks_.begin();
+       it != completed_raster_tasks_.end();
+       ++it) {
+    internal::WorkerPoolTask* task = it->get();
+    RasterTaskState::Vector::iterator state_it =
+        std::find_if(raster_task_states_.begin(),
+                     raster_task_states_.end(),
+                     RasterTaskState::TaskComparator(task));
+    DCHECK(state_it != raster_task_states_.end());
+    DCHECK_EQ(RasterTaskState::COMPLETED, state_it->type);
 
-    raster_task_states_.erase(task);
+    std::swap(*state_it, raster_task_states_.back());
+    raster_task_states_.pop_back();
 
     task->RunReplyOnOriginThread();
-
-    completed_raster_tasks_.pop_front();
   }
+  completed_raster_tasks_.clear();
 }
 
 SkCanvas* PixelBufferRasterWorkerPool::AcquireCanvasForRaster(
     internal::WorkerPoolTask* task,
     const Resource* resource) {
-  DCHECK(raster_task_states_.find(task) != raster_task_states_.end());
-  DCHECK(!raster_task_states_[task].resource);
-  raster_task_states_[task].resource = resource;
+  RasterTaskState::Vector::iterator it =
+      std::find_if(raster_task_states_.begin(),
+                   raster_task_states_.end(),
+                   RasterTaskState::TaskComparator(task));
+  DCHECK(it != raster_task_states_.end());
+  DCHECK(!it->resource);
+  it->resource = resource;
   resource_provider()->AcquirePixelRasterBuffer(resource->id());
   return resource_provider()->MapPixelRasterBuffer(resource->id());
 }
@@ -240,8 +261,12 @@ SkCanvas* PixelBufferRasterWorkerPool::AcquireCanvasForRaster(
 void PixelBufferRasterWorkerPool::ReleaseCanvasForRaster(
     internal::WorkerPoolTask* task,
     const Resource* resource) {
-  DCHECK(raster_task_states_.find(task) != raster_task_states_.end());
-  DCHECK(raster_task_states_[task].resource == resource);
+  RasterTaskState::Vector::iterator it =
+      std::find_if(raster_task_states_.begin(),
+                   raster_task_states_.end(),
+                   RasterTaskState::TaskComparator(task));
+  DCHECK(it != raster_task_states_.end());
+  DCHECK(it->resource == resource);
   resource_provider()->ReleasePixelRasterBuffer(resource->id());
 }
 
@@ -282,18 +307,21 @@ void PixelBufferRasterWorkerPool::FlushUploads() {
 }
 
 void PixelBufferRasterWorkerPool::CheckForCompletedUploads() {
-  TaskDeque tasks_with_completed_uploads;
+  TaskVector tasks_with_completed_uploads;
 
   // First check if any have completed.
   while (!raster_tasks_with_pending_upload_.empty()) {
     internal::WorkerPoolTask* task =
         raster_tasks_with_pending_upload_.front().get();
-    DCHECK(raster_task_states_.find(task) != raster_task_states_.end());
-    const RasterTaskState& state = raster_task_states_[task];
-    DCHECK_EQ(RasterTaskState::UPLOADING, state.type);
+    RasterTaskState::Vector::const_iterator it =
+        std::find_if(raster_task_states_.begin(),
+                     raster_task_states_.end(),
+                     RasterTaskState::TaskComparator(task));
+    DCHECK(it != raster_task_states_.end());
+    DCHECK_EQ(RasterTaskState::UPLOADING, it->type);
 
     // Uploads complete in the order they are issued.
-    if (!resource_provider()->DidSetPixelsComplete(state.resource->id()))
+    if (!resource_provider()->DidSetPixelsComplete(it->resource->id()))
       break;
 
     tasks_with_completed_uploads.push_back(task);
@@ -305,16 +333,19 @@ void PixelBufferRasterWorkerPool::CheckForCompletedUploads() {
       shutdown_ || client()->ShouldForceTasksRequiredForActivationToComplete();
 
   if (should_force_some_uploads_to_complete) {
-    TaskDeque tasks_with_uploads_to_force;
+    TaskVector tasks_with_uploads_to_force;
     TaskDeque::iterator it = raster_tasks_with_pending_upload_.begin();
     while (it != raster_tasks_with_pending_upload_.end()) {
       internal::WorkerPoolTask* task = it->get();
-      DCHECK(raster_task_states_.find(task) != raster_task_states_.end());
-      const RasterTaskState& state = raster_task_states_[task];
+      RasterTaskState::Vector::const_iterator state_it =
+          std::find_if(raster_task_states_.begin(),
+                       raster_task_states_.end(),
+                       RasterTaskState::TaskComparator(task));
+      DCHECK(state_it != raster_task_states_.end());
 
       // Force all uploads required for activation to complete.
       // During shutdown, force all pending uploads to complete.
-      if (shutdown_ || state.required_for_activation) {
+      if (shutdown_ || state_it->required_for_activation) {
         tasks_with_uploads_to_force.push_back(task);
         tasks_with_completed_uploads.push_back(task);
         it = raster_tasks_with_pending_upload_.erase(it);
@@ -326,23 +357,34 @@ void PixelBufferRasterWorkerPool::CheckForCompletedUploads() {
 
     // Force uploads in reverse order. Since forcing can cause a wait on
     // all previous uploads, we would rather wait only once downstream.
-    for (TaskDeque::reverse_iterator it = tasks_with_uploads_to_force.rbegin();
+    for (TaskVector::reverse_iterator it = tasks_with_uploads_to_force.rbegin();
          it != tasks_with_uploads_to_force.rend();
          ++it) {
       internal::WorkerPoolTask* task = it->get();
-      const RasterTaskState& state = raster_task_states_[task];
-      DCHECK(state.resource);
-
-      resource_provider()->ForceSetPixelsToComplete(state.resource->id());
+      RasterTaskState::Vector::const_iterator state_it =
+          std::find_if(raster_task_states_.begin(),
+                       raster_task_states_.end(),
+                       RasterTaskState::TaskComparator(task));
+      DCHECK(state_it != raster_task_states_.end());
+      DCHECK(state_it->resource);
+
+      resource_provider()->ForceSetPixelsToComplete(state_it->resource->id());
       has_performed_uploads_since_last_flush_ = true;
     }
   }
 
   // Release shared memory and move tasks with completed uploads
   // to |completed_raster_tasks_|.
-  while (!tasks_with_completed_uploads.empty()) {
-    internal::WorkerPoolTask* task = tasks_with_completed_uploads.front().get();
-    RasterTaskState& state = raster_task_states_[task];
+  for (TaskVector::iterator it = tasks_with_completed_uploads.begin();
+       it != tasks_with_completed_uploads.end();
+       ++it) {
+    internal::WorkerPoolTask* task = it->get();
+    RasterTaskState::Vector::iterator state_it =
+        std::find_if(raster_task_states_.begin(),
+                     raster_task_states_.end(),
+                     RasterTaskState::TaskComparator(task));
+    DCHECK(state_it != raster_task_states_.end());
+    RasterTaskState& state = *state_it;
 
     bytes_pending_upload_ -= state.resource->bytes();
 
@@ -359,8 +401,6 @@ void PixelBufferRasterWorkerPool::CheckForCompletedUploads() {
               raster_tasks_required_for_activation_count_);
     raster_tasks_required_for_activation_count_ -=
         state.required_for_activation;
-
-    tasks_with_completed_uploads.pop_front();
   }
 }
 
@@ -483,11 +523,14 @@ void PixelBufferRasterWorkerPool::ScheduleMoreTasks() {
 
     // |raster_task_states_| contains the state of all tasks that we have not
     // yet run reply callbacks for.
-    RasterTaskStateMap::iterator state_it = raster_task_states_.find(task);
+    RasterTaskState::Vector::iterator state_it =
+        std::find_if(raster_task_states_.begin(),
+                     raster_task_states_.end(),
+                     RasterTaskState::TaskComparator(task));
     if (state_it == raster_task_states_.end())
       continue;
 
-    RasterTaskState& state = state_it->second;
+    RasterTaskState& state = *state_it;
 
     // Skip task if completed.
     if (state.type == RasterTaskState::COMPLETED) {
@@ -629,7 +672,10 @@ void PixelBufferRasterWorkerPool::CheckForCompletedWorkerPoolTasks() {
     internal::WorkerPoolTask* task =
         static_cast<internal::WorkerPoolTask*>(it->get());
 
-    RasterTaskStateMap::iterator state_it = raster_task_states_.find(task);
+    RasterTaskState::Vector::iterator state_it =
+        std::find_if(raster_task_states_.begin(),
+                     raster_task_states_.end(),
+                     RasterTaskState::TaskComparator(task));
     if (state_it == raster_task_states_.end()) {
       task->WillComplete();
       task->CompleteOnOriginThread(this);
@@ -639,7 +685,7 @@ void PixelBufferRasterWorkerPool::CheckForCompletedWorkerPoolTasks() {
       continue;
     }
 
-    RasterTaskState& state = state_it->second;
+    RasterTaskState& state = *state_it;
     DCHECK_EQ(RasterTaskState::SCHEDULED, state.type);
     DCHECK(state.resource);
 
@@ -659,11 +705,11 @@ void PixelBufferRasterWorkerPool::CheckForCompletedWorkerPoolTasks() {
         // When priorites change, a raster task can be canceled as a result of
         // no longer being of high enough priority to fit in our throttled
         // raster task budget. The task has not yet completed in this case.
-        for (RasterTaskQueue::Item::Vector::const_iterator it =
+        for (RasterTaskQueue::Item::Vector::const_iterator item_it =
                  raster_tasks_.items.begin();
-             it != raster_tasks_.items.end();
-             ++it) {
-          if (it->task == task) {
+             item_it != raster_tasks_.items.end();
+             ++item_it) {
+          if (item_it->task == task) {
             state.type = RasterTaskState::UNSCHEDULED;
             state.resource = NULL;
             continue;

[vmpstr, 2014/02/21 18:39:41]

no need for continue

[reveman, 2014/02/22 11:32:01]

Oh, this is a bug! This continue statement was supposed to continue the
outermost loop and that obviously doesn't work. Fixed in
https://codereview.chromium.org/170783007 that introduced this problem. 

Thanks! :)