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

cc/resources/pixel_buffer_raster_worker_pool.cc

 // Copyright 2013 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/pixel_buffer_raster_worker_pool.h"
 
+#include <algorithm>
+
 #include "base/containers/stack_container.h"
 #include "base/debug/trace_event.h"
 #include "base/values.h"
 #include "cc/debug/traced_value.h"
 #include "cc/resources/resource.h"
 
 namespace cc {
 namespace {
 
 const int kCheckForCompletedRasterTasksDelayMs = 6;
@@ skipping 47 matching lines @@
 void PixelBufferRasterWorkerPool::Shutdown() {
   shutdown_ = true;
   RasterWorkerPool::Shutdown();
 
   CheckForCompletedWorkerPoolTasks();
   CheckForCompletedUploads();
 
   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;
     }
   }
   DCHECK_EQ(completed_raster_tasks_.size(), raster_task_states_.size());
 }
 
 void PixelBufferRasterWorkerPool::ScheduleTasks(RasterTaskQueue* queue) {
   TRACE_EVENT0("cc", "PixelBufferRasterWorkerPool::ScheduleTasks");
 
   DCHECK_EQ(queue->required_for_activation_count,
             static_cast<size_t>(
                 std::count_if(queue->items.begin(),
                               queue->items.end(),
                               RasterTaskQueue::Item::IsRequiredForActivation)));
 
   if (!should_notify_client_if_no_tasks_are_pending_)
     TRACE_EVENT_ASYNC_BEGIN0("cc", "ScheduledTasks", this);
 
   should_notify_client_if_no_tasks_are_pending_ = true;
   should_notify_client_if_no_tasks_required_for_activation_are_pending_ = true;
 
   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());
+    DCHECK(std::find_if(recycled_raster_task_states_.begin(),
+                        recycled_raster_task_states_.end(),
+                        RasterTaskState::TaskComparator(task)) ==
+           recycled_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)

+    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.
       if (state.type != RasterTaskState::COMPLETED) {
         raster_tasks_required_for_activation_count_ +=
             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) {
       DCHECK(!task->HasBeenScheduled());
       DCHECK(std::find(completed_raster_tasks_.begin(),
                        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
   // of top priority tasks that are scheduled.
   CheckForCompletedWorkerPoolTasks();
   CheckForCompletedUploads();
   FlushUploads();
 
   // Schedule new tasks.
   ScheduleMoreTasks();
@@ skipping 20 matching lines @@
   return resource_provider()->memory_efficient_texture_format();
 }
 
 void PixelBufferRasterWorkerPool::CheckForCompletedTasks() {
   TRACE_EVENT0("cc", "PixelBufferRasterWorkerPool::CheckForCompletedTasks");
 
   CheckForCompletedWorkerPoolTasks();
   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_.clear();
+
+  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);
+
+    std::swap(*state_it, raster_task_states_.back());
+    raster_task_states_.pop_back();
 
     task->RunReplyOnOriginThread();
-
-    completed_image_decode_tasks_.pop_front();
   }
-
-  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);
-
-    raster_task_states_.erase(task);
-
-    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());
 }
 
 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());
 }
 
 void PixelBufferRasterWorkerPool::OnRasterTasksFinished() {
   // |should_notify_client_if_no_tasks_are_pending_| can be set to false as
   // a result of a scheduled CheckForCompletedRasterTasks() call. No need to
   // perform another check in that case as we've already notified the client.
   if (!should_notify_client_if_no_tasks_are_pending_)
     return;
   raster_finished_task_pending_ = false;
@@ skipping 20 matching lines @@
 
 void PixelBufferRasterWorkerPool::FlushUploads() {
   if (!has_performed_uploads_since_last_flush_)
     return;
 
   resource_provider()->ShallowFlushIfSupported();
   has_performed_uploads_since_last_flush_ = false;
 }
 
 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);
     raster_tasks_with_pending_upload_.pop_front();
   }
 
   DCHECK(client());
   bool should_force_some_uploads_to_complete =
       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);
         continue;
       }
 
       ++it;
     }
 
     // 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);
