cc: Optimize decode scheduling for checker-images.

cc/tiles/tile_manager.cc

 // Copyright 2012 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/tile_manager.h"
 
 #include <stddef.h>
 #include <stdint.h>
 
 #include <algorithm>
@@ skipping 625 matching lines @@
   MemoryUsage soft_memory_limit(global_state_.soft_memory_limit_in_bytes,
                                 global_state_.num_resources_limit);
   MemoryUsage memory_usage(resource_pool_->memory_usage_bytes(),
                            resource_pool_->resource_count());
 
   std::unique_ptr<RasterTilePriorityQueue> raster_priority_queue(
       client_->BuildRasterQueue(global_state_.tree_priority,
                                 RasterTilePriorityQueue::Type::ALL));
   std::unique_ptr<EvictionTilePriorityQueue> eviction_priority_queue;
   PrioritizedWorkToSchedule work_to_schedule;
+  CheckerImageTracker::ImageDecodeQueue checker_image_decode_queue;
   for (; !raster_priority_queue->IsEmpty(); raster_priority_queue->Pop()) {
     const PrioritizedTile& prioritized_tile = raster_priority_queue->Top();
     Tile* tile = prioritized_tile.tile();
     TilePriority priority = prioritized_tile.priority();
 
     if (TilePriorityViolatesMemoryPolicy(priority)) {
       TRACE_EVENT_INSTANT0(
           "cc", "TileManager::AssignGpuMemory tile violates memory policy",
           TRACE_EVENT_SCOPE_THREAD);
       break;
@@ skipping 18 matching lines @@
       }
     }
 
     // Prepaint tiles that are far away are only processed for images.
     if (!tile->required_for_activation() && !tile->required_for_draw() &&
         prioritized_tile.is_process_for_images_only()) {
       work_to_schedule.tiles_to_process_for_images.push_back(prioritized_tile);
       continue;
     }
 
+    // Tiles in the raster queue should either require raster or decode for
+    // checker-images. If this tile does not need raster, process it only to
+    // build the decode queue for checkered images.

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

Add a comment saying that this block must come after the solid color analysis
just for robustness. I don't think anything will break if you reorder them, but
who knows with all the CDL work we're doing how the analysis might change. 

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

Done.

+    if (!tile->draw_info().NeedsRaster()) {
+      DCHECK(tile->draw_info().is_checker_imaged());
+      std::vector<DrawImage> images_in_tile;
+      prioritized_tile.raster_source()->GetDiscardableImagesInRect(
+          tile->enclosing_layer_rect(), tile->contents_scale(),
+          &images_in_tile);
+      FilterImagesForCheckering(tile->tiling()->tree(), images_in_tile, nullptr,
+                                nullptr, &checker_image_decode_queue);
+      continue;
+    }
+
     // We won't be able to schedule this tile, so break out early.
     if (work_to_schedule.tiles_to_raster.size() >=
         scheduled_raster_task_limit_) {
       all_tiles_that_need_to_be_rasterized_are_scheduled_ = false;
       break;
     }
 
     tile->scheduled_priority_ = schedule_priority++;
 
     DCHECK(tile->draw_info().mode() == TileDrawInfo::OOM_MODE ||
@@ skipping 26 matching lines @@
     // If we couldn't fit the tile into our current memory limit, then we're
     // done.
     if (!memory_usage_is_within_limit) {
       if (tile_is_needed_now)
         had_enough_memory_to_schedule_tiles_needed_now = false;
       all_tiles_that_need_to_be_rasterized_are_scheduled_ = false;
       break;
     }
 
     memory_usage += memory_required_by_tile_to_be_scheduled;
+
+    // If the tile has a scheduled task that will rasterize a resource with
+    // checker-imaged content, add those images to the decode queue. Note that
+    // we add all images as we process the raster priority queue to ensure that
+    // images are added to the decode queue in raster priority order.
+    if (tile->raster_task_scheduled_with_checker_images()) {

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

Maybe flip the if and the dcheck? If, if tile has a resource, dcheck that it has
checker images? Then the else if can be just an else.

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

Not sure I followed, at this point the tile should definitely not have a
resource, we handled that case above.

We have 3 cases to handle here:
1) A Tile which is checker-imaged and has a valid resource, but still needs
image decoding.
2) A Tile which has a raster task with images to checker that is already
running.
3) A Tile for which we will create a raster task right now with checker-images.

