532998 - Horrible performance with a small textarea element and huge lines of text

Status: RESOLVED FIXED

(Core :: DOM: Editor, defect)

Description

[(no longer active)]

Attachment: Test case

Sam had this problem with his Firefox profile where restoring his old session practically hanged his browser.  He kindly sent me his sessionstore.js, and I managed to find the problem page by looking at the URLs in his session one by one.

The problem happens on http://new.heimat.de/home/bibdat/isdat.htm, which is a near 2MB HTML file containing a default-sized textarea with two extremely long lines of text.

I am attaching the file as plain text for viewing, but beware that loading it may hang your browser for a few minutes.

Sharking Firefox reveals that we're spending ~95% of our time in this memchr call:

<http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#2157>

Comment 1

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

It's only a few seconds to load that testcase for me. Are you using the HTML5 parser?

Comment 2

[(no longer active)]

(In reply to comment #1)
> It's only a few seconds to load that testcase for me. Are you using the HTML5
> parser?

No.  I just tested it again on my nightly (which is an optimized build) and it took near 1.5 minutes to load.

Are you testing this on Mac?

Comment 3

[(no longer active)]

I found a possible dupe, bug 228146, which was resolved INVALID.  I also asked Jeff to load this, and he saw a similar perf problem.

Safari on Mac loads the page just fine.

Comment 5

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

I'm testing on Mac, yes. In a debug build. When I did a frame dump, your testcase has the text broken into a lot of 4096-char text nodes, which is what the old parser does. Is that what you see?

Comment 6

[(no longer active)]

When I did a frame dump, I got a huge frame tree containing numerous line frames for each line of text as displayed inside the textarea.  Here is a sample of the frame tree (the whole tree is too large to attach):

                      Block(div)(-1)@0x25d1a0e0 [view=0xa110f10] [content=0xa110090] {0,0,9500,2580} [state=01d06010] [overflow=0,0,9500,106043280] sc=0x25d19f70(i=126242,b=0) pst=:-moz-scrolled-content<
                        line 0x25d1a2c8: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,0,9360,840} ca={59,0,9361,840} <
                          Text(0)@0x25d1a280[0,20,F]  next=0x25d1a780 next-continuation=0x25d1a780 {60,0,9360,840} [state=c0604200] SELECTED [content=0xa110030] [overflow=-1,0,9361,840] sc=0xdba2510 pst=:-moz-non-element<                            "Aaby, P; Garly, ML; "
                          >
                        >
                        line 0x25d1a7c8: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,840,5616,840} ca={60,840,5640,840} <
                          Text(0)@0x25d1a780[20,12,F]  next=0x25d1a860 prev-continuation=0x25d1a280 next-continuation=0x25d1a860 {60,840,5616,840} [state=84604204] SELECTED [content=0xa110030] [overflow=0,0,5640,840] sc=0xdba2510 pst=:
-moz-non-element<                            "Bale, C, et "
                          >
                        >
                        line 0x25d1a8a8: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,1680,7488,840} ca={60,1680,7500,840} <
                          Text(0)@0x25d1a860[32,16,F]  next=0x25d1a8d0 prev-continuation=0x25d1a780 next-continuation=0x25d1a8d0 {60,1680,7488,840} [state=84604204] SELECTED [content=0xa110030] [overflow=0,0,7500,840] sc=0xdba2510 pst=
:-moz-non-element<
                            "al.*Survival of "
                          >
                        >
                        line 0x25d1a918: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,2520,8892,840} <
                          Text(0)@0x25d1a8d0[48,19,F]  next=0x25d1a940 prev-continuation=0x25d1a860 next-continuation=0x25d1a940 {60,2520,8892,840} [state=80604004] [content=0xa110030] sc=0xdba2510 pst=:-moz-non-element<
                            "previously measles-"
                          >
                        >
                        line 0x25d1a988: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,3360,7020,840} <
                          Text(0)@0x25d1a940[67,15,F]  next=0x25d1a9b0 prev-continuation=0x25d1a8d0 next-continuation=0x25d1a9b0 {60,3360,7020,840} [state=80604004] [content=0xa110030] sc=0xdba2510 pst=:-moz-non-element<                            "vaccinated and "
                          >
                        >
                        line 0x25d1a9f8: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,4200,3744,840} ca={59,4200,3745,840} <
                          Text(0)@0x25d1a9b0[82,8,F]  next=0x25d1aa20 prev-continuation=0x25d1a940 next-continuation=0x25d1aa20 {60,4200,3744,840} [state=80604004] [content=0xa110030] [overflow=-1,0,3745,840] sc=0xdba2510 pst=:-moz-non
