cc: Implement tile iteration order based on pyramid sequence. [old]

cc: Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. The pyramid sequence
iterates level by level, i.e. inner level to outer level and vice
versa. This is used to implement SpiralDifferenceIterator and
ReverseSpiralDifferenceIterator. The pyramid sequence takes width and
height of the tile into consideration, giving better order of tiles
over previous version. This patch also adds support for move assignment
and move constructor, so that objects can be in-place constructed and
moved to desired container.

This patch also adds test for the tiling smaller than tile size and
center rect not intersecting to tiling rect.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel;tryserver.blink:linux_blink_rel

[prashant.n, 2016-06-15 15:09:42]

Description was changed from

==========
tisd

BUG=
==========

to

==========
tisd

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[prashant.n, 2016-06-16 15:14:46]

prashant.n@samsung.com changed reviewers:
+ vmpstr@chromium.org

[prashant.n, 2016-06-16 15:14:46]

Just have a look. Patch is not yet finished. I've been implementing this
approach for GPU tiles' issue.

[vmpstr, 2016-06-16 18:28:58]

I'm just reading through the code in terms of code itself. It's hard for me to
verify your logic here because I'm not sure what each of the classes intends to
do. Can you add comments throughout the code to make it easier? 

Alternatively, you can write up a small doc to describe your design.

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
File cc/base/pyramid_sequence.cc (right):

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.cc:61: default:
Don't put the default, so that the compiler complains if you don't handle all
cases

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.cc:84: if (current_ > end_)
return current_ <= end_;

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.cc:103: if (current_ < end_)
return current_ >= end_

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.cc:119: if (current_ != start_)
return current_ == start_;

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.cc:135: if (current_ != start_)
return current_ == start_;

Also, diagonal forward and diagonal backward are the same?

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequence.h
File cc/base/pyramid_sequence.h (right):

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.h:13: class CC_EXPORT PyramidSequence {
Can you put a comprehensive comment here explaining what this does?

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.h:22: PyramidSequence(Type type, int start, int end,
int levels);
This needs a comment to explain what each variable does

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.h:25: int GetCurrent();
Name this better... GetCurrent what?

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.h:27: bool within_bounds() { return within_bounds_; }
is_within_bounds

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.h:31: typedef void (PyramidSequence::*InflateFn)();
using InflateFn = void (PyramidSequence::*)();

https://codereview.chromium.org/2067213002/diff/20001/cc/base/pyramid_sequenc...
cc/base/pyramid_sequence.h:54: InflateFn inflater_;
I'd call this "inflate_" and "determine_within_bounds_" or something (like verbs
instead of nouns, but up to you)

https://codereview.chromium.org/2067213002/diff/20001/cc/base/tiling_data.cc
File cc/base/tiling_data.cc (right):

https://codereview.chromium.org/2067213002/diff/20001/cc/base/tiling_data.cc#...
cc/base/tiling_data.cc:604: // UL
Expand comments please.

https://codereview.chromium.org/2067213002/diff/20001/cc/base/tiling_data.h
File cc/base/tiling_data.h (right):