1 gets handled above and we don't reach here. The rest 2 are handled here.

+      DCHECK(tile->HasRasterTask());
+      std::vector<DrawImage> images_in_tile;
+      prioritized_tile.raster_source()->GetDiscardableImagesInRect(

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

This isn't really a trivial operation, is there any way to cache the images? 

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

I was thinking about it. Is there a reason for not doing this already? We can
store something like image analysis performed on a tile and stash 2 vectors on
it, the ones that the raster tasks need to depend on and the ones which are
checkered. The state shouldn't change for any tile coz we change the
checker-image state only by invalidating tiles and replacing them with new ones.

This should also remove the |scheduled_draw_images_| map right? Coz if a tile is
scheduled, it always depends on the same set of images?

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

Cached this on Tile. I didn't realize that |scheduled_draw_images_| is still
needed in case the tile goes away before the raster task finishes.

+          tile->enclosing_layer_rect(), tile->contents_scale(),
+          &images_in_tile);
+      FilterImagesForCheckering(tile->tiling()->tree(), images_in_tile, nullptr,
+                                nullptr, &checker_image_decode_queue);
+    } else if (!tile->HasRasterTask()) {
+      // Creating the raster task here will acquire resources, but
+      // this resource usage has already been accounted for above.
+      tile->raster_task_ =
+          CreateRasterTask(prioritized_tile, client_->GetRasterColorSpace(),

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

It's a bit unfortunate that we're doing this here now. I don't think it really
matters, but it changes what traces tell us about which part of the code is
slow. 

Is there a trace in CreateRasterTask? If not, could you add one?

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

Done.

+                           &checker_image_decode_queue);
+    }
     work_to_schedule.tiles_to_raster.push_back(prioritized_tile);
   }
 
   // Note that we should try and further reduce memory in case the above loop
   // didn't reduce memory. This ensures that we always release as many resources
   // as possible to stay within the memory limit.
   eviction_priority_queue = FreeTileResourcesUntilUsageIsWithinLimit(

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

What happens if eviction evicts tiles that are being checker imaged now?

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

The eviction here shouldn't remove resources from any tiles that we went through
in the raster priority queue above right?

       std::move(eviction_priority_queue), hard_memory_limit, &memory_usage);
 
+  // At this point if we still have a tile that is holding onto a resource with
+  // checker-imaged content, add it to the decode queue to ensure that the
+  // resource is eventually invalidated.
+  while (!raster_priority_queue->IsEmpty()) {

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

You can't do this here. This part defeats the point of having a lazy priority
queue, since it ensures that we always process all tiles that haven't been
scheduled yet, which means we update all tile priorities, which makes this a
pretty big regression.

We need to rethink this. 

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

Sorry, I had missed looking at the implementation of the queue to see it is
lazily populated. You're right, this would be horrible and can be optimized a
bunch.

We can keep track of the checkered images at any time. And only iterate through
the tile queue until more than one is left to be added. This will still have a
worst case scenario where we go through the whole queue if the last tile has 2
checkered images for instance. Do you think that's reasonable?

+    const PrioritizedTile& prioritized_tile = raster_priority_queue->Top();
+    Tile* tile = prioritized_tile.tile();
+    if (tile->draw_info().is_checker_imaged() ||
+        tile->raster_task_scheduled_with_checker_images()) {
+      std::vector<DrawImage> images_in_tile;
+      prioritized_tile.raster_source()->GetDiscardableImagesInRect(
+          tile->enclosing_layer_rect(), tile->contents_scale(),
+          &images_in_tile);
+      FilterImagesForCheckering(tile->tiling()->tree(), images_in_tile, nullptr,
+                                nullptr, &checker_image_decode_queue);
+    }
+    raster_priority_queue->Pop();
+  }
+
+  // Schedule running of the checker-image decode queue. This replaces the
+  // previously scheduled queue and effectively cancels image decodes from the
+  // previously scheduled queue, if not already started.
+  checker_image_tracker_.ScheduleImageDecodeQueue(

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

Can you move this call out of this function and do it at a later time?
AssignGpuMemory shouldn't be doing any scheduling. We might need to refactor
tile manager here before you can land this patch, but I'm not a fan of the
coupling we're introducing throughout this function.

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

Moved it to ScheduleTasks.

+      std::move(checker_image_decode_queue));
+
   UMA_HISTOGRAM_BOOLEAN("TileManager.ExceededMemoryBudget",
                         !had_enough_memory_to_schedule_tiles_needed_now);
   did_oom_on_last_assign_ = !had_enough_memory_to_schedule_tiles_needed_now;
 
   memory_stats_from_last_assign_.total_budget_in_bytes =
       global_state_.hard_memory_limit_in_bytes;
   memory_stats_from_last_assign_.total_bytes_used = memory_usage.memory_bytes();
   DCHECK_GE(memory_stats_from_last_assign_.total_bytes_used, 0);
   memory_stats_from_last_assign_.had_enough_memory =
       had_enough_memory_to_schedule_tiles_needed_now;
