cc: Use pointers for heaps in tile manager 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 {
 
 class RasterOrderComparator {
  public:
   explicit RasterOrderComparator(TreePriority tree_priority)
       : tree_priority_(tree_priority) {}
 
   bool operator()(
-      const RasterTilePriorityQueue::PairedPictureLayerQueue& a,
-      const RasterTilePriorityQueue::PairedPictureLayerQueue& b) const {
-    if (a.IsEmpty())
+      const RasterTilePriorityQueue::PairedPictureLayerQueue* a,
+      const RasterTilePriorityQueue::PairedPictureLayerQueue* b) const {
+    if (a->IsEmpty())
       return true;
 
-    if (b.IsEmpty())
+    if (b->IsEmpty())
       return false;
 
-    WhichTree a_tree = a.NextTileIteratorTree(tree_priority_);
+    WhichTree a_tree = a->NextTileIteratorTree(tree_priority_);
     const PictureLayerImpl::LayerRasterTileIterator* a_iterator =
-        a_tree == ACTIVE_TREE ? &a.active_iterator : &a.pending_iterator;
+        a_tree == ACTIVE_TREE ? &a->active_iterator : &a->pending_iterator;
 
-    WhichTree b_tree = b.NextTileIteratorTree(tree_priority_);
+    WhichTree b_tree = b->NextTileIteratorTree(tree_priority_);
     const PictureLayerImpl::LayerRasterTileIterator* b_iterator =
-        b_tree == ACTIVE_TREE ? &b.active_iterator : &b.pending_iterator;
+        b_tree == ACTIVE_TREE ? &b->active_iterator : &b->pending_iterator;
 
     const Tile* a_tile = **a_iterator;
     const Tile* b_tile = **b_iterator;
 
     const TilePriority& a_priority =
         a_tile->priority_for_tree_priority(tree_priority_);
     const TilePriority& b_priority =
         b_tile->priority_for_tree_priority(tree_priority_);
     bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
 
@@ skipping 28 matching lines @@
 }  // namespace
 
 RasterTilePriorityQueue::RasterTilePriorityQueue() {
 }
 
 RasterTilePriorityQueue::~RasterTilePriorityQueue() {
 }
 
 void RasterTilePriorityQueue::Build(
     const std::vector<PictureLayerImpl::Pair>& paired_layers,
     TreePriority tree_priority) {

[reveman, 2014/07/30 16:04:09]

That this function is not being faster makes me very suspicious. Why is the
greatest saving not from make_heap? Once you start iterating you'll end up with
non-empty PairedPictureLayerQueue::returned_shared_tiles. Does that have a
significant factor in why this patch makes iterating cheaper?

Another general observation of these results. The improvement is 300% to 440%.
The reason for this being faster would be because less data has to be copied
when moving elements around in the heap. Reducing the size of
PairedPictureLayerQueue to 1/4 of its current size should have the same effect.
What's the current size of PairedPictureLayerQueue? It would be interesting to
see a break down of each of the members. I would not be surprised if we could
reduce the size of this significantly. That would not only provide the heap
performance we're looking for but also improve the performance of these
iterators in other aspects, such as construction.

[vmpstr, 2014/07/30 16:45:51]

One possible explanation is that reallocations in paired_queues_heap_ coupled
with an extra iteration is the thing that prevents us from seeing savings here.

Another more likely case is that make_heap does no work in perftests, since the
layers initially have equal priority (every layer has a now bin tile at the
top). So the cost we're seeing here is just from the loop construction. I did an
experiment where I kept the code the same, just added an extra loop to push
paired layers pointers into a temp vector and I see the same type of regression.
I don't know if 1/4 the current size is the magic number here. Just from moving
objects around (ignoring pointer indirection when accessing elements), wouldn't
we have to reduce the layer iterator to the size of a single pointer? I agree
that reducing the size is always a good thing, but at the same time I'm weary of
the fact that our performance profile would depend heavily on the size of layer
iterator (note that it has the tiling iterator as members as well, so the
performance would depend on the size of all the iterator layers below this).
That makes it difficult for us to change any meaningful part of the iterator (ie
adding new variables, caching something) without negatively affecting
performance.

In other words, I'd rather us see take a black box approach to this performance,
and not have to assume anything about the size of the iterators that we're
using. Note the same general statements that we normally state when talking
about iterators still apply: they are fairly cheap to create and are appropriate
for stack creation, since they aren't large. IMO, talking about particular size
and relying on the characteristic that if we reduce the size by half, our
performance doubles encourages micro-optimizations that favor tiny object sizes
over clarity.

For reference here's what the layer raster iterator contains:
    enum IteratorType { LOW_RES, HIGH_RES, NUM_ITERATORS };
    struct IterationStage {
      IteratorType iterator_type;
      TilePriority::PriorityBin tile_type;
    };

    PictureLayerImpl* layer_;
    int current_stage_;
    IterationStage stages_[4];
    PictureLayerTiling::TilingRasterTileIterator iterators_[NUM_ITERATORS];

That's probably not the optimal size (we can remove stages array in favor of
determining the next stage computationally for instance), but for the sake of
clarity I think this is pretty streamlined.

Wdyt?

[reveman, 2014/07/31 03:05:19]

Ok, let's start by fixing the perftests then.
Yes, no idea what the actual number is but I'd guess that the difference will
become insignificant much before you reach the size of a pointer. It's hard to
say as moving some data around might be free unless it causes a cache miss. You
need to access the data even if you use pointers so we might get the same cache
misses and the pointers might not buy us much at all.
Not making assumptions about the size makes some sense. 

Although, I think that reducing the size of these are one of the most useful
optimizations we can do. It improves performance not only when accessing these
objects but when constructing them and moving them. That said, we should be
careful about making changes that reduce readability.
I actually think it's a great idea to remove that array and compute the stage as
we iterate instead of at construction time. I think it can improve readability
if done right.
I'm not completely against this patch. I just need some more data to be
convinced that this is a good idea. After updating the perftests, can you do
some profiling and post the results to this CL?

   tree_priority_ = tree_priority;
   for (std::vector<PictureLayerImpl::Pair>::const_iterator it =
            paired_layers.begin();
        it != paired_layers.end();
        ++it) {
     paired_queues_.push_back(PairedPictureLayerQueue(*it, tree_priority_));
   }
 
-  std::make_heap(paired_queues_.begin(),
-                 paired_queues_.end(),
+  for (size_t i = 0; i < paired_queues_.size(); ++i) {
+    paired_queues_heap_.push_back(&paired_queues_[i]);
+  }
+
+  std::make_heap(paired_queues_heap_.begin(),
+                 paired_queues_heap_.end(),
                  RasterOrderComparator(tree_priority_));
 }
 
 void RasterTilePriorityQueue::Reset() {
   paired_queues_.clear();
+  paired_queues_heap_.clear();
 }
 
 bool RasterTilePriorityQueue::IsEmpty() const {
-  return paired_queues_.empty() || paired_queues_.front().IsEmpty();
+  return paired_queues_heap_.empty() || paired_queues_heap_.front()->IsEmpty();
 }
 
 Tile* RasterTilePriorityQueue::Top() {
   DCHECK(!IsEmpty());
-  return paired_queues_.front().Top(tree_priority_);
+  return paired_queues_heap_.front()->Top(tree_priority_);
 }
 
 void RasterTilePriorityQueue::Pop() {
   DCHECK(!IsEmpty());
 
-  std::pop_heap(paired_queues_.begin(),
-                paired_queues_.end(),
+  std::pop_heap(paired_queues_heap_.begin(),
+                paired_queues_heap_.end(),
                 RasterOrderComparator(tree_priority_));
-  PairedPictureLayerQueue& paired_queue = paired_queues_.back();
-  paired_queue.Pop(tree_priority_);
-  std::push_heap(paired_queues_.begin(),
-                 paired_queues_.end(),
+  PairedPictureLayerQueue* paired_queue = paired_queues_heap_.back();
+  paired_queue->Pop(tree_priority_);
+  std::push_heap(paired_queues_heap_.begin(),
+                 paired_queues_heap_.end(),
                  RasterOrderComparator(tree_priority_));
 }
 
 RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
 }
 
 RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue(
     const PictureLayerImpl::Pair& layer_pair,
     TreePriority tree_priority)
     : active_iterator(layer_pair.active
@@ skipping 93 matching lines @@
     default:
       NOTREACHED();
   }
 
   NOTREACHED();
   // Keep the compiler happy.
   return ACTIVE_TREE;
 }
 
 }  // namespace cc