cc: Add tiling raster tile iterators.

cc/resources/picture_layer_tiling.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_layer_tiling.h"
 
 #include <algorithm>
 #include <cmath>
 #include <limits>
 
 #include "base/debug/trace_event.h"
 #include "cc/base/math_util.h"
+#include "cc/resources/tile.h"
+#include "cc/resources/tile_priority.h"
 #include "ui/gfx/point_conversions.h"
 #include "ui/gfx/rect_conversions.h"
 #include "ui/gfx/safe_integer_conversions.h"
 #include "ui/gfx/size_conversions.h"
 
 namespace cc {
+namespace {
+
+class HighPriorityFirstOrder {
+ public:
+  explicit HighPriorityFirstOrder(WhichTree tree) : tree_(tree) {}
+  ~HighPriorityFirstOrder() {}
+
+  bool operator()(const Tile* a, const Tile* b) const {
+    const TilePriority& a_priority = a->priority(tree_);
+    const TilePriority& b_priority = b->priority(tree_);
+
+    return (a_priority.priority_bin < b_priority.priority_bin) ||
+           (a_priority.priority_bin == b_priority.priority_bin &&
+            a_priority.distance_to_visible < b_priority.distance_to_visible);
+  }
+
+ private:
+  WhichTree tree_;
+};
+
+class LowPriorityFirstOrder {
+ public:
+  explicit LowPriorityFirstOrder(WhichTree tree) : tree_(tree) {}
+  ~LowPriorityFirstOrder() {}
+
+  bool operator()(const Tile* a, const Tile* b) const {
+    const TilePriority& a_priority = a->priority(tree_);
+    const TilePriority& b_priority = b->priority(tree_);
+
+    return (a_priority.priority_bin > b_priority.priority_bin) ||
+           (a_priority.priority_bin == b_priority.priority_bin &&
+            a_priority.distance_to_visible > b_priority.distance_to_visible);
+  }
+
+ private:
+  WhichTree tree_;
+};
+
+}  // namespace
 
 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
     float contents_scale,
     const gfx::Size& layer_bounds,
     PictureLayerTilingClient* client) {
   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
                                                 layer_bounds,
                                                 client));
 }
 
@@ skipping 28 matching lines @@
 }
 
 gfx::Rect PictureLayerTiling::ContentRect() const {
   return gfx::Rect(tiling_data_.total_size());
 }
 
 gfx::SizeF PictureLayerTiling::ContentSizeF() const {
   return gfx::ScaleSize(layer_bounds_, contents_scale_);
 }
 
+bool PictureLayerTiling::HasVisibleTilesAtOrAfterPriority(size_t priority_index)
+    const {
+  return priority_index < visible_tiles_.size();
+}
+
+Tile* PictureLayerTiling::RasterTileForPriority(size_t priority_index) {
+  // First, return visible tiles.
+  if (priority_index < visible_tiles_.size())
+    return visible_tiles_[priority_index];
+  priority_index -= visible_tiles_.size();
+
+  // Next, return skewport tiles.
+  if (priority_index < skewport_tiles_.size()) {
+    if (!skewport_tiles_sorted_) {
+      std::sort(skewport_tiles_.begin(),
+                skewport_tiles_.end(),
+                HighPriorityFirstOrder(last_update_tree_));
+      skewport_tiles_sorted_ = true;
+    }
+    return skewport_tiles_[priority_index];
+  }
+  priority_index -= skewport_tiles_.size();
+
+  // Next, return eventually tiles.
+  if (priority_index < eventually_tiles_.size()) {
+    if (!eventually_tiles_sorted_) {
+      std::sort(eventually_tiles_.begin(),
+                eventually_tiles_.end(),
+                HighPriorityFirstOrder(last_update_tree_));
+      eventually_tiles_sorted_ = true;
+    }
+    return eventually_tiles_[priority_index];
+  }
+
+  // If we got here, that means we're out of tiles that need raster.
+  return NULL;
+}
+
+Tile* PictureLayerTiling::EvictionTileForPriority(size_t priority_index) {
+  if (priority_index < eviction_tiles_.size()) {
+    if (!eviction_tiles_sorted_) {
+      std::sort(eviction_tiles_.begin(),
+                eviction_tiles_.end(),
+                LowPriorityFirstOrder(last_update_tree_));
+      eviction_tiles_sorted_ = true;
+    }
+    return eviction_tiles_[priority_index];
+  }
+
+  // No more eviction tiles present.
+  return NULL;
+}
+
 Tile* PictureLayerTiling::TileAt(int i, int j) const {
   TileMap::const_iterator iter = tiles_.find(TileMapKey(i, j));
   if (iter == tiles_.end())
     return NULL;
   return iter->second.get();
 }
 
 void PictureLayerTiling::CreateTile(int i,
                                     int j,
                                     const PictureLayerTiling* twin_tiling) {
@@ skipping 346 matching lines @@
                                        ContentRect(),
                                        &expansion_cache_);
 
   DCHECK(eventually_rect.IsEmpty() || ContentRect().Contains(eventually_rect));
 
   SetLiveTilesRect(eventually_rect);
 
   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 
