cc: Implement geometry-based tile eviction

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 9d8ea84e6966d715afecaff0588fc97e584c2b7c..0e1f14bf4ceab968510a3ceea08f089e724352eb 100644
--- a/cc/resources/picture_layer_tiling.cc
+++ b/cc/resources/picture_layer_tiling.cc
@@ -25,35 +25,6 @@ namespace {
 
 const float kSoonBorderDistanceInScreenPixels = 312.f;
 
-class TileEvictionOrder {
- public:
-  explicit TileEvictionOrder(TreePriority tree_priority)
-      : tree_priority_(tree_priority) {}
-  ~TileEvictionOrder() {}
-
-  bool operator()(const Tile* a, const Tile* b) {
-    const TilePriority& a_priority =
-        a->priority_for_tree_priority(tree_priority_);
-    const TilePriority& b_priority =
-        b->priority_for_tree_priority(tree_priority_);
-
-    DCHECK(a_priority.priority_bin == b_priority.priority_bin);
-    DCHECK(a->required_for_activation() == b->required_for_activation());
-
-    // Or if a is occluded and b is unoccluded.
-    bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
-    bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
-    if (a_is_occluded != b_is_occluded)
-      return a_is_occluded;
-
-    // Or if a is farther away from visible.
-    return a_priority.distance_to_visible > b_priority.distance_to_visible;
-  }
-
- private:
-  TreePriority tree_priority_;
-};
-
 }  // namespace
 
 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
@@ -79,9 +50,7 @@ PictureLayerTiling::PictureLayerTiling(float contents_scale,
       has_visible_rect_tiles_(false),
       has_skewport_rect_tiles_(false),
       has_soon_border_rect_tiles_(false),
-      has_eventually_rect_tiles_(false),
-      eviction_tiles_cache_valid_(false),
-      eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
+      has_eventually_rect_tiles_(false) {
   gfx::Size content_bounds =
       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
@@ -145,7 +114,6 @@ Tile* PictureLayerTiling::CreateTile(int i,
     tile->set_tiling_index(i, j);
     tiles_[key] = tile;
   }
-  eviction_tiles_cache_valid_ = false;
   return tile.get();
 }
 
@@ -468,7 +436,6 @@ bool PictureLayerTiling::RemoveTileAt(int i,
     return false;
   found->second->set_shared(false);
   tiles_.erase(found);
-  eviction_tiles_cache_valid_ = false;
   if (recycled_twin) {
     // Recycled twin does not also have a recycled twin, so pass NULL.
     recycled_twin->RemoveTileAt(i, j, NULL);
@@ -485,7 +452,6 @@ void PictureLayerTiling::Reset() {
       recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL);
   }
   tiles_.clear();
-  eviction_tiles_cache_valid_ = false;
 }
 
 gfx::Rect PictureLayerTiling::ComputeSkewport(
@@ -594,8 +560,6 @@ void PictureLayerTiling::ComputeTilePriorityRects(
   last_viewport_in_layer_space_ = viewport_in_layer_space;
   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 
-  eviction_tiles_cache_valid_ = false;
-
   current_visible_rect_ = visible_rect_in_content_space;
   current_skewport_rect_ = skewport;
   current_soon_border_rect_ = soon_border_rect;
@@ -998,92 +962,6 @@ gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
   return result;
 }
 
-void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
-    TreePriority tree_priority) {
-  if (eviction_tiles_cache_valid_ &&
-      eviction_cache_tree_priority_ == tree_priority)
-    return;
-
-  eviction_tiles_now_.clear();
-  eviction_tiles_now_and_required_for_activation_.clear();
-  eviction_tiles_soon_.clear();
-  eviction_tiles_soon_and_required_for_activation_.clear();
-  eviction_tiles_eventually_.clear();
-  eviction_tiles_eventually_and_required_for_activation_.clear();
-
-  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    Tile* tile = it->second.get();
-    UpdateTileAndTwinPriority(tile);
-    const TilePriority& priority =
-        tile->priority_for_tree_priority(tree_priority);
-    switch (priority.priority_bin) {
-      case TilePriority::EVENTUALLY:
-        if (tile->required_for_activation())
-          eviction_tiles_eventually_and_required_for_activation_.push_back(
-              tile);
-        else
-          eviction_tiles_eventually_.push_back(tile);
-        break;
-      case TilePriority::SOON:
-        if (tile->required_for_activation())
-          eviction_tiles_soon_and_required_for_activation_.push_back(tile);
-        else
-          eviction_tiles_soon_.push_back(tile);
-        break;
-      case TilePriority::NOW:
-        if (tile->required_for_activation())
-          eviction_tiles_now_and_required_for_activation_.push_back(tile);
-        else
-          eviction_tiles_now_.push_back(tile);
-        break;
-    }
-  }
-
-  // TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that
-  // can be updated for each of the queues.
-  TileEvictionOrder sort_order(tree_priority);
-  std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order);
-  std::sort(eviction_tiles_now_and_required_for_activation_.begin(),
-            eviction_tiles_now_and_required_for_activation_.end(),
-            sort_order);
-  std::sort(
-      eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order);
-  std::sort(eviction_tiles_soon_and_required_for_activation_.begin(),
-            eviction_tiles_soon_and_required_for_activation_.end(),
-            sort_order);
-  std::sort(eviction_tiles_eventually_.begin(),
-            eviction_tiles_eventually_.end(),
-            sort_order);
-  std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(),
-            eviction_tiles_eventually_and_required_for_activation_.end(),
-            sort_order);
-
-  eviction_tiles_cache_valid_ = true;
-  eviction_cache_tree_priority_ = tree_priority;
-}
-
-const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles(
-    TreePriority tree_priority,
-    EvictionCategory category) {
-  UpdateEvictionCacheIfNeeded(tree_priority);
-  switch (category) {
-    case EVENTUALLY:
-      return &eviction_tiles_eventually_;
-    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
-      return &eviction_tiles_eventually_and_required_for_activation_;
-    case SOON:
-      return &eviction_tiles_soon_;
-    case SOON_AND_REQUIRED_FOR_ACTIVATION:
-      return &eviction_tiles_soon_and_required_for_activation_;
-    case NOW:
-      return &eviction_tiles_now_;
-    case NOW_AND_REQUIRED_FOR_ACTIVATION:
-      return &eviction_tiles_now_and_required_for_activation_;
-  }
-  NOTREACHED();
-  return &eviction_tiles_eventually_;
-}
-
 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
     : tiling_(NULL), current_tile_(NULL) {}
 
