Cluster invalidation rectangles into coherent regions to lessen SkPicture re-recording

cc/resources/picture_pile.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/resources/picture_pile.h"
 
 #include <algorithm>
 #include <limits>
 #include <vector>
 
 #include "cc/base/region.h"
 #include "cc/debug/rendering_stats_instrumentation.h"
 #include "cc/resources/picture_pile_impl.h"
 
 namespace {
 // Layout pixel buffer around the visible layer rect to record.  Any base
 // picture that intersects the visible layer rect expanded by this distance
 // will be recorded.
 const int kPixelDistanceToRecord = 8000;
+
+// TODO(humper): The density threshold here is somewhat arbitrary; need a
+// way to set // this from the command line so we can write a benchmark
+// script and find a sweet spot.
+const float kDensityTreshold = 0.5f;
+
+bool rect_sort_y(const gfx::Rect &r1, const gfx::Rect &r2) {
+  return r1.y() < r2.y() || (r1.y() == r2.y() && r1.x() < r2.x());
+}
+
+bool rect_sort_x(const gfx::Rect &r1, const gfx::Rect &r2) {
+  return r1.x() < r2.x() || (r1.x() == r2.x() && r1.y() < r2.y());
+}
+
 }  // namespace
 
 namespace cc {
 
 PicturePile::PicturePile() {
 }
 
 PicturePile::~PicturePile() {
 }
 
+float do_clustering(const std::vector<gfx::Rect>& tiles,

[vmpstr, 2013/11/21 19:47:59]

You can move all of the non member functions to the anonymous namespace

[humper, 2013/11/21 20:51:14]

Done.

+                    std::vector<gfx::Rect>* clustered_rects) {
+  TRACE_EVENT0("cc.debug", "do_clustering");
+
+  // These variables track the record area and invalid area
+  // for the entire clustering
+  int total_record_area = 0;
+  int total_invalid_area = 0;
+
+  // These variables track the record area and invalid area
+  // for the current cluster being constructed.
+  gfx::Rect cur_record_rect;
+  int total_area = 0, invalid_area = 0;
+
+  for (std::vector<gfx::Rect>::const_iterator it = tiles.begin();
+        it != tiles.end();
+        it++) {
+    gfx::Rect invalid_tile = *it;
+
+    // For each tile, we consider adding the invalid tile to the
+    // current record rectangle.  Only add it if the amount of empty
+    // space created is below a density threshold.
+    int tile_area = invalid_tile.width() * invalid_tile.height();
+
+    gfx::Rect proposed_union = cur_record_rect;
+    proposed_union.Union(invalid_tile);
+    int proposed_area = proposed_union.width() * proposed_union.height();
+    float proposed_density =
+      static_cast<float>(invalid_area + tile_area) /
+      static_cast<float>(proposed_area);
+
+    if (proposed_density >= kDensityTreshold) {
+      // It's okay to add this invalid tile to the
+      // current recording rectangle.
+      cur_record_rect = proposed_union;
+      total_area = proposed_area;
+      invalid_area += tile_area;
+      total_invalid_area += tile_area;
+    } else {
+      // Adding this invalid tile to the current recording rectangle
+      // would exceed our badness threshold, so put the current rectangle
+      // in the list of recording rects, and start a new one.
+      clustered_rects->push_back(cur_record_rect);
+      total_record_area += total_area;
+      cur_record_rect = invalid_tile;
+      invalid_area = tile_area;
+      total_area = tile_area;
+    }
+  }
+
+  if (!cur_record_rect.IsEmpty()) {
+    clustered_rects->push_back(cur_record_rect);
+    total_record_area += total_area;
+  }
+
+  if (total_record_area == 0) {
+    return 1;
+  } else {
+    return static_cast<float>(total_invalid_area) /
+           static_cast<float>(total_record_area);
+  }
+}
+
+float ClusterTiles(const std::vector<gfx::Rect>& invalid_tiles,
+                   std::vector<gfx::Rect>* record_rects) {
+  TRACE_EVENT1("cc.debug", "ClusterTiles",
+               "number of tiles",
+               invalid_tiles.size());
+
+  if (invalid_tiles.size() <= 1) {
+    // Quickly handle the special case for common
+    // single-invalidation update, and also the less common
+    // case of no tiles passed in.
+    *record_rects = invalid_tiles;
+    return 1;
+  }
+
+  // Sort the invalid tiles by y coordinate.
+  std::vector<gfx::Rect> invalid_tiles_vertical = invalid_tiles;
+  std::sort(invalid_tiles_vertical.begin(),
+            invalid_tiles_vertical.end(),
+            rect_sort_y);
+
+  float vertical_density;
+  std::vector<gfx::Rect> vertical_clustering;
+  vertical_density = do_clustering(invalid_tiles_vertical,
+                                   &vertical_clustering);
+
+  // Now try again with a horizontal sort, see which one is best
+  // TODO(humper): Heuristics for skipping this step?

[vmpstr, 2013/11/21 19:47:59]

I think we should either just skip the horizontal cluster or do it if
vertical_density < something. I'm concerned that we might spend more time trying
to be the best we can, rather than just recording the good enough clustering.

That is, the savings on the recording cost from having a possibly better
clustering are offset by two things:
1. The time we spend to determine the better clustering
2. Possibly more calls to picture raster calls down the road (it's not that bad
that we have _some_ empty space in the cluster).

It would be nice if we had some sort of a measure of the performance. Maybe
rasterize and record can help? I'm not sure it would exercise all of the use
cases though.

[humper, 2013/11/21 20:51:14]

I'm concerned about sites that have two long vertical strips of updates on
either side of the page (e.g. two sidebars with content in the middle).  For
those sites, the horizontal clustering should do much better.

+  std::vector<gfx::Rect> invalid_tiles_horizontal = invalid_tiles;
+  std::sort(invalid_tiles_vertical.begin(),
+            invalid_tiles_vertical.end(),
+            rect_sort_x);
+
+  float horizontal_density;
+  std::vector<gfx::Rect> horizontal_clustering;
+  horizontal_density = do_clustering(invalid_tiles_vertical,
+                                     &horizontal_clustering);
+
+  if (vertical_density < horizontal_density) {
+    *record_rects = horizontal_clustering;
+    return horizontal_density;
+  } else {
+    *record_rects = vertical_clustering;
+    return vertical_density;
+  }
+}
+
 bool PicturePile::Update(
     ContentLayerClient* painter,
     SkColor background_color,
     bool contents_opaque,
     const Region& invalidation,
     gfx::Rect visible_layer_rect,
     RenderingStatsInstrumentation* stats_instrumentation) {
   background_color_ = background_color;
   contents_opaque_ = contents_opaque;
 
@@ skipping 14 matching lines @@
       const PictureMapKey& key = iter.index();
 
       PictureMap::iterator picture_it = picture_map_.find(key);
       if (picture_it == picture_map_.end())
         continue;
 
       invalidated = picture_it->second.Invalidate() || invalidated;
     }
   }
 