@@ skipping 16 matching lines @@
 }
 
 void TileManager::FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(
     Tile* tile) {
   bool was_ready_to_draw = tile->draw_info().IsReadyToDraw();
   FreeResourcesForTile(tile);
   if (was_ready_to_draw)
     client_->NotifyTileStateChanged(tile);
 }
 
+void TileManager::FilterImagesForCheckering(
+    WhichTree tree,
+    const std::vector<DrawImage>& images_in_tile,
+    std::vector<DrawImage>* images_to_decode_for_raster,
+    ImageIdFlatSet* checkered_images,
+    CheckerImageTracker::ImageDecodeQueue* image_decode_queue) {
+  DCHECK(!images_to_decode_for_raster || images_to_decode_for_raster->empty());

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

It's not clear to me why some of the output parameters are optional. Can we
avoid this?

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

I think computing it once and storing it on tile should simplify this a bunch.

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

Done.

+  DCHECK(!checkered_images || checkered_images->empty());
+
+  for (const auto& draw_image : images_in_tile) {
+    const sk_sp<const SkImage>& image = draw_image.image();
+    DCHECK(image->isLazyGenerated());
+    if (checker_image_tracker_.ShouldCheckerImage(image, tree)) {
+      if (checkered_images)
+        checkered_images->insert(image->uniqueID());

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

Here you're adding the image to both the vector and the set. That's something
that the calling code can do, eliminating one output parameter. 

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

Function died.

+      image_decode_queue->push_back(std::move(image));
+    } else if (images_to_decode_for_raster) {
+      images_to_decode_for_raster->push_back(draw_image);

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

image to decode for raster is not a clear name. I think this is meant to
basically be "images _not_ to checker"

Is it possible to make this function a simple partition?

iterator PartitionImagesForCheckering(tree, images) {
 return std::stable_partition(images.begin(), images.end(), [](image) { ... });
}

then the calling code will get both sets of images that need checkering and
images that don't, and it can do whatever it wants with that information. 

If it makes the calling code verbose in a few places, then just add another free
function or another member function (ie refactor a bit)

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

Function died.

+    }
+  }
+}
+
 void TileManager::ScheduleTasks(
     const PrioritizedWorkToSchedule& work_to_schedule) {
   const std::vector<PrioritizedTile>& tiles_that_need_to_be_rasterized =
       work_to_schedule.tiles_to_raster;
   TRACE_EVENT1("cc", "TileManager::ScheduleTasks", "count",
                tiles_that_need_to_be_rasterized.size());
 
   DCHECK(did_check_for_completed_tasks_since_last_schedule_tasks_);
 
   if (!has_scheduled_tile_tasks_) {
@@ skipping 28 matching lines @@
   scoped_refptr<TileTask> all_done_task =
       CreateTaskSetFinishedTask(&TileManager::DidFinishRunningAllTileTasks);
 
   // Build a new task queue containing all task currently needed. Tasks
   // are added in order of priority, highest priority task first.
   for (auto& prioritized_tile : tiles_that_need_to_be_rasterized) {
     Tile* tile = prioritized_tile.tile();
 
     DCHECK(tile->draw_info().requires_resource());
     DCHECK(!tile->draw_info().resource());
-
-    if (!tile->raster_task_) {
-      tile->raster_task_ =
-          CreateRasterTask(prioritized_tile, raster_color_space);
-    }
+    DCHECK(tile->HasRasterTask());

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

comment why this is true now.

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

Done.

 
     TileTask* task = tile->raster_task_.get();
 
     DCHECK(!task->HasCompleted());
 
     if (tile->required_for_activation()) {
       required_for_activate_count++;
       graph_.edges.push_back(
           TaskGraph::Edge(task, required_for_activation_done_task.get()));
     }
@@ skipping 88 matching lines @@
   tile_task_manager_->ScheduleTasks(&graph_);
 
   did_check_for_completed_tasks_since_last_schedule_tasks_ = false;
 
   TRACE_EVENT_ASYNC_STEP_INTO1("cc", "ScheduledTasks", this, "running", "state",
                                ScheduledTasksStateAsValue());
 }
 
 scoped_refptr<TileTask> TileManager::CreateRasterTask(
     const PrioritizedTile& prioritized_tile,
-    const gfx::ColorSpace& color_space) {
+    const gfx::ColorSpace& color_space,
+    CheckerImageTracker::ImageDecodeQueue* checker_image_decode_queue) {
   Tile* tile = prioritized_tile.tile();
 
   // Get the resource.
   uint64_t resource_content_id = 0;
   Resource* resource = nullptr;
   gfx::Rect invalidated_rect = tile->invalidated_content_rect();
   if (UsePartialRaster() && tile->invalidated_id()) {
     resource = resource_pool_->TryAcquireResourceForPartialRaster(
         tile->id(), tile->invalidated_content_rect(), tile->invalidated_id(),
         &invalidated_rect);
   }
 
   if (resource) {
     resource_content_id = tile->invalidated_id();
     DCHECK_EQ(DetermineResourceFormat(tile), resource->format());
   } else {
     resource = resource_pool_->AcquireResource(tile->desired_texture_size(),
                                                DetermineResourceFormat(tile),
                                                color_space);
   }
 
   // For LOW_RESOLUTION tiles, we don't draw or predecode images.
   RasterSource::PlaybackSettings playback_settings;
   playback_settings.skip_images =
       prioritized_tile.priority().resolution == LOW_RESOLUTION;
 
   // Create and queue all image decode tasks that this tile depends on.
   TileTask::Vector decode_tasks;
-  std::vector<DrawImage>& images = scheduled_draw_images_[tile->id()];
-  ImageIdFlatSet images_to_skip;
-  images.clear();
+  std::vector<DrawImage>& images_to_decode_for_raster =
+      scheduled_draw_images_[tile->id()];
+  images_to_decode_for_raster.clear();
   if (!playback_settings.skip_images) {
+    std::vector<DrawImage> images_in_tile;
     prioritized_tile.raster_source()->GetDiscardableImagesInRect(

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

The pattern of these two calls appears throughout. I think it's worth adding a
helper function.

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

Happens only once now. Moved to EnsureImageAnalysisPerformed.

-        tile->enclosing_layer_rect(), tile->contents_scale(), &images);
-    checker_image_tracker_.FilterImagesForCheckeringForTile(
-        &images, &images_to_skip, prioritized_tile.tile()->tiling()->tree());
+        tile->enclosing_layer_rect(), tile->contents_scale(), &images_in_tile);
+    FilterImagesForCheckering(
+        tile->tiling()->tree(), images_in_tile, &images_to_decode_for_raster,
+        &playback_settings.images_to_skip, checker_image_decode_queue);
   }
 
   // We can skip the image hijack canvas if we have no images, or no images to
   // skip during raster.
   playback_settings.use_image_hijack_canvas =
-      !images.empty() || !images_to_skip.empty();
-  playback_settings.images_to_skip = std::move(images_to_skip);
+      !images_to_decode_for_raster.empty() ||
+      !playback_settings.images_to_skip.empty();
+  tile->raster_task_scheduled_with_checker_images_ =
+      !playback_settings.images_to_skip.empty();
 
   // Get the tasks for the required images.
   ImageDecodeCache::TracingInfo tracing_info(
       prepare_tiles_count_, prioritized_tile.priority().priority_bin);
-  image_controller_.GetTasksForImagesAndRef(&images, &decode_tasks,
-                                            tracing_info);
+  image_controller_.GetTasksForImagesAndRef(&images_to_decode_for_raster,
+                                            &decode_tasks, tracing_info);
 
   std::unique_ptr<RasterBuffer> raster_buffer =
       raster_buffer_provider_->AcquireBufferForRaster(
           resource, resource_content_id, tile->invalidated_id());
   return make_scoped_refptr(new RasterTaskImpl(
       this, tile, resource, prioritized_tile.raster_source(), playback_settings,
       prioritized_tile.priority().resolution, invalidated_rect,
       prepare_tiles_count_, std::move(raster_buffer), &decode_tasks,
       use_gpu_rasterization_));
 }
 
 void TileManager::ResetSignalsForTesting() {
   signals_.reset();
 }
 
 void TileManager::OnRasterTaskCompleted(
     std::unique_ptr<RasterBuffer> raster_buffer,
     Tile::Id tile_id,
     Resource* resource,
     bool was_canceled) {
   raster_buffer_provider_->ReleaseBufferForRaster(std::move(raster_buffer));
 
   auto found = tiles_.find(tile_id);
   Tile* tile = nullptr;
+  bool raster_task_scheduled_with_checker_images = false;
   if (found != tiles_.end()) {
     tile = found->second;
     DCHECK(tile->raster_task_.get());
+    raster_task_scheduled_with_checker_images =

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

just make the setter return the old value

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

Done.

+        tile->raster_task_scheduled_with_checker_images_;
     tile->raster_task_ = nullptr;
+    tile->raster_task_scheduled_with_checker_images_ = false;
   }
 
   // Unref all the images.
   auto images_it = scheduled_draw_images_.find(tile_id);
   image_controller_.UnrefImages(images_it->second);
   scheduled_draw_images_.erase(images_it);
 
   if (was_canceled) {
     ++flush_stats_.canceled_count;
     resource_pool_->ReleaseResource(resource);
     return;
   }
 
   resource_pool_->OnContentReplaced(resource->id(), tile_id);
   ++flush_stats_.completed_count;
 
   if (!tile) {
     resource_pool_->ReleaseResource(resource);
     return;
   }
 
   TileDrawInfo& draw_info = tile->draw_info();
   draw_info.set_resource(resource);
+  draw_info.resource_is_checker_imaged_ =
+      raster_task_scheduled_with_checker_images;
   draw_info.contents_swizzled_ = DetermineResourceRequiresSwizzle(tile);
 
   // In SMOOTHNESS_TAKES_PRIORITY mode, we wait for GPU work to complete for a
   // tile before setting it as ready to draw.
   if (global_state_.tree_priority == SMOOTHNESS_TAKES_PRIORITY &&
       !raster_buffer_provider_->IsResourceReadyToDraw(resource->id())) {
     pending_gpu_work_tiles_.insert(tile);
     return;
   }
 
@@ skipping 385 matching lines @@
   all_tile_tasks_completed = false;
   did_notify_all_tile_tasks_completed = false;
 }
 
 TileManager::PrioritizedWorkToSchedule::PrioritizedWorkToSchedule() = default;
 TileManager::PrioritizedWorkToSchedule::PrioritizedWorkToSchedule(
     PrioritizedWorkToSchedule&& other) = default;
 TileManager::PrioritizedWorkToSchedule::~PrioritizedWorkToSchedule() = default;
 
 }  // namespace cc