@@ -1217,48 +1095,255 @@ operator++() {
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
-    : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
+    : tiling_(nullptr),
+      tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      eviction_category_(EVENTUALLY),
+      processing_soon_border_rect_(false),
+      skip_shared_out_of_order_tiles_(false),
+      unoccluded_now_tiles_index_(0u),
+      current_tile_(nullptr) {
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
     PictureLayerTiling* tiling,
     TreePriority tree_priority,
-    EvictionCategory category)
-    : eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)),
-      // Note: initializing to "0 - 1" works as overflow is well defined for
-      // unsigned integers.
-      current_eviction_tiles_index_(static_cast<size_t>(0) - 1) {
-  DCHECK(eviction_tiles_);
-  ++(*this);
+    EvictionCategory category,
+    bool skip_shared_out_of_order_tiles)
+    : tiling_(tiling),
+      tree_priority_(tree_priority),
+      eviction_category_(category),
+      processing_soon_border_rect_(true),
+      skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
+      unoccluded_now_tiles_index_(0u),
+      current_tile_(nullptr) {
+  TilePriority::PriorityBin max_tile_priority_bin =
+      tiling_->client_->GetMaxTilePriorityBin();

[vmpstr, 2014/11/19 16:47:58]

I'm not sure if this check matters here. The order here will only matter for the
layer. That is, the layer will consume all of these tiles and this will only
determine the cross-tilings order. However, since MaxTilePriorityBin is a layer
property, if it's set at EVENTUALLY, then all tiles will be returned as
eventually. If this is an optimization, then it's not worth it. If this is a
correctness fix, then I don't see it (can you explain?).

[USE eero AT chromium.org, 2014/11/20 14:54:38]

[...]
It's a bit of both. I removed if from here (thus removed the optimization part)
and added the correctness fix to AdvanceNow (IsTileOccluded should not be called
if the final priority bin is not NOW.

+  switch (eviction_category_) {
+    case EVENTUALLY:
+    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      if (tiling_->has_eventually_rect_tiles_) {
+        if (max_tile_priority_bin < TilePriority::EVENTUALLY)
+          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+              &tiling_->tiling_data_, tiling_->current_eventually_rect_,
+              tiling_->current_skewport_rect_,
+              tiling_->current_soon_border_rect_);
+        else
+          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+              &tiling_->tiling_data_, tiling_->current_eventually_rect_,
+              gfx::Rect(), gfx::Rect());
+        AdvanceEventually();
+      }
+      break;
+    case SOON:
+    case SOON_AND_REQUIRED_FOR_ACTIVATION:

[vmpstr, 2014/11/19 16:47:58]

Doing both SOON and SOON_AND_RFA would return double the tiles no? (Assuming
they aren't actually evicted but iterated).

[USE eero AT chromium.org, 2014/11/20 14:54:38]

No. SOON returns only tiles which are not required-for-activation in the pending
tree while SOON_AND_RFA returns only tiles which are required-for-activation in
the pending tree.

+      if (max_tile_priority_bin <= TilePriority::SOON &&
+          (tiling_->has_skewport_rect_tiles_ ||
+           tiling_->has_soon_border_rect_tiles_)) {
+        if (tiling_->has_soon_border_rect_tiles_)
+          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+              &tiling_->tiling_data_, tiling_->current_soon_border_rect_,
+              tiling_->current_skewport_rect_, tiling_->current_visible_rect_);
+        AdvanceSoon();
+      }
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      if (max_tile_priority_bin <= TilePriority::NOW &&
+          tiling_->has_visible_rect_tiles_) {
+        visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
+                                                 tiling_->current_visible_rect_,
+                                                 false /* include_borders */);
+        AdvanceNow();
+      }
+      break;
+  }
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
 }
 
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceEventually() {
+  bool required_for_activation =
+      eviction_category_ == EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION;
+
+  while (spiral_iterator_) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+    ++spiral_iterator_;
+    if (!tile || !tile->HasResources())
+      continue;
+    if (PreparseTileUnlessReturningShouldBeDoneByTwin(tile) &&
+        tile->required_for_activation() == required_for_activation) {
+      current_tile_ = tile;
+      return;
+    }
+  }
+
+  current_tile_ = nullptr;
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceSoon() {
+  bool required_for_activation =
+      eviction_category_ == SOON_AND_REQUIRED_FOR_ACTIVATION;
+
+  for (;;) {
+    if (!spiral_iterator_) {
+      if (!processing_soon_border_rect_)
+        break;
+      // Max tile priority bin should never be SOON so there is no need to
+      // handle that case (to return visible tiles as SOON tiles).
+      DCHECK_LT(tiling_->client_->GetMaxTilePriorityBin(), TilePriority::SOON);
+      processing_soon_border_rect_ = false;
+      if (tiling_->has_skewport_rect_tiles_) {
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &tiling_->tiling_data_, tiling_->current_skewport_rect_,
+            tiling_->current_visible_rect_, tiling_->current_visible_rect_);
+      }
+      if (!spiral_iterator_)
+        break;
+    }
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+    ++spiral_iterator_;
+    if (!tile || !tile->HasResources())
+      continue;
+    if (PreparseTileUnlessReturningShouldBeDoneByTwin(tile) &&
+        tile->required_for_activation() == required_for_activation) {
+      current_tile_ = tile;
+      return;
+    }
+  }
+
+  current_tile_ = nullptr;
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceNow() {
+  bool required_for_activation =
+      eviction_category_ == NOW_AND_REQUIRED_FOR_ACTIVATION;
+
+  if (visible_iterator_) {
+    WhichTree tree = tiling_->client_->GetTree();
+    bool skip_all_shared_tiles =
+        skip_shared_out_of_order_tiles_ &&
+        tree_priority_ == (tree == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
+                                               : SMOOTHNESS_TAKES_PRIORITY);
+    do {
+      std::pair<int, int> next_index = visible_iterator_.index();
+      Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+      ++visible_iterator_;
+      if (!tile || !tile->HasResources())
+        continue;
+      if (skip_all_shared_tiles && tile->is_shared())
+        continue;
+      if (tree == PENDING_TREE &&
+          tiling_->IsTileRequiredForActivationIfVisible(tile) !=
+              required_for_activation)
+        continue;
+      if (!tiling_->IsTileOccluded(tile)) {
+        unoccluded_now_tiles_.push_back(tile);
+        continue;
+      }
+      if (PreparseTileUnlessReturningShouldBeDoneByTwin(tile) &&
+          tile->required_for_activation() == required_for_activation) {
+        current_tile_ = tile;
+        return;
+      }
+    } while (visible_iterator_);
+  }
+
+  while (unoccluded_now_tiles_index_ < unoccluded_now_tiles_.size()) {
+    Tile* tile = unoccluded_now_tiles_[unoccluded_now_tiles_index_];
+    ++unoccluded_now_tiles_index_;
+    DCHECK(tile);
+    if (!tile->HasResources())
+      continue;
+    if (PreparseTileUnlessReturningShouldBeDoneByTwin(tile) &&
+        tile->required_for_activation() == required_for_activation) {
+      current_tile_ = tile;
+      return;
+    }
+  }
+
+  current_tile_ = nullptr;
+}
+
+bool PictureLayerTiling::TilingEvictionTileIterator::
+    PreparseTileUnlessReturningShouldBeDoneByTwin(Tile* tile) const {

[vmpstr, 2014/11/19 16:47:58]

This is named a bit awkwardly. It feels like it's two functions
"IsReturnedByTwin(tile)" and "UpdateTileAndTwinPriority" (which already exists
on tiling)

[USE eero AT chromium.org, 2014/11/20 14:54:38]

Yes, and avoids calling costly UpdateTileAndTwinPriority when not absolutely
needed. But those two functionalities are quite easy to separate now, so I did
that.

+  if (skip_shared_out_of_order_tiles_ && tile->is_shared()) {
+    WhichTree tree = tiling_->client_->GetTree();
+    switch (tree_priority_) {
+      case SMOOTHNESS_TAKES_PRIORITY:
+        // The priority for tile priority of a shared tile will be the active
+        // priority thus return shared tiles from the active tree.
+        if (tree != ACTIVE_TREE)
+          return false;
+        break;
+      case NEW_CONTENT_TAKES_PRIORITY:
+        // The priority for tile priority of a shared tile will be the pending
+        // priority thus return shared tiles from the pending tree.
+        if (tree != PENDING_TREE)
+          return false;
+        break;
+      case SAME_PRIORITY_FOR_BOTH_TREES: {
+        // The priority for tile priority of a shared tile will be a combined
+        // priority thus return shared tiles from a higher priority tree.
+        tiling_->UpdateTileAndTwinPriority(tile);
+        WhichTree other_tree = tree == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
+        const TilePriority& priority = tile->priority(tree);
+        const TilePriority& other_priority = tile->priority(other_tree);
+        if (priority.priority_bin != other_priority.priority_bin)
+          return priority.priority_bin < other_priority.priority_bin;
+        const bool occluded = tile->is_occluded(tree);
+        const bool other_occluded = tile->is_occluded(other_tree);
+        if (occluded != other_occluded)
+          return !occluded;
+        if (priority.distance_to_visible != other_priority.distance_to_visible)
+          return priority.distance_to_visible <
+                 other_priority.distance_to_visible;
+        // If priorities are the same, it does not matter which tree returns
+        // the tile. Let's pick the active tree.
+        return tree == ACTIVE_TREE;
+      }
+      default:
+        NOTREACHED();
+    }
+  }
+  tiling_->UpdateTileAndTwinPriority(tile);
+  return true;
+}
+
 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
-  return eviction_tiles_ &&
-         current_eviction_tiles_index_ != eviction_tiles_->size();
+  return !!current_tile_;
 }
 
 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
   DCHECK(*this);
-  return (*eviction_tiles_)[current_eviction_tiles_index_];
+  return current_tile_;
 }
 
 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
   DCHECK(*this);
-  return (*eviction_tiles_)[current_eviction_tiles_index_];
+  return current_tile_;
 }
 
 PictureLayerTiling::TilingEvictionTileIterator&
 PictureLayerTiling::TilingEvictionTileIterator::
 operator++() {
   DCHECK(*this);
-  do {
-    ++current_eviction_tiles_index_;
-  } while (current_eviction_tiles_index_ != eviction_tiles_->size() &&
-           !(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources());
-
+  switch (eviction_category_) {
+    case EVENTUALLY:
+    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceEventually();
+      break;
+    case SOON:
+    case SOON_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceSoon();
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceNow();
+      break;
+  }
   return *this;
 }