1927114 - Consider making nsLineBox::RIndexOf search the line from both ends

Status: RESOLVED FIXED

(Core :: Layout, enhancement)

Description

[Jonathan Kew [:jfkthame]]

In nsBlockFrame::InsertFrames, we use nsLineBox::RIndexOf while trying to find the line containing the previous sibling frame, so that we search the given aPrevSiblingLine (if any) from the end. This was done in bug 1568501 to fix a performance cliff, where the frame we're looking for tends to be at the end of the (possibly very long) aPrevSiblingLine.

However, the profile https://share.firefox.dev/3NDcwnl from bug 1926808 comment 3 suggests that this is not always the right thing: almost 50% of the samples in this 11-minute profile are within this nsLineBox::RIndexOf call. This implies, I think, that in this example we're having to search all the way backwards through an extremely long line, and searching from the beginning would have been the better choice.

In the specific case of bug 1926808, the restructuring of View Source in bug 1926824 should avoid the problem, but there must be other pages that could potentially hit the same issue.

I wonder, therefore, if the best strategy when nsBlock::InsertFrames is trying to find the previous sibling's line would be to search aPrevSiblingLine from both ends, so that we find the target frame quickly if it is either at the beginning or the end. In practice these are the two likely cases; in theory, given the right mix of bidi content, I think the previous sibling could be somewhere in the middle of the line, but that will be much less common.

I'm pushing a try run to see whether modifying nsLineBox::RIndexOf in this way affects the bidi-resolution perf test that bug 1568501 was fixing:

Base: https://treeherder.mozilla.org/jobs?repo=try&revision=a518caa0e33ea172ce8ccf8564b3569b2c5a83f5
Patched: https://treeherder.mozilla.org/jobs?repo=try&revision=27a0c8f50b94419aab7ad2d466b4a7ae6640840e

Comment 1

[Jonathan Kew [:jfkthame]]

Using local builds on macOS, I profiled opening View Source for the big HTML spec https://html.spec.whatwg.org/. (Note that my tree does not yet include bug 1926824.)

With a plain mozilla-central build: https://share.firefox.dev/40ksavA - this shows 47K samples in nsBlockFrame::InsertFrames
Patched nsLineBox::RIndexOf: https://share.firefox.dev/4hniFl9 - now there are only 175 samples in nsBlockFrame::InsertFrames

So if this doesn't significantly regress other examples, it seems like a clear win.

Comment 2

[Jonathan Kew [:jfkthame]]

Attachment: Bug 1927114 - Rename nsLineBox::RIndexOf to RLIndexOf and make it search from both ends of the line. r=#layout

This does not change the result, only the performance characteristics:
the search will be fast if the target frame is near either edge of the line,
not only if it's at the end.

Comment 3

[Jonathan Kew [:jfkthame]]

Attachment: Bug 1927114 - Cleanup/constify a few things in nsLineBox. r=#layout

No change in behavior; this is just a bit of cleanup that I noticed
in the region around the first patch here.

Comment 4

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/4cb0ee10f360
Rename nsLineBox::RIndexOf to RLIndexOf and make it search from both ends of the line. r=dshin

Comment 5

[Norisz Fay [:noriszfay]]

https://hg.mozilla.org/mozilla-central/rev/4cb0ee10f360