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..1d7293963f176b50e1efc81f6b28cfdd0661b8fa 100644
--- a/cc/resources/raster_tile_priority_queue.cc
+++ b/cc/resources/raster_tile_priority_queue.cc
@@ -63,6 +63,39 @@ class RasterOrderComparator {
   TreePriority tree_priority_;
 };
 
+const WhichTree kHigherPriorityTreeForSmoothnessTakesPriority = ACTIVE_TREE;
+const WhichTree kHigherPriorityTreeForNewContentTakesPriority = PENDING_TREE;
+
+WhichTree HigherPriorityTree(TreePriority tree_priority,
+                             const Tile* active_tile,
+                             const Tile* pending_tile) {

[reveman, 2014/09/10 18:53:35]

I don't understand why this can't include the tree_priority switch statement
instead of having that duplicated in two places. Are you worried that a function
call in NextTileIteratorTree to a function that can easily be inlined by the
compiler might have a negative performance impact?

[USE eero AT chromium.org, 2014/09/11 06:55:24]

If HigherPriorityTree included the tree_priority switch statement and
NextPriorityTree called it unconditionally like in

  WhichTree
  RasterTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
      TreePriority tree_priority) const {
    if (!active_iterator)
      return PENDING_TREE;
    if (!pending_iterator)
      return ACTIVE_TREE;
    return HigherPriorityTree(
        tree_priority, *active_iterator, *pending_iterator);
  }

then NextTileIteratorTree would execute *active_iterator and *pending_iterator
statements unconditionally and THAT is not fast and is not needed unless
tree_priority is SAME_PRIORITY_FOR_BOTH_TREES.

[reveman, 2014/09/11 12:59:53]

Ok, thanks for explaining. Maybe the code in your previous patch is better then.
Your call.

+  // This function does not handle simple tree priorities for which constants
+  // can be used.
+  DCHECK(tree_priority == SAME_PRIORITY_FOR_BOTH_TREES);
+
+  const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE);
+  const TilePriority& pending_priority = pending_tile->priority(PENDING_TREE);
+
+  if (active_priority.IsHigherPriorityThan(pending_priority))
+    return ACTIVE_TREE;
+  return PENDING_TREE;
+}
+
+WhichTree PrimaryTreeForSharedTile(TreePriority tree_priority,
+                                   const Tile* shared_tile) {
+  switch (tree_priority) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      return kHigherPriorityTreeForSmoothnessTakesPriority;
+    case NEW_CONTENT_TAKES_PRIORITY:
+      return kHigherPriorityTreeForNewContentTakesPriority;
+    case SAME_PRIORITY_FOR_BOTH_TREES:
+      return HigherPriorityTree(tree_priority, shared_tile, shared_tile);
+    default:
+      NOTREACHED();
+      return ACTIVE_TREE;
+  }
+}
+
 }  // namespace
 
 RasterTilePriorityQueue::RasterTilePriorityQueue() {
@@ -122,7 +155,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 +175,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 +187,30 @@ 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);

[USE eero AT chromium.org, 2014/09/11 06:55:24]

Here the next_iterator is advanced, which change the value returned by
NextTileIteratorTree.

[reveman, 2014/09/11 12:59:53]

you'd have to move this into the loop.

 
-  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;
-    next_tree = NextTileIteratorTree(tree_priority);
-    next_iterator =
-        next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  if (has_both_layers) {

[reveman, 2014/09/10 18:53:35]

Not sure it's worth DCHECKing when this is not the case. It's fine to return
early here if !has_both_layers imo. Whatever you prefer.

+    // We have both layers (active and pending) thus we can encounter shared
+    // tiles twice (from the active iterator and from the pending iterator).
+    for (; !IsEmpty(); ++(*next_iterator)) {
+      next_tree = NextTileIteratorTree(tree_priority);
+      next_iterator =
+          next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;

[reveman, 2014/09/10 18:53:35]

I thinks it's a bit ugly that we compute these values again here after having
done it above. Consider using a do-while loop instead. ie. something like this:

do {
  const Tile* tile = **next_iterator;
  if (!tile->is_shared())
    break;
  if (PrimaryTreeForSharedTile(tree_priority, tile) == next_tree)
    break;

  next_tree = NextTileIteratorTree(tree_priority);
  next_iterator =
      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
} while(!IsEmpty());

[USE eero AT chromium.org, 2014/09/11 06:55:25]

We do not compute the same values again.
Instead of that, we compute new values for the new next_iterator.
Note that we advanced the previous next_iterator on the line 191, thus the newly
computed next_iterator may be different than the previous one.
This would be incorrect. The next_iterator should not be used after it is
advanced (on line 191) unless the next_iterator is computed again.

[reveman, 2014/09/11 12:59:53]

I see now that your code is consistent with the old code so looks good to me
from that pov.

For a function that is supposed to do a simple
advance-at-least-one-until-reaching-a-valid-value this function looks a bit
unconventional but there's no need to improve that in this patch. 

+
+      // Accept the tile if it is not shared or if it is shared and the next
+      // tree is the primary one corresponding the iterator (active or pending)
+      // which usually (but due to spiral iterators not always) returns the
+      // shared tile first.
+      const Tile* tile = **next_iterator;
+      if (!tile->is_shared() ||
+          next_tree == PrimaryTreeForSharedTile(tree_priority, tile))
+        break;
+    }
   }
+
+  // If no empty, use Top to do DCHECK the next iterator.
+  DCHECK(IsEmpty() || Top(tree_priority));
 }
 
 WhichTree
@@ -190,30 +227,16 @@ RasterTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
   // Now both iterators have tiles, so we have to decide based on tree priority.
   switch (tree_priority) {
     case SMOOTHNESS_TAKES_PRIORITY:
-      return ACTIVE_TREE;
+      return kHigherPriorityTreeForSmoothnessTakesPriority;
     case NEW_CONTENT_TAKES_PRIORITY:
-      return PENDING_TREE;
-    case SAME_PRIORITY_FOR_BOTH_TREES: {
-      const Tile* active_tile = *active_iterator;
-      const Tile* pending_tile = *pending_iterator;
-      if (active_tile == pending_tile)
-        return ACTIVE_TREE;
-
-      const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE);
-      const TilePriority& pending_priority =
-          pending_tile->priority(PENDING_TREE);
-
-      if (active_priority.IsHigherPriorityThan(pending_priority))
-        return ACTIVE_TREE;
-      return PENDING_TREE;
-    }
+      return kHigherPriorityTreeForNewContentTakesPriority;
+    case SAME_PRIORITY_FOR_BOTH_TREES:
+      return HigherPriorityTree(
+          tree_priority, *active_iterator, *pending_iterator);
     default:
       NOTREACHED();
+      return ACTIVE_TREE;
   }
-
-  NOTREACHED();
-  // Keep the compiler happy.
-  return ACTIVE_TREE;
 }
 
 }  // namespace cc