cc: Add tiling raster tile iterators.

cc/resources/picture_layer_tiling.cc

Index: cc/resources/picture_layer_tiling.cc
diff --git a/cc/resources/picture_layer_tiling.cc b/cc/resources/picture_layer_tiling.cc
index 939e0b163d4a459aa50d0437a9aec5b94c2f8230..2efa10e60c12d2130bab003de35624d63fba4658 100644
--- a/cc/resources/picture_layer_tiling.cc
+++ b/cc/resources/picture_layer_tiling.cc
@@ -10,12 +10,53 @@
 
 #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,
@@ -64,6 +105,59 @@ 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())
@@ -430,6 +524,14 @@ void PictureLayerTiling::UpdateTilePriorities(
   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);
@@ -441,11 +543,14 @@ void PictureLayerTiling::UpdateTilePriorities(
     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;
@@ -464,6 +569,8 @@ void PictureLayerTiling::UpdateTilePriorities(
 
     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
@@ -486,7 +593,11 @@ void PictureLayerTiling::UpdateTilePriorities(
     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(
@@ -556,6 +667,21 @@ void PictureLayerTiling::UpdateTilesToCurrentPile() {
   }
 }
 
+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());
@@ -723,4 +849,65 @@ gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
   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