cc: Compute the inflated rect to cover a fixed number of tiles.

cc: Compute the inflated rect to cover a fixed number of tiles.

Currently we expand the area around the viewport in which we want to
paint tiles by a fixed amount in all 4 directions. For narrow pages,
this was designed to work well since it will expand and add a "linear"
number of pixels (relative to the width of the viewport). However,
when pinch-zoomed in, or on a wide page, the rect is expanded far
in all directions and so expands to include a quadratic number of
pixels. This creates inconsistent behaviour, and we include too many
tiles in the rect in the latter case, in order to get enough tiles in
the former case.

Instead of expanding the rect in all 4 directions by a very large amount,
we expand the rect to fill a given area, or to cover a given number of
pixels. This way we always include roughly the same number of tiles in the
rect. We expand the rect out in all 4 directions equally to cover the
target area. However, if the rect bumps into the edge of the tiling's
content rect, then we will continue to expand the rect equally along its
other edges until the rect covers the target number of pixels or completely
fills the content rect.

Tests:
PictureLayerTilingTest.ExpandRectEqual
PictureLayerTilingTest.ExpandRectSmaller
PictureLayerTilingTest.ExpandRectUnbounded
PictureLayerTilingTest.ExpandRectBoundedSmaller
PictureLayerTilingTest.ExpandRectBoundedEqual
PictureLayerTilingTest.ExpandRectBoundedSmallerStretchVertical
PictureLayerTilingTest.ExpandRectBoundedEqualStretchVertical
PictureLayerTilingTest.ExpandRectBoundedSmallerStretchHorizontal
PictureLayerTilingTest.ExpandRectBoundedEqualStretchHorizontal
PictureLayerTilingTest.ExpandRectBoundedLeft
PictureLayerTilingTest.ExpandRectBoundedRight
PictureLayerTilingTest.ExpandRectBoundedTop
PictureLayerTilingTest.ExpandRectBoundedBottom
PictureLayerTilingTest.ExpandRectSquishedHorizontally
PictureLayerTilingTest.ExpandRectSquishedVertically

BUG=176580
NOTRY=true

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=183385

[danakj, 2013-02-16 12:39:49]

https://codereview.chromium.org/12287027/diff/5001/cc/picture_layer_tiling.cc
File cc/picture_layer_tiling.cc (right):

https://codereview.chromium.org/12287027/diff/5001/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:397: static const int64 kMaxTilesForPrioritizedRect =
80;
I got 80 from ~1280*4906 with 256*256 tile size, to kinda approximate our
current intended behaviour in the "good" case.

1280/256 = 5
4096/256 = 16
16 * 5 = 80

[nduca, 2013-02-16 22:30:59]

yaaay! Thank you Dana!!!!

https://codereview.chromium.org/12287027/diff/5017/cc/picture_layer_tiling.cc
File cc/picture_layer_tiling.cc (right):

https://codereview.chromium.org/12287027/diff/5017/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:397: static const int64 kMaxTilesForPrioritizedRect =
80;
Should we put this by where the old constant lived? Or at least, up at the top
of the file? Finding these constants when we want to tweak them is tricky. :)

[danakj, 2013-02-18 19:26:20]

https://codereview.chromium.org/12287027/diff/5017/cc/picture_layer_tiling.cc
File cc/picture_layer_tiling.cc (right):

https://codereview.chromium.org/12287027/diff/5017/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:397: static const int64 kMaxTilesForPrioritizedRect =
80;
On 2013/02/16 22:30:59, nduca wrote:
> Should we put this by where the old constant lived? Or at least, up at the top
> of the file? Finding these constants when we want to tweak them is tricky. :)

Right, I feel like asking 3 people would get you 3 different answers about where
this should go, I dunno what's best. Perk of putting it here is it's right where
it's used so when you find the code that uses it you also find the constant.
Perk of putting it out in tile_priority.h is its grouped with other constants
that are somewhat related. I stuck it here cuz I couldn't figure out what I like
more, if you like it more there I'll happily move it :) 

I think to move it, it needs a more descriptive name so you can tell what it is
from out of context over in the header. Maybe like
kNumTilesToCoverWithInflatedViewportRectForPrioritization.

[danakj, 2013-02-19 16:38:51]

Moved the constant to TilePriority. PTAL

[ccameron, 2013-02-19 20:01:09]

Very nice.

I'm a bit worried about CPU overhead here. We found in crbug.com/176150 that
PictureLayerTiling::UpdateTilePriorities was taking a lot of time, and this will
add to that.

Your patch in 
https://chromiumcodereview.appspot.com/12259027/
should help a some.

I wonder if we could we move this math to PictureLayerImpl::updateTilePriorities
to only do the computation once per layer instead of once per tiling?

We would have to take care to make sure that the early-out in
PictureLayerTiling::UpdateTilePriorities of (!first_update_in_new_impl_frame &&
!first_update_in_new_source_frame) is respected. It looks like
https://chromiumcodereview.appspot.com/12259027/ already adds an early-out
structure.

