727831 - Make removing normal flow child frames in block frames faster (DoRemoveFrame)

Status: RESOLVED FIXED

(Core :: Layout: Block and Inline, defect)

Description

[Mats Palmgren (inactive)]

DoRemoveFrame is slow because it needs to find the line the child frame
is on, which is a linear search, O(n) on the number of normal flow child
frames in the block.  Bug 726637 shows the problem with View Source on
a very large page that has much of the content on the same line (about 60%
of the time is in nsLineBox::IndexOf, all from DoRemoveFrame).

Comment 1

[Mats Palmgren (inactive)]

Attachment: Setup and use the line cursor

This is a somewhat scary patch that makes use of the line cursor property
to point out the last inline line that we started reflowing, and then use
that as the starting point for the search.  It fixes the DoRemoveFrame
part of bug 726637 completely.

Comment 2

[Mats Palmgren (inactive)]

I'm going to try a less intrusive and safer approach next -- search the last few
lines (in reverse) first and then do the normal forward search...
I'll try to get some stats of where we find the frame also.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Note also bug 682052...

Comment 4

[Mats Palmgren (inactive)]

Attachment: Some statistics on DoRemoveFrame

Without the line cursor, the target line is usually near the start of the
block, with sloping numbers.  If the block is in reflow, the first line
is rarely hit, instead the slope starts from the second line.

The View Source testcase in bug 726637 stands out with high numbers for
lines in the middle of the block (not first/last 19 lines).

The line cursor patch changes the numbers so that pretty much all frames
are found on the next line after the cursor, in fact it's close to 100%
at first-frame-at-next-line, which makes sense.  There were no cases
where the frame was on a line *before* the line cursor.
The more reflow intensive, the higher chance there is a line cursor
available, which also makes sense since I set up the cursor just before
starting reflowing an inline line.

I don't see a simpler approach than using a line cursor, without
redesigning the data structures involved.

Comment 5

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee didn't login in Bugzilla in the last months and this bug has severity 'major'.
:jfkthame, could you have a look please?
For more information, please visit auto_nag documentation.

Comment 6

[BugBot [:suhaib / :marco/ :calixte]]

In the process of migrating remaining bugs to the new severity system, the severity for this bug cannot be automatically determined. Please retriage this bug using the new severity system.

Comment 7

[Jonathan Kew [:jfkthame]]

Attachment: Bug 727831 - Use the line cursor to optimize nsBlockFrame::DoRemoveFrame, to avoid perf cliff when reflowing/modifying large blocks of text. r=#layout

This is basically Mats' line-cursor patch from 2012, updated to account for changes
in nsBlockFrame that have happened since then.

The example in https://bugzilla.mozilla.org/show_bug.cgi?id=1911451, for instance,
benefits hugely from this. Profile of resizing the textarea in the example there,
after pasting in the huge JS source:

Current mozilla-central: https://share.firefox.dev/3M6gUui
(truncated because I got tired of waiting for the reflow to finish)

With this patch applied: https://share.firefox.dev/46RMmpy
It's still janky, but only takes a second or so to reflow at each step.

Comment 8

[Jonathan Kew [:jfkthame]]

Attachment: Bug 727831 - Add a perf-reftest for resizing a textarea with large contents. r=#layout

In my local build, this reports timings of around 800ms using current mozilla-central,
and drops to around 80ms with the patch applied.

Comment 9

[Mayank Bansal]

The patches seems to massively improve bug 1405989

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/2fdfc56a4640
Use the line cursor to optimize nsBlockFrame::DoRemoveFrame, to avoid perf cliff when reflowing/modifying large blocks of text. r=layout-reviewers,emilio
https://hg.mozilla.org/integration/autoland/rev/95661209edef
Add a perf-reftest for resizing a textarea with large contents. r=layout-reviewers,perftest-reviewers,emilio,sparky

Comment 11

[Jonathan Kew [:jfkthame]]

(In reply to Mayank Bansal from comment #9)

The patches seems to massively improve bug 1405989

That makes sense given what the profile there showed; thanks for testing & confirming that. I think we can resolve it as a dupe of this.

Comment 13

[Cosmin Sabou [:CosminS]]

https://hg.mozilla.org/mozilla-central/rev/2fdfc56a4640
https://hg.mozilla.org/mozilla-central/rev/95661209edef