pressing Enter in a large textarea is very CPU intensive with Firefox 4.0

[Jamie Strandboge]

Binary package hint: firefox

On up to date natty with Firefox 4.0, pressing Enter in a large textarea is very CPU intensive.

Go to:
https://wiki.ubuntu.com/MozillaTeam/test677551

Edit the page, and then click 'Enter' a few times at the top of the editing textarea. The CPU will spike. Holding 'Enter' pegs the CPU entirely (there is no need to commit your changes). This is a regression over 3.6 on Ubuntu 10.10.

[Bzbarsky (bzbarsky)]

Profile (on Mac) says 95% of the time is spent in the reflow that we trigger from EndUpdateViewBatch. Even more interestingly, 93% is under nsLineLayout::TrimTrailingWhiteSpace and almost all of this is under EnsureTextRun. Sounds like we're recreating textruns for the whole thing, presumably because inserting some text marked them all dirty?

Oh, and we're spending most of our time here on line-breaking in the textrun code.

Are we trying to trim trailing whitespace all down the line, or are we just creating huge textrun? I thought we limited textrun length or something... and we shouldn't have to trim trailing whitespace all down the line (and in fact, should be able to stop the reflow at the next line that ends in a newline char, yes?)

[Jonas-sicking (jonas-sicking)]

Actually, it appears adding enough text on one line that it wraps also slows things down. So it's not the newline character in itself that's the culprit.

[Bzbarsky (bzbarsky)]

Right; it's the fact that we end up having to reflow over to the next line at all. We should still be terminating that reflow at the _next_ newline we hit. So if you have:

  AAAAAAA
  CCCCCCC

on two adjacent lines and you type a bunch of Bs after the As until you line-wrap, we shouldn't reflow past the end of the Cs if we're doing it right. Imo.

[Roc-ocallahan (roc-ocallahan)]

One problem is that we can't insert a frame into the middle of the continuation chain. So if you need to split one line into two, the continuation frame for each later line N+1 becomes the continuation for line N (which requires reflow of course).

Should only be O(N) per split though.

[Jonas-sicking (jonas-sicking)]

You seem to be right in that it's not n^2. If I duplicate the size of a 100KB text area the time it takes to add a newline early in the area goes from 3 seconds to 6 seconds on a reasonably new macbook pro.

Still very slow though. Slow enough that it's annoying to review big patches directly in bugzilla.

[Roc-ocallahan (roc-ocallahan)]

We can probably insert a text frame into the continuation chain, but it's a little tricky.

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #6)
> We can probably insert a text frame into the continuation chain, but it's a
> little tricky.

Hmm, aren't text frame continuations stored as a linked list? Is there some other data structure which needs to get updated as well? Would you elaborate please?

[Roc-ocallahan (roc-ocallahan)]

Actually I guess it might just work.

[Jonas-sicking (jonas-sicking)]

What's very weird to me is that when doing the steps in comment 0, step 2 is much faster than step 4. Doesn't both (re)create the full set of line frames?

[Bzbarsky (bzbarsky)]

I'd think so, yes.... That's odd, indeed.

[Jonas-sicking (jonas-sicking)]

Similarly, copying the full contents of the textarea, moving to the end, and pasting is also basically instant. Even though I would expect that to create/reflow just as many inline frames.

In fact, pasting a full copy the end is about 30 times faster than inserting a newline at the beginning.

[Bzbarsky (bzbarsky)]

Yeah, that's really weird. roc, any idea what's going on there?

[Roc-ocallahan (roc-ocallahan)]

Not without debugging it.

[Ehsan-mozilla (ehsan-mozilla)]

It seems to me that the majority of the problem here is textrun reconstruction for the entire textarea.

I saw this comment <http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#3911>, and this code indeed is what invalidates all of the continuations' textruns when the field is edited.

I didn't understand the comment though, and I'm not sure how to do what it says, but I'm pretty sure that we'll get a huge perf benefit if we can avoid invalidating those textruns unnecessarily.

[Ehsan-mozilla (ehsan-mozilla)]

Moving to Layout: Text which is probably a better component for this bug.

