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

cc/resources/picture_pile.cc

Index: cc/resources/picture_pile.cc
diff --git a/cc/resources/picture_pile.cc b/cc/resources/picture_pile.cc
index 9f485b829602fa607353e467abb82cad3e09760c..bc3ad48bbfb39e0d91e1d06aa639541b660802e1 100644
--- a/cc/resources/picture_pile.cc
+++ b/cc/resources/picture_pile.cc
@@ -17,6 +17,20 @@ namespace {
 // 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 {
@@ -27,6 +41,115 @@ 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,
@@ -61,51 +184,65 @@ bool PicturePile::Update(
     }
   }
 
-  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);
-
-  {
-    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);
+  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());
+
+    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;
+      }
     }
   }