https://codereview.chromium.org/2067213002/diff/20001/cc/base/tiling_data.h#n...
cc/base/tiling_data.h:152: class LDSequence {
I prefer to not abberviate here

https://codereview.chromium.org/2067213002/diff/20001/cc/base/tiling_data.h#n...
cc/base/tiling_data.h:152: class LDSequence {
Needs a comment

https://codereview.chromium.org/2067213002/diff/20001/cc/base/tiling_data.h#n...
cc/base/tiling_data.h:156: LDSequence(PyramidSequence traversal_seq,
don't abbreviate seq

[prashant.n, 2016-06-17 04:20:01]

Once complete with all possible unittests added, I'll add more comments and a
doc for design.

[prashant.n, 2016-06-17 14:20:48]

I'm thinking of adding new iterator (something like
SpiralDistanceDifferenceIterator) co-exist with current SpiralDifferenceIterator
and once stabilized we can retire SpiralDifferenceIterator. What's your opinion?

I'll first finish the implementation to start the formal review. It will take
more time for implementation as there are hell lot of edge cases.

[prashant.n, 2016-06-17 14:26:52]

Description was changed from

==========
tisd

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
tild

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[prashant.n, 2016-06-30 14:32:42]

ptal @ initial version of new implementation. I've added explainatory comments.
It now passes all existing test cases, but still crashes while running chrome.
I'm working on it. Once it is fixed, I'll add the test cases for wide tiles.

Meanwhile pls. add review comments on the implementation.

[prashant.n, 2016-07-08 13:49:27]

Pls. wait for review until I finish the chrome working with patch.

[prashant.n, 2016-07-18 11:42:25]

Description was changed from

==========
tild

BUG=
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. This is used to
implement SpiralDifferenceIterator and ReverseSpiralDifferenceIterator.
The pyramid sequence takes width and height of the tile into
consideration, so that it gives better order of tiles over previous
version. This patch also adds support for move assignment and move
constructor, so that objects can be in-place constructed and moved to
desired container.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[prashant.n, 2016-07-18 11:42:25]

prashant.n@samsung.com changed reviewers:
+ enne@chromium.org

[prashant.n, 2016-07-18 11:42:58]

The CQ bit was checked by prashant.n@samsung.com to run a CQ dry run

[commit-bot: I haz the power, 2016-07-18 11:43:07]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-18 11:43:10]

Your CL relies on deprecated CQ feature(s):
 * Specifying master names in CQ_INCLUDE_TRYBOTS part of description without
"master." prefix is deprecated:
     tryserver.blink
   For more details, see http://crbug.com/617627.

[prashant.n, 2016-07-18 11:49:11]

+enne.

vmpstr@ and enne@ I've finished implementing new logic. This works well with
chrome and I've also added the unittests testing the same. Kindly review the
same, patchset 33. (Sorry for the number of patchsets).

In next patch set, I shall have better order of level distance sequences for the
given direction and hence will modify the unittests accordingly.

[commit-bot: I haz the power, 2016-07-18 11:56:23]

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

[commit-bot: I haz the power, 2016-07-18 11:56:24]

Dry run: Try jobs failed on following builders:
  android_compile_dbg on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_comp...)

[prashant.n, 2016-07-18 16:49:13]

Description was changed from

==========
Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. This is used to
implement SpiralDifferenceIterator and ReverseSpiralDifferenceIterator.
The pyramid sequence takes width and height of the tile into
consideration, so that it gives better order of tiles over previous
version. This patch also adds support for move assignment and move
constructor, so that objects can be in-place constructed and moved to
desired container.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
cc: Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. This is used to
implement SpiralDifferenceIterator and ReverseSpiralDifferenceIterator.
The pyramid sequence takes width and height of the tile into
consideration, so that it gives better order of tiles over previous
version. This patch also adds support for move assignment and move
constructor, so that objects can be in-place constructed and moved to
desired container.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[prashant.n, 2016-07-19 12:46:32]

ptal patchset 37, few unit tests are breaking. I will be fixing them tomorrow.

[vmpstr, 2016-07-19 20:28:28]

