src/cc/resources/picture_pile.cc

   1 // Copyright 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "cc/resources/picture_pile.h"
   6
   7 #include <algorithm>
   8 #include <limits>
   9 #include <vector>
  10
  11 #include "cc/base/region.h"
  12 #include "cc/debug/rendering_stats_instrumentation.h"
  13 #include "cc/resources/picture_pile_impl.h"
  14 #include "cc/resources/raster_worker_pool.h"
  15 #include "cc/resources/tile_priority.h"
  16
  17 namespace {
  18 // Layout pixel buffer around the visible layer rect to record.  Any base
  19 // picture that intersects the visible layer rect expanded by this distance
  20 // will be recorded.
  21 const int kPixelDistanceToRecord = 8000;
  22
  23 // TODO(humper): The density threshold here is somewhat arbitrary; need a
  24 // way to set // this from the command line so we can write a benchmark
  25 // script and find a sweet spot.
  26 const float kDensityThreshold = 0.5f;
  27
  28 bool rect_sort_y(const gfx::Rect &r1, const gfx::Rect &r2) {
  29   return r1.y() < r2.y() || (r1.y() == r2.y() && r1.x() < r2.x());
  30 }
  31
  32 bool rect_sort_x(const gfx::Rect &r1, const gfx::Rect &r2) {
  33   return r1.x() < r2.x() || (r1.x() == r2.x() && r1.y() < r2.y());
  34 }
  35
  36 float do_clustering(const std::vector<gfx::Rect>& tiles,
  37                     std::vector<gfx::Rect>* clustered_rects) {
  38   // These variables track the record area and invalid area
  39   // for the entire clustering
  40   int total_record_area = 0;
  41   int total_invalid_area = 0;
  42
  43   // These variables track the record area and invalid area
  44   // for the current cluster being constructed.
  45   gfx::Rect cur_record_rect;
  46   int cluster_record_area = 0, cluster_invalid_area = 0;
  47
  48   for (std::vector<gfx::Rect>::const_iterator it = tiles.begin();
  49         it != tiles.end();
  50         it++) {
  51     gfx::Rect invalid_tile = *it;
  52
  53     // For each tile, we consider adding the invalid tile to the
  54     // current record rectangle.  Only add it if the amount of empty
  55     // space created is below a density threshold.
  56     int tile_area = invalid_tile.width() * invalid_tile.height();
  57
  58     gfx::Rect proposed_union = cur_record_rect;
  59     proposed_union.Union(invalid_tile);
  60     int proposed_area = proposed_union.width() * proposed_union.height();
  61     float proposed_density =
  62       static_cast<float>(cluster_invalid_area + tile_area) /
  63       static_cast<float>(proposed_area);
  64
  65     if (proposed_density >= kDensityThreshold) {
  66       // It's okay to add this invalid tile to the
  67       // current recording rectangle.
  68       cur_record_rect = proposed_union;
  69       cluster_record_area = proposed_area;
  70       cluster_invalid_area += tile_area;
  71       total_invalid_area += tile_area;
  72     } else {
  73       // Adding this invalid tile to the current recording rectangle
  74       // would exceed our badness threshold, so put the current rectangle
  75       // in the list of recording rects, and start a new one.
  76       clustered_rects->push_back(cur_record_rect);
  77       total_record_area += cluster_record_area;
  78       cur_record_rect = invalid_tile;
  79       cluster_invalid_area = tile_area;
  80       cluster_record_area = tile_area;
  81     }
  82   }
  83
  84   DCHECK(!cur_record_rect.IsEmpty());
  85   clustered_rects->push_back(cur_record_rect);
  86   total_record_area += cluster_record_area;;
  87
  88   DCHECK_NE(total_record_area, 0);
  89
  90   return static_cast<float>(total_invalid_area) /
  91          static_cast<float>(total_record_area);
  92   }
  93
  94 float ClusterTiles(const std::vector<gfx::Rect>& invalid_tiles,
  95                    std::vector<gfx::Rect>* record_rects) {
  96   TRACE_EVENT1("cc", "ClusterTiles",
  97                "count",
  98                invalid_tiles.size());
  99
 100   if (invalid_tiles.size() <= 1) {
 101     // Quickly handle the special case for common
 102     // single-invalidation update, and also the less common
 103     // case of no tiles passed in.
 104     *record_rects = invalid_tiles;
 105     return 1;
 106   }
 107
 108   // Sort the invalid tiles by y coordinate.
 109   std::vector<gfx::Rect> invalid_tiles_vertical = invalid_tiles;
 110   std::sort(invalid_tiles_vertical.begin(),
 111             invalid_tiles_vertical.end(),
 112             rect_sort_y);
 113
 114   float vertical_density;
 115   std::vector<gfx::Rect> vertical_clustering;
 116   vertical_density = do_clustering(invalid_tiles_vertical,
 117                                    &vertical_clustering);
 118
 119   // Now try again with a horizontal sort, see which one is best
 120   // TODO(humper): Heuristics for skipping this step?
 121   std::vector<gfx::Rect> invalid_tiles_horizontal = invalid_tiles;
 122   std::sort(invalid_tiles_vertical.begin(),
 123             invalid_tiles_vertical.end(),
 124             rect_sort_x);
 125
 126   float horizontal_density;
 127   std::vector<gfx::Rect> horizontal_clustering;
 128   horizontal_density = do_clustering(invalid_tiles_vertical,
 129                                      &horizontal_clustering);
 130
 131   if (vertical_density < horizontal_density) {
 132     *record_rects = horizontal_clustering;
 133     return horizontal_density;
 134   }
 135
 136   *record_rects = vertical_clustering;
 137   return vertical_density;
 138 }
 139
 140 }  // namespace
 141
 142 namespace cc {
 143
 144 PicturePile::PicturePile() {
 145 }
 146
 147 PicturePile::~PicturePile() {
 148 }
 149
 150 bool PicturePile::Update(
 151     ContentLayerClient* painter,
 152     SkColor background_color,
 153     bool contents_opaque,
 154     const Region& invalidation,
 155     const gfx::Rect& visible_layer_rect,
 156     int frame_number,
 157     RenderingStatsInstrumentation* stats_instrumentation) {
 158   background_color_ = background_color;
 159   contents_opaque_ = contents_opaque;
 160
 161   gfx::Rect interest_rect = visible_layer_rect;
 162   interest_rect.Inset(
 163       -kPixelDistanceToRecord,
 164       -kPixelDistanceToRecord,
 165       -kPixelDistanceToRecord,
 166       -kPixelDistanceToRecord);
 167
 168   bool invalidated = false;
 169   for (Region::Iterator i(invalidation); i.has_rect(); i.next()) {
 170     gfx::Rect invalidation = i.rect();
 171     // Split this inflated invalidation across tile boundaries and apply it
 172     // to all tiles that it touches.
 173     for (TilingData::Iterator iter(&tiling_, invalidation);
 174          iter; ++iter) {
 175       const PictureMapKey& key = iter.index();
 176
 177       PictureMap::iterator picture_it = picture_map_.find(key);
 178       if (picture_it == picture_map_.end())
 179         continue;
 180
 181       // Inform the grid cell that it has been invalidated in this frame.
 182       invalidated = picture_it->second.Invalidate(frame_number) || invalidated;
 183     }
 184   }
 185
 186   // Make a list of all invalid tiles; we will attempt to
 187   // cluster these into multiple invalidation regions.
 188   std::vector<gfx::Rect> invalid_tiles;
 189
 190   for (TilingData::Iterator it(&tiling_, interest_rect);
 191        it; ++it) {
 192     const PictureMapKey& key = it.index();
 193     PictureInfo& info = picture_map_[key];
 194
 195     gfx::Rect rect = PaddedRect(key);
 196     int distance_to_visible =
 197         rect.ManhattanInternalDistance(visible_layer_rect);
 198
 199     if (info.NeedsRecording(frame_number, distance_to_visible)) {
 200       gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
 201       invalid_tiles.push_back(tile);
 202     }
 203   }
 204
 205   std::vector<gfx::Rect> record_rects;
 206   ClusterTiles(invalid_tiles, &record_rects);
 207
 208   if (record_rects.empty()) {
 209     if (invalidated)
 210       UpdateRecordedRegion();
 211     return invalidated;
 212   }
 213
 214   for (std::vector<gfx::Rect>::iterator it = record_rects.begin();
 215        it != record_rects.end();
 216        it++) {
 217     gfx::Rect record_rect = *it;
 218     record_rect = PadRect(record_rect);
 219
 220     int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
 221     scoped_refptr<Picture> picture;
 222     int num_raster_threads = RasterWorkerPool::GetNumRasterThreads();
 223
 224     // Note: Currently, gathering of pixel refs when using a single
 225     // raster thread doesn't provide any benefit. This might change
 226     // in the future but we avoid it for now to reduce the cost of
 227     // Picture::Create.
 228     bool gather_pixel_refs = num_raster_threads > 1;
 229
 230     {
 231       base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
 232           std::numeric_limits<int64>::max());
 233       for (int i = 0; i < repeat_count; i++) {
 234         base::TimeTicks start_time = stats_instrumentation->StartRecording();
 235         picture = Picture::Create(record_rect,
 236                                   painter,
 237                                   tile_grid_info_,
 238                                   gather_pixel_refs,
 239                                   num_raster_threads);
 240         base::TimeDelta duration =
 241             stats_instrumentation->EndRecording(start_time);
 242         best_duration = std::min(duration, best_duration);
 243       }
 244       int recorded_pixel_count =
 245           picture->LayerRect().width() * picture->LayerRect().height();
 246       stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
 247     }
 248
 249     for (TilingData::Iterator it(&tiling_, record_rect);
 250         it; ++it) {
 251       const PictureMapKey& key = it.index();
 252       gfx::Rect tile = PaddedRect(key);
 253       if (record_rect.Contains(tile)) {
 254         PictureInfo& info = picture_map_[key];
 255         info.SetPicture(picture);
 256       }
 257     }
 258   }
 259
 260   UpdateRecordedRegion();
 261   return true;
 262 }
 263
 264 }  // namespace cc