339935 - Performance regression rendering a line with lots of bidi frames

Status: RESOLVED FIXED

(Core :: Layout: Text and Fonts, defect)

Description

[Uri Bernstein]

Following the fix to bug 330373, rendering a single line containing a large number of bidi frames (i.e., frames that need to be split) now takes much longer (performance is O(n^2)), due to repeated calls to nsLineBox::Contains (which is O(n)).

Bug 339699 caused nsLineBox::Contains not to be called for non-bidi frames, and thus resolved the more typical case where most frames aren't actually bidi. However, it had no effect on the case where all frames on the line are themselves bidi.

I'll attach a testcase immediately.

Comment 1

[Uri Bernstein]

Attachment: testcase

A single line with 20,000 bidi frames on it.
This renderes for me in about 7 seconds in a 1.8 branch build (which doesn't have bug 330373), and in around 35 seconds in a 2006-05-31 trunk build.

Comment 2

[Uri Bernstein]

Since we're traversing the frame list linearly (only going forward), we don't actually need to search the entire line in order to see whether it contains our frame. We only need to start looking from the previous frame we found on the line.

My idea is to create a version of nsLineBox::Contains which would receive a reference to a struct containing a frame and a number (the frame's index within the line). The method will start searching from the given frame, and, if the requested frame is found, will update the struct so it can be used for the next call.

Does this sound right?

Comment 3

[Uri Bernstein]

Attachment: like this?

Assuming the general idea is right, I'd appreciate suggestions for better names (especially for the struct).

Also, this probably makes the changes made in bug 339699 unnecessary. Should I get rid of them?

Comment 4

[Boris Zbarsky [:bzbarsky]]

I'd prefer that roc or dbaron review this... I don't really know this code well enough to be confident in doing a quick review, and don't have time for a slow review for at least a week, probably.

Comment 5

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

I think you can get away without the struct. Just pass the last frame you found; Contains() can then search from that frame; you'll know you reached the end of the line when you reach null or the first frame of the next line. Then perhaps a good name would be

  PRBool ContainsAfter(nsIFrame* aFrameInLine, nsIFrame* aFrameToFind);

Comment 6

[Uri Bernstein]

(In reply to comment #5)
> you'll know you reached the
> end of the line when you reach null or the first frame of the next line.
> 

Except I haven't figured out a way to get the next line (and its first frame) from within a method of nsLineBox.
Please clue me in.

Comment 7

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

I guess you'll have to pass the line iterator as a parameter.

First child is mFirstChild.

Comment 8

[Uri Bernstein]

Attachment: patch v.2

Sorry for the delay.

I had to pass in end_lines as well, because trying to get mFirstFrame on end_lines triggers an assertion (instead of just returning null as I originally expected).
I'm passing the iterator into ContainsAfter by value, because I don't want the ++'ing to happen on the actual iterator I'm using outside. I hope this is the right way to do it.

Comment 9

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

Comment on attachment 224572 [details] [diff] [review]
patch v.2

Looks good to me. Please add a comment to ContainsAfter describing what it does and what the parameters mean.

Comment 10

[Uri Bernstein]

Checked in, with comment:

Checking in layout/generic/nsLineBox.h;
/cvsroot/mozilla/layout/generic/nsLineBox.h,v  <--  nsLineBox.h
new revision: 1.76; previous revision: 1.75
done
Checking in layout/generic/nsLineBox.cpp;
/cvsroot/mozilla/layout/generic/nsLineBox.cpp,v  <--  nsLineBox.cpp
new revision: 1.102; previous revision: 1.101
done
Checking in layout/base/nsBidiPresUtils.cpp;
/cvsroot/mozilla/layout/base/nsBidiPresUtils.cpp,v  <--  nsBidiPresUtils.cpp
new revision: 1.78; previous revision: 1.77
done