cc: Implement RemoveLast for DisplayItemList.

cc: Implement RemoveLast for DisplayItemList.

Blink currently does this operation on its display item lists to remove
superfluous begin/end pairs. To port Blink's current display item list
operations, such an operation is required.

This is not possible when in "cached picture" mode, but Blink currently only
does this on the unmerged list (in blink::DisplayItemList::add), so this should
be sufficient (if unfortunately asymmetric).

BUG=484943
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

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

[jbroman, 2015-06-02 19:36:18]

jbroman@chromium.org changed reviewers:
+ danakj@chromium.org

[jbroman, 2015-06-02 19:36:19]

Unit tests are a little sparse (ask for more if this doesn't satisfy you), and
the implementation isn't super-hyper-efficient (in particular, there's a
possibility of thrashing around an allocation boundary), but it's simple and
probably sufficient. Premature optimization, and all that.

WDYT?

https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
File cc/quads/list_container_unittest.cc (right):

https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
cc/quads/list_container_unittest.cc:672: TEST(ListContainerTest, RemoveLast) {
Note that this will probably collide with a Samsung contributor's effort to move
this unit test out of cc/quads, but it should be pretty easy to resolve the
merge conflict, whoever it hits.

[danakj, 2015-06-02 20:04:32]

I know the answer will be no but I've gotta ask: can we make blink not add items
to the list that it's going to remove? Avoiding work is always better than
cleaning up wasted work.

https://codereview.chromium.org/1163803003/diff/20001/cc/base/list_container.cc
File cc/base/list_container.cc (right):

https://codereview.chromium.org/1163803003/diff/20001/cc/base/list_container....
cc/base/list_container.cc:134: DeallocateLastList();
Is it possible to avoid this deallocate and just leave the empty last list
around with size 0?

This could lead to a huge performance cliff, and it'll be rare/random/hard to
reproduce.

https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
File cc/quads/list_container_unittest.cc (right):

https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
cc/quads/list_container_unittest.cc:688: // We should also be okay to remove the
last multiple times, as long as there
Can you add a test where you append one past a new allocation, and then remove
it, and verify iterators work begin/end/rbegin/rend/etc. Then append over the
boundary again and verify the same thing?

[jbroman, 2015-06-02 20:31:51]

On 2015/06/02 20:04:32, danakj wrote:
> I know the answer will be no but I've gotta ask: can we make blink not add
items
> to the list that it's going to remove? Avoiding work is always better than
> cleaning up wasted work.

I haven't investigated why these happen, but it's probably the case that we
don't know until we descend into a subtree whether anything will be drawn. It's
certainly correct to leave the begin/end pair there, but I assume this
optimization was added for a reason. We could buffer them in Blink, but that
seems no better.

>
https://codereview.chromium.org/1163803003/diff/20001/cc/base/list_container.cc
> File cc/base/list_container.cc (right):
> 
>
https://codereview.chromium.org/1163803003/diff/20001/cc/base/list_container....
> cc/base/list_container.cc:134: DeallocateLastList();
> Is it possible to avoid this deallocate and just leave the empty last list
> around with size 0?

The trouble is that we can call RemoveLast several times in a row (potentially
through several or all inner lists, in the worst case). Not deallocating the
list means that we won't have an accurate last_list_ pointer when we try to
append again (we'll end up attaching things to the last list, leaving several
blank lists in the middle).

> This could lead to a huge performance cliff, and it'll be rare/random/hard to
> reproduce.

Potentially yes. This seemed simplest. It's possible to avoid this, but it means
complicating the adding logic to have a distinction between the last list that
exists and the last list with items in it. Not too bad, but at risk of being
premature optimization. WDYT?

>
https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
> File cc/quads/list_container_unittest.cc (right):
> 
>
https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
> cc/quads/list_container_unittest.cc:688: // We should also be okay to remove
the
> last multiple times, as long as there
> Can you add a test where you append one past a new allocation, and then remove
> it, and verify iterators work begin/end/rbegin/rend/etc. Then append over the
> boundary again and verify the same thing?

I'm not entirely clear here. Does this class have a general promise that
iterators remain valid across mutations? If so, will add such a test.

[danakj, 2015-06-02 20:45:41]

On Tue, Jun 2, 2015 at 1:31 PM, <jbroman@chromium.org> wrote:

> On 2015/06/02 20:04:32, danakj wrote:
>
>> I know the answer will be no but I've gotta ask: can we make blink not add
>>
> items
>
>> to the list that it's going to remove? Avoiding work is always better than
>> cleaning up wasted work.
>>
>
> I haven't investigated why these happen, but it's probably the case that we
> don't know until we descend into a subtree whether anything will be drawn.
> It's
> certainly correct to leave the begin/end pair there, but I assume this
> optimization was added for a reason. We could buffer them in Blink, but
> that
> seems no better.


It's possible blink could cache a bool "should begin" and lazily do the
work of adding a begin once it's actually needed. I am not familiar with
the blink code at all to say so, but that seems like it would be
simpler/better if it's possible.


>
>
>
>
>
https://codereview.chromium.org/1163803003/diff/20001/cc/base/list_container.cc
>
>> File cc/base/list_container.cc (right):
>>
>
>
>
>
https://codereview.chromium.org/1163803003/diff/20001/cc/base/list_container....
>
>> cc/base/list_container.cc:134: DeallocateLastList();
>> Is it possible to avoid this deallocate and just leave the empty last list
>> around with size 0?
>>
>
> The trouble is that we can call RemoveLast several times in a row
> (potentially
> through several or all inner lists, in the worst case). Not deallocating
> the
> list means that we won't have an accurate last_list_ pointer when we try to
> append again (we'll end up attaching things to the last list, leaving
> several
> blank lists in the middle).
>
>  This could lead to a huge performance cliff, and it'll be
>> rare/random/hard to
>> reproduce.
>>
>
> Potentially yes. This seemed simplest. It's possible to avoid this, but it
> means
> complicating the adding logic to have a distinction between the last list
> that
> exists and the last list with items in it. Not too bad, but at risk of
> being
> premature optimization. WDYT?


I'd prefer to keep O(n) malloc possibilities out of this class. I think
it's worth dealing with this properly if we need it in the API.


>
>
>
>
>
https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
>
>> File cc/quads/list_container_unittest.cc (right):
>>
>
>
>
>
https://codereview.chromium.org/1163803003/diff/20001/cc/quads/list_container...
>
>> cc/quads/list_container_unittest.cc:688: // We should also be okay to
>> remove
>>
> the
>
>> last multiple times, as long as there
>> Can you add a test where you append one past a new allocation, and then
>> remove
>> it, and verify iterators work begin/end/rbegin/rend/etc. Then append over
>> the
>> boundary again and verify the same thing?
>>
>
> I'm not entirely clear here. Does this class have a general promise that
> iterators remain valid across mutations? If so, will add such a test.
>

Not that they remain valid across mutations, but that you can iterate
correctly after mutating (rbegin is actually the last thing, and ++ goes to
the right place still etc). There's some similar tests in there already for
when we cross allocation boundaries.


>
> https://codereview.chromium.org/1163803003/
>

To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[jbroman, 2015-06-03 19:33:42]

On 2015/06/02 20:45:41, danakj wrote:
> It's possible blink could cache a bool "should begin" and lazily do the
> work of adding a begin once it's actually needed. I am not familiar with
> the blink code at all to say so, but that seems like it would be
> simpler/better if it's possible.

It's pretty non-local. I think the problem is cases where one element clips
and some descendant element may or may not paint. You'd have to buffer up
the contents of the begin display item, or the information required to
compute it (i.e. recorder construction arguments).

But we already have a buffer for display item contents, so it seemed
reasonable to use it (and also minimize the scope of the Blink change).

The alternative would probably look something like recorders adding
themselves to a stack which would be flushed to the display item list
when a content-drawing display item was found. Seemed more complicated.

> I'd prefer to keep O(n) malloc possibilities out of this class. I think
> it's worth dealing with this properly if we need it in the API.

If we only deallocate when we have another free inner list, this should
prevent the O(n) behaviour you're afraid of.

> Not that they remain valid across mutations, but that you can iterate
> correctly after mutating (rbegin is actually the last thing, and ++ goes to
> the right place still etc). There's some similar tests in there already for
> when we cross allocation boundaries.

Added ListContainerTest.RemoveLastIteration. Is this what you are looking for?

[danakj, 2015-06-03 23:21:23]

LGTM

https://codereview.chromium.org/1163803003/diff/100001/cc/base/list_container.cc
File cc/base/list_container.cc (right):

https://codereview.chromium.org/1163803003/diff/100001/cc/base/list_container...
cc/base/list_container.cc:137: last_list_ = storage_[0];
nit: storage_[last_list_index_]

https://codereview.chromium.org/1163803003/diff/100001/cc/base/list_container...
cc/base/list_container.cc:210: // storage_[last_list_index_]
can you make this a sentence?

[jbroman, 2015-06-04 00:00:47]

https://codereview.chromium.org/1163803003/diff/100001/cc/base/list_container.cc
File cc/base/list_container.cc (right):

https://codereview.chromium.org/1163803003/diff/100001/cc/base/list_container...
cc/base/list_container.cc:137: last_list_ = storage_[0];
On 2015/06/03 23:21:23, danakj wrote:
> nit: storage_[last_list_index_]

Done.

https://codereview.chromium.org/1163803003/diff/100001/cc/base/list_container...
cc/base/list_container.cc:210: // storage_[last_list_index_]
On 2015/06/03 23:21:23, danakj wrote:
> can you make this a sentence?

Done.

[jbroman, 2015-06-04 00:00:51]

The CQ bit was checked by jbroman@chromium.org

[jbroman, 2015-06-04 00:00:51]

The patchset sent to the CQ was uploaded after l-g-t-m from danakj@chromium.org
Link to the patchset: https://codereview.chromium.org/1163803003/#ps120001
(title: "danakj comments")

[commit-bot: I haz the power, 2015-06-04 00:02:06]

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

[commit-bot: I haz the power, 2015-06-04 00:48:58]

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

[commit-bot: I haz the power, 2015-06-04 00:48:59]

Try jobs failed on following builders:
  linux_blink_rel on tryserver.blink (JOB_FAILED,
http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/6...)

[jbroman, 2015-06-05 15:11:33]

The CQ bit was checked by jbroman@chromium.org

[commit-bot: I haz the power, 2015-06-05 15:12:19]

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

[commit-bot: I haz the power, 2015-06-05 17:36:05]

Committed patchset #7 (id:120001)

[commit-bot: I haz the power, 2015-06-05 18:03:23]

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