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/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 {
 
 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 486 matching lines @@
   gfx::Rect soon_border_rect = visible_rect_in_content_space;
   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_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 354 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),
+      unoccluded_now_tiles_index_(0u),
+      current_tile_(nullptr) {
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
     PictureLayerTiling* tiling,
     TreePriority tree_priority,

[ajuma, 2014/10/23 23:12:54]

Unused now, remove?

[vmpstr, 2014/10/29 18:19:41]

Done.

     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),
+      unoccluded_now_tiles_index_(0),
+      current_tile_(nullptr) {
+  switch (category) {
+    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 EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      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 SOON_AND_REQUIRED_FOR_ACTIVATION:

[ajuma, 2014/10/23 23:12:54]

Why is there nothing to do for this case? Is it because SOON tiles are never
required for activation? (And if that's the case, why do we have this category
at all?)

[vmpstr, 2014/10/29 18:19:41]

Yes and removed.

+      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 (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_;
+
+  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 (tile && tile->HasResources()) {
+      current_tile_ = tile;
+      break;
+    }
+    ++spiral_iterator_;
+    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(
+    bool first_run) {
+  if (!first_run) {
+    if (processing_occluded_now_tiles_)
+      ++visible_iterator_;
+    else
+      ++unoccluded_now_tiles_index_;
+  }
+
+  current_tile_ = nullptr;
+  while (visible_iterator_ ||
+         (unoccluded_now_tiles_index_ < unoccluded_now_tiles_.size())) {
+    if (!visible_iterator_)
+      processing_occluded_now_tiles_ = false;
+
+    if (processing_occluded_now_tiles_) {
+      std::pair<int, int> next_index = visible_iterator_.index();
+      Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+      if (!tile || !tile->HasResources()) {
+        ++visible_iterator_;
+        continue;
+      }
+
+      bool tile_required_for_activation = false;
+      if (tiling_->client_->GetTree() == PENDING_TREE)
+        tile_required_for_activation =
+            tiling_->IsTileRequiredForActivation(tile);
+      if ((eviction_category_ == NOW_AND_REQUIRED_FOR_ACTIVATION &&
+           !tile_required_for_activation) ||
+          (eviction_category_ == NOW && tile_required_for_activation)) {
+        ++visible_iterator_;
+        continue;
+      }
+
+      if (!tiling_->IsTileOccluded(tile)) {
+        unoccluded_now_tiles_.push_back(tile);
+        ++visible_iterator_;
+        continue;
+      }
+
+      current_tile_ = tile;
+      break;
+    }
+
+    Tile* tile = unoccluded_now_tiles_[unoccluded_now_tiles_index_];
+    DCHECK(tile);
+    if (!tile->HasResources()) {
+      ++unoccluded_now_tiles_index_;
+      continue;
+    }

[ajuma, 2014/10/23 23:12:54]

Why don't we need to consider whether the tile is required for activation when
dealing with unoccluded tiles?

[vmpstr, 2014/10/29 18:19:41]

Tile that is occluded is not required for activation... I've added some comments
throughout the code that hopefully makes it easier to read.

+
+    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 EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      break;
+    case SOON:
+      AdvanceSoon(false);
+      break;
+    case SOON_AND_REQUIRED_FOR_ACTIVATION:
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceNow(false);
+      break;
+  }
   return *this;
 }
 
 }  // namespace cc