cc: Start using raster/eviction iterators.

cc/resources/eviction_tile_priority_queue.h

Index: cc/resources/eviction_tile_priority_queue.h
diff --git a/cc/resources/eviction_tile_priority_queue.h b/cc/resources/eviction_tile_priority_queue.h
new file mode 100644
index 0000000000000000000000000000000000000000..f3ecb5ac13ace29fd489aa5ed1bd88c6d8862709
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.h
@@ -0,0 +1,74 @@
+// 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.
+
+#ifndef CC_RESOURCES_EVICTION_TILE_PRIORITY_QUEUE_H_
+#define CC_RESOURCES_EVICTION_TILE_PRIORITY_QUEUE_H_
+
+#include <utility>
+#include <vector>
+
+#include "cc/base/cc_export.h"
+#include "cc/layers/picture_layer_impl.h"
+#include "cc/resources/tile_priority.h"
+#include "cc/resources/tile_priority_queue.h"
+
+namespace cc {
+
+class CC_EXPORT EvictionTilePriorityQueue : public TilePriorityQueue {
+ public:
+  EvictionTilePriorityQueue();
+  virtual ~EvictionTilePriorityQueue();
+
+  void Reset();
+  void BuildQueue(const std::vector<PairedPictureLayer>& paired_picture_layers,
+                  TreePriority tree_priority);
+
+  // TilePriorityQueue overrides.
+  virtual void Pop() OVERRIDE;
+  virtual bool IsEmpty() OVERRIDE;
+  virtual Tile* Top() OVERRIDE;
+
+ private:
+  struct PairedPictureLayerIterator {

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

This doesn't look like an iterator. PeekTile/PopTile, looks like this is also a
priority queue. PairedPictureLayerQueue?

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

Yeah you're right, I will change that.

+    PairedPictureLayerIterator();
+    ~PairedPictureLayerIterator();
+
+    Tile* PeekTile(TreePriority tree_priority);
+    void PopTile(TreePriority tree_priority);
+
+    PictureLayerImpl::LayerEvictionTileIterator* NextTileIterator(
+        TreePriority tree_priority);
+
+    PictureLayerImpl::LayerEvictionTileIterator active_iterator;
+    PictureLayerImpl::LayerEvictionTileIterator pending_iterator;
+
+    std::vector<Tile*> returned_shared_tiles;

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

can you explain what this is for? looked at the .cc file but not perfectly
clear.

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

active and pending iterators can return the same tile (if it's shared on both
trees). When we return a tile, we put it in this vector. Later, when a tile is
returned we check this vector and if the tile was already returned (ie is
present in the vector), we skip it.

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

That's unfortunate. Sort of defeats the purpose of reusing the queue to avoid
heap allocations if you're going to have to heap allocate these vectors every
time.. But I guess it's not too bad as they are empty by default and not
populated until PopTile is called.

We could handle this much more efficiently at the tile manager level as we
already have a vector (never larger than 32) with the tiles already returned
that we can check against..

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

That was one of the considerations I had initially. It feels really awkward to
have a priority queue return a tile, then check if that tile was already
returned though. It's kind of non-obvious that this particular queue can return
duplicate items. You're right that the thing that makes it OK, IMO, is the fact
that it starts empty and only grows on a pop.

Note that this is also per layer pair, which means that they probably remain
smaller than 32 with more than one layer. At tile manager level, this would be
all layers together (probably doesn't make much of a difference though).

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

Instead of checking if we've returned the tile already using a vector, can you
check if the other tree priority is higher? In which case, we should have
returned the tile already, right?

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

I think this would not work for eviction, since tiles are turned in combined
priority order (lowest to highest).

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

Ok, if this is the only case where we need a temporary heap allocation when
queuing tiles for raster/eviction then it might be worth removing just as a
cleanup. No need to do it as part of this patch but it I think it's worth a TODO
for at least investigating.

+  };
+
+  class EvictionOrderComparator {
+   public:
+    explicit EvictionOrderComparator(TreePriority tree_priority);
+
+    bool operator()(PairedPictureLayerIterator* a,
+                    PairedPictureLayerIterator* b) const;
+
+   private:
+    TreePriority tree_priority_;
+  };
+
+  void Initialize();
+
+  std::vector<PairedPictureLayerIterator> paired_iterators_;
+  std::vector<PairedPictureLayerIterator*> iterator_heap_;

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

why both paired_iterators_ and iterator_heap_ instead of just making
paired_iterators_ a heap? are iterator instances large enough that they become
expensive to move? in that case, can we do something about that?

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

They are certainly more expensive than moving a pointer. Not sure what we can do
here: layer iterators contain a vector or two, with some more data. During
iteration we remove and re-add those, so the cost accumulates.

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

How hard would it be to remove these vectors or replace them by arrays? Having
all the priority queue data stored in one chunk of memory could make a big
difference performance wise.

A heap with pointers might still make sense though. Have you done any profiling
of this?

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

Sorry, this is already two arrays, one is an array of 4 elements (struct with
two enums), and one is of size 3 (tiling iterators). Tiling iterators has two
tiling data iterators, a couple of enums, a pointer and a bool...

I mean, I would say the size is not small. I haven't done any profiling on this.
My goal at this stage is not really optimizing at this level, but rather
encapsulate all of these operations behind an interface and make sure it works.
If that's done properly, we should be able to play around with different ways of
actually implementing the interface without affecting correctness. 

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

Cool, that's great! So if we just eliminate the |returned_shared_tiles| vector,
TilePriorityQueue is just one big chunk of memory. I think that's going to be
very valuable when trying to make this fast.
I agree. Getting the interface right is top priority. I think second is making
sure the implementation is simple and clean so that it's easy to follow up with
profiling and performance tweaks.

+  std::vector<PairedPictureLayer> paired_picture_layers_;
+  TreePriority tree_priority_;
+  EvictionOrderComparator comparator_;
+  bool initialized_;
+
+  DISALLOW_COPY_AND_ASSIGN(EvictionTilePriorityQueue);
+};
+
+}  // namespace cc
+
+#endif  // CC_RESOURCES_EVICTION_TILE_PRIORITY_QUEUE_H_