I just looked at the pyramid sequence. I think we can break that into two
classes. What do you think? I don't like that this class is trying to be too
smart and doing too many things at once. If it makes sense, can we adopt an
iterator style api and just return the least possible work per level? That is,
we need something to just iterate and expand/shrink intervals; something to just
iterate intervals; something to iterate sequences in reverse; etc.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
File cc/base/pyramid_sequence.h (right):

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:26: //  0 1 2 3 4 5 6 7      (level 4)
What would level 5 look like here?

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:52: class CC_EXPORT TriangularSequence {
I think this class is conflating too many settings into one.

First, is this class returning Intervals or numbers within intervals? I'm not
clear what "Advance" does. Does this iterate over individual numbers and then
advance to the next level when appropriate?

If that's the case, I would prefer two separate classes. One to generate
Intervals so it would just have operator++ and operator* where operator* would
return the current interval and operator++ would advance the level. Then, you
can iterate over the given interval to iterate specific numbers. The caller of
this class can handle the double nesting. 

Second, I don't understand forward/backward/diagonal split. As far as I can
tell, you can just deal with forward case and iterate the interval backwards if
so desired. Diagonal seems to be a special case of start == end, but it's no
different than a regular forward with [start, start], so why the special case? 

At a high level, I'm also very confused by the naming.. why is this a pyramid
sequence? Why is start == end called "diagonal"?

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:64: Interval(const Interval& other) = default;
You don't need to specify copy/move operations here.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:108: // Same like above, but in reverse direction.
This is not clear at all. GetCurrentSequenceNumber's comment is pretty
complicated; simply saying "but in reverse" breaks my understanding even more. 

My confusion is exacerbated by the fact that you already have a
backwards/forward split in the Type, and now you have a reverse getter as well.
So, if I have a backward sequence and use GetReverseCurrentSequenceNumber is
that equivalent to using a forward sequence with GetCurrentSequenceNumber?

[prashant.n, 2016-07-20 03:10:49]

Thanks for the review comments. I'll write more illustrative comments with more
intuitive function names following some general pattern.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
File cc/base/pyramid_sequence.cc (right):

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.cc:67: // This function returns the positions for
different directions.
This function will play important role in giving better iteration order when
content is flowing either by means of scrolling, zooming or animation. I'll
write another CL, which will give us benefit of this. http://crbug.com/629052.

Currently only RIGHT with BOTTOM_RIGHT inclined is supported.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
File cc/base/pyramid_sequence.h (right):

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:26: //  0 1 2 3 4 5 6 7      (level 4)
On 2016/07/19 20:28:28, vmpstr wrote:
> What would level 5 look like here?

-1 0 1 2 3 4 5 6 7 8

The inflation of intervals happens non-restrictively meaning it can flow in all
quadrants of the co-ordinate system.

Our interest is for positive quadrant meaning both x and y to be positive, which
we take care by passing interval_limit.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:52: class CC_EXPORT TriangularSequence {
On 2016/07/19 20:28:28, vmpstr wrote:
> I think this class is conflating too many settings into one.

This is to cater different portions of the pyramid sequence. Pyramid sequence is
list of 8 different level distance sequence.

> 
> First, is this class returning Intervals or numbers within intervals? I'm not
> clear what "Advance" does. Does this iterate over individual numbers and then
> advance to the next level when appropriate?

All of the classes in this file, be it TriagularSequence, LevelDistanceSequence
or PyramidSequence return the next sequence and to advance or point to next
sequence, user should call Advance() method. To check whether sequence is
finished or not IsTravesed() method should be used.

** TriagularSequence is 1 dimensional sequence returns the numbers in inflated
or deflated order (decided by reverse variable)

** LevelDistanceSequence encapsulates the TriagularSequence to give 2
dimentional sequence, current level being traversed and sequence number in
current interval. It traverses one level at a time based on distance assigned to
the level, hence the name LevelDistanceSequence.

** PyramidSequence - It is the list of 8 different level distance sequences
which cover the given rectangle. As it has octgonal base (8 sequences) and these
8 faces are triangular (yeilding sequences in triangular fashion), this is a
kind of octagonal pyramid. This sequence traverses level by level each its
underlined LevelDistanceSequence based on distance, it is more like a slicing
the Pyramid level by level. If we slice this Pyramid from top to down fashion it
yeilds us what Spiral iterator should do and if sliced from bottom to up
fashion, it yeilds us what Reverse Spiral iterator should do.


> 
> If that's the case, I would prefer two separate classes. One to generate
> Intervals so it would just have operator++ and operator* where operator* would
> return the current interval and operator++ would advance the level. Then, you
> can iterate over the given interval to iterate specific numbers. The caller of
> this class can handle the double nesting.

I guess returning iterval will complicate the interface further. The
TriagularSequence should give next sequence number until it finishes all the
levels. So we need 3 simple interfaces -
1. IsTraversed() (this is current not implemented as it was handled by
is_within_bounds(), but for readability we should have this function),
2. Advance() - go to next sequence number
3. GetCurrent

Let me check how can we handle forward sequence and backward sequence in better
way based on your comments.

> 
> Second, I don't understand forward/backward/diagonal split. As far as I can
> tell, you can just deal with forward case and iterate the interval backwards
if
> so desired. Diagonal seems to be a special case of start == end, but it's no
> different than a regular forward with [start, start], so why the special case?

This is to have less and only needed computations respective to indivual case,
i.e. to avoid checking what is a case each time we inflate or check where it is
within limits/bounds.

That's why we have different function definitions for below function pointers.

using InflateFn = void (TriangularSequence::*)(int levels);
using IsWithinBoundsFn = bool (TriangularSequence::*)();

> 
> At a high level, I'm also very confused by the naming.. why is this a pyramid
> sequence? Why is start == end called "diagonal"?

If we make start == end it will give us only one sequence number in
TriagularSequence at each level, so in a way it is linear sequence and we use it
here to cover diagonal portions of the pyramid as given in pyramid split -up
diagram. Hence the name.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:64: Interval(const Interval& other) = default;
On 2016/07/19 20:28:28, vmpstr wrote:
> You don't need to specify copy/move operations here. 

When I tested on Windows (Visual Studio 2013) it was calling copy constructor
instead of move constructor when object is passed as an argument.

I wanted all in-place construction to be move construction, so that we have
minimal overhead when we assign an object to another object.

I'll check if we can skip move constructor and move assignment for simple
classes like these.

At
https://cs.chromium.org/chromium/src/cc/tiles/tiling_set_raster_queue_all.cc?...
we assign the object from newly constructed object, so there we can take benefit
of move assignment.

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:108: // Same like above, but in reverse direction.
On 2016/07/19 20:28:28, vmpstr wrote:
> This is not clear at all. GetCurrentSequenceNumber's comment is pretty
> complicated; simply saying "but in reverse" breaks my understanding even more.

> 
> My confusion is exacerbated by the fact that you already have a
> backwards/forward split in the Type, and now you have a reverse getter as
well.
> So, if I have a backward sequence and use GetReverseCurrentSequenceNumber is
> that equivalent to using a forward sequence with GetCurrentSequenceNumber?

Hmm. I'll write simple functions having more appropriate comments and function
names.

[prashant.n, 2016-07-20 03:53:10]

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
File cc/base/pyramid_sequence.h (right):

https://codereview.chromium.org/2067213002/diff/720001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:52: class CC_EXPORT TriangularSequence {

> If that's the case, I would prefer two separate classes. One to generate

For this I'll check if we can have container <-> iterator kind of separation.

[prashant.n, 2016-07-25 12:27:28]

ptal.

[prashant.n, 2016-07-28 13:10:20]

vmpstr@, with latest patchset following tests are failing where increasing or
decreasing distances are considered.

PictureLayerImplTest.TilingSetEvictionQueue
TileManagerTilePriorityQueueTest.EvictionTilePriorityQueue
TileManagerTilePriorityQueueTest.RasterTilePriorityQueue

For the test PictureLayerImplTest.TilingSetEvictionQueue, the manhattan
distances to viewport are 

tile index [3, 3]   distance_to_visible = 528
tile index [2, 3]   distance_to_visible = 274
tile index [1, 3]   distance_to_visible = 264
tile index [0, 3]   distance_to_visible = 264
tile index [3, 0]   distance_to_visible = 264
tile index [3, 1]   distance_to_visible = 264
tile index [3, 2]   distance_to_visible = 274

when the spiral iterator considers the sequence of coverage directions in pyamid
sequence {RIGHT, TOP_RIGHT, TOP, TOP_LEFT, LEFT, BOTTOM_LEFT, BOTTOM, 
BOTTOM_RIGHT} and passes the test.

But I've implemented the functionality to consider the direction of coverage
needed (which would be useful when user is scrolling in some direction or
zooming with some anchor point). This makes following sequence of coverage
directions in pyramid sequence
{RIGHT, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM, TOP, BOTTOM_LEFT, TOP_LEFT, LEFT},
giving following distances from viewport -

tile index [2, 3]   distance_to_visible = 274
tile index [1, 3]   distance_to_visible = 264
tile index [0, 3]   distance_to_visible = 264
tile index [3, 3]   distance_to_visible = 528
tile index [3, 0]   distance_to_visible = 264
tile index [3, 1]   distance_to_visible = 264
tile index [3, 2]   distance_to_visible = 274

which is breaking the test.

I need your opinion for - should we delete the checks for increasing or
decreasing distances?

[vmpstr, 2016-07-28 18:50:57]

On 2016/07/28 13:10:20, prashant.n wrote:
> vmpstr@, with latest patchset following tests are failing where increasing or
> decreasing distances are considered.
> 
> PictureLayerImplTest.TilingSetEvictionQueue
> TileManagerTilePriorityQueueTest.EvictionTilePriorityQueue
> TileManagerTilePriorityQueueTest.RasterTilePriorityQueue
> 
> For the test PictureLayerImplTest.TilingSetEvictionQueue, the manhattan
> distances to viewport are 
> 
> tile index [3, 3]   distance_to_visible = 528
> tile index [2, 3]   distance_to_visible = 274
> tile index [1, 3]   distance_to_visible = 264
> tile index [0, 3]   distance_to_visible = 264
> tile index [3, 0]   distance_to_visible = 264
> tile index [3, 1]   distance_to_visible = 264
> tile index [3, 2]   distance_to_visible = 274
> 
> when the spiral iterator considers the sequence of coverage directions in
pyamid
> sequence {RIGHT, TOP_RIGHT, TOP, TOP_LEFT, LEFT, BOTTOM_LEFT, BOTTOM, 
> BOTTOM_RIGHT} and passes the test.
> 
> But I've implemented the functionality to consider the direction of coverage
> needed (which would be useful when user is scrolling in some direction or
> zooming with some anchor point). This makes following sequence of coverage
> directions in pyramid sequence
> {RIGHT, BOTTOM_RIGHT, TOP_RIGHT, BOTTOM, TOP, BOTTOM_LEFT, TOP_LEFT, LEFT},
> giving following distances from viewport -
> 
> tile index [2, 3]   distance_to_visible = 274
> tile index [1, 3]   distance_to_visible = 264
> tile index [0, 3]   distance_to_visible = 264
> tile index [3, 3]   distance_to_visible = 528
> tile index [3, 0]   distance_to_visible = 264
> tile index [3, 1]   distance_to_visible = 264
> tile index [3, 2]   distance_to_visible = 274
> 
> which is breaking the test.
> 
> I need your opinion for - should we delete the checks for increasing or
> decreasing distances?

The idea of the spiral iterator is to keep mostly increasing distances except on
the corners of the spiral, hence the checks. I'm curious why you think the new
sequence is better?

[prashant.n, 2016-07-29 02:13:13]

> The idea of the spiral iterator is to keep mostly increasing distances except
on
> the corners of the spiral, hence the checks. I'm curious why you think the new
> sequence is better?

 TL  T  TR
  L  *   R    --->
 BL  B  BR

The spiral order {R, TR, T, TL, L, BL, B, BR} does not give better coverage when
direction of scrolling (or anchor of zoom is considered) and the layout of
tiling data would be

   x  0  1  2  3  4
  y.---------------
  0| 16 15 14 13 12
  1| 17  4  3  2 11
  2| 18  5  *  1 10
  3| 19  6  7  8  9
  4| 20 21 22 23 24

The pyramid sequence can yeild better iteration order, if the positions of its
inlined triangular sequences are properly considered. Suppose primary direction
for coverage is right, then it can have inclination either to top right or
bottom right. This inclination is input by secondary direction.

When user is scrolling in right direction (inclined to bottom right), then tiles
at right are most important and tiles at left are least important. In the above
example tile at 8 would be needed before tiles at 4, 5, 6. The relative
importance of tiles at different directions in this case is {R, BR, TR, B, T,
BL, TL, L}. (the main coverage direction can be deduced by x-velocity and
secondary direction can be deduced from y-velocity). The layout of tiling data
would be

   x  0  1  2  3  4
  y.---------------
  0| 21 19 18 17 13
  1| 22  7  5  3 11
  2| 23  8  *  1 10    --->
  3| 24  6  4  2  9
  4| 20 14 15 16 12

[prashant.n, 2016-07-29 02:27:09]

The newer implementation is spiral but with precedence.

[prashant.n, 2016-07-29 02:45:50]

TL  T  TR
  L  *   R
 BL  B  BR

where -

R = right
TR = top right
T = top
TL = top left
L = left
BL = bottom left
B = bottom
BR = bottom right

[prashant.n, 2016-07-29 03:05:44]

For the test PictureLayerImplTest.TilingSetEvictionQueue, the layout of tiling
for eviction order is given below. Note the precedences of triagular sequences
are {B, BR, R} as per this CL implementation.
  
   x  0  1  2  3
  y.------------
  0|  V  V  *  5
  1|  V  V  *  6      --->
  2|  *  *  *  7
  3|  3  2  1  4

V = viewport and is the ignore rect

If user is scrolling in right direction then tiles at 5, 6, 7 should be evicted
after tiles at 1, 2, 3, 4. Eventhough the manhattan distance for 4 is higher
than manhattan distance for 1, as per coverage direction precedence, tile at 1
should evicted before tile at 4. So in my opinion, checks for the distance
increasing or decreasing based on manhattan distance should be removed. May be
we should use level distance which is used in pyramid sequence. Distances from
viewport based on level distance is given below (tile size = 256). Now this will
always give increasing order of distances for spiral and decreasing order of
distances for reverse spiral.

   x   0   1   2   3
  y.----------------
  0|   V   V   0 256
  1|   V   V   0 256
  2|   0   0   0 256
  3| 256 256 256 256

(In separate patch, I'll be associating proper coverage directions as per user's
scroll direction and anchor point for zooming. crbug.com/629052. Currently
default coverage direction is {RIGHT, BOTTOM_RIGHT}.)

[prashant.n, 2016-08-01 21:20:06]

ping. vmpstr@ can you pls. comment on this?

[prashant.n, 2016-08-09 04:31:26]

vmpstr@, can you pls. review this further?

[vmpstr, 2016-08-09 18:55:59]

On 2016/07/29 02:13:13, prashant.n wrote:
> > The idea of the spiral iterator is to keep mostly increasing distances
except
> on
> > the corners of the spiral, hence the checks. I'm curious why you think the
new
> > sequence is better?
> 
>  TL  T  TR
>   L  *   R    --->
>  BL  B  BR
> 
> The spiral order {R, TR, T, TL, L, BL, B, BR} does not give better coverage
when
> direction of scrolling (or anchor of zoom is considered) and the layout of
> tiling data would be
> 
>    x  0  1  2  3  4
>   y.---------------
>   0| 16 15 14 13 12
>   1| 17  4  3  2 11
>   2| 18  5  *  1 10
>   3| 19  6  7  8  9
>   4| 20 21 22 23 24
> 
> The pyramid sequence can yeild better iteration order, if the positions of its
> inlined triangular sequences are properly considered. Suppose primary
direction
> for coverage is right, then it can have inclination either to top right or
> bottom right. This inclination is input by secondary direction.
> 
> When user is scrolling in right direction (inclined to bottom right), then
tiles
> at right are most important and tiles at left are least important. In the
above
> example tile at 8 would be needed before tiles at 4, 5, 6. The relative
> importance of tiles at different directions in this case is {R, BR, TR, B, T,
> BL, TL, L}. (the main coverage direction can be deduced by x-velocity and
> secondary direction can be deduced from y-velocity). The layout of tiling data
> would be
> 
>    x  0  1  2  3  4
>   y.---------------
>   0| 21 19 18 17 13
>   1| 22  7  5  3 11
>   2| 23  8  *  1 10    --->
>   3| 24  6  4  2  9
>   4| 20 14 15 16 12

I don't necessarily agree that this gives better coverage. Both approaches are
fairly arbitrary and we use several regions to enforce better behavior. That is,
when the user starts scrolling we generate a skewport, which is a region
projected in time in the direction of the scroll. Then we use the spiral
iterator to iterate this region in roughly increasing distance to viewport. That
region by itself is what defines the coverage we want. When it comes to the
spiral iterator, we want a simple, easy to reason, order in which that region
will be covered. I would claim that a simple spiral provides this. 

The intent of these patches is to consider the aspect ratios of the tiles when
maintaining the spiral iteration. It becomes harder to reason about the order of
the tiles, if given an arbitrary set of regions (viewport, skewport, soon border
rect, eventually rect), one has to figure out in which order within the region
the tiles are iterated. Mind you, I don't think this is bad. I just think this
is a bit too complicated to follow. Can we retain the ordering that we had
before? At least this way, we can land a patch that only considers the aspect
ratios. Later, if we measure a performance improvement, we can vary the
iteration order gradually to attain optimal results.

[prashant.n, 2016-08-10 01:11:41]

> I don't necessarily agree that this gives better coverage. Both approaches are
> fairly arbitrary and we use several regions to enforce better behavior. That
is,
> when the user starts scrolling we generate a skewport, which is a region
> projected in time in the direction of the scroll. Then we use the spiral
> iterator to iterate this region in roughly increasing distance to viewport.
That
> region by itself is what defines the coverage we want. When it comes to the
> spiral iterator, we want a simple, easy to reason, order in which that region
> will be covered. I would claim that a simple spiral provides this.

Basically the TilingSetRasterQueueAll is iterated (by means of Top() and Pop())
by the step of schedule tasks limit (i.e. 32). During fast scrolling or zooming,
it might get updated before it gets fully iterated. So in such case it would be
good if we keep coverage order properly. e.g. If user is scrolling fastly to
right direction, then tiles at left are least important. This is properly
ordered with coverage direction code. So IMO, it is definitely better than
simple spiral.

If it is not okay in this patch, I'll add another patch for the coverage
direction keeping the coverage direction simple as suggested by you.

[prashant.n, 2016-08-10 11:00:59]

The CQ bit was checked by prashant.n@samsung.com to run a CQ dry run

[commit-bot: I haz the power, 2016-08-10 11:01:28]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-10 11:01:31]

Your CL relies on deprecated CQ feature(s):
 * Specifying master names in CQ_INCLUDE_TRYBOTS part of description without
"master." prefix is deprecated:
     tryserver.blink
   For more details, see http://crbug.com/617627.

[commit-bot: I haz the power, 2016-08-10 11:03:43]

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

[commit-bot: I haz the power, 2016-08-10 11:03:45]

Dry run: Try jobs failed on following builders:
  linux_blink_rel on tryserver.blink (JOB_FAILED, no build URL)

[prashant.n, 2016-08-10 11:13:52]

Description was changed from

==========
cc: Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. This is used to
implement SpiralDifferenceIterator and ReverseSpiralDifferenceIterator.
The pyramid sequence takes width and height of the tile into
consideration, so that it gives better order of tiles over previous
version. This patch also adds support for move assignment and move
constructor, so that objects can be in-place constructed and moved to
desired container.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
cc: Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. The pyramid sequence
iterates level by level, i.e. inner level to outer level and vice
versa. This is used to implement SpiralDifferenceIterator and
ReverseSpiralDifferenceIterator. The pyramid sequence takes width and
height of the tile into consideration, giving better order of tiles
over previous version. This patch also adds support for move assignment
and move constructor, so that objects can be in-place constructed and
moved to desired container.

This patch also adds test for the tiling smaller than tile size and
center rect not intersecting to tiling rect.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

[vmpstr, 2016-08-10 20:45:41]

On 2016/08/10 01:11:41, prashant.n wrote:
> > I don't necessarily agree that this gives better coverage. Both approaches
are
> > fairly arbitrary and we use several regions to enforce better behavior. That
> is,
> > when the user starts scrolling we generate a skewport, which is a region
> > projected in time in the direction of the scroll. Then we use the spiral
> > iterator to iterate this region in roughly increasing distance to viewport.
> That
> > region by itself is what defines the coverage we want. When it comes to the
> > spiral iterator, we want a simple, easy to reason, order in which that
region
> > will be covered. I would claim that a simple spiral provides this.
> 
> Basically the TilingSetRasterQueueAll is iterated (by means of Top() and
Pop())
> by the step of schedule tasks limit (i.e. 32). During fast scrolling or
zooming,
> it might get updated before it gets fully iterated. So in such case it would
be
> good if we keep coverage order properly. e.g. If user is scrolling fastly to
> right direction, then tiles at left are least important. This is properly
> ordered with coverage direction code. So IMO, it is definitely better than
> simple spiral.
> 
> If it is not okay in this patch, I'll add another patch for the coverage
> direction keeping the coverage direction simple as suggested by you.

If the user is scrolling to the right, then the skewport would start at the
viewport and extend to the right, so a simple spiral over the skewport still
gives you correct tiles. Conversely, if the user is scrolling to the left, then
this iteration order is worse than a simple spiral (although we would calculate
the skewport to be only to the left).

Yeah I think it would be nice if we have a patch that doesn't change behavior
other than considering aspect ratio.

[prashant.n, 2016-08-11 02:11:39]

> Yeah I think it would be nice if we have a patch that doesn't change behavior
> other than considering aspect ratio.

Yes. The patchset 44 does the simple spiral coverage wihtout changing behavior
compared to previous implementation.

PTAL.

[prashant.n, 2016-08-12 01:38:15]

> If the user is scrolling to the right, then the skewport would start at the
> viewport and extend to the right, so a simple spiral over the skewport still
> gives you correct tiles. Conversely, if the user is scrolling to the left,
then
> this iteration order is worse than a simple spiral (although we would
calculate
> the skewport to be only to the left).
> 

Yes. With coverage directions considered as proposed in the patch, we should
have complete implementation where directions are deduced from x-velocity and
y-velocity. Otherwise as pointed by you, just providing default implementation
for RIGHT direction would work better only in case of user is scrolling right,
in all other directions it would work worse than spiral iteration. So I'll
submit full implementation as a separate patch.

Meanwhile current patchset 44, does consider only the aspect ratio of tile size
additionally over ToT.

[vmpstr, 2016-08-16 00:40:48]

This code seems too complicated for what we want.. Can we step back and come up
with a solution that addresses only the problem we have? Can we switch to a
document where we can iterate on the design quicker?

As an example, the Interval class (as far as I can tell) is a pair of ints and
the ability to iterate from one int to the other one... A whole class for that
seems hardly worth it. I admit that I might be missing some usefulness in it,
but maybe that's part of the problem.

Can we remove all of the code that we aren't currently using and simplify the
rest of the code in as little code as possible?

To begin though, can you write up a small doc describing both the problem and
the solution you're proposing? We can iterate quickly on the doc and come up
with a design that we can both agree on.

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
File cc/base/pyramid_sequence.h (right):

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:16: // This class provides interating mechanism for
the mathematical interval
iterating

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:22: // for (Interval it(FORWARD, 3, 4, 0, 6, false),
it; ++it)
I'm not sure what this example is demonstrating, can you elaborate on the
inputs?

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:31: //   FORWARD            [2, 4]
Can we always have just one direction (ie FORWARD), and just iterate the range
using some sort of a reverse iterator if we need to go in the opposite
direction?

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:33: //   DIAGONAL_FORWARD   [4, 4]
Why is [4, 4] a valid interval? It seems to not encompass the initial given
sequence.

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:39: DIAGONAL_BACKWARD
If these are not currently used, please remove them.

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:49: bool reverse_order);
As I mentioned in my previous comment, I don't understand why you have FORWARD
and BACKWARD as well as reverse_order bool. That seems like too many controls.