[Roc-ocallahan (roc-ocallahan)]

Yeah, that is exactly what we need to do here. See
http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#191
to about
http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#249

[Bzbarsky (bzbarsky)]

That hypothesis doesn't really address the question from comment 9 or comment 11, as far as I can tell...

Also, that code runs when _any_ char is typed, no? Why is typing non-newlines fast? Just because we only reconstruct the textruns for the line that was edited?

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #17)
> That hypothesis doesn't really address the question from comment 9 or comment
> 11, as far as I can tell...

It doesn't. I tried figuring it out today but couldn't. Maybe tomorrow I'll notice something that I've missed today.

> Also, that code runs when _any_ char is typed, no? Why is typing non-newlines
> fast? Just because we only reconstruct the textruns for the line that was
> edited?

On second look, this code should have the same effect no matter what character is typed, which means that the textruns for the following lines are invalidated either way, which makes my theory in comment 14 invalid perhaps.

[Bzbarsky (bzbarsky)]

Well, textrun invalidation is (relatively) cheap. If we then don't need to _reconstruct_ the textruns for the text outside the visible part of the textarea, things would be fast.

But give comment 9 and comment 11, it sounds to me like we reconstruct textruns multiple times when enter is pressed. Or something.

[Ehsan-mozilla (ehsan-mozilla)]

So, here's what's happening. We're actually reflowing three times:

1. Once from nsRefreshDriver::Notify which seems to be a usual refresh event pending in the event queue.
2. Once from nsTypedSelection::ScrollIntoViewEvent::Run which we post when the editing operation is done.
3. Once from nsViewManager::CallWillPaintOnObservers which happens when painting the invalidated area generated in steps 1 and 2.

Why we reflow three times really puzzles me...

[Tnikkel (tnikkel)]

Can you track what is requesting these reflows by seeing what is calling PresShell::FrameNeedsReflow?

[Ehsan-mozilla (ehsan-mozilla)]

Also, I tried taking out the loop in question in comment 14 out, and it indeed fixes the perf problem.

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #21)
> Can you track what is requesting these reflows by seeing what is calling
> PresShell::FrameNeedsReflow?

Probably... But given comment 22, I don't think that's going to be too useful now...

[Ehsan-mozilla (ehsan-mozilla)]

Created attachment 479929
Don't invalidate textruns

So, this is what I could make out of the comment in the code, but the code is very broken, in that it seems to update the frame content offsets to invalidate values. Does anybody have any idea what I've been missing here?

[Bzbarsky (bzbarsky)]

Again, typing _anything_ does the textrun invalidation. Pasting the text in starts with invalid textruns.

Give me a bit to look into this.

[Bzbarsky (bzbarsky)]

So a bit of testing with a 4-line textarea....

I confirmed that typing non-newline characters reflows just the line they're typed on (as long as it doesn't wrap) while typing enter reflows all the lines.

I also confirmed that typing enter a single time clears textruns once via that loop and reflows each line exactly once.

I also confirmed that cutting and then pasting all the text in the textarea reflows each line exactly once. Also that it's much much faster than hitting enter.

I added a printf in ClearAllTextRunReferences right before the SetTextRun call, like so:

    if (aFrame->GetContent()->GetParent() &&
        aFrame->GetContent()->GetParent()->GetParent() &&
        aFrame->GetContent()->GetParent()->GetParent()->Tag() ==
          nsGkAtoms::textarea &&
        aFrame->GetTextRun()) {
      printf("Clearing: %p\n", aFrame);
    }
and one at the beginning of nsTextFrame::ReflowText like so:

  if (mContent->GetParent() &&
      mContent->GetParent()->GetParent() &&
      mContent->GetParent()->GetParent()->Tag() == nsGkAtoms::textarea) {
    printf("Reflowing: %p\n", this);
  }

Here's what the output looks like if I paste 4 lines into a textarea (the lines contain one char each: "a", "b", "c", and "d"):

  Reflowing: 0x103bd8990
  Reflowing: 0x103bd93a8
  Reflowing: 0x103bd92f0
  Reflowing: 0x103bd9198

