Closed Bug 1300293 Opened 10 years ago Closed 7 years ago

reflowing view-source very slow in nsLineBox::RFindLineContaining

Categories

(Core :: Layout, defect, P3)

Product:
Core
Component:
Layout
Version:
50 Branch
Type:
defect

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla70
Tracking Flags:
Tracking Status
firefox70 --- fixed

People

(Reporter: smaug, Assigned: dbaron)

References

Details

(Keywords: perf)

Attachments

(4 external files)

Load https://html.spec.whatwg.org/#the-option-element:htmloptionelement select the text right before the algorithm and also algorithm steps 1-7 and right click -> view selection source. Once enough data is loaded, there are long hangs where all the time is spent in nsLineBox::RFindLineContaining There is a worrisome comment about O(N²) in http://searchfox.org/mozilla-central/rev/3582398bc9db5a83e25c2a8299cc780a52ad7ca8/layout/generic/nsBlockFrame.cpp#5219 Could we possibly cache something here?
There is another issue... when I switch from other pages to the view source page, there is another long hang...
Keywords: perf
Blocks: 1285982
Priority: -- → P3
sounds like duplicate of bug 190147. It has many friends in the dependencies. And perhaps more, that are not in the dependencies - bug 667412, bug 723788 15 seconds for me with FF56 nightly and e10s, 40 seconds with chrome beta.
Flags: needinfo?(bugs)
Summary: reflowing view-source very slow → reflowing view-source very slow in nsLineBox::RFindLineContaining
(In reply to Wayne Mery (:wsmwk) from comment #2) > sounds like duplicate of bug 190147. It has many friends in the > dependencies. Quite possibly. RFindLineContaining is found in bug 190147 comment 6 as well. I'm not going to dupe it yet, since this bug describes a very specific code change and we don't know that it will completely fix bug 190147 (which has a number of other profiler hot spots.)
Flags: needinfo?(bugs)
Blocks: 190147
See Also: → 1456964
See Also: → 1475222

dholbert duped bug 1561394 over here, which was about scrolling taskcluster logs before they're fully loaded. It's worth pointing out that you can hit this problem even without scrolling taskcluster logs, which means it's apparently rolling the dice whether you can load logs and get your work done in Firefox vs. something else. It didn't used to be like this, so perhaps there have been changes that make this more likely?

Here's a try run for a set of patches that I think should avoid the RFindLineContaining performance problem -- although I'd really like to find an example of that performance problem that's reliably reproducable enough that I can take measurements of it...

(At least, I think it should fix the RFindLineContaining problem that was in a profile of a taskcluster log -- which may or may not be the same one that's showing up in view source.)

OK, my conditional breakpoint while running a reverse-continue in rr did finally fire, and gave me what's probably a more useful stack (which I wish I got in the Gecko profiler):

#0  0x00007fa4e1cb4818 in nsLineBox::RFindLineContaining(nsIFrame*, nsLineList_iterator const&, nsLineList_iterator&, nsIFrame*, int*) (aFrame=0x7fa4a8afa350, aBegin=..., aEnd=..., aLastFrameBeforeEnd=0x7fa4acfa8610, aFrameIndexInLine=0x7ffccfddb52c) at /home/dbaron/builds/gecko/gecko/layout/generic/nsLineBox.cpp:386
#1  0x00007fa4e1c17582 in nsBlockFrame::AddFrames(nsFrameList&, nsIFrame*, nsLineList_iterator const*) (this=<optimized out>, aFrameList=..., aPrevSibling=0x7fa4a8afa350, aPrevSiblingLine=0x0)
    at /home/dbaron/builds/gecko/gecko/layout/generic/nsBlockFrame.cpp:5488
#2  0x00007fa4e1c18883 in nsBlockFrame::InsertFrames(mozilla::layout::FrameChildListID, nsIFrame*, nsLineList_iterator const*, nsFrameList&) (this=0x7fa4acfa8370, aListID=mozilla::layout::kNoReflowPrincipalList, aPrevFrame=0x7fa4a8afa350, aPrevFrameLine=0x0, aFrameList=...)
    at /home/dbaron/builds/gecko/gecko/layout/generic/nsBlockFrame.cpp:5378
#3  0x00007fa4e1b78ee0 in CreateContinuation(nsIFrame*, nsIFrame**, bool) (aFrame=0x7fa4a8afa350, aNewFrame=<optimized out>, aIsFluid=<optimized out>)
    at /home/dbaron/builds/gecko/gecko/layout/base/nsBidiPresUtils.cpp:608
#4  0x00007fa4e1b784ee in nsBidiPresUtils::EnsureBidiContinuation(nsIFrame*, nsIFrame**, int, int) (aFrame=<optimized out>, aNewFrame=<optimized out>, aStart=13148, aEnd=13149)
    at /home/dbaron/builds/gecko/gecko/layout/base/nsBidiPresUtils.cpp:1778
#5  0x00007fa4e1b784ee in nsBidiPresUtils::ResolveParagraph(BidiParagraphData*) (aBpd=<optimized out>)
    at /home/dbaron/builds/gecko/gecko/layout/base/nsBidiPresUtils.cpp:881
#6  0x00007fa4e1b76e91 in nsBidiPresUtils::Resolve(nsBlockFrame*) (aBlockFrame=<optimized out>)
    at /home/dbaron/builds/gecko/gecko/layout/base/nsBidiPresUtils.cpp:713
#7  0x00007fa4e1c086ba in nsBlockFrame::Reflow(nsPresContext*, mozilla::ReflowOutput&, mozilla::ReflowInput const&, nsReflowStatus&) (this=0x7fa4acfa8370, aPresContext=0x7fa4d70e2800, aMetrics=..., aReflowInput=..., aStatus=...) at /home/dbaron/builds/gecko/gecko/layout/generic/nsBlockFrame.cpp:1244
Assignee: nobody → dbaron
Status: NEW → ASSIGNED

Here's a try run for some work in progress which clearly needs a bit more debugging.

Though it seems like that doesn't fix the main problem here either.

Here's a profile from a week ago showing this bug; I think the thing I missed was that it went through the SplitInlineAncestors callsite. That said... it also seems like what I want to do is hard to make safe due to the way this manipulates the frame tree, so I'll need to do something a little more complicated (and also a little slower) but still not as slow as what we were doing before.

I confirmed in a profile that RFindLineContaining has gone away with the latest patches; the profile is now a good bit flatter. (Edit to remove incorrect profile link; I lost the real one.)

This information is used in the next patch, which will use that information to
maintain a line iterator while iterating over mLogicalFrames (and will remove
the stored mLinePerFrame).

TraverseFrames gathers a bunch of frames into an array, and then at
forced breaks or the end of the block flushes its array by running
ResolveParagraph. ResolveParagraph can sometimes cause lines to break,
so lines recorded during TraverseFrames may no longer be accurate during
ResolveParagraph.

It may look like the lines are only needed during ResolveParagraph and
we could handle the one issue in TraverseFrames that deals with
preformatted newlines by restructuring the code a tad. However, in the
next patch, there will be an additional caller that needs the current
line during TraverseFrames to pass to CreateContinuation, which makes
such a structure less plausible.

This will also make it easier to produce a current line for the call to
SplitInlineAncestors within ResolveParagraph, which will be done in the
patch after the next.

Hopefully for real this time, here's the flatter profile that shows up with these patches. (I believe this profile covers the entire load of view-source: of the single-page HTML spec.)

Here's a try run with the changes to address review comments.

Pushed by dbaron@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/553dfbd68c94 Track the block and line list that each frame in BidiParagraphData::mLogicalFrames came from. r=jfkthame https://hg.mozilla.org/integration/autoland/rev/fc179320bf36 Make nsBidiPresUtils track line boxes separately for the progress of TraverseFrames and ResolveParagraph. r=jfkthame https://hg.mozilla.org/integration/autoland/rev/b82381247a5e Pass the line box from nsBidiPresUtils::ResolveParagraph through EnsureBidiContinuation to nsIFrame::InsertFrames. r=jfkthame https://hg.mozilla.org/integration/autoland/rev/57c43ac551e8 Pass the line box from nsBidiPresUtils::ResolveParagraph through SplitInlineAncestors to nsIFrame::InsertFrames. r=jfkthame
Regressions: 1568501
Regressions: 1576972
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: