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..02a40927c8706914f7cefa55bddbd5285a04fb63 100644
--- a/cc/resources/picture_pile.cc
+++ b/cc/resources/picture_pile.cc
@@ -27,6 +27,84 @@ PicturePile::PicturePile() {
 PicturePile::~PicturePile() {
 }
 
+static bool rect_sort_y(const gfx::Rect &r1, const gfx::Rect &r2) {
+  return r1.y() < r2.y();
+}
+
+static bool rect_sort_x(const gfx::Rect &r1, const gfx::Rect &r2) {
+  return r1.x() < r2.x();
+}
+
+class TileClustering {

[vmpstr, 2013/11/20 18:02:32]

Why is this a separate class? Since all of the interesting work is done in the
constructor, I think it would be slightly more efficient to have a function that
takes the resulting rects as a pointer and returns the final density

[humper, 2013/11/20 20:47:13]

No particular reason; I had initially imagined it as something more complex, and
it turned out to just be a function.  I'll redo it as a function, that will be
better.

+  public:
+    TileClustering(const std::vector<gfx::Rect> &tiles, float thresh)

[vmpstr, 2013/11/20 18:02:32]

nit: spacing (vector<...>& tiles) and don't abbreviate threshold

[humper, 2013/11/20 20:47:13]

Done.

+      : total_record_area(0),
+        invalid_record_area(0),
+        clustering_threshold(thresh) {
+      gfx::Rect cur_record_rect;
+      int total_area = 0, invalid_area = 0;
+
+      for (std::vector<gfx::Rect>::iterator it = tiles.begin();

[humper, 2013/11/21 18:49:29]

Heh, that's what I get for not testing before doing the CL upload because I
thought I was just doing "nits" -- this has to be const_iterator.

+           it != tiles.end();
+           it++) {
+        gfx::Rect invalid_tile = *it;
+
+        // 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 >= clustering_threshold) {

[vmpstr, 2013/11/20 18:02:32]

What happens in the case where we have a full row followed by an empty row
followed by a full row (full = invalidated, empty = not invalidated). If I
understand this correct, both rows would end up in a separate cluster after we
add the first tile of the last row, although if we added the full row then the
density would still be > 0.5. Is this expected? Ie we just have to live with it?
:P

[humper, 2013/11/20 20:47:13]

This is partially an artifact of the greedy clustering algorithm, and partly a
consequence of the fact that I don't pre-group adjacent tiles together (see
comment by enne below).  The greediness can't be helped, but certainly we can
cluster things by line instead of by tile, which would help with this concern
(if it is indeed a concern).

+          // okay to add this invalid tile to the current recording rectangle
+
+          cur_record_rect = proposed_union;
+          total_area = proposed_area;
+          invalid_area += tile_area;
+          invalid_record_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.
+
+          record_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()) {
+        record_rects.push_back(cur_record_rect);
+        total_record_area += total_area;
+      }
+    }
+    std::vector<gfx::Rect> getRecordRects() const {
+      return record_rects;
+    }
+
+    float density() const {
+      if (total_record_area == 0)
+        return 1;
+      return static_cast<float>(invalid_record_area) /
+             static_cast<float>(total_record_area);
+    }
+
+  private:
+    std::vector<gfx::Rect> record_rects;

[vmpstr, 2013/11/20 18:02:32]

nit: we typically name private members with a trailing udnerscore

[humper, 2013/11/20 20:47:13]

Done.

+    int total_record_area;
+    int invalid_record_area;
+    float clustering_threshold;
+};
+
 bool PicturePile::Update(
     ContentLayerClient* painter,
     SkColor background_color,
@@ -61,51 +139,93 @@ bool PicturePile::Update(
     }
   }
 
-  gfx::Rect record_rect;
+  // make a  list of all invalid tiles; we will attempt to
+  // cluster these into multiple invalidation regions.
+

[vmpstr, 2013/11/20 18:02:32]

nit: remove this line (and most trailing blank lines after comments)

[humper, 2013/11/20 20:47:13]

Done.

+  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);
+    }
+  }
+
+  std::vector<gfx::Rect> record_rects;
+
+  if (invalid_tiles.size() == 1) {

[vmpstr, 2013/11/20 18:02:32]

Maybe make this a helper function, something along the lines of the following:

ClusterRects(invalid_tiles, &record_rects); 

just to keep the Update function cleaner

[humper, 2013/11/20 20:47:13]

will do.

+    // special case for common single-invalidation update
+    record_rects = invalid_tiles;
+  } else {
+    // sort the invalid tiles by y coordinate.
+
+    std::vector<gfx::Rect> invalid_tiles_vertical = invalid_tiles;
+    std::sort(invalid_tiles_vertical.begin(),

[vmpstr, 2013/11/20 18:02:32]

Assuming that the sort totally ignores the other coordinate, can't you end up in
situations like having one row of tiles (say 5 tiles 256x256) and having the
first two tiles being at 0,0 and at 1024,0 (sort by y here), so then adding the
second tile would immediately break the threshold?

I think this might be solved by a more involved sort function though
like a.y < b.y || (a.y == b.y && a.x < b.x) or something

[humper, 2013/11/20 20:47:13]

better sort would help with this, although grouping adjacent tiles and
clustering by line will help also; since the clustering is really meant to work
in 1D I think we should do that before this lands.

+              invalid_tiles_vertical.end(),
+              rect_sort_y);
+    // Note: density 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.
+    TileClustering vertical_clustering(invalid_tiles_vertical, 0.5);

[vmpstr, 2013/11/20 18:02:32]

nit: Make density a constant at the top please, and you can move the comment
there as well.

[humper, 2013/11/20 20:47:13]

Yeah, absolutely -- wasn't sure the best way to make it controllable so it ended
up as a magic number :)

+
+    std::vector<gfx::Rect> invalid_tiles_horizontal = invalid_tiles;
+    std::sort(invalid_tiles_vertical.begin(),
+              invalid_tiles_vertical.end(),
+              rect_sort_x);
+    TileClustering horizontal_clustering(invalid_tiles_vertical, 0.5);

[enne (OOO), 2013/11/20 19:15:33]

Is it expensive to sort and walk through all the invalidated tiles twice in
different directions?

Did you abandon your original approach (at least that I had heard described)
about merging everything on horizontal rows and then clustering those rows
vertically?  Was it not performant?

[humper, 2013/11/20 20:47:13]

Not abandoned, just not done yet.  There are a couple of ways to handle that; if
I use a more clever sort like vlad describes above, I can add all horizontally
(or vertically, depending on the direction) adjacent tiles at once, since adding
more adjacent tiles should typically (but not always) improve the density.

We could also only do the horizontal version if the vertical version results in
multiple clusters, or with a separate density control (if the best we could do
was something close to the threshold, say).

+
+    if (vertical_clustering.density() < horizontal_clustering.density()) {
+      record_rects = horizontal_clustering.getRecordRects();
+    } else {
+      record_rects = vertical_clustering.getRecordRects();
     }
   }
 
-  if (record_rect.IsEmpty()) {
+  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;
+      }
     }
   }