Here's what happens if I hit space on the first line before the "a":
  Clearing: 0x103bd8990
  Clearing: 0x103bd93a8
  Clearing: 0x103bd92f0
  Clearing: 0x103bd9198
  Reflowing: 0x103bd8990Here's what happens if I hit enter before the "d":

  Clearing: 0x103bd9198
  Reflowing: 0x103bd92f0
  Reflowing: 0x103bd9198
  Reflowing: 0x1041b06d8
Here's what happens if I hit enter before the "c":

  Clearing: 0x103bd92f0
  Clearing: 0x103bd9198
  Reflowing: 0x103bd93a8
  Reflowing: 0x103bd92f0
  Clearing: 0x103bd92f0
  Clearing: 0x103bd9198
  Reflowing: 0x103bd9198
  Reflowing: 0x1041b06d8Here's what I get if I hit enter before the "a":

  Clearing: 0x103bd8990
  Clearing: 0x103bd93a8
  Clearing: 0x103bd92f0
  Clearing: 0x103bd9198
  Reflowing: 0x103bd8990
  Clearing: 0x103bd8990
  Clearing: 0x103bd93a8
  Reflowing: 0x103bd93a8
  Clearing: 0x103bd93a8
  Clearing: 0x103bd92f0
  Reflowing: 0x103bd92f0
  Clearing: 0x103bd92f0
  Clearing: 0x103bd9198
  Reflowing: 0x103bd9198
  Reflowing: 0x1041b06d8
So it looks like we clear all the textruns for the textarea from the CharacterDataChanged notification, then reflow all the lines, and before reflowing each line we clear its textrun, which is non-null at that point. So presumably we're constructing all those textruns twice... That still doesn't quite explain the behavior I see, where the difference is a lot more than 2x between paste and hitting enter.

[Bzbarsky (bzbarsky)]

