cc: Implement geometry-based tile eviction

cc: Implement geometry-based tile 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 they would have been rasterized in.

In addition to that, shared tiles are returned only by one tiling set
eviction queue. This way tiling set eviction queues can skip shared
tiles those priorities for tree priority are closer to those of unshared
tiles of the twin tiling. This lessen the number of out of reversed
priority order tiles returned by tiling set eviction queues (which
were previously handled by sorting). This will also allow eviction tile
priority queue not to check for shared tiles returned twice.

Committed: https://crrev.com/b4f58cb105bf52668175780da598bb3703d24462
Cr-Commit-Position: refs/heads/master@{#308078}

[USE eero AT chromium.org, 2014-11-18 15:22:10]

e.hakkinen@samsung.com changed reviewers:
+ vmpstr@chromium.org

[USE eero AT chromium.org, 2014-11-18 15:28:26]

PTAL.

This is the actual implementation patch set (split from
https://codereview.chromium.org/674103004/) which replaces eviction tile cache
and sorting with the use of reverse spiral difference iterator.

After new eviction algorithm is merged, I have 3-5 optimization commits (for
eviction tile priority queue, for layer eviction tile iterator and a couple for
tiling eviction tile iterator) which depend on this one but not from each other
and can thus be reviewed separately.

[vmpstr, 2014-11-18 18:13:34]

On 2014/11/18 15:28:26, e_hakkinen wrote:
> PTAL.
> 
> This is the actual implementation patch set (split from
> https://codereview.chromium.org/674103004/) which replaces eviction tile cache
> and sorting with the use of reverse spiral difference iterator.
> 
> After new eviction algorithm is merged, I have 3-5 optimization commits (for
> eviction tile priority queue, for layer eviction tile iterator and a couple
for
> tiling eviction tile iterator) which depend on this one but not from each
other
> and can thus be reviewed separately.

Do you know what the relative gains are for the optimization patches, after
https://codereview.chromium.org/644313002/ would land? I'm a bit concerned that
this might be adding some complexity to the code but I'm not sure if the
benefits are worth it. Also, let's wait until
https://codereview.chromium.org/644313002/ lands so that it's clear where the
differences are.

[USE eero AT chromium.org, 2014-11-19 11:41:46]

On 2014/11/18 18:13:34, vmpstr wrote:
> Do you know what the relative gains are for the optimization patches, after
> https://codereview.chromium.org/644313002/ would land?

Performance-wise, this and optimization patches give 7 % gain in
tile_manager_eviction_tile_queue_construct_and_iterate performance unit tests
on (geometric and arithmetic) average.

For all *Eviction* cc performance unit tests the gain is 0-1 % on average.
That is because this patch moves shared tile filtering from the eviction tile
priority queue to tiling eviction tile iterators. That slows down tiling
eviction tile iterators (and therefore also layer eviction tile iterators)
in terms of returned tiles (which is what performance unit tests measure)
but not in terms of processed tiles (which is what actually matters for real
cases). On the other hand, this patch also eliminates the handling of
duplicated shared tiles which were previously returned by iterators and then
later filtered out by priority queues which benefits the eviction tile
priority queue.

So all in all, I think that the 7 % gain is more relevant than the 0-1 % gain.

> I'm a bit concerned that this might be adding some complexity to the code
> but I'm not sure if the benefits are worth it.

As I said previously (at https://codereview.chromium.org/644313002/#msg4)
it is not only question about performance but also about correctness of
eviction order which is worsen more by
https://codereview.chromium.org/644313002/
(using reverse spiral difference iterators and not taking some required
for activation states into account) than by this patch (using reverse
spiral difference iterators but taking all required for activation states
into account)

[vmpstr, 2014-11-19 16:47:59]

On 2014/11/19 11:41:46, e_hakkinen wrote:
> On 2014/11/18 18:13:34, vmpstr wrote:
> > Do you know what the relative gains are for the optimization patches, after
> > https://codereview.chromium.org/644313002/ would land?
> 
> Performance-wise, this and optimization patches give 7 % gain in
> tile_manager_eviction_tile_queue_construct_and_iterate performance unit tests
> on (geometric and arithmetic) average.
> 
> For all *Eviction* cc performance unit tests the gain is 0-1 % on average.
> That is because this patch moves shared tile filtering from the eviction tile
> priority queue to tiling eviction tile iterators. That slows down tiling
> eviction tile iterators (and therefore also layer eviction tile iterators)
> in terms of returned tiles (which is what performance unit tests measure)
> but not in terms of processed tiles (which is what actually matters for real
> cases). On the other hand, this patch also eliminates the handling of
> duplicated shared tiles which were previously returned by iterators and then
> later filtered out by priority queues which benefits the eviction tile
> priority queue.
> 
> So all in all, I think that the 7 % gain is more relevant than the 0-1 % gain.

Agreed. It doesn't matter if the tiling iterator gets slower as long as the tile
manager priority queue gets faster.

> 
> > I'm a bit concerned that this might be adding some complexity to the code
> > but I'm not sure if the benefits are worth it.
> 
> As I said previously (at https://codereview.chromium.org/644313002/#msg4)
> it is not only question about performance but also about correctness of
> eviction order which is worsen more by
> https://codereview.chromium.org/644313002/
> (using reverse spiral difference iterators and not taking some required
> for activation states into account) than by this patch (using reverse
> spiral difference iterators but taking all required for activation states
> into account)

That's where I'm a bit confused. Pending tree is the only one that sets the
required for activation, so it feels that the logic of dealing with who returns
the twin just to deal with activation is too complicated. The tiling eviction
iterator as it stands right now separates NOW and NOW_AND_RFA tiles into two
different categories which are iterated one after the other. So at tiling level,
the separation is there. I'm pretty sure you would find the same separation at
the layer level (especially since only one tiling can have RFA tiles -- the high
res one, which should be evicted last). So, given that, is * below enough to
make sure we prioritize rfa tiles correctly? If so, that should be a separate
patch with just that in there.

I have some other comments below, but at this point I feel that we should
rethink a high level structure here first, then optimize. That is, I think it
would make sense to have PictureLayerTilingSet be more of a cache storage and
these iterators be pre-warm and eviction policies (hidden behind a virtual base
perhaps). I also think that the layer level iterators should become picture
layer tiling set level iterators. I'm going to try to write a doc at some point
that describes what I want this code to look like.

I'm going a bit off tangent here, but my point is that I think we should invest
some time to clean up the code and move some bits around so that when asked "who
determines when an rfa tile is evicted" we don't have to scratch our head and
remember where to look... With this patch the answer would be first look in the
tiling iterator, then look in the tile manager priority queue, which seems... I
don't know, too complicated. I also think we should do this without too much
consideration for performance, as long as it stays more or less the same. The
hope being that once this is simple and easy to understand, we can optimize.

What do you think about all of this?

https://codereview.chromium.org/736753002/diff/1/cc/resources/eviction_tile_p...
File cc/resources/eviction_tile_priority_queue.cc (right):

https://codereview.chromium.org/736753002/diff/1/cc/resources/eviction_tile_p...
cc/resources/eviction_tile_priority_queue.cc:216: if
(active_priority.priority_bin == pending_priority.priority_bin) {
*

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

https://codereview.chromium.org/736753002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1120:
tiling_->client_->GetMaxTilePriorityBin();
I'm not sure if this check matters here. The order here will only matter for the
layer. That is, the layer will consume all of these tiles and this will only
determine the cross-tilings order. However, since MaxTilePriorityBin is a layer
property, if it's set at EVENTUALLY, then all tiles will be returned as
eventually. If this is an optimization, then it's not worth it. If this is a
correctness fix, then I don't see it (can you explain?).

https://codereview.chromium.org/736753002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1138: case
SOON_AND_REQUIRED_FOR_ACTIVATION:
Doing both SOON and SOON_AND_RFA would return double the tiles no? (Assuming
they aren't actually evicted but iterated).

https://codereview.chromium.org/736753002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1271:
PreparseTileUnlessReturningShouldBeDoneByTwin(Tile* tile) const {
This is named a bit awkwardly. It feels like it's two functions
"IsReturnedByTwin(tile)" and "UpdateTileAndTwinPriority" (which already exists
on tiling)

[USE eero AT chromium.org, 2014-11-20 14:54:38]

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

https://codereview.chromium.org/736753002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1120:
tiling_->client_->GetMaxTilePriorityBin();
On 2014/11/19 16:47:58, vmpstr wrote:
> I'm not sure if this check matters here.
[...]
> If this is an optimization, then it's not worth it. If this is a
> correctness fix, then I don't see it (can you explain?).

It's a bit of both. I removed if from here (thus removed the optimization part)
and added the correctness fix to AdvanceNow (IsTileOccluded should not be called
if the final priority bin is not NOW.

https://codereview.chromium.org/736753002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1138: case
SOON_AND_REQUIRED_FOR_ACTIVATION:
On 2014/11/19 16:47:58, vmpstr wrote:
> Doing both SOON and SOON_AND_RFA would return double the tiles no?

No. SOON returns only tiles which are not required-for-activation in the pending
tree while SOON_AND_RFA returns only tiles which are required-for-activation in
the pending tree.

https://codereview.chromium.org/736753002/diff/1/cc/resources/picture_layer_t...
cc/resources/picture_layer_tiling.cc:1271:
PreparseTileUnlessReturningShouldBeDoneByTwin(Tile* tile) const {
On 2014/11/19 16:47:58, vmpstr wrote:
> This is named a bit awkwardly. It feels like it's two functions
> "IsReturnedByTwin(tile)" and "UpdateTileAndTwinPriority" (which already exists
> on tiling)

Yes, and avoids calling costly UpdateTileAndTwinPriority when not absolutely
needed. But those two functionalities are quite easy to separate now, so I did
that.

[USE eero AT chromium.org, 2014-11-20 15:29:16]

On 2014/11/19 16:47:59, vmpstr wrote:
> That's where I'm a bit confused. Pending tree is the only one that sets the
> required for activation, so it feels that the logic of dealing with who
returns
> the twin just to deal with activation is too complicated. The tiling eviction
> iterator as it stands right now separates NOW and NOW_AND_RFA tiles into two
> different categories which are iterated one after the other. So at tiling
level,
> the separation is there. I'm pretty sure you would find the same separation at
> the layer level (especially since only one tiling can have RFA tiles -- the
high
> res one, which should be evicted last). So, given that, is * below enough to
> make sure we prioritize rfa tiles correctly? If so, that should be a separate
> patch with just that in there.

The problem in priority order is caused by "out of order tiles" whose priority
for tree priority is raised by the twin priority. Those tiles can block
iteration of an tiling eviction tile iterator and hide lower priority tiles and
prevent them from being evicted. That could cause tiles from different layers to
be evicted in incorrect order.

With current (sorting method) that problem does not exist so much as tiles are
sorted based on their priority for tree priority.

> I have some other comments below, but at this point I feel that we should
> rethink a high level structure here first, then optimize.

I agree.

> That is, I think it
> would make sense to have PictureLayerTilingSet be more of a cache storage and
> these iterators be pre-warm and eviction policies (hidden behind a virtual
base
> perhaps). I also think that the layer level iterators should become picture
> layer tiling set level iterators. I'm going to try to write a doc at some
point
> that describes what I want this code to look like.
> 
> I'm going a bit off tangent here, but my point is that I think we should
invest
> some time to clean up the code and move some bits around so that when asked
"who
> determines when an rfa tile is evicted" we don't have to scratch our head and
> remember where to look... With this patch the answer would be first look in
the
> tiling iterator, then look in the tile manager priority queue, which seems...
I
> don't know, too complicated. I also think we should do this without too much
> consideration for performance, as long as it stays more or less the same. The
> hope being that once this is simple and easy to understand, we can optimize.
> 
> What do you think about all of this?

Cleaning up would make sense.

IMHO, it should be acknowledged that there is a very tight coupling between
layer eviction tile iterators and tiling eviction tile iterators and actually
merge them.

Most of the time eviction tile iterators iterate over tiles using a reverse
spiral difference iterator (or using a vector index as in now) which is actually
quite simple. That could be the main part of operator++ of the iterator.

Only then the current reverse spiral difference iterator (or the current vector)
is exhausted, where is a need to change eviction category, tiling, reverse
spiral difference iterator or tile vector. That would be much cleaner if there
were only one level of eviction tile iterators and one class to implement that.
Only the creation of tiling data iterators could then maybe be delegated to
tilings.

[vmpstr, 2014-11-20 18:49:37]

> 
> Cleaning up would make sense.
> 
> IMHO, it should be acknowledged that there is a very tight coupling between
> layer eviction tile iterators and tiling eviction tile iterators and actually
> merge them.
> 
> Most of the time eviction tile iterators iterate over tiles using a reverse
> spiral difference iterator (or using a vector index as in now) which is
actually
> quite simple. That could be the main part of operator++ of the iterator.
> 
> Only then the current reverse spiral difference iterator (or the current
vector)
> is exhausted, where is a need to change eviction category, tiling, reverse
> spiral difference iterator or tile vector. That would be much cleaner if there
> were only one level of eviction tile iterators and one class to implement
that.
> Only the creation of tiling data iterators could then maybe be delegated to
> tilings.

I think that makes sense. The initial implementation of eviction iterators
basically modeled raster iterators. There, the separation might make more
sense, since the layer raster picks one or two tilings (high and possibly 
low res) and determines the interleaving order. However, I guess
you could argue that those could be merged as well.

[USE eero AT chromium.org, 2014-11-27 16:35:20]

Here is a rebase on top of tiling set eviction queue. This does not yet really
take advantage of code clean up, so I have to do that later.

[USE eero AT chromium.org, 2014-12-08 14:46:42]

PTAL.

The implementation is much cleaner now that eviction tile iterators are merged
into eviction tile priority queue.

[vmpstr, 2014-12-09 02:10:59]

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
cc/layers/picture_layer_impl_unittest.cc:3886: if (tile->is_occluded(tree))
This should happen outside of the if (is shared) block

https://codereview.chromium.org/736753002/diff/60001/cc/resources/eviction_ti...
File cc/resources/eviction_tile_priority_queue.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/eviction_ti...
cc/resources/eviction_tile_priority_queue.cc:211: if
(active_priority.priority_bin == pending_priority.priority_bin) {
While here, can you add a couple more comments in this functions:

at line 202, something like:
// If tiles are the same, it doesn't matter which tree we return.

before this block, something like:
// If the bins are the same and activation differs, then return the tree of the
tile not required for activaiton.

and below this block:
// Return tile with a lower priority.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/eviction_ti...
cc/resources/eviction_tile_priority_queue.cc:213: if
(!pending_tile->required_for_activation())
I think this can be a bit simpler:

if (active_priority.priority_bin == pending_priority.priority_bin &&
    active_tile->required_for_activation() !=    
        pending_tile_required_for_activation()) {
 return active_tile->required_for_activation()
            ? PENDING_TREE : ACTIVE_TREE;
}

That works, right?

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:40:
current_required_for_activation_tiling_index_(kNullTilingIndex),
Can we just find the high res tiling index directly? I'm not sure if there are
more uses of this, or is it just used as a high res index?

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:83: WhichTree tree =
current_tiling_->client_->GetTree();
You can take this as a ctor argument, since it won't change during iteration.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:85: bool skip_all_shared_tiles =
likewise, this can be determined at ctor time

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:90: while (spiral_iterator_ ||
can we maybe split this into a nested loop? something like the following:

while (true) {
 while (spiral_iterator_) {
   ...
 }

 if (processing_soon_border_rect_) {
   AdvanceToSkewport();
   processing_soon_border_rect_ = false;
 } else {
   break;
 }
}

Wdyt?
It's a bit difficult for me to reason about this at a glance otherwise.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:100: if (IsSharedOutOfOrderTile(tile))
For symmetry, maybe this should be

if (skip_shared_out_of_order_tiles && IsSharedOutOfOrderTile(tile))

It's a bit confusing that IsSharedOutOfOrderTile returns false if we don't have
to skip them. That is, the tile is either share out of order or it's not, and
that shouldn't depend on whether we're required to skip them.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.h (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.h:44: bool
processing_required_for_activation_tiling_;
I'm not sure what this means.. tilings aren't typically classified as required
for activation, just tiles. Is this true if we're processing a pending tree high
res tiling?

[USE eero AT chromium.org, 2014-12-09 18:44:15]

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
cc/layers/picture_layer_impl_unittest.cc:3886: if (tile->is_occluded(tree))
On 2014/12/09 02:10:58, vmpstr wrote:
> This should happen outside of the if (is shared) block

No, it should not.
The purpose of this second while loop is to count tiles which are occluded and
which belong to the layer (passed as the first parameter) but which are not
returned by the first eviction queue. This can happen for tiles which are shared
and those priority for tree priority is closer to the priority for the twin tree
and therefore they would be out of order tiles if they were returned by the
first eviction queue. So they are returned by the twin eviction queue.

My idea here was to modify unit tests as little as possible. Therefore I did not
modify numbers such as expected_occluded_tile_count. If you would like a
different approach, please say so.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/eviction_ti...
File cc/resources/eviction_tile_priority_queue.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/eviction_ti...
cc/resources/eviction_tile_priority_queue.cc:211: if
(active_priority.priority_bin == pending_priority.priority_bin) {
On 2014/12/09 02:10:58, vmpstr wrote:
> While here, can you add a couple more comments in this functions:
> 
> at line 202, something like:
> // If tiles are the same, it doesn't matter which tree we return.
> 
> before this block, something like:
> // If the bins are the same and activation differs, then return the tree of
the
> tile not required for activaiton.
> 
> and below this block:
> // Return tile with a lower priority.

Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/eviction_ti...
cc/resources/eviction_tile_priority_queue.cc:213: if
(!pending_tile->required_for_activation())
On 2014/12/09 02:10:58, vmpstr wrote:
> I think this can be a bit simpler:
> 
> if (active_priority.priority_bin == pending_priority.priority_bin &&
>     active_tile->required_for_activation() !=    
>         pending_tile_required_for_activation()) {
>  return active_tile->required_for_activation()
>             ? PENDING_TREE : ACTIVE_TREE;
> }
> 
> That works, right?

Yes. Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:40:
current_required_for_activation_tiling_index_(kNullTilingIndex),
On 2014/12/09 02:10:58, vmpstr wrote:
> Can we just find the high res tiling index directly? I'm not sure if there are
> more uses of this, or is it just used as a high res index?

The other reason is not to process the tiling having RFA tiles for the second
time (on the first time RFA tiles are skipped) if we do not see any RFA tiles
(because there aren't any or because they are skipped and to be returned by the
thin queue).
And while it is easy to get the tiling index in the case of the pending tree (in
which case it is always the high res tiling), I think it is more complex in the
case of the active tree. Usually the twin tiling of the pending high res tiling
is active high res tiling but is it guaranteed to be so?

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:83: WhichTree tree =
current_tiling_->client_->GetTree();
On 2014/12/09 02:10:58, vmpstr wrote:
> You can take this as a ctor argument, since it won't change during iteration.

Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:85: bool skip_all_shared_tiles =
On 2014/12/09 02:10:58, vmpstr wrote:
> likewise, this can be determined at ctor time

Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:90: while (spiral_iterator_ ||
On 2014/12/09 02:10:58, vmpstr wrote:
> can we maybe split this into a nested loop? something like the following:
> 
> while (true) {
>  while (spiral_iterator_) {
>    ...
>  }
> 
>  if (processing_soon_border_rect_) {
>    AdvanceToSkewport();
>    processing_soon_border_rect_ = false;
>  } else {
>    break;
>  }
> }
> 
> Wdyt?
> It's a bit difficult for me to reason about this at a glance otherwise.

Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:100: if (IsSharedOutOfOrderTile(tile))
On 2014/12/09 02:10:58, vmpstr wrote:
> For symmetry, maybe this should be
> 
> if (skip_shared_out_of_order_tiles && IsSharedOutOfOrderTile(tile))
> 
> It's a bit confusing that IsSharedOutOfOrderTile returns false if we don't
have
> to skip them. That is, the tile is either share out of order or it's not, and
> that shouldn't depend on whether we're required to skip them.

Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.h (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.h:44: bool
processing_required_for_activation_tiling_;
On 2014/12/09 02:10:59, vmpstr wrote:
> Is this true if we're processing a pending tree high res tiling?

Yes. But it is also true if we are processing the an active tree tiling whose
twin tiling is the high res pending tree tiling and we are returning shared
required-for-activation tiles from the active tree eviction queue because tree
priority is SMOOTHNESS_TAKES_PRIORITY.

Do you have a better name? Should it be
processing_tiling_having_required_for_activation_tiles_, or something? That does
not tell that it can be a twin tiling, though.

[vmpstr, 2014-12-09 19:47:56]

The patch looks good overall. I think we need to simplify the whole rfa logic
and finding the right tiling before this can land. As far as I can see, we're
using a bool and an index to kind of do a dance to figure out when to process
rfa tiles. I think we need to make this more in line with the rest of the code. 

One option would be to add another PictureLayertilingSet::RFA_TILING or
something like that, but I also don't think that's the correct approach, since
it makes little sense for active tree. 

I'm not sure I have better ideas. Maybe if we move more calculations to the
ctor, it would be cleaner.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:40:
current_required_for_activation_tiling_index_(kNullTilingIndex),
On 2014/12/09 18:44:15, e_hakkinen wrote:
> On 2014/12/09 02:10:58, vmpstr wrote:
> > Can we just find the high res tiling index directly? I'm not sure if there
are
> > more uses of this, or is it just used as a high res index?
> 
> The other reason is not to process the tiling having RFA tiles for the second
> time (on the first time RFA tiles are skipped) if we do not see any RFA tiles
> (because there aren't any or because they are skipped and to be returned by
the
> thin queue).
> And while it is easy to get the tiling index in the case of the pending tree
(in
> which case it is always the high res tiling), I think it is more complex in
the
> case of the active tree. Usually the twin tiling of the pending high res
tiling
> is active high res tiling but is it guaranteed to be so?

It's not guaranteed, but I don't think it's that much more complicated, you just
have to find a twin tiling with HIGH_RESOLUTION and then find an index of the
tiling in this set that has the same scale. The point is that this would
simplify the rest of the code by ensuring that
current_required_for_activation_tiling_index_ (or what should probably be
renamed to tiling_index_with_required_for_activation_tiles_) is always correct.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.h (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.h:44: bool
processing_required_for_activation_tiling_;
On 2014/12/09 18:44:15, e_hakkinen wrote:
> On 2014/12/09 02:10:59, vmpstr wrote:
> > Is this true if we're processing a pending tree high res tiling?
> 
> Yes. But it is also true if we are processing the an active tree tiling whose
> twin tiling is the high res pending tree tiling and we are returning shared
> required-for-activation tiles from the active tree eviction queue because tree
> priority is SMOOTHNESS_TAKES_PRIORITY.
> 
> Do you have a better name? Should it be
> processing_tiling_having_required_for_activation_tiles_, or something? That
does
> not tell that it can be a twin tiling, though.

I see. I think the second name is better, since it kinda says that you'er
processing a tiling and that tiling might have tiles required for activation...
Maybe even something like processing_tiling_with_required_for_activation_tiles_

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:54: const PictureLayerTilingClient*
client = tiling_set_->tiling_at(0)->client_;
tiling_set has a client as well (and it's the same client), so
tiling_set_->client() would work here.

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:112:
SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);
This is the part that is confusing to me. I think if we compute the tiling ahead
of time, then I won't have to wonder things like "ok, if all required for
activation tiles don't have resources, would this ever hit here, since we
continue above?"

I think once we start the iteration (and all the calls to Advance*), we
shouldn't be trying to figure out which tiling is which at the same time. This
should be done ahead of time (in the ctor).

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:349: default:
Don't put a default case (if a new case is added, it will be a compiler error
rather than a run time error)

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:357: const TilePriority&
other_priority = tile->priority(other_tree);
nit: twin_tree/twin_priority

[USE eero AT chromium.org, 2014-12-10 12:35:46]

On 2014/12/09 19:47:56, vmpstr wrote:
> The patch looks good overall. I think we need to simplify the whole rfa logic
> and finding the right tiling before this can land.
[...]
> Maybe if we move more calculations to the ctor, it would be cleaner.

I moved calculations to the ctor or actually to a function called by the ctor.

I also changed the value used for indicating no such tiling from max size_t
to past-the-last index. That is maybe more in line with common conventions.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:40:
current_required_for_activation_tiling_index_(kNullTilingIndex),
On 2014/12/09 19:47:55, vmpstr wrote:
> On 2014/12/09 18:44:15, e_hakkinen wrote:
> > On 2014/12/09 02:10:58, vmpstr wrote:
> > > Can we just find the high res tiling index directly? I'm not sure if there
> are
> > > more uses of this, or is it just used as a high res index?
> > 
> > The other reason is not to process the tiling having RFA tiles for the
second
> > time (on the first time RFA tiles are skipped) if we do not see any RFA
tiles
> > (because there aren't any or because they are skipped and to be returned by
> the
> > thin queue).
> > And while it is easy to get the tiling index in the case of the pending tree
> (in
> > which case it is always the high res tiling), I think it is more complex in
> the
> > case of the active tree. Usually the twin tiling of the pending high res
> tiling
> > is active high res tiling but is it guaranteed to be so?
> 
> It's not guaranteed, but I don't think it's that much more complicated, you
just
> have to find a twin tiling with HIGH_RESOLUTION and then find an index of the
> tiling in this set that has the same scale. The point is that this would
> simplify the rest of the code by ensuring that
> current_required_for_activation_tiling_index_ (or what should probably be
> renamed to tiling_index_with_required_for_activation_tiles_) is always
correct.

Done.

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.h (right):

https://codereview.chromium.org/736753002/diff/60001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.h:44: bool
processing_required_for_activation_tiling_;
On 2014/12/09 19:47:55, vmpstr wrote:
> On 2014/12/09 18:44:15, e_hakkinen wrote:
> > On 2014/12/09 02:10:59, vmpstr wrote:
> > > Is this true if we're processing a pending tree high res tiling?
> > 
> > Yes. But it is also true if we are processing the an active tree tiling
whose
> > twin tiling is the high res pending tree tiling and we are returning shared
> > required-for-activation tiles from the active tree eviction queue because
tree
> > priority is SMOOTHNESS_TAKES_PRIORITY.
> > 
> > Do you have a better name? Should it be
> > processing_tiling_having_required_for_activation_tiles_, or something? That
> does
> > not tell that it can be a twin tiling, though.
> 
> I see. I think the second name is better, since it kinda says that you'er
> processing a tiling and that tiling might have tiles required for
activation...
> Maybe even something like
processing_tiling_with_required_for_activation_tiles_

Done.

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:54: const PictureLayerTilingClient*
client = tiling_set_->tiling_at(0)->client_;
On 2014/12/09 19:47:56, vmpstr wrote:
> tiling_set has a client as well (and it's the same client), so
> tiling_set_->client() would work here.

Done.

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:112:
SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);
On 2014/12/09 19:47:56, vmpstr wrote:
> This is the part that is confusing to me. I think if we compute the tiling
ahead
> of time, then I won't have to wonder things like "ok, if all required for
> activation tiles don't have resources, would this ever hit here, since we
> continue above?"
> 
> I think once we start the iteration (and all the calls to Advance*), we
> shouldn't be trying to figure out which tiling is which at the same time. This
> should be done ahead of time (in the ctor).

Done.

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:349: default:
On 2014/12/09 19:47:56, vmpstr wrote:
> Don't put a default case (if a new case is added, it will be a compiler error
> rather than a run time error)

Done. Had to add case for NUM_TREE_PRIORITIES, though.

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:357: const TilePriority&
other_priority = tile->priority(other_tree);
On 2014/12/09 19:47:56, vmpstr wrote:
> nit: twin_tree/twin_priority

Done.

[vmpstr, 2014-12-10 18:01:15]

I think this is almost ready.

As another request, can you put a (large) comment in the .h of the queue
explaining in which order the tiles will be returned, which will be skipped, and
all of that? It can be just a point form summary. Thanks!

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
cc/layers/picture_layer_impl_unittest.cc:3886: if (tile->is_occluded(tree))
On 2014/12/09 18:44:14, e_hakkinen wrote:
> On 2014/12/09 02:10:58, vmpstr wrote:
> > This should happen outside of the if (is shared) block
> 
> No, it should not.
> The purpose of this second while loop is to count tiles which are occluded and
> which belong to the layer (passed as the first parameter) but which are not
> returned by the first eviction queue. This can happen for tiles which are
shared
> and those priority for tree priority is closer to the priority for the twin
tree
> and therefore they would be out of order tiles if they were returned by the
> first eviction queue. So they are returned by the twin eviction queue.
> 
> My idea here was to modify unit tests as little as possible. Therefore I did
not
> modify numbers such as expected_occluded_tile_count. If you would like a
> different approach, please say so.

I think that makes sense, thanks for the explanation. Can you leave a comment
explaining this? At a first glance, it seems that we're ignoring unshared tiles
erroneously.

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/80001/cc/resources/tiling_set_...
cc/resources/tiling_set_eviction_queue.cc:349: default:
On 2014/12/10 12:35:46, e_hakkinen wrote:
> On 2014/12/09 19:47:56, vmpstr wrote:
> > Don't put a default case (if a new case is added, it will be a compiler
error
> > rather than a run time error)
> 
> Done. Had to add case for NUM_TREE_PRIORITIES, though.

Ok, that's fine. We can remove NUM_TREE_PRIORITIES in a follow-up. It seems to
be only be used in tests.

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:102: if
(tile->required_for_activation() == required_for_activation) {
nit: for consistency, you might as well have

if (tile->rfa() != rfa)
  continue;
current_eviction_tile = tile;
return true;

but that's really up to you.

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:123: TilePriority::PriorityBin
max_tile_priority_bin =
If we move this outside of the if, the whole thing becomes

getter
while (visible_iterator_) {
  ...
}

instead of

if (visible_iterator_) {
 getter
 do {
   ...
 } while(visible_iterator_);
}

Unless I missed something... If that's equivalent can you change it to that
please?

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:133: if (max_tile_priority_bin <=
TilePriority::NOW) {
Put a comment here explaining this block please (ie, why do we only check rfa
for pending tree only when max priority is now).

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:155: while
(next_unoccluded_now_tile_index_ < unoccluded_now_tiles_.size()) {
I'm thinking it might be cleaner to just pop_front (if you change this to a
deque) or pop_back (if you keep this a vector) and use the front tile always.

This would eliminate the index, and the clear and the if check just becomes
while (!empty) check.

[USE eero AT chromium.org, 2014-12-11 15:22:00]

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
File cc/layers/picture_layer_impl_unittest.cc (right):

https://codereview.chromium.org/736753002/diff/60001/cc/layers/picture_layer_...
cc/layers/picture_layer_impl_unittest.cc:3886: if (tile->is_occluded(tree))
On 2014/12/10 18:01:15, vmpstr wrote:
> On 2014/12/09 18:44:14, e_hakkinen wrote:
> > On 2014/12/09 02:10:58, vmpstr wrote:
> > > This should happen outside of the if (is shared) block
> > 
> > No, it should not.
> > The purpose of this second while loop is to count tiles which are occluded
and
> > which belong to the layer (passed as the first parameter) but which are not
> > returned by the first eviction queue. This can happen for tiles which are
> shared
> > and those priority for tree priority is closer to the priority for the twin
> tree
> > and therefore they would be out of order tiles if they were returned by the
> > first eviction queue. So they are returned by the twin eviction queue.
> > 
> > My idea here was to modify unit tests as little as possible. Therefore I did
> not
> > modify numbers such as expected_occluded_tile_count. If you would like a
> > different approach, please say so.
> 
> I think that makes sense, thanks for the explanation. Can you leave a comment
> explaining this? At a first glance, it seems that we're ignoring unshared
tiles
> erroneously. 

Done.

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:102: if
(tile->required_for_activation() == required_for_activation) {
On 2014/12/10 18:01:15, vmpstr wrote:
> nit: for consistency, you might as well have
> 
> if (tile->rfa() != rfa)
>   continue;
> current_eviction_tile = tile;
> return true;
> 
> but that's really up to you.

Done. That makes sense now that this does not have to keep track of tiling with
rfa tiles. I changed other loop similarly, too.

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:123: TilePriority::PriorityBin
max_tile_priority_bin =
On 2014/12/10 18:01:15, vmpstr wrote:
> If we move this outside of the if, the whole thing becomes
[...]
> Unless I missed something... If that's equivalent can you change it to that
> please?

Done. There used to be quite a many variables which were needed only while
iterating the visible iterator. Now there is only one, so it makes hardly a
difference.

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:133: if (max_tile_priority_bin <=
TilePriority::NOW) {
On 2014/12/10 18:01:15, vmpstr wrote:
> Put a comment here explaining this block please (ie, why do we only check rfa
> for pending tree only when max priority is now).

Done.

https://codereview.chromium.org/736753002/diff/120001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:155: while
(next_unoccluded_now_tile_index_ < unoccluded_now_tiles_.size()) {
On 2014/12/10 18:01:15, vmpstr wrote:
> I'm thinking it might be cleaner to just pop_front (if you change this to a
> deque) or pop_back (if you keep this a vector) and use the front tile always.
> 
> This would eliminate the index, and the clear and the if check just becomes
> while (!empty) check.

Done.

[USE eero AT chromium.org, 2014-12-11 15:27:03]

On 2014/12/10 18:01:15, vmpstr wrote:
> I think this is almost ready.
> 
> As another request, can you put a (large) comment in the .h of the queue
> explaining in which order the tiles will be returned, which will be skipped,
and
> all of that? It can be just a point form summary. Thanks!

Done.

While doing that, I noticed that I am somehow managed to get
IsSharedOutOfOrderTile reversed (so it actually implemented
IsSharedInOrderTile). Quite embarrassing. Well, better to catch that before
integration than after that. I fixed that and added more unit test tests (which
fail with old implementation and succeed with the fixed implementation).

[vmpstr, 2014-12-11 18:35:03]

Was there a test that caught the fact that the condition got reversed? If not, I
think we might want to put in at least some smoke tests to ensure that we're
doing the right thing.

Other than that, lgtm.

https://codereview.chromium.org/736753002/diff/180001/cc/resources/tiling_set...
File cc/resources/tiling_set_eviction_queue.cc (right):

https://codereview.chromium.org/736753002/diff/180001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:334: DCHECK_EQ(ACTIVE_TREE, tree_);
I know we can do this because of skip_all_shared_tiles optimization, but I'm
almost thinking that we should just return tree_ == PENDING_TREE (which should
always be false) and similarly for the new content case.

That's really up to you though.

https://codereview.chromium.org/736753002/diff/180001/cc/resources/tiling_set...
File cc/resources/tiling_set_eviction_queue.h (right):

https://codereview.chromium.org/736753002/diff/180001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:15: // This eviction queue returned
tiles from all tilings in a tiling set in
That's awesome. Thanks for the comment.

[USE eero AT chromium.org, 2014-12-12 09:02:30]

On 2014/12/11 18:35:03, vmpstr wrote:
> Was there a test that caught the fact that the condition got reversed? If not,
I
> think we might want to put in at least some smoke tests to ensure that we're
> doing the right thing.

While I noticed the error, I also added unit test tests.
So the Patch Set 9 contains both the fix and tests to test that the
implementation is correct.

> Other than that, lgtm.

[USE eero AT chromium.org, 2014-12-12 10:29:57]

The CQ bit was checked by e.hakkinen@samsung.com

[commit-bot: I haz the power, 2014-12-12 10:30:44]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/736753002/180001

[commit-bot: I haz the power, 2014-12-12 14:41:41]

Committed patchset #10 (id:180001)

[commit-bot: I haz the power, 2014-12-12 14:42:48]

Patchset 10 (id:??) landed as
https://crrev.com/b4f58cb105bf52668175780da598bb3703d24462
Cr-Commit-Position: refs/heads/master@{#308078}