cc: Rework tiling set eviction iterator.

cc: Rework tiling set eviction iterator.

This patch changes the way the tiling set eviction iterators work. It mostly
restructures how each phase is processed in order to allow easier changes
in the future.

High level summary of changes:
- Create helper iterators that can process individual phases
- Preprocess the order in which tilings are processed
- Define explicit enums for combinations of phases, instead of an enum + flags

R=enne, danakj

Committed: https://crrev.com/58d6a71707faa1ca205cfcd8de181ef13fe6b7a8
Cr-Commit-Position: refs/heads/master@{#324290}

[vmpstr, 2015-03-26 20:30:35]

vmpstr@chromium.org changed reviewers:
+ danakj@chromium.org, enne@chromium.org

[vmpstr, 2015-03-26 20:32:11]

Please take a look. I know this is a bit more code, but overall I think a lot of
the structure repeats which makes it nice to reason about each phase of
processing. We can probably further reduce the size of the code by refactoring
more common code, but I think this is a good balance.

[vmpstr, 2015-03-26 20:41:41]

On 2015/03/26 20:32:11, vmpstr wrote:
> Please take a look. I know this is a bit more code, but overall I think a lot
of
> the structure repeats which makes it nice to reason about each phase of
> processing. We can probably further reduce the size of the code by refactoring
> more common code, but I think this is a good balance.

FYI, this passes cc_unittests (there are several tests that test eviction), and
it has negligible impact on cc_perftests --gtest_filter="*Eviction*".

[USE eero AT chromium.org, 2015-03-27 10:40:59]

Have you intentionally changed the algorithm so that it does not differentiate
between not-required-for-activation EVENTUALLY tiles and rfa EVENTUALLY tiles
(and between not-rfa SOON tiles and rfa SOON tiles)? That is not mentioned in
the commit message.

In https://codereview.chromium.org/471833002, you said that that differentiation
is needed. Has something changed since then?

[vmpstr, 2015-03-27 17:00:19]

On 2015/03/27 10:40:59, e_hakkinen wrote:
> Have you intentionally changed the algorithm so that it does not differentiate
> between not-required-for-activation EVENTUALLY tiles and rfa EVENTUALLY tiles
> (and between not-rfa SOON tiles and rfa SOON tiles)? That is not mentioned in
> the commit message.
> 
> In https://codereview.chromium.org/471833002, you said that that
differentiation
> is needed. Has something changed since then?

The change was intentional yes. Since the initial implementation, you've changed
this algorithm to skip shared out of order tiles (previously we depended on a
set in the higher level iterators to skip these). For the reason, I don't think
the rfa/non-rfa eventually tiles matters. That is, rfa tiles can only come from
visible tiles on the pending tree, so if it's eventually on the active then it
would be skipped anyway. Does that make sense?

The main goal of this patch is to actually allow us to easily change these
categories, so if the consensus is that we should still have eventually
rfa/non-rfa tiles then that can also add more enums to Phase.

I've updated the description to include this.

[enne (OOO), 2015-03-27 19:12:11]

Looks like good cleanup in general.  I like the abstraction into a set of
iterators.  I also like not having to accumulate all the different types of
visible tiles (and the change to use flags), because you only have one iterator.

It is three extra walks of all the visible tiles though.  Is that ok for
performance?

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:85: // 1. Higher than high res from
higher to lower resolution.
This seems like a duplicate comment from some other file.  Can you make it one
place and then just refer to the other?

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:413: continue;
This is maybe just a style nit, but these loops are a bit confusing to me. 
tilings_ is ordered, right? So, the first time we don't have a skewport tile,
you should just break instead of continue?

Can this just be like:

  for (size_t idx = tiling_index_; idx < tilings_->size() &&
has_skewport_tiles(idx); ++idx)

...instead of a while loop and this continue?

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:525: return
(tile->required_for_activation() ==
style nit: no need for parens.  You could also break this up into two temporary
booleans, and it'd still be three lines long.

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:44: //  1. Process higher than high res
tilings.
I feel like this needs wording like "down to" or "up to" to indicate the order
that you process higher than high res tilings, e.g. "Process the highest scale
tiling down to, but not including, high res."

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:83: class OnePriorityRectIterator {
What does "one priority" mean?

[vmpstr, 2015-03-27 20:19:28]

PTAL

On 2015/03/27 19:12:11, enne wrote:
> Looks like good cleanup in general.  I like the abstraction into a set of
> iterators.  I also like not having to accumulate all the different types of
> visible tiles (and the change to use flags), because you only have one
iterator.
> 
> It is three extra walks of all the visible tiles though.  Is that ok for
> performance?

There is no noticeable impact on performance from this patch (from
cc_perftests). Also, the visible iteration would only really be reached after
all prepainting tiles are evicted and we still don't have memory. I'm not too
worried about fast performance in those situations. (Also happens when memory
goes to 0, ie going invisible).

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:85: // 1. Higher than high res from
higher to lower resolution.
On 2015/03/27 19:12:11, enne wrote:
> This seems like a duplicate comment from some other file.  Can you make it one
> place and then just refer to the other?

Done.

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:413: continue;
On 2015/03/27 19:12:11, enne wrote:
> This is maybe just a style nit, but these loops are a bit confusing to me. 
> tilings_ is ordered, right? So, the first time we don't have a skewport tile,
> you should just break instead of continue?
> 
> Can this just be like:
> 
>   for (size_t idx = tiling_index_; idx < tilings_->size() &&
> has_skewport_tiles(idx); ++idx)
> 
> ...instead of a while loop and this continue?

The has skewport rect tiles check is on the tiling though. That is, if the first
tiling doesn't have tiles in that region, a second one could. 

This is like:

If this tiling doesn't have tiles, try the next tiling
Create the iterator
If the iterator is empty, try the next tiling
Else done.

The while loop with continues seems like a most natural way to capture that to
me. I'm open to suggestions (a for loop would also work, but it would still have
continues, would you prefer that instead?)

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:525: return
(tile->required_for_activation() ==
On 2015/03/27 19:12:11, enne wrote:
> style nit: no need for parens.  You could also break this up into two
temporary
> booleans, and it'd still be three lines long.

Eh, I'm not so worried about length, but I did change it for clarity.

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:44: //  1. Process higher than high res
tilings.
On 2015/03/27 19:12:11, enne wrote:
> I feel like this needs wording like "down to" or "up to" to indicate the order
> that you process higher than high res tilings, e.g. "Process the highest scale
> tiling down to, but not including, high res."

Done.

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:83: class OnePriorityRectIterator {
On 2015/03/27 19:12:11, enne wrote:
> What does "one priority" mean?

Well, it's just one priority rect as in eventually or soon border or skewport or
visible

I just want to extract some of the common functionality of those into one class.
This is the name we have in the equivalent raster iterators, but I'm open to
suggestions for a name that better captures the intent.

[enne (OOO), 2015-03-27 21:48:05]

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.cc:413: continue;
On 2015/03/27 20:19:27, vmpstr wrote:
> On 2015/03/27 19:12:11, enne wrote:
> > This is maybe just a style nit, but these loops are a bit confusing to me. 
> > tilings_ is ordered, right? So, the first time we don't have a skewport
tile,
> > you should just break instead of continue?
> > 
> > Can this just be like:
> > 
> >   for (size_t idx = tiling_index_; idx < tilings_->size() &&
> > has_skewport_tiles(idx); ++idx)
> > 
> > ...instead of a while loop and this continue?
> 
> The has skewport rect tiles check is on the tiling though. That is, if the
first
> tiling doesn't have tiles in that region, a second one could. 
> 
> This is like:
> 
> If this tiling doesn't have tiles, try the next tiling
> Create the iterator
> If the iterator is empty, try the next tiling
> Else done.
> 
> The while loop with continues seems like a most natural way to capture that to
> me. I'm open to suggestions (a for loop would also work, but it would still
have
> continues, would you prefer that instead?)

Oh, right.  I think I was thinking about the wrong dimension of the problem
here.  Ignore this comment!

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:83: class OnePriorityRectIterator {
On 2015/03/27 20:19:27, vmpstr wrote:
> On 2015/03/27 19:12:11, enne wrote:
> > What does "one priority" mean?
> 
> Well, it's just one priority rect as in eventually or soon border or skewport
or
> visible
> 
> I just want to extract some of the common functionality of those into one
class.
> This is the name we have in the equivalent raster iterators, but I'm open to
> suggestions for a name that better captures the intent.

I guess it's the "OnePriority" part that confuses me.

What about just like RectIterator? Or even EvictionRectIterator?

[vmpstr, 2015-03-27 22:46:55]

PTAL

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

https://codereview.chromium.org/1038793002/diff/40001/cc/resources/tiling_set...
cc/resources/tiling_set_eviction_queue.h:83: class OnePriorityRectIterator {
On 2015/03/27 21:48:05, enne wrote:
> On 2015/03/27 20:19:27, vmpstr wrote:
> > On 2015/03/27 19:12:11, enne wrote:
> > > What does "one priority" mean?
> > 
> > Well, it's just one priority rect as in eventually or soon border or
skewport
> or
> > visible
> > 
> > I just want to extract some of the common functionality of those into one
> class.
> > This is the name we have in the equivalent raster iterators, but I'm open to
> > suggestions for a name that better captures the intent.
> 
> I guess it's the "OnePriority" part that confuses me.
> 
> What about just like RectIterator? Or even EvictionRectIterator?

Done.

[enne (OOO), 2015-03-27 22:48:54]

lgtm

[vmpstr, 2015-03-27 22:49:49]

On 2015/03/27 22:48:54, enne wrote:
> lgtm

Thanks. I will commit on Monday to ensures that I'm available if there are
issues with this patch in ToT/Canary

[USE eero AT chromium.org, 2015-03-30 08:02:37]

On 2015/03/27 17:00:19, vmpstr wrote:
> The change was intentional yes. Since the initial implementation, you've
changed
> this algorithm to skip shared out of order tiles (previously we depended on a
> set in the higher level iterators to skip these). For the reason, I don't
think
> the rfa/non-rfa eventually tiles matters. That is, rfa tiles can only come
from
> visible tiles on the pending tree, so if it's eventually on the active then it
> would be skipped anyway. Does that make sense?

Mostly.
But if tree priority is SMOOTHNESS_TAKES_PRIORITY, all shared tiles (including
rfa tiles) are returned only by the active tiling set eviction queue as rfa
EVENTUALLY, SOON or NOW tiles. So it seems that after this change, some rfa
tiles will not be evicted until tree priority is changed to either
NEW_CONTENT_TAKES_PRIORITY or SAME_PRIORITY_FOR_BOTH_TREES.

Other other hand, maybe the skipping algorithm should be changed to reflect
https://codereview.chromium.org/924613002

> The main goal of this patch is to actually allow us to easily change these
> categories, so if the consensus is that we should still have eventually
> rfa/non-rfa tiles then that can also add more enums to Phase.

> I've updated the description to include this.

Thanks.

[vmpstr, 2015-04-07 22:11:47]

Please take another look at this, since is is now rebased on
https://codereview.chromium.org/1051473002/

[USE eero AT chromium.org, 2015-04-07 22:48:22]

lgtm

Now it's LGTM, too.

[USE eero AT chromium.org, 2015-04-07 22:49:40]

Now it's lgtm, too.

[vmpstr, 2015-04-07 23:47:04]

The CQ bit was checked by vmpstr@chromium.org

[vmpstr, 2015-04-07 23:47:05]

The patchset sent to the CQ was uploaded after l-g-t-m from enne@chromium.org
Link to the patchset: https://codereview.chromium.org/1038793002/#ps100001
(title: "rebase")

[commit-bot: I haz the power, 2015-04-07 23:48:10]

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

[commit-bot: I haz the power, 2015-04-08 00:49:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-04-08 00:49:45]

Try jobs failed on following builders:
  win8_chromium_rel on tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win8_chromium_rel...)

[vmpstr, 2015-04-08 18:01:59]

The CQ bit was checked by vmpstr@chromium.org

[vmpstr, 2015-04-08 18:01:59]

The patchset sent to the CQ was uploaded after l-g-t-m from
e.hakkinen@samsung.com, enne@chromium.org
Link to the patchset: https://codereview.chromium.org/1038793002/#ps120001
(title: "fix compile")

[commit-bot: I haz the power, 2015-04-08 18:03:08]

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

[commit-bot: I haz the power, 2015-04-08 19:17:26]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-04-08 19:17:28]

Try jobs failed on following builders:
  win8_chromium_rel on tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win8_chromium_rel...)

[vmpstr, 2015-04-08 19:22:02]

The CQ bit was checked by vmpstr@chromium.org

[vmpstr, 2015-04-08 19:22:02]

The patchset sent to the CQ was uploaded after l-g-t-m from
e.hakkinen@samsung.com, enne@chromium.org
Link to the patchset: https://codereview.chromium.org/1038793002/#ps140001
(title: "actual compile fix")

[commit-bot: I haz the power, 2015-04-08 19:24:17]

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

[commit-bot: I haz the power, 2015-04-08 21:56:52]

Committed patchset #8 (id:140001)

[commit-bot: I haz the power, 2015-04-08 21:57:42]

Patchset 8 (id:??) landed as
https://crrev.com/58d6a71707faa1ca205cfcd8de181ef13fe6b7a8
Cr-Commit-Position: refs/heads/master@{#324290}