nsIFrame::BuildDisplayList() is heavy

[Thinker K.F. Li]

I am doing profiling for several Apps on b2g, and have found near 1x% ~
20% of CPU time when scrolling are spent on building display list. So,
I think we can use cache for display lists to save time of creating the
same display items repeatedly.

I just have done some studies, and have a rough idea. My idea is
attaching the caches with frames. When a frame is
MarkIntrinsicWidthsDirty()ed, the attached cache is deleted if any. For
the frames that their parents are MarkIntrinsicWidthsDirty()ed for last
reflowing, but not themself, the results of their BuildDisplayList() are
kept in the cache. I guess most animation will modify the same set of
subtrees repeatedly. So, we can save time for building display lists.

Feedback is welcomed!

--
Sinker
--
天教懶漫帶疏狂

[matt.w...@gmail.com]

Hi Thinker

Gal and I were discussing this same problem last week, and decided on the same solution.

The main problem is that display item positions are relative to the screen (or the nearest transformed ancestor) so they change when we scroll. This means we'd have to invalidate the cache for all scrolled frames, or modify the cached items.

What we decided on instead was to make the scroll root a 'reference frame' so that all display items below it have coordinates relative to that instead of the screen. This should mean that we no longer have to modify the display items when we scroll.

I was planning on working on this in about 2 weeks, once I've finished up with my current set of graphics bugs. I'm happy to discuss this further though if you want to get started sooner than that.

The rest of the proposal looks good, but you'll at least need to invalidate the cached items when we get a style change. Some items (like tables) will require special handling too.

- Matt

[L. David Baron]

On Wednesday 2013-08-21 20:52 +0800, Thinker K.F. Li wrote:
> I am doing profiling for several Apps on b2g, and have found near 1x% ~
> 20% of CPU time when scrolling are spent on building display list. So,
> I think we can use cache for display lists to save time of creating the
> same display items repeatedly.
>
> I just have done some studies, and have a rough idea. My idea is
> attaching the caches with frames.

Which items would you cache, on which frames, and for how long?

> When a frame is
> MarkIntrinsicWidthsDirty()ed, the attached cache is deleted if any. For
> the frames that their parents are MarkIntrinsicWidthsDirty()ed for last
> reflowing, but not themself, the results of their BuildDisplayList() are
> kept in the cache. I guess most animation will modify the same set of
> subtrees repeatedly. So, we can save time for building display lists.

