cc: Use a ListContainer for DisplayItemList to reduce allocations.

cc: Use a ListContainer for DisplayItemList to reduce allocations.

Currently every DisplayItem is malloced/freed individually. Follow the
pattern used for DrawQuads instead, using ListContainer to allocate
log(n) times instead of once for each item. This replaces each
DisplayFooItem::Create(...) with a default constructor and a
DisplayFooItem::SetNew(...) that must be called on newly constructed
items before they are used.

This patch changes the time to do UpdateLayers (after making
gfx::ImageSkiaReps immutable cuz they dominate times for now) for a
single tab loading spinner from .174ms to .167ms on a linux x620,
giving a 4% reduction in frame record time. I used a mean of 3000
samples in each run to reduce noise.

R=ajuma, enne
BUG=466426
Committed: https://crrev.com/f15802914bd7a8f5ea8c4d7893e9c79450804714
Cr-Commit-Position: refs/heads/master@{#328797}

[danakj, 2015-05-06 01:01:45]

+pdr/chrishtr fyi, this should help blink perf numbers a bit too

[chrishtr, 2015-05-06 03:51:07]

chrishtr@chromium.org changed reviewers:
+ chrishtr@chromium.org

[chrishtr, 2015-05-06 03:51:08]

Cool. Presumably the Blink-side DisplayItemList class will also benefit from
this.

[chrishtr, 2015-05-06 03:55:32]

Filed crbug.com/484943.

[jbroman, 2015-05-06 04:09:12]

Heh, this CL totally obsoletes the CL I had been working on for the past 2 days
or so (but had trouble getting measurements of). :P

[jbroman, 2015-05-06 04:35:23]

One comment, though: for phase 1, we are presently only using the picture, so
why bother writing it to the vector (even efficiently) at all when we can just
replay it to the cached picture right away?

[ajuma, 2015-05-06 15:49:48]

https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
File cc/resources/display_item_list.cc (right):

https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
cc/resources/display_item_list.cc:113: for (DisplayItem* item : items_) {
With this post-processing approach, the ListContainer will need to have enough
capacity for the entire list of items even when we're not retaining individual
items. If this is a lot of memory, an alternative would be to process after
every item (or after every, say, 100 items).

[chrishtr, 2015-05-06 16:54:14]

On 2015/05/06 at 04:35:23, jbroman wrote:
> One comment, though: for phase 1, we are presently only using the picture, so
why bother writing it to the vector (even efficiently) at all when we can just
replay it to the cached picture right away?

Good point. Dana?

[chrishtr, 2015-05-06 17:01:33]

On 2015/05/06 at 16:54:14, chrishtr wrote:
> On 2015/05/06 at 04:35:23, jbroman wrote:
> > One comment, though: for phase 1, we are presently only using the picture,
so why bother writing it to the vector (even efficiently) at all when we can
just replay it to the cached picture right away?
> 
> Good point. Dana?

I see, there is a malloc followed immediately by a free for this case, so we
still get the O(n) -> O(log n) win.

[danakj, 2015-05-06 17:03:32]

On Wed, May 6, 2015 at 9:54 AM, <chrishtr@chromium.org> wrote:

> On 2015/05/06 at 04:35:23, jbroman wrote:
>
>> One comment, though: for phase 1, we are presently only using the
>> picture, so
>>
> why bother writing it to the vector (even efficiently) at all when we can
> just
> replay it to the cached picture right away?
>
> Good point. Dana?
>

It's true, though this is still turning O(n) allocs/frees into O(logn)
allocs and 1 free. Since this creates and returns a pointer that must be
filled in, the DisplayItemList has to own/store that pointer somewhere
until ProcessAppendedItems is called.

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

[danakj, 2015-05-06 22:50:06]

Patchset #2 (id:20001) has been deleted

[danakj, 2015-05-06 22:50:50]

Patchset #2 (id:40001) has been deleted

[danakj, 2015-05-06 22:56:59]

On 2015/05/06 15:49:48, ajuma wrote:
>
https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
> File cc/resources/display_item_list.cc (right):
> 
>
https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
> cc/resources/display_item_list.cc:113: for (DisplayItem* item : items_) {
> With this post-processing approach, the ListContainer will need to have enough
> capacity for the entire list of items even when we're not retaining individual
> items. If this is a lot of memory, an alternative would be to process after
> every item (or after every, say, 100 items).

OK We could do something like this. Then we'd get log(100)*n/100 allocations.
That's 0.07*n allocations. That sounds better than n allocations still, and
doesn't affect ui compositor at all for now.

[ajuma, 2015-05-06 23:21:36]

On 2015/05/06 22:56:59, danakj wrote:
> On 2015/05/06 15:49:48, ajuma wrote:
> >
>
https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
> > File cc/resources/display_item_list.cc (right):
> > 
> >
>
https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
> > cc/resources/display_item_list.cc:113: for (DisplayItem* item : items_) {
> > With this post-processing approach, the ListContainer will need to have
enough
> > capacity for the entire list of items even when we're not retaining
individual
> > items. If this is a lot of memory, an alternative would be to process after
> > every item (or after every, say, 100 items).
> 
> OK We could do something like this. Then we'd get log(100)*n/100 allocations.
> That's 0.07*n allocations. That sounds better than n allocations still, and
> doesn't affect ui compositor at all for now.

And with an initial ListContainer capacity of 100 (which the patch currently
does), we'd avoid the log(100) factor, so we'd just have 0.01*n allocations.

[danakj, 2015-05-06 23:24:29]

On Wed, May 6, 2015 at 4:21 PM, <ajuma@chromium.org> wrote:

> On 2015/05/06 22:56:59, danakj wrote:
>
>> On 2015/05/06 15:49:48, ajuma wrote:
>> >
>>
>
>
>
https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
>
>> > File cc/resources/display_item_list.cc (right):
>> >
>> >
>>
>
>
>
https://codereview.chromium.org/1123983002/diff/1/cc/resources/display_item_l...
>
>> > cc/resources/display_item_list.cc:113: for (DisplayItem* item : items_)
>> {
>> > With this post-processing approach, the ListContainer will need to have
>>
> enough
>
>> > capacity for the entire list of items even when we're not retaining
>>
> individual
>
>> > items. If this is a lot of memory, an alternative would be to process
>> after
>> > every item (or after every, say, 100 items).
>>
>
>  OK We could do something like this. Then we'd get log(100)*n/100
>> allocations.
>> That's 0.07*n allocations. That sounds better than n allocations still,
>> and
>> doesn't affect ui compositor at all for now.
>>
>
> And with an initial ListContainer capacity of 100 (which the patch
> currently
> does), we'd avoid the log(100) factor, so we'd just have 0.01*n
> allocations.
>

Oh ya, word. Patch incoming.

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

[danakj, 2015-05-06 23:29:06]

PTAL

[ajuma, 2015-05-07 13:23:31]

lgtm!

[danakj, 2015-05-07 17:48:58]

The CQ bit was checked by danakj@chromium.org

[commit-bot: I haz the power, 2015-05-07 17:52:18]

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

[commit-bot: I haz the power, 2015-05-07 18:26:24]

Committed patchset #4 (id:100001)

[commit-bot: I haz the power, 2015-05-07 18:27:09]

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