-  gfx::Rect record_rect;
+  // Make a list of all invalid tiles; we will attempt to
+  // cluster these into multiple invalidation regions.
+  std::vector<gfx::Rect> invalid_tiles;
+
   for (TilingData::Iterator it(&tiling_, interest_rect);
        it; ++it) {
     const PictureMapKey& key = it.index();
     const PictureInfo& info = picture_map_[key];
     if (!info.picture.get()) {
-      gfx::Rect tile = PaddedRect(key);
-      record_rect.Union(tile);
+      gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
+      invalid_tiles.push_back(tile);
     }
   }
 
-  if (record_rect.IsEmpty()) {
+  std::vector<gfx::Rect> record_rects;
+  ClusterTiles(invalid_tiles, &record_rects);
+
+  if (record_rects.empty()) {
     if (invalidated)
       UpdateRecordedRegion();
     return invalidated;
   }
 
-  int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
-  scoped_refptr<Picture> picture = Picture::Create(record_rect);
+  for (std::vector<gfx::Rect>::iterator it = record_rects.begin();
+       it != record_rects.end();
+       it++) {
+    gfx::Rect record_rect = *it;
+    record_rect.Inset(-buffer_pixels(), -buffer_pixels(),
+                      -buffer_pixels(), -buffer_pixels());
 
-  {
-    base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
-        std::numeric_limits<int64>::max());
-    for (int i = 0; i < repeat_count; i++) {
-      base::TimeTicks start_time = stats_instrumentation->StartRecording();
-      picture->Record(painter, tile_grid_info_);
-      base::TimeDelta duration =
-          stats_instrumentation->EndRecording(start_time);
-      best_duration = std::min(duration, best_duration);
+    int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
+    scoped_refptr<Picture> picture = Picture::Create(record_rect);
+
+    {
+      base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
+          std::numeric_limits<int64>::max());
+      for (int i = 0; i < repeat_count; i++) {
+        base::TimeTicks start_time = stats_instrumentation->StartRecording();
+        picture->Record(painter, tile_grid_info_);
+        base::TimeDelta duration =
+            stats_instrumentation->EndRecording(start_time);
+        best_duration = std::min(duration, best_duration);
+      }
+      int recorded_pixel_count =
+          picture->LayerRect().width() * picture->LayerRect().height();
+      stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
+      if (num_raster_threads_ > 1)
+        picture->GatherPixelRefs(tile_grid_info_);
+      picture->CloneForDrawing(num_raster_threads_);
     }
-    int recorded_pixel_count =
-        picture->LayerRect().width() * picture->LayerRect().height();
-    stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
-    if (num_raster_threads_ > 1)
-      picture->GatherPixelRefs(tile_grid_info_);
-    picture->CloneForDrawing(num_raster_threads_);
-  }
 
-  for (TilingData::Iterator it(&tiling_, record_rect);
-       it; ++it) {
-    const PictureMapKey& key = it.index();
-    gfx::Rect tile = PaddedRect(key);
-    if (record_rect.Contains(tile)) {
-      PictureInfo& info = picture_map_[key];
-      info.picture = picture;
+    for (TilingData::Iterator it(&tiling_, record_rect);
+        it; ++it) {
+      const PictureMapKey& key = it.index();
+      gfx::Rect tile = PaddedRect(key);
+      if (record_rect.Contains(tile)) {
+        PictureInfo& info = picture_map_[key];
+        info.picture = picture;
+      }
     }
   }
 
   UpdateRecordedRegion();
   return true;
 }
 
 }  // namespace cc