+      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.resource->id());
+      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();
 
     task->WillComplete();
     task->CompleteOnOriginThread(this);
     task->DidComplete();
 
     DCHECK(std::find(completed_raster_tasks_.begin(),
                      completed_raster_tasks_.end(),
                      task) == completed_raster_tasks_.end());
     completed_raster_tasks_.push_back(task);
     state.type = RasterTaskState::COMPLETED;
     DCHECK_LE(state.required_for_activation,
               raster_tasks_required_for_activation_count_);
     raster_tasks_required_for_activation_count_ -=
         state.required_for_activation;
-
-    tasks_with_completed_uploads.pop_front();
   }
 }
 
 void PixelBufferRasterWorkerPool::ScheduleCheckForCompletedRasterTasks() {
   base::TimeDelta delay =
       base::TimeDelta::FromMilliseconds(kCheckForCompletedRasterTasksDelayMs);
   if (check_for_completed_raster_tasks_time_.is_null())
     check_for_completed_raster_tasks_time_ = base::TimeTicks::Now() + delay;
 
   if (check_for_completed_raster_tasks_pending_)
@@ skipping 102 matching lines @@
 
   for (RasterTaskQueue::Item::Vector::const_iterator it =
            raster_tasks_.items.begin();
        it != raster_tasks_.items.end();
        ++it) {
     const RasterTaskQueue::Item& item = *it;
     internal::RasterWorkerPoolTask* task = item.task;
 
     // |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) {
       DCHECK(std::find(completed_raster_tasks_.begin(),
                        completed_raster_tasks_.end(),
                        task) != completed_raster_tasks_.end());
       continue;
     }
 
     // All raster tasks need to be throttled by bytes of pending uploads.
@@ skipping 121 matching lines @@
 }
 
 void PixelBufferRasterWorkerPool::CheckForCompletedWorkerPoolTasks() {
   CollectCompletedWorkerPoolTasks(&completed_tasks_);
   for (internal::Task::Vector::const_iterator it = completed_tasks_.begin();
        it != completed_tasks_.end();
        ++it) {
     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);
       task->DidComplete();
 
       completed_image_decode_tasks_.push_back(task);
       continue;
     }
 
-    RasterTaskState& state = state_it->second;
+    RasterTaskState& state = *state_it;
     DCHECK_EQ(RasterTaskState::SCHEDULED, state.type);
     DCHECK(state.resource);
 
     // Balanced with MapPixelRasterBuffer() call in AcquireCanvasForRaster().
     bool content_has_changed =
         resource_provider()->UnmapPixelRasterBuffer(state.resource->id());
 
     // |content_has_changed| can be false as result of task being canceled or
     // task implementation deciding not to modify bitmap (ie. analysis of raster
     // commands detected content as a solid color).
     if (!content_has_changed) {
       task->WillComplete();
       task->CompleteOnOriginThread(this);
       task->DidComplete();
 
       if (!task->HasFinishedRunning()) {
         // 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! :)

           }
         }
       }
 
       DCHECK(std::find(completed_raster_tasks_.begin(),
                        completed_raster_tasks_.end(),
                        task) == completed_raster_tasks_.end());
       completed_raster_tasks_.push_back(task);
       state.type = RasterTaskState::COMPLETED;
       DCHECK_LE(state.required_for_activation,
@@ skipping 34 matching lines @@
 
   throttle_state->SetInteger("bytes_available_for_upload",
                              max_bytes_pending_upload_ - bytes_pending_upload_);
   throttle_state->SetInteger("bytes_pending_upload", bytes_pending_upload_);
   throttle_state->SetInteger("scheduled_raster_task_count",
                              scheduled_raster_task_count_);
   return throttle_state.PassAs<base::Value>();
 }
 
 }  // namespace cc