-element<
                            "measles-"
                          >
                        >
                        line 0x25d1aa68: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,5040,6084,840} <
                          Text(0)@0x25d1aa20[90,13,F]  next=0x25d1aa90 prev-continuation=0x25d1a9b0 next-continuation=0x25d1aa90 {60,5040,6084,840} [state=80604204] SELECTED [content=0xa110030] sc=0xdba2510 pst=:-moz-non-element<
                            "unvaccinated "
                          >
                        >
                        line 0x25d1aad8: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,5880,7020,840} <
                          Text(0)@0x25d1aa90[103,15,F]  next=0x25d1ab00 prev-continuation=0x25d1aa20 next-continuation=0x25d1ab00 {60,5880,7020,840} [state=80604004] [content=0xa110030] sc=0xdba2510 pst=:-moz-non-element<
                            "children in an "
                          >
                        >
                        line 0x25d1ab48: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,6720,4680,840} <
                          Text(0)@0x25d1ab00[118,10,F]  next=0x25d1ab70 prev-continuation=0x25d1aa90 next-continuation=0x25d1ab70 {60,6720,4680,840} [state=80604004] [content=0xa110030] sc=0xdba2510 pst=:-moz-non-element<
                            "emergency "
                          >
                        >
                        line 0x25d1abb8: count=1 state=inline,clean,prevmarginclean,not impacted,wrapped,before:nobr,after:nobr[0x8120] {60,7560,6552,840} <
                          Text(0)@0x25d1ab70[128,14,F]  next=0x2189010 prev-continuation=0x25d1ab00 next-continuation=0x2189010 {60,7560,6552,840} [state=80604004] [content=0xa110030] sc=0xdba2510 pst=:-moz-non-element<
                            "situation: an "
                          >
                        >


I tried this with the old parser, but I also tried the HTML5 parser, and I got the exact same performance problem as with the old parser.

Comment 7

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

What about in the testcase in comment #0?

Comment 8

[(no longer active)]

