cc: Optimize decode scheduling for checker-images.

cc/tiles/checker_image_tracker.cc

Index: cc/tiles/checker_image_tracker.cc
diff --git a/cc/tiles/checker_image_tracker.cc b/cc/tiles/checker_image_tracker.cc
index 8bbcbebe839fa490a47fe1e2d405598781a43ffb..f65266aba6e5c6aedfd5815267eec3b12a083399 100644
--- a/cc/tiles/checker_image_tracker.cc
+++ b/cc/tiles/checker_image_tracker.cc
@@ -36,26 +36,13 @@ CheckerImageTracker::~CheckerImageTracker() {
     image_controller_->UnlockImageDecode(it.second);
 }
 
-void CheckerImageTracker::FilterImagesForCheckeringForTile(
-    std::vector<DrawImage>* images,
-    ImageIdFlatSet* checkered_images,
-    WhichTree tree) {
-  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
-               "CheckerImageTracker::FilterImagesForCheckeringForTile", "tree",
-               tree);
-  DCHECK(checkered_images->empty());
-
-  base::EraseIf(*images,
-                [this, tree, &checkered_images](const DrawImage& draw_image) {
-                  const sk_sp<const SkImage>& image = draw_image.image();
-                  DCHECK(image->isLazyGenerated());
-                  if (ShouldCheckerImage(image, tree)) {
-                    ScheduleImageDecodeIfNecessary(image);
-                    checkered_images->insert(image->uniqueID());
-                    return true;
-                  }
-                  return false;
-                });
+void CheckerImageTracker::ScheduleImageDecodeQueue(
+    ImageDecodeQueue image_decode_queue) {
+  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
+               "CheckerImageTracker::ScheduleImageDecodeQueue");
+  image_decode_queue_ = std::move(image_decode_queue);
+  next_image_index_to_decode_ = 0;
+  ScheduleNextImageDecode();
 }
 
 const ImageIdFlatSet& CheckerImageTracker::TakeImagesToInvalidateOnSyncTree() {
@@ -90,12 +77,13 @@ void CheckerImageTracker::DidFinishImageDecode(
   TRACE_EVENT_ASYNC_END0("cc", "CheckerImageTracker::DeferImageDecode",
                          image_id);
 
-  DCHECK_NE(result, ImageController::ImageDecodeResult::DECODE_NOT_REQUIRED);
-  DCHECK_NE(pending_image_decodes_.count(image_id), 0u);
-  pending_image_decodes_.erase(image_id);
-
+  DCHECK_NE(ImageController::ImageDecodeResult::DECODE_NOT_REQUIRED, result);
+  DCHECK_EQ(outstanding_image_decode_->uniqueID(), image_id);
+  outstanding_image_decode_ = nullptr;
   images_decoded_once_.insert(image_id);
   images_pending_invalidation_.insert(image_id);
+
+  ScheduleNextImageDecode();
   client_->NeedsInvalidationForCheckerImagedTiles();
 }
 
@@ -115,12 +103,6 @@ bool CheckerImageTracker::ShouldCheckerImage(const sk_sp<const SkImage>& image,
     return true;
   }
 
-  // If a decode request is pending for this image, continue checkering it.

[vmpstr, 2017/03/29 19:11:45]

Why is this check gone?

[Khushal, 2017/03/29 22:10:20]

This shouldn't be necessary I think. It was making sure if we saw an image
previously that we decided to checker, we should continue to do so. But that
would happen anyway because we decide based on the image size. The rest of the
checks after this, |images_pending_invalidation_| and |images_decoded_once_|
should never be true if the image is pending decode.

-  if (pending_image_decodes_.find(image->uniqueID()) !=
-      pending_image_decodes_.end()) {
-    return true;
-  }
-
   // If the image is pending invalidation, continue checkering it. All tiles
   // for these images will be invalidated on the next pending tree.
   if (images_pending_invalidation_.find(image->uniqueID()) !=
@@ -137,28 +119,50 @@ bool CheckerImageTracker::ShouldCheckerImage(const sk_sp<const SkImage>& image,
   return SafeSizeOfImage(image.get()) >= kMinImageSizeToCheckerBytes;
 }
 
-void CheckerImageTracker::ScheduleImageDecodeIfNecessary(
-    const sk_sp<const SkImage>& image) {
+void CheckerImageTracker::ScheduleNextImageDecode() {
   TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
-               "CheckerImageTracker::ScheduleImageDecodeIfNecessary");
-  ImageId image_id = image->uniqueID();
+               "CheckerImageTracker::ScheduleNextImageDecode");
+
+  if (image_decode_queue_.empty())
+    return;
 
-  // If the image has already been decoded, or a decode request is pending, we
-  // don't need to schedule another decode.
-  if (images_decoded_once_.count(image_id) != 0 ||
-      pending_image_decodes_.count(image_id) != 0) {
+  // We can have only one outsanding decode pending completion with the decode
+  // service. We'll come back here when it is completed.
+  if (outstanding_image_decode_)
     return;
+
+  DCHECK_GE(next_image_index_to_decode_, 0u);
+  DCHECK_LT(next_image_index_to_decode_, image_decode_queue_.size());
+  while (next_image_index_to_decode_ != image_decode_queue_.size()) {

[vmpstr, 2017/03/29 19:11:45]

It's not clear to me why you're using an index here. Realistically, this vector
is pretty small, so I would prefer

// We already have an outstanding decode, this function will
// be called again when it completes.
if (oustanding_image_decode_)
  return;

// Process the queue until we find the first image that needs
// to be scheduled, and put it as an |oustanding_image_decode_|.
// If no such image is found, |outsanding_image_decode_| is nullptr
// upon loop termination and the queue is empty.
while (!image_decode_queue_.empty()) {
 auto candidate = image_decode_queue_.front();
 image_decode_queue_.erase(image_decode_queue_.begin());
 if (...) {
  continue;
 }
 outstanding_image_decode_ = std::move(candidate);
 break;
}

// We couldn't find an image that needs a decode, so there
// is no more work to do.
if (!outstanding_image_decode_) {
  DCHECK_EQ(0u, image_decode_queue_.size())
  return;
}

...

[Khushal, 2017/03/29 22:10:20]

Erasing from the beginning of the vector is going to be O(n). And the queue is
going to have multiple instances of the same image (added for every tile), so it
wouldn't be trivially small I think. The index saves us from doing that by just
clearing at the end when we are done with the queue, and keeping an index from
where valid candidates start. Its minimal complexity isolated to this once
place, so I feel like its worth it. If you think not, let me know.

[Khushal, 2017/03/31 04:31:00]

Discussed offline. Changed to erase instead.

+    outstanding_image_decode_ =
+        std::move(image_decode_queue_[next_image_index_to_decode_++]);
+
+    // Schedule decode for this image if it has not already been decoded,
+    // otherwise try the next image in the queue.
+    ImageId image_id = outstanding_image_decode_->uniqueID();
+    if (images_decoded_once_.count(image_id) == 0)
+      break;
+    outstanding_image_decode_ = nullptr;
+  }
+
+  // If we have reached the end of the queue, reset to default state.
+  if (next_image_index_to_decode_ == image_decode_queue_.size()) {
+    next_image_index_to_decode_ = 0;
+    image_decode_queue_.clear();
   }
 
+  if (!outstanding_image_decode_)
+    return;
+
+  ImageId image_id = outstanding_image_decode_->uniqueID();
+  DCHECK_EQ(image_id_to_decode_request_id_.count(image_id), 0u);
   TRACE_EVENT_ASYNC_BEGIN0("cc", "CheckerImageTracker::DeferImageDecode",
                            image_id);
-  DCHECK_EQ(image_id_to_decode_request_id_.count(image_id), 0U);
-
   image_id_to_decode_request_id_[image_id] =
       image_controller_->QueueImageDecode(
-          image, base::Bind(&CheckerImageTracker::DidFinishImageDecode,
-                            weak_factory_.GetWeakPtr(), image_id));
-  pending_image_decodes_.insert(image_id);
+          outstanding_image_decode_,
+          base::Bind(&CheckerImageTracker::DidFinishImageDecode,
+                     weak_factory_.GetWeakPtr(), image_id));
 }
 
 }  // namespace cc