+  visible_tiles_.clear();
+  skewport_tiles_.clear();
+  skewport_tiles_sorted_ = false;
+  eventually_tiles_.clear();
+  eventually_tiles_sorted_ = false;
+  eviction_tiles_.clear();
+  eviction_tiles_sorted_ = false;
+
   // Assign now priority to all visible tiles.
   TilePriority now_priority(resolution_, TilePriority::NOW, 0);
   for (TilingData::Iterator iter(&tiling_data_, visible_rect_in_content_space);
        iter;
        ++iter) {
     TileMap::iterator find = tiles_.find(iter.index());
     if (find == tiles_.end())
       continue;
     Tile* tile = find->second.get();
 
     tile->SetPriority(tree, now_priority);
+    visible_tiles_.push_back(tile);

[vmpstr, 2014/02/27 21:18:34]

Doing conditional pushes here (if it actually needs raster, or if it actually
has resources to evict) results in a bigger regression in update tile
priorities.

With this approach the regression on my machine is about 10% (which is still
pretty bad). But at least, most of the cost is moved to the iterators that are
currently unused.

I think making this part fast is more of a priority than I initially thought.

+    eviction_tiles_.push_back(tile);
   }
 
   // Assign soon priority to all tiles in the skewport that are not visible.
   float content_to_screen_scale =
       1.0f / (contents_scale_ * layer_contents_scale);
+
   for (TilingData::DifferenceIterator iter(
            &tiling_data_, skewport, visible_rect_in_content_space);
        iter;
        ++iter) {
     TileMap::iterator find = tiles_.find(iter.index());
     if (find == tiles_.end())
       continue;
     Tile* tile = find->second.get();
 
     gfx::Rect tile_bounds =
         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 
     float distance_to_visible =
         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
         content_to_screen_scale;
 
     TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible);
     tile->SetPriority(tree, priority);
+    skewport_tiles_.push_back(tile);
+    eviction_tiles_.push_back(tile);
   }
 
   // Assign eventually priority to all tiles in the eventually rect that are not
   // in the skewport.
   for (TilingData::DifferenceIterator iter(
            &tiling_data_, eventually_rect, skewport);
        iter;
        ++iter) {
     TileMap::iterator find = tiles_.find(iter.index());
     if (find == tiles_.end())
       continue;
     Tile* tile = find->second.get();
 
     gfx::Rect tile_bounds =
         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 
     float distance_to_visible =
         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
         content_to_screen_scale;
     TilePriority priority(
         resolution_, TilePriority::EVENTUALLY, distance_to_visible);
     tile->SetPriority(tree, priority);
+    eventually_tiles_.push_back(tile);
+    eviction_tiles_.push_back(tile);
   }
+
+  last_update_tree_ = tree;
 }
 
 void PictureLayerTiling::SetLiveTilesRect(
     const gfx::Rect& new_live_tiles_rect) {
   DCHECK(new_live_tiles_rect.IsEmpty() ||
          ContentRect().Contains(new_live_tiles_rect));
   if (live_tiles_rect_ == new_live_tiles_rect)
     return;
 
   // Iterate to delete all tiles outside of our new live_tiles rect.
@@ skipping 49 matching lines @@
     client_->UpdatePile(it->second.get());
   }
 }
 
 void PictureLayerTiling::UpdateTilesToCurrentPile() {
   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
     client_->UpdatePile(it->second.get());
   }
 }
 
+size_t PictureLayerTiling::RequiredGPUMemoryInBytes() const {
+  size_t amount = 0;
+  for (TilingData::Iterator iter(&tiling_data_,
+                                 last_visible_rect_in_content_space_);
+       iter;
+       ++iter) {
+    TileMap::const_iterator find = tiles_.find(iter.index());
+    if (find == tiles_.end())
+      continue;
+    Tile* tile = find->second.get();
+    amount += tile->GPUMemoryUsageInBytes();
+  }
+  return amount;
+}
+
 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
   state->SetInteger("num_tiles", tiles_.size());
   state->SetDouble("content_scale", contents_scale_);
   state->Set("content_bounds",
              MathUtil::AsValue(ContentRect().size()).release());
   return state.PassAs<base::Value>();
 }
 
 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
@@ skipping 147 matching lines @@
     if (delta < event.distance)
       break;
   }
 
   gfx::Rect result(origin_x, origin_y, width, height);
   if (cache)
     cache->previous_result = result;
   return result;
 }
 
+PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
+    : tiling_(NULL), current_index_(0) {}
+
+PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
+    PictureLayerTiling* tiling)
+    : tiling_(tiling), current_index_(0) {
+  Tile* tile = tiling_->RasterTileForPriority(current_index_);
+  if (!tile)
+    return;
+
+  RasterMode raster_mode =
+      tile->DetermineRasterModeForTree(tiling_->last_update_tree_);
+  if (!tile->NeedsRasterForMode(raster_mode))
+    ++(*this);
+}
+
+PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
+
+void PictureLayerTiling::TilingRasterTileIterator::operator++() {
+  DCHECK(*this);
+  while (true) {
+    ++current_index_;
+
+    Tile* tile = tiling_->RasterTileForPriority(current_index_);
+    if (!tile)
+      break;
+
+    RasterMode raster_mode =
+        tile->DetermineRasterModeForTree(tiling_->last_update_tree_);
+    if (tile->NeedsRasterForMode(raster_mode))
+      break;
+  }
+}
+
+PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
+    : tiling_(NULL), current_index_(0) {}
+
+PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
+    PictureLayerTiling* tiling)
+    : tiling_(tiling), current_index_(0) {
+  Tile* tile = tiling_->EvictionTileForPriority(current_index_);
+  if (!tile)
+    return;
+
+  if (!tile->HasResources())
+    ++(*this);
+}
+
+PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {}
+
+void PictureLayerTiling::TilingEvictionTileIterator::operator++() {
+  DCHECK(*this);
+  while (true) {
+    ++current_index_;
+
+    Tile* tile = tiling_->EvictionTileForPriority(current_index_);
+    if (!tile || tile->HasResources())
+      break;
+  }
+}
+
 }  // namespace cc