43914 - PERF: nsBlockFrame::ReflowDirtyLines slow

Status: VERIFIED FIXED

(Core :: Layout, defect, P1)

Description

[Joe Francis]

Open composer.  Observe the typing speed in an empty document.  Now type in a 
line of text and hit return.  Copy+Paste this up to 1000 lines.  Now Go to the 
front of the document and type.  It's real slow.  

For each character you type, ReflowDirtyLines() is reflowing the line you are on 
and every line below it.  You will see some reasonalbe number of calls to 
ReflowDirtyLines(), but an astronomical # of calls to ReflowLine().  

We need some optimization here.  This makes the editor rather toylike for large 
text documents.  thanks to mjudge for doing a quantify run for me to help 
identify this problem.

Comment 1

[Joe Francis]

setting keywords and milestone

Comment 2

[Jay Patel [:jay]]

Putting on [nsbeta2-] radar. Not critical to beta2.  Adding "nsbeta3" keyword 
for consideration of a fix for that milestone, it is a performance issue.

Comment 3

[Nisheeth Ranjan]

Re-assigning to waterson and ccing buster.

Comment 4

[Chris Waterson]

We need to figure out if we can nuke this code:

http://lxr.mozilla.org/mozilla/source/layout/html/base/src/nsBlockFrame.cpp#4433

I'll dig into it this week.

Comment 5

[Chris Waterson]

Attachment: hack

Comment 6

[buster]

scary patch.  what sort of testing have you done?

Comment 7

[Simon Fraser [no longer active]]

cc kin who messed this this before.

Comment 8

[Chris Waterson]

buster: I've had it in my tree since about 2000-08-05, but haven't really done
any focused testing on it.

Comment 9

[buster]

I think it's worth a little focused testing.   Let's think about why these lines 
were originally added, build test cases that stress those situations, and 
convince ourselves that the code still works well.  I'm particularly interested 
in making sure we paint correctly in response to incremental changes that cause 
frames to be pushed and pulled between lines.  Typing in the editor, using the 
DOM to change the height and width of objects on a page, etc.

Comment 10

[Joe Francis]

Chris, are these the same changes that Simon and I tested with a while back?  If 
so, we saw really bad behavior in the editor when we used them.  If I recall, 
contents of a line that got wrapped to a later line were not properly drawn.

Comment 11

[Chris Waterson]

There are two places in this code where we eagerly invalidate, and they're very
near to one another. (Long live Bina!)

Just removing the *first* of these (which is what the patch shows) seems to not
have any ill effects. But, like I said, I haven't really figured out what that
code was put there for, or how to test it.

I also see evilness when removing *both* eager invalidates.

Comment 12

[Joe Francis]

ok, thanks.  I'll try using your patch and doing some testing.  

Comment 13

[Jason Eager]

Does this also affect slowness in <textareas>? If so, PLEASE bump this bug up in
priority. Speed in text areas is STILL uncomfortably slow on my pentium II 233
system.

Comment 14

[Dan Rosen]

jce2: can you quantify "uncomfortably slow"? because uncomfortable is bound to
happen on debug builds. unacceptable is different (like, two characters per
second)...

Comment 15

[Chris Waterson]

I've been studying this code a bit; just wanted to make some notes. It gets
invoked when a "break-after" (NS_INLINE_IS_BREAK_AFTER) is requested by a frame.
There are only three frame types that will explicitly request a break-after:

- text frames, with "white-space: pre"
- <br> frames
- <spacer> frames

A generic inline frame may convert a break-before into a break-after in some
condition I haven't grokked yet;

http://lxr.mozilla.org/mozilla/source/layout/html/base/src/nsInlineFrame.cpp#611

Furthermore, if SplitLine() actually did have to push frames (need to figure out
how to construct a case where this would happen), it creates a new line box,
whose initial status will be "dirty". That means that the loop in
ReflowDirtyLines will, by default, flow the pushed frames in the new, dirty line
box.

So, is there a case where we *didn't* have to push frames, and the next line box
is not dirty, but we still need to flow it anyway? Trying to figure that out...

Comment 16

[Chris Waterson]

This has missed the nsbeta3 train as far as I'm concerned, but should be
strongly considered for RTM. If we determine that we can safely remove this
code, it will *dramatically* improve mail compose performance on long messages
(e.g., any "reply to" or "forward" where caret is positioned at the top of a
long message). This is causing O(n) behavior in mail messages, because, by
default, mail messages are formatted in a single block using <br> elements.