So clearing caches in MarkIntrinsicWidthsDirty isn't sufficient (at
least due to style changes that either change rendering only, or
change layout without changing intrinsic widths), and it also
doesn't seem like the right point, given the patterns in which it is
called (see PresShell::FrameNeedsReflow) and the overall
architecture (MarkIntrinsicWidthsDirty is really about intrinsic
width changes, which aren't especially related to what you care
about here, although there's a correlation).

I think I'd be more interested in solutions that are more specific
to the problem of scrolling, such as updating an existing display
list specifically for scrolling (as mattwoodrow mentioned), or
perhaps (though this is less an area where I know what's going on)
doing scrolling even further down the pipeline, using layers that
are drawn with extra area that we are scrolling towards.

-David

--
𝄞 L. David Baron http://dbaron.org/ 𝄂
𝄢 Mozilla https://www.mozilla.org/ 𝄂
Before I built a wall I'd ask to know
What I was walling in or walling out,
And to whom I was like to give offense.
- Robert Frost, Mending Wall (1914)

[Thinker K.F. Li]

After a discussion with Kan-Ru, I get more about the problem itself.
Since the positions of all display items in a nsIScrollableFrame are
relative to nsIScrollableFrame itself. By keeping display itmes in the
cache and applying a translation (shift) to the gfxContext before
calling paint() on display items, we don't need to change the display
items in the cache. Of course, invalidate regions should be translated
too.

How do you think?

--
Sinker
--
天教懶漫帶疏狂

[Kan-Ru Chen (陳侃如)]

Hi Matt,

If that approach looks reasonable to you, I and Thinker will start
working on that.

Kanru

thi...@codemud.net (Thinker K.F. Li) writes:

> After a discussion with Kan-Ru, I get more about the problem itself.
> Since the positions of all display items in a nsIScrollableFrame are
> relative to nsIScrollableFrame itself. By keeping display itmes in the
> cache and applying a translation (shift) to the gfxContext before
> calling paint() on display items, we don't need to change the display
> items in the cache. Of course, invalidate regions should be translated
> too.
>
> How do you think?
>
> matt.w...@gmail.com writes:
>

[Robert O'Callahan]

On Thu, Aug 22, 2013 at 10:34 PM, Thinker K.F. Li <thi...@codemud.net>wrote:

> After a discussion with Kan-Ru, I get more about the problem itself.
> Since the positions of all display items in a nsIScrollableFrame are
> relative to nsIScrollableFrame itself. By keeping display itmes in the
> cache and applying a translation (shift) to the gfxContext before
> calling paint() on display items, we don't need to change the display
> items in the cache. Of course, invalidate regions should be translated
> too.
>

The offset to apply to each display item would have to be stored somewhere,
and then those offsets will all have to be updated.

It seems simpler and more efficient to me to make the display items be
relative to their active scrolled root, then nothing will have to be
updated. Matt can explain more of the details of what we think needs to be
done.

Rob
--
Jtehsauts tshaei dS,o n" Wohfy Mdaon yhoaus eanuttehrotraiitny eovni
le atrhtohu gthot sf oirng iyvoeu rs ihnesa.r"t sS?o Whhei csha iids teoa
stiheer :p atroa lsyazye,d 'mYaonu,r "sGients uapr,e tfaokreg iyvoeunr,
'm aotr atnod sgaoy ,h o'mGee.t" uTph eann dt hwea lmka'n? gBoutt uIp
waanndt wyeonut thoo mken.o w *
*

[Thinker K.F. Li]

"Robert O'Callahan" <rob...@ocallahan.org> writes:

> On Thu, Aug 22, 2013 at 10:34 PM, Thinker K.F. Li <thi...@codemud.net>wrote:
>
>> After a discussion with Kan-Ru, I get more about the problem itself.
>> Since the positions of all display items in a nsIScrollableFrame are
>> relative to nsIScrollableFrame itself. By keeping display itmes in the
>> cache and applying a translation (shift) to the gfxContext before
>> calling paint() on display items, we don't need to change the display
>> items in the cache. Of course, invalidate regions should be translated
>> too.
>>
>
> The offset to apply to each display item would have to be stored somewhere,
> and then those offsets will all have to be updated.
>
> It seems simpler and more efficient to me to make the display items be
> relative to their active scrolled root, then nothing will have to be
> updated. Matt can explain more of the details of what we think needs to be
> done.

It seems very similar to what I told. I would very like to know the
details you mentioned.

--
Sinker
--
天教懶漫帶疏狂

[Matt Woodrow]

I think we definitely want to make scrolled items have coordinates
relative to their scrolled root.

The problem with just doing this, and applying a transform to the
context when drawing them is that it makes visibility calcuations much
harder.

nsDisplayList::ComputeVisibility assumes that all child items are in the
same coordinate space, and changing this would be difficult.

I think we instead need to make sure that all scrolled items are within
a 'wrapper' item and have that as the point where we change coordinate
systems. This is what we are currently doing for nsDisplayTransform.

Things that need to be done:

Make sure we always build nsDisplayScrollLayer
(http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsGfxScrollFrame.cpp#2310)
for active scroll frames, instead of only when we have async scrolling.

Convert nsDisplayScrollLayer to be inherit directly from nsDisplayItem
instead of nsDisplayWrapList. nsDisplayWrapList implement
GetSameCoordinateSystemChildren
(http://mxr.mozilla.org/mozilla-central/source/layout/base/nsDisplayList.h#2391)
which we *don't* want. We just want to implement GetChildren() instead.

Make nsDisplayScrollLayer::HitTest, BuildLayer, ComputeVisibility etc
handle the change in coordinate space. nsDisplayTransform does this by
adding a translate into the computed matrix in
nsDisplayTransform::GetTransform. I think we'll just want to manually
shift the visible rect/hit test rect before passing it on to our children.

Make children of the scrolled content choose the scrolled root as their
reference point. We currently do this calculation in two places:
http://mxr.mozilla.org/mozilla-central/source/layout/base/nsDisplayList.h#195,
and
http://mxr.mozilla.org/mozilla-central/source/layout/base/nsDisplayList.h#519.
Note that these have special handling for transforms, and we need to add
the equivalent for scrolled roots.

This function should be what decides if a scroll frame should be a
reference frame for its children:
http://mxr.mozilla.org/mozilla-central/source/layout/base/nsLayoutUtils.cpp#1079

Hopefully that helps! Let me know if you have any more questions :)

- Matt

On 23/08/13 1:57 AM, Thinker K.F. Li wrote:
> "Robert O'Callahan" <rob...@ocallahan.org> writes:
>

>> On Thu, Aug 22, 2013 at 10:34 PM, Thinker K.F. Li <thi...@codemud.net>wrote:
>>
>>> After a discussion with Kan-Ru, I get more about the problem itself.
>>> Since the positions of all display items in a nsIScrollableFrame are
>>> relative to nsIScrollableFrame itself. By keeping display itmes in the
>>> cache and applying a translation (shift) to the gfxContext before
>>> calling paint() on display items, we don't need to change the display
>>> items in the cache. Of course, invalidate regions should be translated
>>> too.
>>>
>> The offset to apply to each display item would have to be stored somewhere,
>> and then those offsets will all have to be updated.
>>
>> It seems simpler and more efficient to me to make the display items be
>> relative to their active scrolled root, then nothing will have to be
>> updated. Matt can explain more of the details of what we think needs to be
>> done.

[Matt Woodrow]

Andreas also filed bug 904328, which has a patch that handles the last
few items on the list already.

- Matt

>>> On Thu, Aug 22, 2013 at 10:34 PM, Thinker K.F. Li <thi...@codemud.net>wrote:
>>>
>>>> After a discussion with Kan-Ru, I get more about the problem itself.
>>>> Since the positions of all display items in a nsIScrollableFrame are
>>>> relative to nsIScrollableFrame itself. By keeping display itmes in the
>>>> cache and applying a translation (shift) to the gfxContext before
>>>> calling paint() on display items, we don't need to change the display
>>>> items in the cache. Of course, invalidate regions should be translated
>>>> too.
>>>>
>>> The offset to apply to each display item would have to be stored somewhere,
>>> and then those offsets will all have to be updated.
>>>
>>> It seems simpler and more efficient to me to make the display items be
>>> relative to their active scrolled root, then nothing will have to be
>>> updated. Matt can explain more of the details of what we think needs to be
>>> done.

>> It seems very similar to what I told. I would very like to know the
>> details you mentioned.
>>
>

> _______________________________________________
> dev-tech-layout mailing list
> dev-tec...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-tech-layout