https://codereview.chromium.org/12287027/diff/13001/cc/picture_layer_tiling.cc
File cc/picture_layer_tiling.cc (right):

https://codereview.chromium.org/12287027/diff/13001/cc/picture_layer_tiling.c...
cc/picture_layer_tiling.cc:679: 
Very nice solution.

[nduca, 2013-02-19 20:05:27]

If it helps, low-risk is key as this is slotted for m25. Thus, if it keeps it
low risk, I'm fine taking the perf hit on sites with stupid numbers of layers in
order to get the increase in tile count.

[vangelis, 2013-02-19 20:15:57]

The problem with this squishy expansion is that when we're at the top (or
bottom) of the page, we'll do all our prepainting in a single direction and the
moment we start scrolling the tiles we generated at the bottom (or top) of the
prepaint region will be scrapped.

We may be able to get around this if we avoid deleting tiles that have already
been painted (by giving them higher relative priority in the sorter) or maybe by
preferring to expand pre-painting towards the prevailing scroll direction?

[nduca, 2013-02-19 20:23:52]

I think thats an acceptable tradeoff for now.

[nduca, 2013-02-19 20:24:43]

Or, hmm, we could assume that the layer's content rect goes off in the negative
direction by exactly 1 viewport....

[danakj, 2013-02-19 20:24:46]

On Tue, Feb 19, 2013 at 3:15 PM, <vangelis@google.com> wrote:

> The problem with this squishy expansion is that when we're at the top (or
> bottom) of the page, we'll do all our prepainting in a single direction
> and the
> moment we start scrolling the tiles we generated at the bottom (or top) of
> the
> prepaint region will be scrapped.
>

So, what I think should happen is this..

# = viewport
* = expanded rect
. = rest of the page.


##############
##############
##############
##############
**************
**************
**************
**************
**************
**************
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............

Scroll a bit..

**************
##############
##############
##############
##############
**************
**************
**************
**************
**************
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............

And a bit more..

**************
**************
**************
##############
##############
##############
##############
**************
**************
**************
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............


And a bit more..

..............
..............
**************
**************
**************
##############
##############
##############
##############
**************
**************
**************
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............
..............


So, you will drop stuff above, but not the moment you start scrolling -
rather after the viewport reaches the middle of the prepainted area. Since
the area is hopefully around 4000px tall, you should have about 2000px in
each direction.




>
> We may be able to get around this if we avoid deleting tiles that have
> already
> been painted (by giving them higher relative priority in the sorter) or
> maybe by
> preferring to expand pre-painting towards the prevailing scroll direction?
>
>
>
https://codereview.chromium.**org/12287027/<https://codereview.chromium.org/1...
>

[danakj, 2013-02-19 20:26:19]

On Tue, Feb 19, 2013 at 3:24 PM, <nduca@chromium.org> wrote:

> Or, hmm, we could assume that the layer's content rect goes off in the
> negative
> direction by exactly 1 viewport....
>

Yeh, we can definitely give a subset of the ContentRect() to the method if
we have that info (do we?)


>
>
https://codereview.chromium.**org/12287027/<https://codereview.chromium.org/1...
>

[enne (OOO), 2013-02-19 20:28:53]

