cc: Use reverse spiral iterator in tiling 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 304 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 89 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 378 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),
+      eviction_category_(EVENTUALLY),
+      processing_occluded_now_tiles_(false),
+      processing_soon_border_rect_(false),
+      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);
+    : tiling_(tiling),
+      eviction_category_(category),
+      processing_occluded_now_tiles_(true),
+      processing_soon_border_rect_(true),
+      current_tile_(nullptr) {
+  switch (category) {

[reveman, 2014/11/18 20:56:21]

We already have a category switch statement at a different level, in
PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextCategory. This makes
me suspicious. It's not a performance concern. My intuition just tells me that
we're doing something wrong if we need this. It looks like we're forcing
ourselves to use some existing concept (TilingEvictionTileIterator and
categories) when it doesn't map to what's really going on.

This problem existed before this patch too but it was harder to tell as all we
did was pick a vector based on it.

+    case EVENTUALLY:
+      if (tiling_->has_eventually_rect_tiles_) {
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &tiling_->tiling_data_, tiling_->current_eventually_rect_,
+            tiling_->current_skewport_rect_,
+            tiling_->current_soon_border_rect_);
+      }
+      AdvanceEventually(true);
+      break;
+    case SOON:
+      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(true);
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      if (tiling_->has_visible_rect_tiles_) {
+        visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
+                                                 tiling_->current_visible_rect_,
+                                                 false /* include_borders */);
+      }
+      AdvanceNow(true);
+      break;
+  }
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceEventually(
+    bool first_run) {
+  if (!first_run)
+    ++spiral_iterator_;
+
+  current_tile_ = nullptr;
+  while (spiral_iterator_) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+
+    // If a tile has resources, then it is a valid tile to return.
+    if (tile && tile->HasResources()) {
+      current_tile_ = tile;
+      break;
+    }
+    ++spiral_iterator_;
+  }
+
+  if (current_tile_)
+    tiling_->UpdateTileAndTwinPriority(current_tile_);
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceSoon(
+    bool first_run) {
+  if (!first_run)
+    ++spiral_iterator_;
+
+  // For the soon rect, we process both the soon border rect and
+  // the skewport rect.
+  current_tile_ = nullptr;
+  while (spiral_iterator_) {

[USE eero AT chromium.org, 2014/11/20 15:03:57]

This is wrong.
If there are skewport tiles but no soon border rect tiles, the constructor does
not initialize the spiral iterator. Then in here, the while block won't be
executed and the spiral iterator won't be replaced with skewport iterator thus
skewport tiles won't be iterated at all.

+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+
+    // If the tile has resources, we can return it.
+    if (tile && tile->HasResources()) {
+      current_tile_ = tile;
+      break;
+    }
+    ++spiral_iterator_;
+
+    // If we ran out of tiles, but we were processing the soon border rect, then
+    // rebuild the iterator to iterate over skewport.

[reveman, 2014/11/18 20:56:21]

Why is Skewport not a different category? Wouldn't that make advancing
Eventually, Soon and Skewport the same and remove this special case?

+    if (!spiral_iterator_ && processing_soon_border_rect_) {
+      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_);
+      }
+      processing_soon_border_rect_ = false;
+    }
+  }
+
+  if (current_tile_)
+    tiling_->UpdateTileAndTwinPriority(current_tile_);
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceNow(

[reveman, 2014/11/18 20:56:21]

Could we either generalize the Now category code so it's the same as other
categories (just operating on a different data set). Or handle the difference in
LayerEvictionTileIterator instead of hiding it in here? ie. making the layer
iterator first iterate "prepaint" then "visible",
LayerEvictionTileIterator::current_iterator_ ->
LayerEvictionTileIterator::current_prepaint_iterator_/current_visible_iterator_.

+    bool first_run) {
+  if (!first_run)
+    ++visible_iterator_;
+
+  // For NOW bin, we process the visible rect, returning occluded tiles first,
+  // followed by unoccluded tiles.
+  current_tile_ = nullptr;
+  while (visible_iterator_ || processing_occluded_now_tiles_) {
+    if (!visible_iterator_) {
+      processing_occluded_now_tiles_ = false;
+      if (tiling_->has_visible_rect_tiles_) {
+        visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
+                                                 tiling_->current_visible_rect_,
+                                                 false /* include_borders */);
+      }
+      continue;
+    }
+
+    std::pair<int, int> next_index = visible_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+
+    // If the tile doesn't have resources, then we won't return it.
+    if (!tile || !tile->HasResources()) {
+      ++visible_iterator_;
+      continue;
+    }
+
+    bool tile_required_for_activation = false;
+    if (tiling_->client_->GetTree() == PENDING_TREE) {
+      tile_required_for_activation =
+          tiling_->IsTileRequiredForActivationIfVisible(tile);
+    }
+
+    // Skip the tile if it doesn't match the requested activation criteria.
+    if ((eviction_category_ == NOW_AND_REQUIRED_FOR_ACTIVATION &&
+         !tile_required_for_activation) ||
+        (eviction_category_ == NOW && tile_required_for_activation)) {
+      ++visible_iterator_;
+      continue;
+    }
+
+    // If the tile is occlusion doesn't match the phase we're processing now,
+    // skip it, since it was either already processed or will be processed
+    // later.
+    if (tiling_->IsTileOccluded(tile) != processing_occluded_now_tiles_) {
+      ++visible_iterator_;
+      continue;
+    }
+
+    // All of the above checks passed, so the tile is good to return now.
+    current_tile_ = tile;
+    break;
+  }
+
+  if (current_tile_)
+    tiling_->UpdateTileAndTwinPriority(current_tile_);
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
 }
 
 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:
+      AdvanceEventually(false);
+      break;
+    case SOON:
+      AdvanceSoon(false);
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceNow(false);
+      break;
+  }
   return *this;
 }
 
 }  // namespace cc