cc: Use reverse spiral iterator in tiling eviction.

cc/layers/picture_layer_impl_unittest.cc

 // Copyright 2013 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/layers/picture_layer_impl.h"
 
 #include <algorithm>
 #include <limits>
 #include <set>
 #include <utility>
@@ skipping 2798 matching lines @@
       pending_layer_, SAME_PRIORITY_FOR_BOTH_TREES);
   EXPECT_FALSE(it);
 
   host_impl_.tile_manager()->InitializeTilesWithResourcesForTesting(all_tiles);
 
   std::set<Tile*> unique_tiles;
   float expected_scales[] = {2.0f, 0.3f, 0.7f, low_res_factor, 1.0f};
   size_t scale_index = 0;
   bool reached_visible = false;
   Tile* last_tile = nullptr;
+  int distance_decreasing = 0;
+  int distance_increasing = 0;
   for (it = PictureLayerImpl::LayerEvictionTileIterator(
            pending_layer_, SAME_PRIORITY_FOR_BOTH_TREES);
        it;
        ++it) {
     Tile* tile = *it;
     if (!last_tile)
       last_tile = tile;
 
     EXPECT_TRUE(tile);
 
     TilePriority priority = tile->priority(PENDING_TREE);
 
     if (priority.priority_bin == TilePriority::NOW) {
       reached_visible = true;
       last_tile = tile;
       break;
     }
 
     EXPECT_FALSE(tile->required_for_activation());
 
     while (std::abs(tile->contents_scale() - expected_scales[scale_index]) >
            std::numeric_limits<float>::epsilon()) {
       ++scale_index;
       ASSERT_LT(scale_index, arraysize(expected_scales));
     }
 
     EXPECT_FLOAT_EQ(tile->contents_scale(), expected_scales[scale_index]);
     unique_tiles.insert(tile);
 
-    // If the tile is the same rough bin as last tile (same activation, bin, and
-    // scale), then distance should be decreasing.
     if (tile->required_for_activation() ==
             last_tile->required_for_activation() &&
         priority.priority_bin ==
             last_tile->priority(PENDING_TREE).priority_bin &&
         std::abs(tile->contents_scale() - last_tile->contents_scale()) <
             std::numeric_limits<float>::epsilon()) {
-      EXPECT_LE(priority.distance_to_visible,
-                last_tile->priority(PENDING_TREE).distance_to_visible);
+      if (priority.distance_to_visible <=
+          last_tile->priority(PENDING_TREE).distance_to_visible) {
+        ++distance_decreasing;
+      } else {
+        ++distance_increasing;
+      }
     }
 
     last_tile = tile;
   }
 
+  EXPECT_EQ(7, distance_increasing);
+  EXPECT_EQ(55, distance_decreasing);

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

Is there an intuitive explanation for why we get these numbers?

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

Well.. I'm not sure how intuitive it is, starting with eventually rect we'll
spiral down, but going from side to corner the distance will increase and going
from corner to side the distance will decrease, so it isn't technically distance
decreasing order. This check is just so that we're _mostly_ distance decreasing.
In raster iterators, I have something like distance_decreasing > 3 * total_tiles
/ 4, but I figured might as well put in the actual numbers.

If you have a suggestion for a better solution, I'll be happy to put it in (I'm
not exactly proud of this test :) )

[ajuma, 2014/10/29 19:42:39]

Ok, I mostly wanted to find out if these specific values were intended to be
immediately obvious from reading the test, since if they were, I was clearly
missing something :)  It makes sense that we're checking that we're mostly
distance decreasing. I'd suggest adding a comment about this.