(In reply to comment #7)
> What about in the testcase in comment #0?

That is the same file, I just saved it locally in case the original URL becomes unavailable for some reason.

Comment 9

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

Comment on attachment 416163 [details]
Test case

Ah, I see the problem ... I was loading it as text/plain...

Comment 10

[(no longer active)]

(In reply to comment #9)
> (From update of attachment 416163 [details])
> Ah, I see the problem ... I was loading it as text/plain...

Oh sorry for the confusion.

I really don't get this bug.  Is memchr _this_ slow?

Comment 11

[(no longer active)]

Hmm, couldn't we cache the position of the next newline character somewhere and not look for it over and over again?

Comment 12

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

Maybe.

All the text is in one giant text node. It's pre-wrap, so during reflow it breaks into many text frames. Each time we reflow a text frame, we look for a \n in the text to limit our reflow to stop at the first \n (but there isn't one). So this leads to O(N^2) behaviour.

Comment 13

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

Attachment: fix

This caches the offset of the first newline after a given offset. It's still not fast, but it's a lot better.

Comment 14

[Simon Montagu :smontagu]

Comment on attachment 417051 [details] [diff] [review]
fix

Looks like this is the testcase, not the patch

Comment 15

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

Attachment: fix

oops

Comment 16

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

Attachment: fix v2

Comment 17

[Simon Montagu :smontagu]

Comment on attachment 417125 [details] [diff] [review]
fix v2


>@@ -6456,16 +6484,38 @@ nsTextFrame::Reflow(nsPresContext*      

>+        if (NS_FAILED(mContent->SetProperty(nsGkAtoms::newline, cachedNewlineOffset,
>+                      NewlineProperty::Destroy))) {

nit: the indentation on the second line should be after the next "("

Comment 18

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

http://hg.mozilla.org/mozilla-central/rev/6dc53634551f

Comment 19

[(no longer active)]

Roc, did you mean to mark this as FIXED?  Also, I think we also want this on 1.9.2.

For the record, the landed patch fixes the performance problem for me.

Comment 20

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

I believe this problem has been around for a long time, therefore the patch doesn't NEED to be in 1.9.2, although it might be good to have it there.

Comment 21

[Julian Seward [:jseward]]

Roc et al, did this get checked for Memcheck cleanness?  I'm getting
the complainage shown below when loading eg http://www.kde.org

It complains about an uninitialised value use at 
layout/generic/nsTextFrameThebes.cpp:6501, viz:

  } else if (cachedNewlineOffset) {          <----------- here
    mContent->DeleteProperty(nsGkAtoms::newline);
  }

and hg ann points at changeset 36903:6dc53634551f, which refers to this
bug.

w/ apologies if I'm on the wrong track here ..

==32280== Conditional jump or move depends on uninitialised value(s)
==32280==    at 0x5799C2F: nsTextFrame::Reflow(nsPresContext*, nsHTMLReflowMetrics&, nsHTMLReflowState const&, unsigned int&) (nsTextFrameThebes.cpp:6501)
==32280==    by 0x57774E4: nsLineLayout::ReflowFrame(nsIFrame*, unsigned int&, nsHTMLReflowMetrics*, int&) (nsLineLayout.cpp:852)
==32280==    by 0x5740D06: nsBlockFrame::ReflowInlineFrame(nsBlockReflowState&, nsLineLayout&, nsLineList_iterator, nsIFrame*, LineReflowStatus*) (nsBlockFrame.cpp:3715)
==32280==    by 0x5741847: nsBlockFrame::DoReflowInlineFrames(nsBlockReflowState&, nsLineLayout&, nsLineList_iterator, nsFlowAreaRect&, int&, nsFloatManager::SavedState*, int*, LineReflowStatus*, int) (nsBlockFrame.cpp:3510)
==32280==    by 0x5741DDF: nsBlockFrame::ReflowInlineFrames(nsBlockReflowState&, nsLineList_iterator, int*) (nsBlockFrame.cpp:3364)
==32280==    by 0x5741FFD: nsBlockFrame::ReflowLine(nsBlockReflowState&, nsLineList_iterator, int*) (nsBlockFrame.cpp:2439)
==32280==    by 0x574265E: nsBlockFrame::ReflowDirtyLines(nsBlockReflowState&) (nsBlockFrame.cpp:1885)
==32280==    by 0x5743342: nsBlockFrame::Reflow(nsPresContext*, nsHTMLReflowMetrics&, nsHTMLReflowState const&, unsigned int&) (nsBlockFrame.cpp:993)
==32280==    by 0x574EC3F: nsFrame::BoxReflow(nsBoxLayoutState&, nsPresContext*, nsHTMLReflowMetrics&, nsIRenderingContext*, int, int, int, int, int) (nsFrame.cpp:6499)
==32280==    by 0x575373F: nsFrame::RefreshSizeCache(nsBoxLayoutState&) (nsFrame.cpp:6085)
==32280==    by 0x5753AF0: nsFrame::GetPrefSize(nsBoxLayoutState&) (nsFrame.cpp:6169)
==32280==    by 0x584E116: nsSprocketLayout::GetPrefSize(nsIFrame*, nsBoxLayoutState&) (nsSprocketLayout.cpp:1366)
==32280==  Uninitialised value was created by a stack allocation
==32280==    at 0x57990B2: nsTextFrame::Reflow(nsPresContext*, nsHTMLReflowMetrics&, nsHTMLReflowState const&, unsigned int&) (nsTextFrameThebes.cpp:6059)

Comment 22

[Boris Zbarsky [:bzbarsky]]

Julian, see bug 539720 (marked as a regression from this bug, etc).