399651 - Appending text to a <textarea> via JS gets progressively slower.

Status: NEW

(Core :: DOM: Editor, defect, P5)

Description

[Justin Dolske [:Dolske]]

Attachment: Testcase

I was writing a little JS utility to convert an image to HTML (using a table with 1-pixel sized cells). The first-pass implementation basically did:

while (stuff) {
    nextline = "another line of text\n"
    textarea.value += nextline;
}

As the textarea accumulates a few hundred lines, it becomes slower and slower. Feels like this is probably O(n), as the speed drops fairly gradually.

Attached is the utility I was writing. I have it calling confirm() at constant intervals to you can bail out when when it becomes too slow.

This is probably another variation of our DOM being slow, but I thought I should file this anyway.

Comment 1

[Justin Dolske [:Dolske]]

Attachment: Testcase image

Image for the test case... Save this and the .html testcase, and enter the filename of this image into the testcase's text box.

Comment 2

[:Gavin Sharp [email: [e-mail]]]

We have existing bugs on this, I think... You probably figured out that using "+=" means it needs to get the value each time it sets it, and that building up the string and then setting it once is much faster.

Comment 3

[:Gavin Sharp [email: [e-mail]]]

Dupe of bug 190147?

Comment 4

[Boris Zbarsky [:bzbarsky]]

Yeah.  Worse yet, the actual set is slow because it involves parsing the string.  So this is an O(N^2) algorithm with a decently big constant.

I don't think we'll get much benefit here until we fix bug 240933.  Then this might still be O(N^2), but we can check.

I think it's worth keeping this separate from bug 190147 because of the increasing string length and profiling once bug 240933 is fixed.

Comment 5

[Justin Dolske [:Dolske]]

190147 does look nearly the same; guess I overlooked that in my search.

Using a temporary JS var instead of textarea.value was the obvious workaround here, the script runs in a second or so now.

Comment 6

[Jeff Walden [:Waldo]]

How could this algorithm be anything other than O(n^2), without specializing how .value is stored/set in concatenations using, say, a pair of substrings to compose the whole, a la ropes[0]?  (That could be a nice thing to do for Moz2, actually, depending how much freedom we have with the implementation.)  JS already does something like this, hence why keeping it in a JS variable sped it up so much.

0. http://en.wikipedia.org/wiki/Rope_%28computer_science%29

Comment 7

[Boris Zbarsky [:bzbarsky]]

> How could this algorithm be anything other than O(n^2)

If resizing a string and appending another string to it is O(1) in string length.

Comment 8

[Biju]

Justin, in your case we can improve speed by hiding textarea while updateing
see bug 504784 comment 7

Comment 9

[(no longer active)]

Justin, how does this look to you now that bug 240933 is fixed?

Comment 10

[Justin Dolske [:Dolske]]

Still beachballs for a couple seconds (with the confirm() commented out from the testcase). I _think_ that's better than it used to be, but I really don't remember, and we've done a wee bit of other perf work in the interim. Would have to profile to see what's still slow.

Comment 11

[Boris Zbarsky [:bzbarsky]]

I profiled this.  About 25% of the time is silly: since the image is in the document, image.width has to flush layout because in a document .width depends on layout, and that means flushing out all the style changes for the scrollbars(!) and the text reflow for all the text we have appended.

Most of the rest is under the value setter, and looks a lot like the things we already analyzed in bug 190147.

Comment 12

[(no longer active)]

(In reply to comment #11)
> I profiled this.  About 25% of the time is silly: since the image is in the
> document, image.width has to flush layout because in a document .width depends
> on layout

Is that true if the image is not scaled?

Comment 13

[Boris Zbarsky [:bzbarsky]]

We have to flush layout to determine whether it's scaled, no?

Comment 14

[(no longer active)]

(In reply to comment #13)
> We have to flush layout to determine whether it's scaled, no?

Hmm, yes.  I guess you're right...  That's sad.

Comment 15

[Boris Zbarsky [:bzbarsky]]

Most things involving layout flushes are.  :(

Comment 16

[Boris Zbarsky [:bzbarsky]]

I should note that image.naturalWidth does NOT need to flush, and does what you'd actually want here....

Comment 17

[Boris Zbarsky [:bzbarsky]]

The other thing that might be somewhat interesting is making layout flushes indicate what we're really flushing, so we can skip reflow roots that can't affect the answer.  We'd still need to flush all the style stuff, though.

Comment 18

[Carlos Alén Silva]

This bug also affects Windows 7, not just Mac. So maybe "Platform:      x86 Mac OS X " should be "Platform:      x86 All".

Comment 19

[Jens Stutte [:jstutte]]

Bulk-downgrade of unassigned, >=3 years untouched DOM/Storage bug's priority.

If you have reason to believe this is wrong, please write a comment and ni :jstutte.