cc: Use reverse spiral iterator in tiling eviction.

cc: Use reverse spiral iterator in tiling eviction.

This patch optimizes the way we do eviction at the tiling level.
Instead of using sort, it uses a reverse spiral iterator to iterate
tiles in reverse order of what it would have been rasterized in.

The fundamental difference in results is that the tiling no longer
uses the tree priority to determine the order of tiles. In practice
this means that each tiling (and thus each layer) will return tiles
that it thinks should be evicted without regard for twin priority.
It's up to the tile manager priority queue to reconcile the two.

The tile manager priority queue already uses tree priority to
determine the tile priority and returns an appropriate (less
needed) tile. However, there are situations where this still
yields worse results than before. For instance if we're in
smoothness mode, and a pending tree has unshared tiles,
those used to be returned first (since active tree priority
is inf). However, now the pending tree will return the tile
that is furthest away from the pending tree viewport, which
means it might return a tile that is shared before an unshared
one. I personally think this is acceptable, since we're gaining
quite a bit of a performance win here (8x-10x on
cc_perftests with "*Eviction*" filter).

R=reveman, danakj

[vmpstr, 2014-10-13 03:41:57]

PTAL. This depends on the reverse spiral iterator patch.

[ajuma, 2014-10-23 23:12:53]

ajuma@chromium.org changed reviewers:
+ ajuma@chromium.org

[ajuma, 2014-10-23 23:12:54]

I'm trying to wrap my head around this stuff and have a few questions.

https://codereview.chromium.org/644313002/diff/1/cc/layers/picture_layer_impl...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/644313002/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl_unittest.cc:2868: EXPECT_EQ(55,
distance_decreasing);
Is there an intuitive explanation for why we get these numbers?

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
File cc/resources/picture_layer_tiling.cc (right):

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1077: TreePriority tree_priority,
Unused now, remove?

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1108: case
SOON_AND_REQUIRED_FOR_ACTIVATION:
Why is there nothing to do for this case? Is it because SOON tiles are never
required for activation? (And if that's the case, why do we have this category
at all?)

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1221: }
Why don't we need to consider whether the tile is required for activation when
dealing with unoccluded tiles?

[USE eero AT chromium.org, 2014-10-28 19:27:09]

> This patch optimizes the way we do eviction at the tiling level. Instead of
using sort, it uses a reverse spiral iterator to iterate tiles in reverse order
of what it would have been rasterized in.

Very good idea, indeed.

> However, there are situations where this still yields worse results than
before.
[...]
> I personally think this is acceptable, since we're gaining quite a bit of a
performance win here (8x-10x on cc_perftests with "*Eviction*" filter). 

I am not so sure, if that is needed or preferable.
It is possible to get almost the same performance win without those worse
results, see https://codereview.chromium.org/674103004/

[vmpstr, 2014-10-29 18:19:41]

PTAL

https://codereview.chromium.org/644313002/diff/1/cc/layers/picture_layer_impl...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/644313002/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl_unittest.cc:2868: EXPECT_EQ(55,
distance_decreasing);
On 2014/10/23 23:12:54, ajuma wrote:
> Is there an intuitive explanation for why we get these numbers?

Well.. I'm not sure how intuitive it is, starting with eventually rect we'll
spiral down, but going from side to corner the distance will increase and going
from corner to side the distance will decrease, so it isn't technically distance
decreasing order. This check is just so that we're _mostly_ distance decreasing.
In raster iterators, I have something like distance_decreasing > 3 * total_tiles
/ 4, but I figured might as well put in the actual numbers.

If you have a suggestion for a better solution, I'll be happy to put it in (I'm
not exactly proud of this test :) )

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
File cc/resources/picture_layer_tiling.cc (right):

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1077: TreePriority tree_priority,
On 2014/10/23 23:12:54, ajuma wrote:
> Unused now, remove?

Done.

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1108: case
SOON_AND_REQUIRED_FOR_ACTIVATION:
On 2014/10/23 23:12:54, ajuma wrote:
> Why is there nothing to do for this case? Is it because SOON tiles are never
> required for activation? (And if that's the case, why do we have this category
> at all?)

Yes and removed.

https://codereview.chromium.org/644313002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1221: }
On 2014/10/23 23:12:54, ajuma wrote:
> Why don't we need to consider whether the tile is required for activation when
> dealing with unoccluded tiles?

Tile that is occluded is not required for activation... I've added some comments
throughout the code that hopefully makes it easier to read.

[ajuma, 2014-10-29 19:42:39]

Thanks, lgtm.

https://codereview.chromium.org/644313002/diff/1/cc/layers/picture_layer_impl...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/644313002/diff/1/cc/layers/picture_layer_impl...
cc/layers/picture_layer_impl_unittest.cc:2868: EXPECT_EQ(55,
distance_decreasing);
On 2014/10/29 18:19:41, vmpstr wrote:
> On 2014/10/23 23:12:54, ajuma wrote:
> > Is there an intuitive explanation for why we get these numbers?
> 
> Well.. I'm not sure how intuitive it is, starting with eventually rect we'll
> spiral down, but going from side to corner the distance will increase and
going
> from corner to side the distance will decrease, so it isn't technically
distance
> decreasing order. This check is just so that we're _mostly_ distance
decreasing.
> In raster iterators, I have something like distance_decreasing > 3 *
total_tiles
> / 4, but I figured might as well put in the actual numbers.
> 
> If you have a suggestion for a better solution, I'll be happy to put it in
(I'm
> not exactly proud of this test :) )

Ok, I mostly wanted to find out if these specific values were intended to be
immediately obvious from reading the test, since if they were, I was clearly
missing something :)  It makes sense that we're checking that we're mostly
distance decreasing. I'd suggest adding a comment about this.

