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.

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

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.

Dupe of bug 190147?

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.

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.

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

> 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.

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

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

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.

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.

(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?

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

(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.

Most things involving layout flushes are. :(

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

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.

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