cc: Implement geometry-based tile 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 2958 matching lines @@
       pending_layer_->CreateEvictionQueue(SAME_PRIORITY_FOR_BOTH_TREES);
   EXPECT_TRUE(queue->IsEmpty());
 
   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;
   queue = pending_layer_->CreateEvictionQueue(SAME_PRIORITY_FOR_BOTH_TREES);
   while (!queue->IsEmpty()) {
     Tile* tile = queue->Top();
     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;
     queue->Pop();
   }
 
+  EXPECT_EQ(7, distance_increasing);
+  EXPECT_EQ(55, distance_decreasing);
+
   EXPECT_TRUE(reached_visible);
   EXPECT_EQ(65u, unique_tiles.size());
 
   scale_index = 0;
   bool reached_required = false;
   while (!queue->IsEmpty()) {
     Tile* tile = queue->Top();
     EXPECT_TRUE(tile);
 
     TilePriority priority = tile->priority(PENDING_TREE);
@@ skipping 789 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(FakePictureLayerImpl* layer,
+                                        FakePictureLayerImpl* twin_layer,
+                                        WhichTree tree,
+                                        size_t expected_occluded_tile_count) {
+    twin_layer->set_has_valid_tile_priorities(false);
     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;
+      std::set<Tile*> shared_tiles;
 
       scoped_ptr<TilingSetEvictionQueue> queue =
           layer->CreateEvictionQueue(tree_priority);
       while (!queue->IsEmpty()) {
         Tile* tile = queue->Top();
         if (!last_tile)
           last_tile = tile;
+        if (tile->is_shared())
+          EXPECT_TRUE(shared_tiles.insert(tile).second);
 
         // 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;
         queue->Pop();
       }
-      EXPECT_EQ(expected_occluded_tile_count[priority_count],
-                occluded_tile_count);
+      queue = twin_layer->CreateEvictionQueue(tree_priority);
+      while (!queue->IsEmpty()) {
+        Tile* tile = queue->Top();
+        if (tile->is_shared()) {
+          EXPECT_TRUE(shared_tiles.insert(tile).second);
+          if (tile->is_occluded(tree))

[vmpstr, 2014/12/09 02:10:58]

This should happen outside of the if (is shared) block

[USE eero AT chromium.org, 2014/12/09 18:44:14]

No, it should not.
The purpose of this second while loop is to count tiles which are occluded and
which belong to the layer (passed as the first parameter) but which are not
returned by the first eviction queue. This can happen for tiles which are shared
and those priority for tree priority is closer to the priority for the twin tree
and therefore they would be out of order tiles if they were returned by the
first eviction queue. So they are returned by the twin eviction queue.

My idea here was to modify unit tests as little as possible. Therefore I did not
modify numbers such as expected_occluded_tile_count. If you would like a
different approach, please say so.

[vmpstr, 2014/12/10 18:01:15]

I think that makes sense, thanks for the explanation. Can you leave a comment
explaining this? At a first glance, it seems that we're ignoring unshared tiles
erroneously. 

[USE eero AT chromium.org, 2014/12/11 15:21:59]

Done.

+            ++occluded_tile_count;
+        }
+        queue->Pop();
+      }
+      EXPECT_EQ(expected_occluded_tile_count, occluded_tile_count);
     }
+    twin_layer->set_has_valid_tile_priorities(true);
   }
 };
 
 TEST_F(OcclusionTrackingPictureLayerImplTest,
        OccludedTilesSkippedDuringRasterization) {
   base::TimeTicks time_ticks;
   time_ticks += base::TimeDelta::FromMilliseconds(1);
   host_impl_.SetCurrentBeginFrameArgs(
       CreateBeginFrameArgsForTesting(time_ticks));
 
@@ skipping 452 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_tile_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_, active_layer_, PENDING_TREE,
+      total_expected_occluded_tile_count_on_trees[PENDING_TREE]);
+  VerifyEvictionConsidersOcclusion(
+      active_layer_, pending_layer_, ACTIVE_TREE,
+      total_expected_occluded_tile_count_on_trees[ACTIVE_TREE]);
 }
 
 TEST_F(PictureLayerImplTest, PendingOrActiveTwinLayer) {
   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_->GetPendingOrActiveTwinLayer());
@@ skipping 286 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