+
   EXPECT_TRUE(reached_visible);
   EXPECT_EQ(65u, unique_tiles.size());
 
   scale_index = 0;
   bool reached_required = false;
   for (; it; ++it) {
     Tile* tile = *it;
     EXPECT_TRUE(tile);
 
     TilePriority priority = tile->priority(PENDING_TREE);
@@ skipping 787 matching lines @@
 class OcclusionTrackingSettings : public LowResTilingsSettings {
  public:
   OcclusionTrackingSettings() { use_occlusion_for_tile_prioritization = true; }
 };
 
 class OcclusionTrackingPictureLayerImplTest : public PictureLayerImplTest {
  public:
   OcclusionTrackingPictureLayerImplTest()
       : PictureLayerImplTest(OcclusionTrackingSettings()) {}
 
-  void VerifyEvictionConsidersOcclusion(
-      PictureLayerImpl* layer,
-      size_t expected_occluded_tile_count[NUM_TREE_PRIORITIES]) {
+  void VerifyEvictionConsidersOcclusion(PictureLayerImpl* layer,
+                                        WhichTree tree,
+                                        size_t expected_occluded_tile_count) {
     for (int priority_count = 0; priority_count < NUM_TREE_PRIORITIES;
          ++priority_count) {
       TreePriority tree_priority = static_cast<TreePriority>(priority_count);
       size_t occluded_tile_count = 0u;
       Tile* last_tile = nullptr;
 
       for (PictureLayerImpl::LayerEvictionTileIterator it =
                PictureLayerImpl::LayerEvictionTileIterator(layer,
                                                            tree_priority);
            it;
            ++it) {
         Tile* tile = *it;
         if (!last_tile)
           last_tile = tile;
 
         // The only way we will encounter an occluded tile after an unoccluded
         // tile is if the priorty bin decreased, the tile is required for
         // activation, or the scale changed.
-        bool tile_is_occluded =
-            tile->is_occluded_for_tree_priority(tree_priority);
+        bool tile_is_occluded = tile->is_occluded(tree);
         if (tile_is_occluded) {
           occluded_tile_count++;
 
-          bool last_tile_is_occluded =
-              last_tile->is_occluded_for_tree_priority(tree_priority);
+          bool last_tile_is_occluded = last_tile->is_occluded(tree);
           if (!last_tile_is_occluded) {
             TilePriority::PriorityBin tile_priority_bin =
-                tile->priority_for_tree_priority(tree_priority).priority_bin;
+                tile->priority(tree).priority_bin;
             TilePriority::PriorityBin last_tile_priority_bin =
-                last_tile->priority_for_tree_priority(tree_priority)
-                    .priority_bin;
+                last_tile->priority(tree).priority_bin;
 
             EXPECT_TRUE(
                 (tile_priority_bin < last_tile_priority_bin) ||
                 tile->required_for_activation() ||
                 (tile->contents_scale() != last_tile->contents_scale()));
           }
         }
         last_tile = tile;
       }
-      EXPECT_EQ(expected_occluded_tile_count[priority_count],
-                occluded_tile_count);
+      EXPECT_EQ(expected_occluded_tile_count, occluded_tile_count);
     }
   }
 };
 
 TEST_F(OcclusionTrackingPictureLayerImplTest,
        OccludedTilesSkippedDuringRasterization) {
   base::TimeTicks time_ticks;
   time_ticks += base::TimeDelta::FromMilliseconds(1);
   host_impl_.SetCurrentBeginFrameArgs(
       CreateBeginFrameArgsForTesting(time_ticks));
@@ skipping 453 matching lines @@
   host_impl_.SetViewportSize(viewport_size);
   host_impl_.active_tree()->UpdateDrawProperties();
   host_impl_.pending_tree()->UpdateDrawProperties();
 
   // The expected number of occluded tiles on each of the 5 tilings for each of
   // the 3 tree priorities.
   size_t expected_occluded_tile_count_on_both[] = {9u, 1u, 1u, 1u, 1u};
   size_t expected_occluded_tile_count_on_active[] = {30u, 5u, 4u, 2u, 2u};
   size_t expected_occluded_tile_count_on_pending[] = {30u, 5u, 4u, 2u, 2u};
 
-  // The total expected number of occluded tiles on all tilings for each of the
-  // 3 tree priorities.
-  size_t total_expected_occluded_tile_count[] = {13u, 43u, 43u};
-
-  ASSERT_EQ(arraysize(total_expected_occluded_tile_count), NUM_TREE_PRIORITIES);
+  size_t total_expected_occluded_count_on_trees[] = {43u, 43u};
 
   // Verify number of occluded tiles on the pending layer for each tiling.
   for (size_t i = 0; i < pending_layer_->num_tilings(); ++i) {
     PictureLayerTiling* tiling = pending_layer_->tilings()->tiling_at(i);
     tiling->CreateAllTilesForTesting();
     tiling->UpdateAllTilePrioritiesForTesting();
 
     size_t occluded_tile_count_on_pending = 0u;
     size_t occluded_tile_count_on_active = 0u;
     size_t occluded_tile_count_on_both = 0u;
@@ skipping 62 matching lines @@
   for (std::vector<PictureLayerTiling*>::iterator tiling_iterator =
            tilings.begin();
        tiling_iterator != tilings.end();
        ++tiling_iterator) {
     std::vector<Tile*> tiles = (*tiling_iterator)->AllTilesForTesting();
     std::copy(tiles.begin(), tiles.end(), std::back_inserter(all_tiles));
   }
 
   host_impl_.tile_manager()->InitializeTilesWithResourcesForTesting(all_tiles);
 
-  VerifyEvictionConsidersOcclusion(pending_layer_,
-                                   total_expected_occluded_tile_count);
-  VerifyEvictionConsidersOcclusion(active_layer_,
-                                   total_expected_occluded_tile_count);
+  VerifyEvictionConsidersOcclusion(
+      pending_layer_,
+      PENDING_TREE,
+      total_expected_occluded_count_on_trees[PENDING_TREE]);
+  VerifyEvictionConsidersOcclusion(
+      active_layer_,
+      ACTIVE_TREE,
+      total_expected_occluded_count_on_trees[ACTIVE_TREE]);
 }
 
 TEST_F(PictureLayerImplTest, RecycledTwinLayer) {
   gfx::Size tile_size(102, 102);
   gfx::Size layer_bounds(1000, 1000);
 
   scoped_refptr<FakePicturePileImpl> pile =
       FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
   SetupPendingTree(pile);
   EXPECT_FALSE(pending_layer_->GetRecycledTwinLayer());
@@ skipping 221 matching lines @@
   result = layer->CalculateTileSize(gfx::Size(447, 400));
   EXPECT_EQ(result.width(), 448);
   EXPECT_EQ(result.height(), 448);
   result = layer->CalculateTileSize(gfx::Size(500, 499));
   EXPECT_EQ(result.width(), 512);
   EXPECT_EQ(result.height(), 500 + 2);
 }
 
 }  // namespace
 }  // namespace cc