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..963953afd041640f4dcff31abde6a9b23e480059 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) {

[vmpstr, 2014/09/05 16:54:34]

nit: member variables should end with _

[vmpstr, 2014/09/05 17:12:57]

Disregard this, I forgot that it's a struct with public members

 }
 
 RasterTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
@@ -141,9 +142,11 @@ Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::Top(
       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
   DCHECK(*next_iterator);
   Tile* tile = **next_iterator;
+#if DCHECK_IS_ON
   DCHECK(std::find(returned_shared_tiles.begin(),
                    returned_shared_tiles.end(),
                    tile) == returned_shared_tiles.end());
+#endif
   return tile;
 }
 
@@ -155,25 +158,73 @@ void RasterTilePriorityQueue::PairedPictureLayerQueue::Pop(
   PictureLayerImpl::LayerRasterTileIterator* next_iterator =
       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
   DCHECK(*next_iterator);
+#if DCHECK_IS_ON
   returned_shared_tiles.push_back(**next_iterator);

[reveman, 2014/09/05 17:08:31]

If returned_shared_tiles is a std::set then you could do something like:
DCHECK(returned_shared_tiles.insert(**next_iterator))

[USE eero AT chromium.org, 2014/09/08 14:08:17]

It needs a .second. Without that it errors with .invalid argument type
'std::pair<iterator, bool>' to unary expression.

+#endif
   ++(*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 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;
+    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;
+  }
+
+#if DCHECK_IS_ON
+  if (!IsEmpty()) {

[reveman, 2014/09/05 17:08:31]

is this check necessary?

[USE eero AT chromium.org, 2014/09/08 14:08:17]

Yes, although it can be put inside DCHECK.
If the paired queue is empty, *next_iterator is not valid (its operator bool()
returns false) and **next_iterator must not be called.

+    DCHECK(std::find(returned_shared_tiles.begin(),
+                     returned_shared_tiles.end(),
+                     **next_iterator) == returned_shared_tiles.end());
   }
+#endif
 }
 
 WhichTree