cc: Optimize decode scheduling for checker-images.

cc/tiles/checker_image_tracker.cc

 // Copyright 2017 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/tiles/checker_image_tracker.h"
 
 #include "base/bind.h"
 #include "base/stl_util.h"
 #include "base/trace_event/trace_event.h"
 
@@ skipping 18 matching lines @@
       client_(client),
       enable_checker_imaging_(enable_checker_imaging),
       weak_factory_(this) {}
 
 CheckerImageTracker::~CheckerImageTracker() {
   // Unlock all images pending decode requests.
   for (auto it : image_id_to_decode_request_id_)
     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() {
   TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                "CheckerImageTracker::TakeImagesToInvalidateOnSyncTree");
   DCHECK_EQ(invalidated_images_on_current_sync_tree_.size(), 0u)
       << "Sync tree can not be invalidated more than once";
 
   invalidated_images_on_current_sync_tree_.swap(images_pending_invalidation_);
   images_pending_invalidation_.clear();
@@ skipping 14 matching lines @@
 
 void CheckerImageTracker::DidFinishImageDecode(
     ImageId image_id,
     ImageController::ImageDecodeRequestId request_id,
     ImageController::ImageDecodeResult result) {
   TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                "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();
 }
 
 bool CheckerImageTracker::ShouldCheckerImage(const sk_sp<const SkImage>& image,
                                              WhichTree tree) const {
   TRACE_EVENT1("cc", "CheckerImageTracker::ShouldCheckerImage", "image_id",
                image->uniqueID());
 
   if (!enable_checker_imaging_)
     return false;
 
   // If the image was invalidated on the current sync tree and the tile is
   // for the active tree, continue checkering it on the active tree to ensure
   // the image update is atomic for the frame.
   if (invalidated_images_on_current_sync_tree_.count(image->uniqueID()) != 0 &&
       tree == WhichTree::ACTIVE_TREE) {
     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()) !=
       images_pending_invalidation_.end()) {
     return true;
   }
 
   // If the image has been decoded once before, don't checker it again.
   if (images_decoded_once_.find(image->uniqueID()) !=
       images_decoded_once_.end()) {
     return false;
   }
 
   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 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) {
+  if (image_decode_queue_.empty())
     return;
+
+  // 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