The math to scale that rect was introduced in r181029
(https://codereview.chromium.org/12225054).  Previously, it just used a fixed
offset increase from the viewport size in content space.  Can you convince me
that this patch isn't going to regress the performance that change was trying to
address?

The purpose of this rect is to generate an area of interest outside the visible
area.  Just because the visible area suddenly bumps up against the side of the
layer, it doesn't mean necessarily that suddenly tiles farther out in other
directions become more interesting.  It kind of seems like one pass of
ComputeOffsetToExpand4EdgesEqually should be sufficient.

What's the intention for handling visible content rects that are larger than the
fixed constant area? Should they be shrunk equally, even though there's no
consideration for where the zoom anchor is?

[ccameron, 2013-02-19 20:37:50]

On 2013/02/19 20:15:57, vangelis wrote:
> We may be able to get around this if we avoid deleting tiles that have already
> been painted

I have a sequence of patches out to do that
- https://codereview.chromium.org/12289021/
- https://codereview.chromium.org/12289020/
- https://codereview.chromium.org/12280021/
But it was decided that this is too risky to land for M25.

[ccameron, 2013-02-19 20:46:37]

On 2013/02/19 20:28:53, enne wrote:
> The math to scale that rect was introduced in r181029
> (https://codereview.chromium.org/12225054).  Previously, it just used a fixed
> offset increase from the viewport size in content space.  Can you convince me
> that this patch isn't going to regress the performance that change was trying
to
> address?

This is trying to do the same thing as that patch, but does it in a more
principled way. That patch was aiming at getting a more-fixed area.

> The purpose of this rect is to generate an area of interest outside the
visible
> area.

IMO the core problem is that this rectangle determines two things
1. What to (pre-)paint now (everything in the rect)
2. What to delete now (everything not in the rect).

IMO this rect should just be the first of these -- "what to (pre-)paint now".
That way, it can be substantially smaller. 

There are two cases we care about here
A. Long, narrow pages -- we want to pre-paint down for sudden user motion
B. Zoomed in pages -- we want to pre-paint every direction the user can scroll
in, but not blow out the tile count.

This approach of "constant area centered at the viewport" is a better
approximation of these. In the case of pinch-zoom, we may want to introduce
yet-more constraints (e.g, don't paint high-resolution tiles outside of
something even smaller than current viewport, etc). There's more room for
tweaking that.

[nduca, 2013-02-20 00:39:49]

Folks, we need this. How do we get it landed? I'm going to go verify this on the
sites that caused us issues

[vangelis, 2013-02-20 01:26:56]

https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc
File cc/picture_layer_tiling.cc (right):

https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:583: int add_each_axis = (-b + sqrt_part) / 2 / a;
Sorry, maybe you've figured this out already but what about the second solution
to the quadratic equation (-b - sqrt_part) / (2*a)?

https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:699: bool left_complete = false;
Should you check that the area of starting_rect < target_area?  Otherwise some
of your calculations may produce unexpected results.

[vangelis, 2013-02-20 01:28:52]

On 2013/02/20 01:26:56, vangelis wrote:
> https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc
> File cc/picture_layer_tiling.cc (right):
> 
>
https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc...
> cc/picture_layer_tiling.cc:583: int add_each_axis = (-b + sqrt_part) / 2 / a;
> Sorry, maybe you've figured this out already but what about the second
solution
> to the quadratic equation (-b - sqrt_part) / (2*a)?
> 
>
https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc...
> cc/picture_layer_tiling.cc:699: bool left_complete = false;
> Should you check that the area of starting_rect < target_area?  Otherwise some
> of your calculations may produce unexpected results.

Other than these comments, LGTM , pending at least some basic verification that
it doesn't explode!!  Nicely done, BTW.

[danakj, 2013-02-20 01:40:05]

Ugh lost my reply by taking too long on it :(

On 2013/02/19 20:28:53, enne wrote:
> The math to scale that rect was introduced in r181029
> (https://codereview.chromium.org/12225054).  Previously, it just used a fixed
> offset increase from the viewport size in content space.  Can you convince me
> that this patch isn't going to regress the performance that change was trying
to
> address?

That patch was trying to keep the number of tiles more constant by inflating the
rect by a value inversely proportional to the scale factor. As you pinch out the
viewport rect grows larger, this tried to compensate and keep the growth
constant. However since it doesn't consider the ideal scale it won't do the
right thing to accomplish that.

This patch inflates the rect to cover a fixed number of tiles always. As the
viewport rect grows, the amount we have to expand decreases because the area of
the final rect is not changed.

Numbers-wise, I see a rect about 2500x2100 instead of 5000x5000 (before this
CL), so I'd say we have a smaller rect not a worse/larger one.

> The purpose of this rect is to generate an area of interest outside the
visible
> area.  Just because the visible area suddenly bumps up against the side of the
> layer, it doesn't mean necessarily that suddenly tiles farther out in other
> directions become more interesting.  It kind of seems like one pass of
> ComputeOffsetToExpand4EdgesEqually should be sufficient.

They don't become more important, but we have the space for them, so I think
it's wasteful to not add them. We want to keep a relatively constant number of
tiles painted all the time.

> What's the intention for handling visible content rects that are larger than
the
> fixed constant area? Should they be shrunk equally, even though there's no
> consideration for where the zoom anchor is?

I'd like to address this in a followup. For now I hope that it's reasonable
because the range is large enough. I think we could weight the growth by the
position of the anchor in the viewport. I'm working on that now.

[danakj, 2013-02-20 01:44:39]

https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc
File cc/picture_layer_tiling.cc (right):

https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:583: int add_each_axis = (-b + sqrt_part) / 2 / a;
On 2013/02/20 01:26:56, vangelis wrote:
> Sorry, maybe you've figured this out already but what about the second
solution
> to the quadratic equation (-b - sqrt_part) / (2*a)? 

This was always the wrong answer for me. Because the width, height, and target
area are always positive numbers, only the one root can be correct.

https://codereview.chromium.org/12287027/diff/3021/cc/picture_layer_tiling.cc...
cc/picture_layer_tiling.cc:699: bool left_complete = false;
On 2013/02/20 01:26:56, vangelis wrote:
> Should you check that the area of starting_rect < target_area?  Otherwise some
> of your calculations may produce unexpected results.

This is covered by PictureLayerTilingTest.ExpandRectSmaller. It should end up
producing a negative amount to grow, and shrink the rect instead of growing it
until it fits the area.

[commit-bot: I haz the power, 2013-02-20 02:29:17]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/danakj@chromium.org/12287027/13001

[nduca, 2013-02-20 02:30:20]

also lgtm

[commit-bot: I haz the power, 2013-02-20 02:44:17]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/danakj@chromium.org/12287027/13001

[commit-bot: I haz the power, 2013-02-20 02:47:41]

Change committed as 183385