https://codereview.chromium.org/2067213002/diff/860001/cc/base/pyramid_sequen...
cc/base/pyramid_sequence.h:98: };
As far as I understand it, this class is just a pair of ints with operator++
that essentially just iterates from one int to the other one...

[prashant.n, 2017-02-21 10:37:01]

Description was changed from

==========
cc: Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. The pyramid sequence
iterates level by level, i.e. inner level to outer level and vice
versa. This is used to implement SpiralDifferenceIterator and
ReverseSpiralDifferenceIterator. The pyramid sequence takes width and
height of the tile into consideration, giving better order of tiles
over previous version. This patch also adds support for move assignment
and move constructor, so that objects can be in-place constructed and
moved to desired container.

This patch also adds test for the tiling smaller than tile size and
center rect not intersecting to tiling rect.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel
==========

to

==========
cc: Implement tile iteration order based on pyramid sequence.

This patch implements pyramid sequence for getting tile indices from
closer to farther or farther to closer fashion. The pyramid sequence
iterates level by level, i.e. inner level to outer level and vice
versa. This is used to implement SpiralDifferenceIterator and
ReverseSpiralDifferenceIterator. The pyramid sequence takes width and
height of the tile into consideration, giving better order of tiles
over previous version. This patch also adds support for move assignment
and move constructor, so that objects can be in-place constructed and
moved to desired container.

This patch also adds test for the tiling smaller than tile size and
center rect not intersecting to tiling rect.

BUG=613695
TESTS=TilingDataTest.SpiralDifferenceIteratorWideTiles*
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel;tryserver.blink:linux_blink_rel
==========