[reveman, 2014-11-11 00:13:27]

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
File cc/resources/picture_layer_tiling.h (right):

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.h:134: void AdvanceNow(bool first_run);
If I understand the code correctly, which one of these functions that we use
depends on on the value of eviction_category_ and we would never use two. I
found that a bit confusing. I expected each one to be used over the lifetime of
an iterator when I first looked at this code.

If these different categories are so significantly different that they need
different functions to advance, should they be implemented as different
iterators?

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.h:141: std::vector<Tile*>
unoccluded_now_tiles_;
can you do two passes instead of having this vector?

[vmpstr, 2014-11-11 22:02:53]

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
File cc/resources/picture_layer_tiling.h (right):

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.h:134: void AdvanceNow(bool first_run);
On 2014/11/11 00:13:27, reveman wrote:
> If I understand the code correctly, which one of these functions that we use
> depends on on the value of eviction_category_ and we would never use two.

Correct.

> I
> found that a bit confusing. I expected each one to be used over the lifetime
of
> an iterator when I first looked at this code.
> 
> If these different categories are so significantly different that they need
> different functions to advance, should they be implemented as different
> iterators?

This is basically to avoid having a vector in the layer level iterators. For
raster, we have a similar problem that that we solve by persisting the HIGH and
LOW res iterator and picking one or the other depending on the next tile
returned. The problem with eviction is that we can have any number of these
tilings so in order to persist iterators, we'd need a vector. 

The current solution is to "instantiate" the iterator with what eviction
category we need. This worked fine in the approach where we sort vectors,
because it simply meant we pick one of these vectors based on the category.
However, with the spiral approach we don't have a vector to pick, we have to
iterate the category that's given to us (which happens to have slightly
different iteration requirements, hence the several functions).

We can have different iterators here, but that would complicate the layer level
iterator, unless we put a virtual base here. However, if we put a virtual base
with a ::Create call that takes a category, we'll have to create these iterators
on the heap. I think that's a more correct direction to go, to be honest,
because it allows us to be a lot more flexible with having different types of
these iterators (for ganesh, for testing, etc), and maybe call them something
other than iterators (queues?). 

That's something that I feel we should consider separately and measure
performance impact (I imagine that sort of change would have to be made for the
raster iterator as well). Wdyt?

[vmpstr, 2014-11-11 22:54:51]

PTAL

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
File cc/resources/picture_layer_tiling.h (right):

https://codereview.chromium.org/644313002/diff/70001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.h:141: std::vector<Tile*>
unoccluded_now_tiles_;
On 2014/11/11 00:13:27, reveman wrote:
> can you do two passes instead of having this vector?

Done.

[vmpstr, 2014-11-18 18:02:20]

reveman: ping (I have a comment in the #8 that answers your question).

[reveman, 2014-11-18 20:56:22]

My general concern here is that TilingEvictionTileIterator is no longer behaving
in a way I would expect from an iterator. I expect an iterator to use the same
logic to iterate independent of the data and parameters it's constructed from.

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
File cc/resources/picture_layer_tiling.cc (right):

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.cc:1112: switch (category) {
We already have a category switch statement at a different level, in
PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextCategory. This makes
me suspicious. It's not a performance concern. My intuition just tells me that
we're doing something wrong if we need this. It looks like we're forcing
ourselves to use some existing concept (TilingEvictionTileIterator and
categories) when it doesn't map to what's really going on.

This problem existed before this patch too but it was harder to tell as all we
did was pick a vector based on it.

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.cc:1184: // rebuild the iterator to iterate
over skewport.
Why is Skewport not a different category? Wouldn't that make advancing
Eventually, Soon and Skewport the same and remove this special case?

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.cc:1199: void
PictureLayerTiling::TilingEvictionTileIterator::AdvanceNow(
Could we either generalize the Now category code so it's the same as other
categories (just operating on a different data set). Or handle the difference in
LayerEvictionTileIterator instead of hiding it in here? ie. making the layer
iterator first iterate "prepaint" then "visible",
LayerEvictionTileIterator::current_iterator_ ->
LayerEvictionTileIterator::current_prepaint_iterator_/current_visible_iterator_.

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
File cc/resources/picture_layer_tiling.h (right):

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.h:144: TilingData::Iterator visible_iterator_;
Would it hurt to use a ReverseSpiralDifferenceIterator for visible tiles too?

[USE eero AT chromium.org, 2014-11-20 15:03:57]

e.hakkinen@samsung.com changed reviewers:
+ e.hakkinen@samsung.com

[USE eero AT chromium.org, 2014-11-20 15:03:57]

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
File cc/resources/picture_layer_tiling.cc (right):

https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
cc/resources/picture_layer_tiling.cc:1172: while (spiral_iterator_) {
This is wrong.
If there are skewport tiles but no soon border rect tiles, the constructor does
not initialize the spiral iterator. Then in here, the while block won't be
executed and the spiral iterator won't be replaced with skewport iterator thus
skewport tiles won't be iterated at all.

[vmpstr, 2014-11-20 18:45:46]

On 2014/11/20 15:03:57, e_hakkinen wrote:
>
https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
> File cc/resources/picture_layer_tiling.cc (right):
> 
>
https://codereview.chromium.org/644313002/diff/90001/cc/resources/picture_lay...
> cc/resources/picture_layer_tiling.cc:1172: while (spiral_iterator_) {
> This is wrong.
> If there are skewport tiles but no soon border rect tiles, the constructor
does
> not initialize the spiral iterator. Then in here, the while block won't be
> executed and the spiral iterator won't be replaced with skewport iterator thus
> skewport tiles won't be iterated at all.

Good catch. I'm going to hold off on this patch for a bit until I can clean up a
bit more of the code, but will fix in the next iteration.