Comment 17

[buster]

I've been testing with this on WinNT for a while, so far so good.

Comment 18

[Joe Francis]

i told chris via email, but adding to bug report now.  i tested with this on mac 
for a while with good results.

Comment 19

[buster]

fix checked into trunk (*not* branch)
this could make NS6 RTM if we get sufficient testing to convince ourselves that
the risk is very low.  If you pull and run with this fix from the trunk, please
report back your findings in this bug report.  Thanks!

Comment 20

[Chris Waterson]

pdt grafitti

Comment 21

[buster]

bad news, hombre.  the hack doesn't work in all cases.  it caused 56102 on the
trunk, so I'm backing it out.  we need some extra logic, not just #if'ing out
the code.

Comment 22

[buster]

fix backed out of trunk

Comment 23

[Joe Francis]

rats. :-(  sorry i didnt catch this in my testing.

Comment 24

[karnaze (gone)]

Marking rtm-. It sounds like PDT will not approve this.

Comment 25

[Chris Waterson]

End-of-milestone reality check.

Comment 26

[Chris Waterson]

Okay, so I just re-applied this patch in my tree, and it doesn't appear to 
regress bug 56102. I'll attach an updated patch; kin, jfrancis, sfraser, or 
anyone else, could you help me test it?

Comment 27

[Chris Waterson]

Attachment: updated patch; don't force next line to be dirty in break-after case

Comment 28

[rbs]

Gave a go the patch. I am still able to reproduce bug 56102 though.
This is how it is documented over there:

------- Additional Comments From [e-mail] 2000-10-11 13:34 -------

This bug affects mozilla and commercial trunk builds only.

This is how to reproduce this particular bug:
 * new composer window
 * type 123
 * press control-b (bold)
 * type abc
 * press return/enter
 * type def [note: you won't see this text yet]
 * press control-b (un-bold)
 * type 456
========================

Additionally: after the return/enter step, no matter what you type (however long 
that might be, including with more return/enter/etc), you don't see your text.

Comment 29

[rbs]

BTW, Edit->Preferences->Debug->Events->"Show frame counts" proves to be an 
extremely useful gem to see how slowly the incremental reflow can become. In 
Composer, it shows that all the lines get reflowed from where Ctrl-b (bold) 
and enter/return is pressed (even worse than what is happening in bug 67495), 
i.e., after typing:

line 1
line 2
...
line n Ctrl-b Return
line n+1
...
line n+m

then typing one character on line n+m causes all lines n..n+m to be reflowed.

Comment 30

[Chris Waterson]

Attachment: DOM-only test case that illustrates the regression, bug 56102

Comment 31

[Chris Waterson]

Attachment: don't force next line to be dirty during reflow of break-after; make sure to dirty continuing frames in ReflowDirtyChild()

Comment 32

[Chris Waterson]

Okay, I think I've got the sauce. This is why we removing that code caused a 
regression. We start with a content model that looks like this (minus the 
whitespace):

  <body>
  abc<b>def<br>
  <br></b>
  </body>

This makes a frame model like this:

  block(body)<
    line<
      text<
        abc
      >
      inline(b)<
        text<
          def
        >
        frame(br)
      >
    >
    line<
      inline(b) <
        frame(br)
      >
    >
  >

When we insert new content into the <b> span after the first <br>, the 
inline frame for the <b> span marks itself dirty, and calls the body frame's 
ReflowDirtyChild() method. nsBlockFrame::ReflowDirtyChild() uses FindLineFor() 
to find the line containing the <b> span's primary frame: it finds the first 
line, and marks only that line dirty.

So, the problem is that if we're not going to force-dirty the next line after a 
break-after (which is what my initial patch did), then we need to make sure that 
ReflowDirtyChild() marks any continuing frames as dirty.

I'd love it if some people could give this a try!

Comment 33

[Chris Waterson]

I think I've got the kinks out; soliciting some hot r= action. (Testing 
appreciated, too!)

Comment 34

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Makes sense to me, although this kind of change scares me a bit because I'm not
sure how you can tell that the code you're removing wasn't covering something
else up.  r=dbaron if you feel you've tested it on enough odd cases.  (I wonder
how hard it would be to further optimize this so that we mark only the right
frame(s) dirty.)

Comment 35

[rbs]

There were two spots with "Mark next line dirty in case SplitLine didn't 
end up pushing any frames". Is this analysis relevant to both of them?

