667412 - Loading lots of text in a narrow textarea is very slow

Status: NEW

(Core :: Layout: Block and Inline, defect)

Description

[Simon Montagu :smontagu]

Attachment: Testcase

I encountered this when trying to assess performance with the patch for bug 664087, and also whether recent bidi performance work has fixed bug 376359, but this is not a bidi issue -- this version of the testcase is LTR text only and still shows the problem.

In a profile of loading the testcase, 77.4% is spent in nsLineBox::RFindLineContaining, called from nsBlockFrame::AddFrames. Apparently we are hitting the "less common" case referred to in the comment there:

    // XXX_perf This is technically O(N^2) in some cases, but by using
    // RFind instead of Find, we make it O(N) in the most common case,
    // which is appending content.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Ah, this is an interesting case.  So the point here is that the textarea has tons of lines and that some of them are longer than the textarea width.  Each such line causes us to wrap and create a continuation, and then we have to find the right line to put that continuation in.  And we do the search in reverse, but the continuations are inserted all over, so it ends up being O(N^2).  Messing with the search order would not help here, of course.

fantasai, do you think we can try to do better here after the split?  If so, we should add a dep.

Comment 2

[Simon Montagu :smontagu]

What I was thinking was that when we call InsertFrames from nsTextFrame::SetLength we already know the line (at least some of the time), so maybe we could pass it in and avoid the search?

Comment 3

[Boris Zbarsky [:bzbarsky]]

We could try...

This seems like a situation that would be helped by something like a line cursor, actually: during reflow, search forward from the line currently being reflowed.

Comment 4

[Simon Montagu :smontagu]

Passing in the line helps some, but it leaves us spending 44% of the time in nsLineBox::IndexOf, called from BuildTextRuns via the nsBlockInFlowLineIterator ctor.

Comment 5

[fantasai]

I doubt the split would make a difference in what we can do here.

Comment 6

[Boris Zbarsky [:bzbarsky]]

OK.  Do we have existing bugs on making it possible to add kids to a block without finding the right line?  I seem to recall some proposals about that...

Comment 7

[Boris Zbarsky [:bzbarsky]]

This might be the same issue as bug 561578.

Comment 8

[Boris Zbarsky [:bzbarsky]]

Or more precisely, the underlying problem is the same: bug 190147.

Comment 9

[Cedric Vivier [:cedricv]]

A much shorter yet reproducible testcase on any textarea (not specially narrow) seems to be Github's stylesheet ( https://a248.e.akamai.net/assets.github.com/stylesheets/bundle_github.css - 'only' 300kB with very long lines).

Comment 10

[Boris Zbarsky [:bzbarsky]]

The key part for this bug is that the textarea be narrow compared to the width of a typical line so there are lots of continuations being created.

Comment 11

[(no longer active)]

As far as I can tell, fixing bug 682052 is the only way that this will ever be fixed, right?

Comment 12

[Boris Zbarsky [:bzbarsky]]

That's the only way this will get _closer_ to being fixed.  Once we fix that, we might find another hotspot.  :(

Comment 13

[Randell Jesup [:jesup] (needinfo me)]

Current Gecko Profiler trace says 76% in nsLineBox::RFindLineContaining() (no surprise), and 17% in nsTextFrame::LastInFlow(), and 2% in BuildTextRuns()