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 (has_both_layers) {

[reveman, 2014/09/09 18:26:47]

doesn't seem to make sense to enter this loop unless this is true. put the whole
loop inside a "if (!has_both_layers)" block?

[USE eero AT chromium.org, 2014/09/10 07:38:23]

Yes, that could be done.
It is just that the DCHECK in the end of the function needs the above
next_iterator update thus it must be duplicated if the loop is inside an if
block.

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

It turned out to be quite easy to work-a-round that problem.
So I put the loop inside an if statement instead of putting the if statement
inside the loop.

+      // We have both layers (active and pending) thus we can encounter shared
+      // tiles twice (from the active iterator and from the pending iterator).
+      // Skip a shared tile if the tree is not 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 != PrimarySharedTileTree(tree_priority, tile))
+        continue;
+    }
+
+    break;

[reveman, 2014/09/09 18:26:47]

I think it would be less awkward to keep iterating for the base case and instead
break out of the loop when you reach a tile that should be returned.

[USE eero AT chromium.org, 2014/09/10 07:38:24]

Done.

   }
+
+  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;
   if (!pending_iterator)
     return ACTIVE_TREE;
 
   // Now both iterators have tiles, so we have to decide based on tree priority.
+  // Keep in sync with PrimarySharedTileTree.
   switch (tree_priority) {
     case SMOOTHNESS_TAKES_PRIORITY:
       return ACTIVE_TREE;
     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;
     }
     default:
       NOTREACHED();
   }
 
   NOTREACHED();
   // Keep the compiler happy.
   return ACTIVE_TREE;
 }
 
+WhichTree
+RasterTilePriorityQueue::PairedPictureLayerQueue::PrimarySharedTileTree(

[reveman, 2014/09/09 18:26:47]

PrimaryTreeForSharedTile?

[USE eero AT chromium.org, 2014/09/10 07:38:23]

Done.

+    TreePriority tree_priority,
+    const Tile* tile) const {
+  DCHECK(has_both_layers && tile->is_shared());
+
+  // Keep in sync with NextTileIteratorTree.

[reveman, 2014/09/09 18:26:47]

Instead of having to keep these functions in sync, could we add something like
a:

WhichTree PrimaryTree(TreePriority tree_priority,
                      const Tile* active_tile,
                      const Tile* pending_tile) const;

function that can be used in both cases?

[USE eero AT chromium.org, 2014/09/10 07:38:23]

The only but is that for the first two cases there is no need to return a tile
from iterators.
I could check if it has any real impact on performance.
If not then do that.
If yes then the SAME_PRIORITY_FOR_BOTH_TREES case could put to a helper
function. The first two cases are so simple that there is not anything special
to keep in sync.

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

It does have a major impact. Half of the improvements achieved by replacing the
vector based shared tile handling is lost, if the whole switch block is put to a
common helper function.
So cc::PictureLayerImpl::LayerRasterTileIterator::operator* is not very fast and
that has an effect on NextTileIteratorTree which is called quite a lot. It is
thus good to avoid calling LayerRasterTileIterator::operator* when reasonably
possible.
So I'll split the switch cases (instead of the whose switch block) into helper
functions and constants.

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

I'm not sure I understand the reasoning here. I'm just asking for the code
duplication to be reduced. There's no reason that should have to make things
slower. If anything, less code should make it faster.

+  switch (tree_priority) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      // Return shared tiles as active tiles as we return all active tiles
+      // before the first pending tile.
+      return ACTIVE_TREE;
+    case NEW_CONTENT_TAKES_PRIORITY:
+      // Return shared tiles as pending tiles as we return all pending tiles
+      // before the first active tile.
+      return PENDING_TREE;
+    case SAME_PRIORITY_FOR_BOTH_TREES: {
+      // Return shared tiles as either active or pending tiles based on their
+      // active and pending priorities order to return them on the first time
+      // they are encountered and to skip them on the second time.
+      const TilePriority& active_priority = tile->priority(ACTIVE_TREE);
+      const TilePriority& pending_priority = tile->priority(PENDING_TREE);
+
+      if (active_priority.IsHigherPriorityThan(pending_priority))
+        return ACTIVE_TREE;
+      return PENDING_TREE;
+    }
+    default:
+      NOTREACHED();
+  }
+
+  NOTREACHED();

[reveman, 2014/09/09 18:26:47]

You're just being consistent here and that's good but feel free to remove one of
these NOTREACHED statements from here and NextTileIteratorTree if you like as
two of them like this doesn't make much sense.

[USE eero AT chromium.org, 2014/09/10 07:38:24]

Done.

+  // Keep the compiler happy.
+  return ACTIVE_TREE;
+}
+
 }  // namespace cc