Comment 36

[Chris Waterson]

Thanks, dbaron. I'd like to get a little bit of private shakedown from some 
editor people before trying it on the trunk.

> (I wonder how hard it would be to further optimize this so that we
> mark only the right frame(s) dirty.)

Yeah, I've been thinking about that. I think the problem starts with 
nsInlineFrame, because there's not much we can do if the _whole_ inline frame 
blandly says, ``I'm dirty'' (which it always does).

One way to improve this might be to alter the semantics of ReflowDirtyChild() a 
bit to allow a more deeply nested child to be passed up to the parent's 
ReflowDirtyChild() method. (Currently, it's assumed -- at least in nsBlockFrame 
-- that only a direct child will be passed in.)

So, if we did this, we'd need to either 1) alter nsBlockFrame's 
ReflowDirtyChild() so that it walked the frame hierarchy in each line (as 
opposed to just the top level frames), or 2) keep the path to the most deeply 
nested dirty child. By doing that, we could constrain the dirtiness to just the 
lines affected.

For example:

  abc<b>def<br>
  ghi<i>jkl<br>
  mno</i>pqr<br>
  stu</b>vwx<br>

With the current code, changing the ``jkl'' text node would cause all four lines 
to be dirtied. If we instead passed up the text node as the dirty child to the 
block frame, the block frame could detect that only line 2 need be dirtied.

Anyway, could be a next step to take if we continue to have performance 
problems.

Comment 37

[Chris Waterson]

rbs: possibly. I'll take a look.

Comment 38

[rbs]

Also, since the initially intention was just to mark the next line. Why, then, 
there is no break out of the loop once the immediate next line is marked?

Comment 39

[Chris Waterson]

rbs: I assume you're referring to the do-while loop that marks continuing frames
dirty in ReflowDirtyChild()? We can't just stop after dirtying the next line,
because _each_ line that the dirty frame continues into must be dirtied. Look at
the frame model from my comment on 2001-05-09 19:56, and imagine that the <b>
span continues across several more <br>-broken lines. If we just dirtied the
line containing the first continuing frame, then the lines containing second
through nth continuing frames would exhibit the bug.

Comment 40

[Chris Waterson]

Anyone had a chance to try the patch? Feedback much appreciated.

rbs wrote:

> There were two spots with "Mark next line dirty in case SplitLine didn't 
> end up pushing any frames". Is this analysis relevant to both of them?

The other place where we splt the line but still force the next line to be dirty 
is the case when the frame's reflow wasn't completed; i.e., 
|NS_FRAME_IS_NOT_COMPLETE(frameReflowStatus)|. Since this is a case where we 
explicitly create a continuation frame, it's not clear to me exactly _when_ this 
will occur. I'm not sure if the archaelogy is worth doing at this point, as this 
change deals with the obvious performance problem.

Also, did my comments on 2001-05-11 10:16 address your concerns?

Comment 41

[rbs]

Yes, they answer my question, and yes, you seem to have the "sauce" this time 
around... As far as I could test, your patch is behaving as the existing code.
The previous regression from bug 56102 is now gone. I was particularly sruck by 
the huge performance win in plain text editing. With your patch, only the
previous and current lines are marked dirty. With the old code, the whole 
paragraph was marked dirty... [Testing can be conveniently made within the 
single interface of Composer by switching between "normal mode" (WYSYWIG 
editing) and "<HTML> source mode" (plain text editing), and setting the pref:
Edit->Preferences->Debug->Events->"Show frame counts".]. 

Composer and Mail/News folks, you should definitively give a go to this patch to 
see how it trades. I saw that it fully resolves the problem described at the 
opening of this bug. Only the first line (out of the 1000 lines) now get 
reflowed as you wanted.

Comment 42

[Marc Attinasi]

This is great stuff, Chris. sr=attinasi

Comment 43

[Chris Waterson]

Fix checked in.

Comment 44

[Chris Waterson]

Reopened, cause bug 81118.

Comment 45

[Chris Waterson]

Attachment: test case illustrating regression from bug 81118

Comment 46

[rbs]

Remembering your explanation to my question about the second "dirty spot", I
wondered what will happen if this other troublesome spot was executed under the 
same condition where the other spot is executed, and so I tried adding an 'if' 
clause:

+  if (NS_FRAME_IS_NOT_COMPLETE(frameReflowStatus)) {
      // Mark next line dirty in case SplitLine didn't end up
      // pushing any frames.
      nsLineBox* next = aLine->mNext;
      if ((nsnull != next) && !next->IsBlock()) {
        next->MarkDirty();
      }
+  }

This cut down on the number of reflows. And furthermore, it doesn't seem to 
exhibit the bug in your latest test case (attachment 34905 [details]). Any thoughts about 
the suitability or possible nasty side-effects of this patch?

Comment 47

[Chris Waterson]

Boioioioing! Great idea! This would be in lieu of the code that dirties the 
continuing frames, right? If so, r=waterson.

Comment 48

[rbs]

Yes, just wrapping the existing code in an 'if':

3550      if (NS_FRAME_IS_NOT_COMPLETE(frameReflowStatus)) {
3551        // Create a continuation for the incomplete frame. Note that the
3552        // frame may already have a continuation.
3553        PRBool madeContinuation;
3554        rv = CreateContinuationFor(aState, aLine, aFrame, madeContinuation);
3555        if (NS_FAILED(rv)) {
3556          return rv;
3557        }
3558        // Remember that the line has wrapped
3559        aLine->SetLineWrapped(PR_TRUE);
3560      }
3561 
3562      // Split line, but after the frame just reflowed
3563      nsIFrame* nextFrame;
3564      aFrame->GetNextSibling(&nextFrame);
3565      rv = SplitLine(aState, aLineLayout, aLine, nextFrame);
3566      if (NS_FAILED(rv)) {
3567        return rv;
3568      }
3569 
+ if (NS_FRAME_IS_NOT_COMPLETE(frameReflowStatus)) {
3570      // Mark next line dirty in case SplitLine didn't end up
3571      // pushing any frames.
3572      nsLineBox* next = aLine->mNext;
3573      if ((nsnull != next) && !next->IsBlock()) {
3574        next->MarkDirty();
3575      }
+ }
3576

Doing this seems to be in agreement with your earlier analysis (cf. "Additional 
Comments From Chris Waterson 2001-05-09 19:56"). Looking at the code-section 
(3550ff), that's exactly the place where the continuing frame is being made, and 
so by dirtying the line right there, it eliminates the risk of missing to do so 
later (i.e., if the code later swings in an unexpected direction...). And the 
'if' test that I added is helping to restrict marking the next line dirty to the 
case where indeed a continuation was made (as opposed to a "blind" marking which 
is unnecessary if no continuation was actually made). I haven't yet tried the 
block & table regression tests though. It is now that I am understanding a bit 
more how to assess the correctness/completeness of the patch.

Comment 49

[Simon Fraser [no longer active]]

Attachment: Latest nsBlockFrame patch

Comment 50

[rbs]

Block and table regression tests: Passed!
sr=?

Comment 51

[Chris Waterson]

You can certainly count my r= either way.

Comment 52

[rbs]

Attachment: Final patch - also fix bug 67495

Comment 53

[rbs]

Building upon the same analysis, it now became clear why the patch that buster 
once attached on bug 67495 worked so well (see on bug 67495: "Additional 
Comments From [e-mail] 2001-02-12 16:46 - attachment 25103 [details] [diff] [review]). I have 
added this patch here because the crux of the matter is expounded here.

If you enable reflow count now, you will see that the whole paragraph which has 
the text-control is reflowed when the first character is typed in. Then, as 
other characters are typed-in, only the first line is reflowed. The full reflow 
at the beginning happens because the target of the reflow is the containing 
block frame when the first character is typed-in (I coincidentally noted this in 
bug 50758 in the past...).

Comment 54

[Simon Fraser [no longer active]]

sr=sfraser

Comment 55

[rbs]

Resolving as FIXED. I finally left buster's patch out of the equation because I 
noted in bug 67495 that attinasi had some reservations about it. Not enough
testing. And this IsIncrementalDamageConstrained() function may be too
restrictive here because the input & textarea have a "pile" of block frames
for their presentation, and maybe not all of them should be interrupted. Plus, 
that function looks expensive to me, it crawls the frame tree at the slightest 
opportunity. It could possibly be be replaced by a cached value or something 
lazily initialized in aState.

Let's see how this one goes, hoping it doesn't suffer the fate of other attempts 
so far :-)

Comment 56

[Christian Mattar]

Great! I hope this patch will finally make ActiveState's Komodo useful on larger 
scripts.

Comment 57

[Chris Petersen]

Marking verified per last comments.