cc: Start using raster/eviction iterators.

cc/resources/eviction_tile_priority_queue.cc

Index: cc/resources/eviction_tile_priority_queue.cc
diff --git a/cc/resources/eviction_tile_priority_queue.cc b/cc/resources/eviction_tile_priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..326134ff5959457e8ff2121a0725329268cc6431
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.cc
@@ -0,0 +1,217 @@
+// 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/eviction_tile_priority_queue.h"
+
+#include "cc/resources/tile.h"
+
+namespace cc {
+
+EvictionTilePriorityQueue::EvictionTilePriorityQueue()
+    : tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      comparator_(tree_priority_),
+      initialized_(true) {
+}
+
+void EvictionTilePriorityQueue::Reset() {
+  paired_queues_.clear();
+  queue_heap_.clear();
+  paired_picture_layers_.clear();
+}
+
+void EvictionTilePriorityQueue::BuildQueue(
+    const std::vector<PictureLayerImpl*>& layers,
+    TreePriority tree_priority) {
+  DCHECK(paired_queues_.empty());
+  DCHECK(queue_heap_.empty());
+  DCHECK(paired_picture_layers_.empty());
+
+  GetPairedPictureLayers(layers, &paired_picture_layers_);

[reveman, 2014/07/15 19:44:37]

Sorry, I think this is the wrong approach. Now we're forced to build a vector
for each iterator while in previous patch LTHI could be maintaining an up to
date version of this vector and only update it when necessary or even make
incremental updates to it.

[vmpstr, 2014/07/15 20:38:17]

I don't think this is too bad. Incremental updates to this would require things
like activation handling, which will iterate everything, creating new pending
trees (which would be a bit of a pain to maintain) and deleting a layer would
involve looking through this whole vector anyway. 

Since we're talking about the number of layers here, I would argue this is
acceptable. If you disagree, then I'm not sure what we can do better (previous
version did a copy of pairs). I don't think we can build the heap here, because
it's too expensive. Making it cheaper is probably possible, but it will also
probably involve some redesign. Please suggest an alternative.

If making iterator creating cheap is the direction you're suggesting, then most
likely all of the pieces that have already landed will need to be changed. In
that case, I think we have to schedule a meeting and discuss this in a larger
setting (ie, back to the drawing board).

[reveman, 2014/07/15 22:31:55]

Incremental approach might not be worth it but you can at least avoid building
it each time you build a queue.
 
We don't have to create the heap (call make_heap) but creating a vector of
iterators would be nice as not doing that requires storing some temporary
vector. A temporary vector makes the code less clean and it makes performance in
the general use case worse. Are you sure we need to re-design things to avoid a
temporary vector?
I think we should do both. Making iterators cheap to instantiate and not require
any heap allocations would be great as it improves performance of the general
use case and not just this specific "avoid building eviction queue unless used"
optimization. However, if there's a clean way to do this lazy work and that's
enough to land this then I'm OK with that. Problem is that I don't think the
current approach is good enough. It looks too much like an urgent short term fix
to get this landed without causing a major performance regression and less like
something written for good performance and code quality in the long term.

I'm just trying to suggest possible alternatives and explore possibilities for
how this can be done in a way that we both think is acceptable. Not having the
tile manager build the eviction queue unless it needs to use it is an acceptable
solution to me. And probably the easiest if you want to minimize the back and
forth needed before this can land. I'm happy to keep trying to figure out how we
can do this lazy work as part of the queue as well though.

If you think that the best we can do with the current design is basically what
you have here and we should already be trying to get the most out of it by
sacrificing code quality and performance of the general use case to gain some
for a specific use case, then I think it's best to get back to the drawing
board. I've been assuming that this is not the case.

+  tree_priority_ = tree_priority;
+  comparator_ = EvictionOrderComparator(tree_priority);
+  initialized_ = false;
+}
+
+void EvictionTilePriorityQueue::Initialize() {
+  // Since iterator heap uses pointers into paired_queues, we have to reserve
+  // the paired_queues to avoid reallocations of the vector.
+  paired_queues_.reserve(paired_picture_layers_.size());

[reveman, 2014/07/15 19:44:37]

I don't understand this and the comment doesn't help. Why does this vector not
grow just once to the size needed as the other vectors?

[vmpstr, 2014/07/15 20:38:17]

These pointers point to the vector's memory. If paired_queues_ is reallocated
internally, it invalidates the pointers that have already been created.

[reveman, 2014/07/15 22:31:55]

Ah, I see. That's very subtle. Not using two vectors would be my preferred
solution but if we need this vector of pointers then I think building it using a
separate loop is better as I would have easily assumed that this was just an
optimization if not familiar with the code.

+  for (std::vector<PairedPictureLayer>::iterator it =
+           paired_picture_layers_.begin();
+       it != paired_picture_layers_.end();
+       ++it) {
+    PairedPictureLayerQueue paired_queue;
+    if (it->active_layer) {
+      paired_queue.active_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->active_layer,
+                                                      tree_priority_);
+    }
+
+    if (it->pending_layer) {
+      paired_queue.pending_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->pending_layer,
+                                                      tree_priority_);
+    }
+
+    if (paired_queue.PeekTile(tree_priority_) != NULL) {
+      paired_queues_.push_back(paired_queue);
+      queue_heap_.push_back(&paired_queues_.back());
+    }
+  }
+
+  std::make_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+  initialized_ = true;
+}
+
+EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
+}
+
+void EvictionTilePriorityQueue::Pop() {
+  if (!initialized_)
+    Initialize();
+
+  std::pop_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+  PairedPictureLayerQueue* paired_queue = queue_heap_.back();
+  queue_heap_.pop_back();
+
+  paired_queue->PopTile(tree_priority_);
+  if (paired_queue->PeekTile(tree_priority_) != NULL) {
+    queue_heap_.push_back(paired_queue);
+    std::push_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+  }
+}
+
+bool EvictionTilePriorityQueue::IsEmpty() {
+  if (!initialized_)
+    Initialize();
+
+  return queue_heap_.empty();
+}
+
+Tile* EvictionTilePriorityQueue::Top() {
+  if (!initialized_)
+    Initialize();
+
+  DCHECK(!IsEmpty());
+  return queue_heap_.front()->PeekTile(tree_priority_);
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
+}
+
+Tile* EvictionTilePriorityQueue::PairedPictureLayerQueue::PeekTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      NextTileIterator(tree_priority);
+  if (!next_iterator)
+    return NULL;
+
+  DCHECK(*next_iterator);
+  DCHECK(std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) == returned_shared_tiles.end());
+  return **next_iterator;
+}
+
+void EvictionTilePriorityQueue::PairedPictureLayerQueue::PopTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      NextTileIterator(tree_priority);
+  DCHECK(next_iterator);
+  DCHECK(*next_iterator);
+  returned_shared_tiles.push_back(**next_iterator);
+  ++(*next_iterator);
+
+  next_iterator = NextTileIterator(tree_priority);
+  while (next_iterator &&
+         std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) != returned_shared_tiles.end()) {
+    ++(*next_iterator);
+    next_iterator = NextTileIterator(tree_priority);
+  }
+}
+
+PictureLayerImpl::LayerEvictionTileIterator*
+EvictionTilePriorityQueue::PairedPictureLayerQueue::NextTileIterator(
+    TreePriority tree_priority) {
+  // If both iterators are out of tiles, return NULL.
+  if (!active_iterator && !pending_iterator)
+    return NULL;
+
+  // If we only have one iterator with tiles, return it.
+  if (!active_iterator)
+    return &pending_iterator;
+  if (!pending_iterator)
+    return &active_iterator;
+
+  Tile* active_tile = *active_iterator;
+  Tile* pending_tile = *pending_iterator;
+  if (active_tile == pending_tile)
+    return &active_iterator;
+
+  const TilePriority& active_priority =
+      active_tile->priority_for_tree_priority(tree_priority);
+  const TilePriority& pending_priority =
+      pending_tile->priority_for_tree_priority(tree_priority);
+
+  if (pending_priority.IsHigherPriorityThan(active_priority))
+    return &active_iterator;
+  return &pending_iterator;
+}
+
+EvictionTilePriorityQueue::EvictionOrderComparator::EvictionOrderComparator(
+    TreePriority tree_priority)
+    : tree_priority_(tree_priority) {
+}
+
+bool EvictionTilePriorityQueue::EvictionOrderComparator::operator()(
+    PairedPictureLayerQueue* a,
+    PairedPictureLayerQueue* b) const {
+  PictureLayerImpl::LayerEvictionTileIterator* a_iterator =
+      a->NextTileIterator(tree_priority_);
+  DCHECK(a_iterator);
+  DCHECK(*a_iterator);
+
+  PictureLayerImpl::LayerEvictionTileIterator* b_iterator =
+      b->NextTileIterator(tree_priority_);
+  DCHECK(b_iterator);
+  DCHECK(*b_iterator);
+
+  Tile* a_tile = **a_iterator;
+  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;
+
+  // Now we have to return true iff b is lower priority than a.
+
+  // If the bin is the same but the resolution is not, then the order will be
+  // determined by whether we prioritize low res or not.
+  // TODO(vmpstr): Remove this when TilePriority is no longer a member of Tile
+  // class but instead produced by the iterators.
+  if (b_priority.priority_bin == a_priority.priority_bin &&
+      b_priority.resolution != a_priority.resolution) {
+    // Non ideal resolution should be sorted higher than other resolutions.
+    if (a_priority.resolution == NON_IDEAL_RESOLUTION)
+      return false;
+
+    if (b_priority.resolution == NON_IDEAL_RESOLUTION)
+      return true;
+
+    if (prioritize_low_res)
+      return a_priority.resolution == LOW_RESOLUTION;
+
+    return a_priority.resolution == HIGH_RESOLUTION;
+  }
+  return a_priority.IsHigherPriorityThan(b_priority);
+}
+
+}  // namespace cc