928403 - nsFrameConstructorState::ProcessFrameInsertions is slow

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Olli Pettay [:smaug][[e-mail]]]

When opening the treeview in Gecko profiler and resizing the window, 
nsLayoutUtils::DoCompareTreePosition(nsIFrame*,nsIFrame*...) takes over 85% of the time.
Under it GetPlaceholderFrameFor is about 50%.

I'm testing a simple placeholder cache if it helps with this case.
If not, perhaps we should keep placeholder member variable in frames?

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

The cache doesn't seem to help.

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

ok, so the problem is nsFrameConstructorState::ProcessFrameInsertions.
We end up calling CompareTreePosition a lot, and that calls FillAncestors.
Simple fix is to cache the result of FillAncestors for firstNewFrame,
but for other things...
One possibility would be to not do the linear search but binary or tree search or so when
going trough childList.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

patch coming

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

Attachment: wip

https://tbpl.mozilla.org/?tree=Try&rev=1cdf6fa27f23

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

And the testcase is to create a profile using gecko profiler and alt+click the root arrow
(that expands the whole tree-view).

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Bug 928645 is annoying, but I think we should fix this even before that.
Or in other words, I don't have cycles to look at bug 928645.

Comment 7

[Olli Pettay [:smaug][[e-mail]]]

Attachment: patch

https://tbpl.mozilla.org/?tree=Try&rev=7795afa9001c

The hack for the old behavior isn't pretty, but easy to remove once
the other bug is fixed.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 819356 [details] [diff] [review]
patch

Actually, since the code is originally from bug 217604, perhaps you
roc could review.
(I'm sure you remember what you did 10 years ago ;) )

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 819356 [details] [diff] [review]
patch

Review of attachment 819356 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/base/nsCSSFrameConstructor.cpp
@@ +1270,5 @@
> +      nsIFrame* insertionPoint = nullptr;
> +      int32_t imin = 0;
> +      int32_t imax = children.Length() - 1;
> +      int32_t imid = 0;
> +      while (imax >= imin) {

I think it's a little clear if imax is exclusive; so set imax to children.Length() and make appropriate changes below.

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

There was a reason why it was imax, not max ;)
But ok.

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

Attachment: v2

This way then.
(to me this is harder to understand since we don't handle
boundary points the same way anymore. [min, max] vs [min, max) )

Comment 12

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 820294 [details] [diff] [review]
v2

Review of attachment 820294 [details] [diff] [review]:
-----------------------------------------------------------------

::: layout/base/nsCSSFrameConstructor.cpp
@@ +1271,5 @@
> +      int32_t imin = 0;
> +      int32_t imid = 0;
> +      int32_t max = children.Length();
> +      while (max > imin) {
> +        imid = imin + ((max - imin) / 2);

declare imid here.

Comment 13

[Olli Pettay [:smaug][[e-mail]]]

Attachment: imid

Comment 14

[Olli Pettay [:smaug][[e-mail]]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6bb23207bdbb

Comment 15

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/6bb23207bdbb