Er... some of the newlines in the previous comment disappeared :(

[Bzbarsky (bzbarsky)]

nsTextFrame::SetLength called from nsTextFrame::ReflowText is what ends up doing some of that textrun clearing on next-in-flows and the like.

[Bzbarsky (bzbarsky)]

Wait. When I paste that huge textarea, I see something like 3 textruns being constructed... (as measured by a breakpoint in gfxTextRun::gfxTextRun).

If I hit enter a few lines from the end I get two textruns constructed per line between me and the end. roc, is that expected?

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #27)
> Er... some of the newlines in the previous comment disappeared :(

Hmm, dbaron also told me yesterday that he's seen this as well. Do you happen to have STRs?

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #26)
> So it looks like we clear all the textruns for the textarea from the
> CharacterDataChanged notification, then reflow all the lines, and before
> reflowing each line we clear its textrun, which is non-null at that point. So
> presumably we're constructing all those textruns twice... That still doesn't
> quite explain the behavior I see, where the difference is a lot more than 2x
> between paste and hitting enter.

Why is the textrun non-null when reflowing? We've already cleared them all, right?

Also, from what I read in this comment, it seems to me that we don't need to clear the textruns at all in CharacterDataChanged. But that breaks us horribly (having tried that). Is there something missing in this picture?

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #28)
> nsTextFrame::SetLength called from nsTextFrame::ReflowText is what ends up
> doing some of that textrun clearing on next-in-flows and the like.

Yes, and I think we're actually relying on that: <http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsTextFrameThebes.cpp#3881>

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #29)
> Wait. When I paste that huge textarea, I see something like 3 textruns being
> constructed... (as measured by a breakpoint in gfxTextRun::gfxTextRun).

How many lines are you pasting? (We should create at least one textrun per line, right?)

> If I hit enter a few lines from the end I get two textruns constructed per line
> between me and the end. roc, is that expected?

Looks like we should be able to get away without constructing that many textruns on pressing Enter then, right? Of course, I have no idea how... :(

[Bzbarsky (bzbarsky)]

> Do you happen to have STRs?

Not offhand.... there was cutting and pasting involved, though. Past that... I'll see what I can dig up.

> Why is the textrun non-null when reflowing? We've already cleared them all,
> right?

We cleared them. Presumably something regenerated them!

> Yes, and I think we're actually relying on that:

Right. The point is we end up clearing+recreating there at least twice.

And again, that doesn't account for all of the slowdown.

> How many lines are you pasting?

I'm using the testcase linked from comment 0. So 4379 lines.

> (We should create at least one textrun per line, right?)

An excellent question!

[Bzbarsky (bzbarsky)]

And the real issue here is roc's on vacation. He might know the answer to that question, and my question from comment 29.

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #34)
> > Do you happen to have STRs?
>
> Not offhand.... there was cutting and pasting involved, though. Past that...
> I'll see what I can dig up.

Great, thanks. I did some rough testing with cutting and pasting and couldn't repro...

> > Why is the textrun non-null when reflowing? We've already cleared them all,
> > right?
>
> We cleared them. Presumably something regenerated them!

That's... sad.

> > Yes, and I think we're actually relying on that:
>
> Right. The point is we end up clearing+recreating there at least twice.

Yep.

> And again, that doesn't account for all of the slowdown.

Hmm, I think it should. See comment 22.

> > How many lines are you pasting?
>
> I'm using the testcase linked from comment 0. So 4379 lines.
>
> > (We should create at least one textrun per line, right?)
>
> An excellent question!

Well, that basically contradicts all that I know about textruns (which isn't that much, but still!)

(In reply to comment #35)
> And the real issue here is roc's on vacation. He might know the answer to that
> question, and my question from comment 29.

Yeah. Unless someone has a better idea, let's wait for roc to come back.

[Bzbarsky (bzbarsky)]

> Hmm, I think it should. See comment 22.

Huh. That's... odd. Really odd, since we're clearing the textruns as we reflow too, right?

> Well, that basically contradicts all that I know about textruns

Note that it's _possible_ I was getting hits on the textrun cache. Again, I was just looking at the constructor invocations.

[Ehsan-mozilla (ehsan-mozilla)]

(In reply to comment #37)
> > Hmm, I think it should. See comment 22.
>
> Huh. That's... odd. Really odd, since we're clearing the textruns as we
> reflow too, right?

Yes. I observed things getting a lot faster when I took out that loop, but I can't really explain it.

> > Well, that basically contradicts all that I know about textruns
>
> Note that it's _possible_ I was getting hits on the textrun cache. Again, I
> was just looking at the constructor invocations.

Hmm, IINM we remove textruns from the cache when we're clearing them (why are we doing that?!).

[Bzbarsky (bzbarsky)]

Excellent question. If you leave the clearing code but take out the cache-removal bit, are things fast?

[Roc-ocallahan (roc-ocallahan)]

Are you talking about ClearTextRun?

  if (!(textRun->GetFlags() & gfxTextRunWordCache::TEXT_IN_CACHE)) {
    // Remove it now because it's not doing anything useful
    gTextRuns->RemoveFromCache(textRun);
    delete textRun;

So we only remove it from gTextRuns (an nsExpirationTracker) if the textrun is NOT referenced from the gfxTextRunWordCache.

(In reply to comment #29)
> If I hit enter a few lines from the end I get two textruns constructed per line
> between me and the end. roc, is that expected?

No, that sounds like a definite problem. What should happen is that in CharacterDataChanged we clear the textruns from the caret to the end, then when we reflow the line with the caret (or maybe the line before the caret), we reconstruct text runs for those lines, and then no more textrun construction happens.

[Bzbarsky (bzbarsky)]

pd, that sounds like a separate issue. The "characters remaining" thing is very likely part of the problem in your case, but the details could depend on what styles are used, etc. Can you please file a bug on your problem with detailed steps to reproduce, as well as details about your OS and the graphics information from about:support, and cc me on that bug?

[Mounir-lamouri (mounir-lamouri)]

A user was complaining that he/she had to wait 10 minutes when entering a new line in a textarea sometimes. How is that a softblocker? I mean, according to Johnath blog post [1] a softblocker is a "visual polish, strange edge cases, optional aspects of new specs, or opportunistic performance wins". This bug is none of them. However, it matches the description of a hardblocker which can be a "performance hit".

[1] http://blog.johnath.com/2011/01/13/its-almost-ready/

[Bzbarsky (bzbarsky)]

Yeah, I think we need to retriage this.

Mats, did you ever get anywhere on the deletion case?

[Mats Palmgren (matspal)]

Not really, I'm still at the debugging stage with the deletion case.
Any help with that would be appreciated. I have a couple of hardblockers
left but they should be done in a day or two I hope...

[Khuey (khuey)]

Created attachment 507129
Possible patch

I don't purport to fully understand what this code actually does, but following the same idea for the growing case as the shrinking case makes deletion fast for me.

[Jst (jst)]

Agreed, this sounds more like a hardblocker to me as well, given the recent comments. Roc, if you or someone else disagrees, feel free to mark otherwise.

[Bzbarsky (bzbarsky)]

No, that patch is definitely wrong, since it'll mess with frames whose content offset is too big (and incidentally doesn't make deletion fast for me).

[Khuey (khuey)]

Comment on attachment 507129
Possible patch

Yeah, it blew up in crashtests on try too.

[Bzbarsky (bzbarsky)]

So what I think happens in the deletion case I'm testing is that we delete the newline char, end up with an empty text frame, reflow, and effectively move each bit of text to the previous textframe... which means rebuilding text runs for all of them.

[Bzbarsky (bzbarsky)]

Created attachment 507163
This might work, on the other hand

This seems to fix the deleting case for me too. Mats, what do you think?

[Ehsan-mozilla (ehsan-mozilla)]

Comment on attachment 507163
This might work, on the other hand

This works nicely for me. Is there anything else remaining to be done here? Or could we enter the review stage?

(Note: s/Whateve/Whatever/)

[Roc-ocallahan (roc-ocallahan)]

Comment on attachment 507163
This might work, on the other hand

This is scary but it *should* work.

[Bzbarsky (bzbarsky)]

Mats, you want me to land this? Or do you want to?

[Mats Palmgren (matspal)]

There was an assertion on TryServer in one of the reftests when I tested my
patch, in nsFirstLetterFrame IIRC. Feel free to land it if that doesn't occur
anymore. (sorry, I should have noted that on the bug at the time)

[Bzbarsky (bzbarsky)]

Ah.... I have no idea. Pushing this to try right now, to see.

[Mats Palmgren (matspal)]

When I run reftests locally on Linux64 I get:
###!!! ASSERTION: null frame is not allowed: 'aFrame',
file layout/generic/nsLineLayout.cpp, line 656
followed by a crash. The call comes from nsFirstLetterFrame::Reflow

[Mats Palmgren (matspal)]

Removing the last hunk fixes that. I'm re-running the tests again to see
if I can catch the assertion I saw with my part...

[Mats Palmgren (matspal)]

Yeah, from the first part we get:
###!!! ASSERTION: bad overflow list: 'mFrames.IsEmpty()',
file layout/generic/nsFirstLetterFrame.cpp, line 364
when loading layout/reftests/bugs/408493-2.html

[Bzbarsky (bzbarsky)]

OK. For the second hunk, we should probably only do the removal if we're not changing parent in the process. That should fix the comment 93 assert+crash.

We can probably fix the comment 95 assert by checking whether the parent is a letter frame... but could other inline frames have similar issues, or just the weirdness that is letterframe?

[Roc-ocallahan (roc-ocallahan)]

Do you know what the actual issue is with the letterframe?

[Bzbarsky (bzbarsky)]

Not yet.

[Mats Palmgren (matspal)]

Created attachment 507510
Patch v2

This is with Boris' suggested fixes. It still asserts though:
###!!! ASSERTION: overflow list w/o frames: 'mFrames.NotEmpty()',
file layout/generic/nsFirstLetterFrame.cpp, line 377
when loading layout/generic/crashtests/533379-1.html

I'm debugging these assertions to see what's going on...

[Mats Palmgren (matspal)]

Created attachment 507580
Framedump (for the asserion in comment 99)

The last assertion comes from removing the child of a first-letter frame
(0x7fffde659138 blue), on the next reflow we call DrainOverflowFrames
which asserts that the principal list is non-empty when there is an
non-empty overflow list.

I think this is just my fault of not implementing Boris' suggested fix
quite right...
 + next->GetParent() == f->GetParent()) {
should have been
 + GetParent() == f->GetParent()) {
which would avoid doing the RemoveFrame optimization in this case.

[Bzbarsky (bzbarsky)]

No, I'd in fact been thinking of comparing the parents of next and f.

If we remove |f|, which is the child of a first-letter frame, but next->GetParent() == f->GetParent(), then |next| is a child of that first-letter too. So how does the principal child list get empty? Do we end up pushing |next| for some reason?

[Mats Palmgren (matspal)]

Created attachment 507585
Patch v3

This is the fix Boris' suggested I think.
I'll submit it to the TryServer and ask for review if it pass unit tests...
Meanwhile, I'll debug the assertions in comment 93/95.

[Mats Palmgren (matspal)]

You're fast ;-)
The principal list becomes empty because 'next' is on the overflow list.
I guess we could just remove that assertion; I mean the important
thing is that the principal list is non-empty after draining overflow.

Or we could just avoid doing the second optimization at all when a
first-letter frame is onvolved, just to be on the safe side...

[Bzbarsky (bzbarsky)]

Oh, |next| is already on the overflow list but |f| is not while we're reflowing |f|?

I think a simple solution would be to only do this optimization when f->GetNextSibling() == next. That ensures that they're in the same child list, etc.

[Mats Palmgren (matspal)]

Yes. Ok, that sounds good.

[Mats Palmgren (matspal)]

(Well, to be precise, "while we're reflowing |f|" isn't correct - we're
 reflowing its prev-in-flow (0x7fffde6532e0) which has a different
 first-letter parent.)

[Mats Palmgren (matspal)]

Created attachment 507599
Patch v4

This is with the "f->GetNextSibling() == next" check.

[Bzbarsky (bzbarsky)]

> we're reflowing its prev-in-flow

Aha, I see. OK, that makes perfect sense!

We should document why the GetNextSibling() check is there.

For the other, do we know why there's a problem with first-letter? Is it really first-letter specific?

[Mats Palmgren (matspal)]

Created attachment 507697
Framedump (for the assertion in comment 93)

The cause of the assertion/crash in comment 93 is the RemoveFrame we added
causes a lot of first-letter frames to become empty. Then we reflow one
of those and it can't handle that. (See bug 578977.)
The GetNextSibling() check we added should prevent this.

The assertion in comment 95 looks like a bogus assert. I think it's a typo
that was really meant to be "overflowFrames->IsEmpty()":
http://hg.mozilla.org/mozilla-central/annotate/e98b94aa64fa/layout/generic/nsFirstLetterFrame.cpp#l364
I propose we simply remove it since StealOverflowFrames() already assert this:
http://hg.mozilla.org/mozilla-central/annotate/e98b94aa64fa/layout/generic/nsContainerFrame.h#l627

[Mats Palmgren (matspal)]

Created attachment 507698
Patch v5

Add comment about GetNextSibling() check. Remove bogus assert.
(v4 looks good on Try so far...)

[Mats Palmgren (matspal)]

I meant "!overflowFrames->IsEmpty()" of course :-)

[Mats Palmgren (matspal)]

After thinking some more about that assertion; it's probably not a typo
but intended to catch an empty first-letter frame that should have been
removed (as in bug 578977). So let's keep it.

[Bzbarsky (bzbarsky)]

Comment on attachment 507698
Patch v5

This looks fine if we document that parent frame type check. Have roc look at this too?

[Roc-ocallahan (roc-ocallahan)]

Comment on attachment 507698
Patch v5

Assuming you leave in the assert in nsFirstLetterFrame.

[Mats Palmgren (matspal)]

With additional comment and assert in nsFirstLetterFrame intact.
http://hg.mozilla.org/mozilla-central/rev/f704da8cce12

[Aleksej P. (chaos8)]

Verified with Mozilla/5.0 (X11; Linux i686; rv:2.0b12pre) Gecko/20110204 Firefox/4.0b12pre

[Jamie Strandboge (jdstrand)]

This was fixed in 4.0~b11+build3+nobinonly-0ubuntu1.