cc: Implement geometry-based tile eviction

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 <set>
 
 #include "base/debug/trace_event.h"
 #include "base/debug/trace_event_argument.h"
 #include "base/logging.h"
 #include "cc/base/math_util.h"
 #include "cc/resources/tile.h"
 #include "cc/resources/tile_priority.h"
 #include "ui/gfx/geometry/point_conversions.h"
 #include "ui/gfx/geometry/rect_conversions.h"
 #include "ui/gfx/geometry/safe_integer_conversions.h"
 #include "ui/gfx/geometry/size_conversions.h"
 
 namespace cc {
 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(
     float contents_scale,
     const gfx::Size& layer_bounds,
     PictureLayerTilingClient* client) {
   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
                                                 layer_bounds,
                                                 client));
 }
 
 PictureLayerTiling::PictureLayerTiling(float contents_scale,
                                        const gfx::Size& layer_bounds,
                                        PictureLayerTilingClient* client)
     : contents_scale_(contents_scale),
       layer_bounds_(layer_bounds),
       resolution_(NON_IDEAL_RESOLUTION),
       client_(client),
       tiling_data_(gfx::Size(), gfx::Size(), kBorderTexels),
       last_impl_frame_time_in_seconds_(0.0),
       content_to_screen_scale_(0.f),
       can_require_tiles_for_activation_(false),
       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);
   if (tile_size.IsEmpty()) {
     layer_bounds_ = gfx::Size();
     content_bounds = gfx::Size();
   }
 
   DCHECK(!gfx::ToFlooredSize(
       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
@@ skipping 43 matching lines @@
     }
   }
 
   // Create a new tile because our twin didn't have a valid one.
   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
   if (tile.get()) {
     DCHECK(!tile->is_shared());
     tile->set_tiling_index(i, j);
     tiles_[key] = tile;
   }
-  eviction_tiles_cache_valid_ = false;
   return tile.get();
 }
 
 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
   const PictureLayerTiling* twin_tiling =
       client_->GetPendingOrActiveTwinTiling(this);
   bool include_borders = false;
   for (TilingData::Iterator iter(
            &tiling_data_, live_tiles_rect_, include_borders);
        iter;
@@ skipping 302 matching lines @@
 }
 
 bool PictureLayerTiling::RemoveTileAt(int i,
                                       int j,
                                       PictureLayerTiling* recycled_twin) {
   TileMap::iterator found = tiles_.find(TileMapKey(i, j));
   if (found == tiles_.end())
     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);
   }
   return true;
 }
 
 void PictureLayerTiling::Reset() {
   live_tiles_rect_ = gfx::Rect();
   PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
     it->second->set_shared(false);
     if (recycled_twin)
       recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL);
   }
   tiles_.clear();
-  eviction_tiles_cache_valid_ = false;
 }
 
 gfx::Rect PictureLayerTiling::ComputeSkewport(
     double current_frame_time_in_seconds,
     const gfx::Rect& visible_rect_in_content_space) const {
   gfx::Rect skewport = visible_rect_in_content_space;
   if (last_impl_frame_time_in_seconds_ == 0.0)
     return skewport;
 
   double time_delta =
@@ skipping 88 matching lines @@
   float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale_;
   soon_border_rect.Inset(-border, -border, -border, -border);
 
   // Update the tiling state.
   SetLiveTilesRect(eventually_rect);
 
   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
   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;
   current_eventually_rect_ = eventually_rect;
   current_occlusion_in_layer_space_ = occlusion_in_layer_space;
 
   // Update has_*_tiles state.
   gfx::Rect tiling_rect(tiling_size());
 
   has_visible_rect_tiles_ = tiling_rect.Intersects(current_visible_rect_);
@@ skipping 382 matching lines @@
     if (delta < event.distance)
       break;
   }
 
   gfx::Rect result(origin_x, origin_y, width, height);
   if (cache)
     cache->previous_result = result;
   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) {}
 
 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
     PictureLayerTiling* tiling)
     : tiling_(tiling), phase_(VISIBLE_RECT), current_tile_(NULL) {
   if (!tiling_->has_visible_rect_tiles_) {
     AdvancePhase();
     return;
   }
@@ skipping 113 matching lines @@
     }
     current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
   }
 
   if (current_tile_)
     tiling_->UpdateTileAndTwinPriority(current_tile_);
   return *this;
 }
 
 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;
 }
 
 }  // namespace cc