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

cc/resources/raster_tile_priority_queue.cc

Index: cc/resources/raster_tile_priority_queue.cc
diff --git a/cc/resources/raster_tile_priority_queue.cc b/cc/resources/raster_tile_priority_queue.cc
index e0591b3d2a228a07db43edbdd28b371aa372d4c9..931578617b2603321fc0d847b47f5a04ffa6d093 100644
--- a/cc/resources/raster_tile_priority_queue.cc
+++ b/cc/resources/raster_tile_priority_queue.cc
@@ -122,7 +122,8 @@ RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue(
                            ? 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() {
@@ -141,9 +142,7 @@ Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::Top(
       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;
 }
 
@@ -155,25 +154,67 @@ void RasterTilePriorityQueue::PairedPictureLayerQueue::Pop(
   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