cc: Optimise shared raster tile handling in raster tile priority queue.

cc/resources/raster_tile_priority_queue.cc

 // Copyright 2014 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/raster_tile_priority_queue.h"
 
 namespace cc {
 
 namespace {
 
@@ skipping 104 matching lines @@
     TreePriority tree_priority)
     : active_iterator(layer_pair.active
                           ? PictureLayerImpl::LayerRasterTileIterator(
                                 layer_pair.active,
                                 tree_priority == SMOOTHNESS_TAKES_PRIORITY)
                           : PictureLayerImpl::LayerRasterTileIterator()),
       pending_iterator(layer_pair.pending
                            ? PictureLayerImpl::LayerRasterTileIterator(
                                  layer_pair.pending,
                                  tree_priority == SMOOTHNESS_TAKES_PRIORITY)
-                           : PictureLayerImpl::LayerRasterTileIterator()) {
+                           : PictureLayerImpl::LayerRasterTileIterator()),
+      has_both_layers(layer_pair.active && layer_pair.pending) {
 }
 
 RasterTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
 }
 
 bool RasterTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const {
   return !active_iterator && !pending_iterator;
 }
 
 Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::Top(
     TreePriority tree_priority) {
   DCHECK(!IsEmpty());
 
   WhichTree next_tree = NextTileIteratorTree(tree_priority);
   PictureLayerImpl::LayerRasterTileIterator* next_iterator =
       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
   DCHECK(*next_iterator);
   Tile* tile = **next_iterator;
-  DCHECK(std::find(returned_shared_tiles.begin(),
-                   returned_shared_tiles.end(),
-                   tile) == returned_shared_tiles.end());
+  DCHECK(returned_tiles_for_debug.find(tile) == returned_tiles_for_debug.end());
   return tile;
 }
 
 void RasterTilePriorityQueue::PairedPictureLayerQueue::Pop(
     TreePriority tree_priority) {
   DCHECK(!IsEmpty());
 
   WhichTree next_tree = NextTileIteratorTree(tree_priority);
   PictureLayerImpl::LayerRasterTileIterator* next_iterator =
       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
   DCHECK(*next_iterator);
-  returned_shared_tiles.push_back(**next_iterator);
+  DCHECK(returned_tiles_for_debug.insert(**next_iterator).second);
   ++(*next_iterator);
 
-  if (IsEmpty())
-    return;
-
-  next_tree = NextTileIteratorTree(tree_priority);
-  next_iterator =
-      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
-  while (std::find(returned_shared_tiles.begin(),
-                   returned_shared_tiles.end(),
-                   **next_iterator) != returned_shared_tiles.end()) {
-    ++(*next_iterator);
-    if (IsEmpty())
-      break;
+  for (; !IsEmpty(); ++(*next_iterator)) {
     next_tree = NextTileIteratorTree(tree_priority);
     next_iterator =
         next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+
+    // If we do not have both layers (active and pending), we do not care about
+    // shared tiles because we do not encounter them twice.
+    // We do not encounter shared tile twice in that case, because in that case
+    // shared tiles are either shared between an active and a recycled layer
+    // (and we do not have nor want an iterator for a recycled layer) or shared
+    // between an active and a pending layer either of which do not have
+    // valid tile priorities (and we do not have nor want an iterator for
+    // a layer without valid tile priorities because such layers will not be
+    // displayed).
+    if (!has_both_layers)
+      break;
+
+    Tile* tile = **next_iterator;

[reveman, 2014/09/08 14:38:42]

Consider adding a helper function for the rest of the body of this loop. ie.
bool HasTileAlreadyBeenReturned(Tile* tile, WhichTree tree, TreePriority
tree_priority)

I think that would make the code a bit cleaner as you don't need these multiple
levels of break statements.

[USE eero AT chromium.org, 2014/09/09 17:22:18]

I am bit hesitated to do that, because the code does not actually test, whether
the tile has already been returned but whether is should have been already been
returned. The difference is that tiling raster tile iterators may return tiles a
bit out of priority order due to the use of spiral iterators.
True.

+    if (!tile->is_shared())
+      break;
+
+    switch (tree_priority) {
+      case SMOOTHNESS_TAKES_PRIORITY:
+        // If we reach a pending tile, all shared tiles have been returned once
+        // as active tiles and should not be returned again.
+        if (next_tree != ACTIVE_TREE)
+          continue;
+        break;
+      case NEW_CONTENT_TAKES_PRIORITY:
+        // If we reach an active tile, all shared tiles have been returned once
+        // as pending tiles and should not be returned again.
+        if (next_tree != PENDING_TREE)
+          continue;
+        break;
+      case SAME_PRIORITY_FOR_BOTH_TREES: {
+        // Skip the shared tile if its local priority in the next tree is lower
+        // than its local priority in the other tree in order to skip it on
+        // the second time but not on the first time it is encountered.
+        const TilePriority& active_priority = tile->priority(ACTIVE_TREE);
+        const TilePriority& pending_priority = tile->priority(PENDING_TREE);
+        WhichTree higher_priority_tree =
+            pending_priority.IsHigherPriorityThan(active_priority)
+                ? PENDING_TREE
+                : ACTIVE_TREE;
+        if (next_tree != higher_priority_tree)
+          continue;
+        break;
+      }
+      default:
+        NOTREACHED();
+    }
+
+    break;
   }
+
+  DCHECK(!*next_iterator ||
+         returned_tiles_for_debug.find(**next_iterator) ==
+             returned_tiles_for_debug.end());
 }
 
 WhichTree
 RasterTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
     TreePriority tree_priority) const {
   DCHECK(!IsEmpty());
 
   // If we only have one iterator with tiles, return it.
   if (!active_iterator)
     return PENDING_TREE;
@@ skipping 23 matching lines @@
     default:
       NOTREACHED();
   }
 
   NOTREACHED();
   // Keep the compiler happy.
   return ACTIVE_TREE;
 }
 
 }  // namespace cc