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..456f38b5742d1418d70306bf2a61f7344e5fad54
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.cc
@@ -0,0 +1,215 @@
+// 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_iterators_.clear();
+  iterator_heap_.clear();
+}
+
+void EvictionTilePriorityQueue::BuildQueue(
+    const std::vector<PairedPictureLayer>& paired_picture_layers,
+    TreePriority tree_priority) {
+  DCHECK(paired_iterators_.empty());
+  DCHECK(iterator_heap_.empty());
+  paired_picture_layers_ = paired_picture_layers;

[reveman, 2014/07/15 01:51:10]

Hm, you're making a copy of a large vector here. I would have guessed that
iterating the vector and building the paired_iterators_ vector would have a
similar cost. Now we're doing both..

[vmpstr, 2014/07/15 05:36:26]

We can pass the raw layers vector and build it, if you prefer.

[reveman, 2014/07/15 16:49:56]

Keeping a raw pointer around and assuming that it's valid when we like to use it
is really nasty. I'd much rather we made the building of the iterator vector
fast enough that we don't need to delay that part. That would not only improve
this specific use case you're trying to optimize for here but the general usage.

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

I meant we can pass in const std::vector<PictureLayerImpl*>& layers, and build
paired_picture_layers_ as a part of BuildQueue (this is definitely can be common
code to TilePriorityIterator), which would save a copy (take a look at the
latest patch set).

+  tree_priority_ = tree_priority;
+  comparator_ = EvictionOrderComparator(tree_priority);
+  initialized_ = false;
+}
+
+void EvictionTilePriorityQueue::Initialize() {
+  paired_iterators_.reserve(paired_picture_layers_.size());
+  iterator_heap_.reserve(paired_picture_layers_.size());

[reveman, 2014/07/15 01:51:09]

Let's not bother with reserve() when this only grows once.

[vmpstr, 2014/07/15 05:36:26]

That knowledge is not obvious in this class, but sure I can do that.

+  for (std::vector<PairedPictureLayer>::iterator it =
+           paired_picture_layers_.begin();
+       it != paired_picture_layers_.end();
+       ++it) {
+    PairedPictureLayerIterator paired_iterator;
+    if (it->active_layer) {
+      paired_iterator.active_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->active_layer,
+                                                      tree_priority_);
+    }
+
+    if (it->pending_layer) {
+      paired_iterator.pending_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->pending_layer,
+                                                      tree_priority_);
+    }
+
+    if (paired_iterator.PeekTile(tree_priority_) != NULL) {
+      paired_iterators_.push_back(paired_iterator);
+      iterator_heap_.push_back(&paired_iterators_.back());
+    }
+  }

[reveman, 2014/07/15 01:51:10]

How much of the cost of Initialize is building these vectors compared to
make_heap? Lazy make_heap makes sense but it's not clear why building a vector
that is already large enough would be expensive. Would it help to not call
PeekTile here?

[vmpstr, 2014/07/15 05:36:26]

The vector building here is the expensive part. The ctor of
LayerEvictionTileIterator creates TilingEvictionTileIterators, which cause us to
do work. After iterator construction, PeekTile is almost free. make_heap has its
own cost, but I doubt it's the dominant one.

[reveman, 2014/07/15 16:49:56]

Could most of the ctor cost be moved to PeekTile in a clean way?

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

PeekTile will find a tiling iterator and access its tile. We _could_ make more
things lazy, but I think that's overly complicating things since then
TilingRasterTileIterator becomes a queue as well, and it becomes lazy in much
the same way as this is.

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

Hm, looks like we already have some lazy init stuff there. I see some "if
(!IsValid()) Initialize();" code which looks OK to me as it's updating the
underlying data type (the tiling) and not destroying it in any way. Is this not
already providing the laziness we need?

Fyi, I don't think it's the laziness that makes it a queue. I think it can be
fine to have a lazy iterator. Ideally it would just make some lazy update to the
underlying data type as what it looks like the TilingRasterTileIterator is
doing. If the iterator uses a heap internally to iterate then it might be better
to use a priority queue API instead trying of an iterator. Doesn't look like
that's the case here.

+
+  std::make_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  initialized_ = true;
+}
+
+EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
+}
+
+void EvictionTilePriorityQueue::Pop() {
+  if (!initialized_)
+    Initialize();
+
+  std::pop_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  PairedPictureLayerIterator* paired_iterator = iterator_heap_.back();
+  iterator_heap_.pop_back();
+
+  paired_iterator->PopTile(tree_priority_);
+  if (paired_iterator->PeekTile(tree_priority_) != NULL) {
+    iterator_heap_.push_back(paired_iterator);
+    std::push_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  }
+}
+
+bool EvictionTilePriorityQueue::IsEmpty() {
+  if (!initialized_)
+    Initialize();
+
+  return iterator_heap_.empty();
+}
+
+Tile* EvictionTilePriorityQueue::Top() {
+  if (!initialized_)
+    Initialize();
+
+  DCHECK(!IsEmpty());
+  return iterator_heap_.front()->PeekTile(tree_priority_);
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerIterator::
+    PairedPictureLayerIterator() {
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerIterator::
+    ~PairedPictureLayerIterator() {
+}
+
+Tile* EvictionTilePriorityQueue::PairedPictureLayerIterator::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::PairedPictureLayerIterator::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::PairedPictureLayerIterator::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()(
+    PairedPictureLayerIterator* a,
+    PairedPictureLayerIterator* 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