581747 - Avoid n^2 performance when using JSOP_CONCATN

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alan Pierce]

In sunspider's string-validate-input, if you change line 86:

endResult += "\n" + r;

to

endResult = endResult + "\n" + r;

then the test takes about 500 times as long (5 seconds on my machine). The reason is that we emit JSOP_CONCATN here instead of doing our usual string concatenation. ConcatN builds a JSCharBuffer, without doing optimizations like building a rope or trying to realloc the buffer from the leftmost string. So, repeatedly doing ConcatNs like this causes us to copy the string each time, so we take n^2 time. This issue existed before ropes, so it's not a regression.

There are a few ways to fix this:
-Remove ConcatN entirely
-Make ConcatN build a rope
-Make ConcatN intelligently build a rope, avoiding string header creation when possible

I'm relatively sure that fixing this issue doesn't help us noticeably on sunspider or the v8 benchmarks.

Comment 1

[Brendan Eich [:brendan]]

I've been burned by every O(n^2) algorithm (save one) I've ever committed into SpiderMonkey.

I don't know whether JSOP_CONCATN is worth it, but we need to cast a wider net than SS and V8 benchmarket-ware to decide.

If CONCATN goes, so can JSOP_OBJTOSTR, if memory serves.

/be

Comment 2

[Luke Wagner [:luke]]

So I think this n^2 behavior is a recent regression from bug 558446.  Before that, when the emitter saw:

endResult = endResult + "\n" + r;

it would generate:

getlocal endResult
objtostr
string "\n"
getlocal r
objtostr
concatn 2
add

Totally forgetting about the mutable-realloc optimization, bug 558446 "optimized" this to be

getlocal endResult
objtostr
string "\n"
getlocal r
objtostr
concatn 3

So, we can just go back to the first (without reintroducing the actual bug fixed 558446).

Comment 3

[Luke Wagner [:luke]]

Or, I guess I didn't quite finish the idea in comment 2:

If concatn only begins after a string literal, and the realloc optimization only applies when the lhs is a mutable string, then, any place the optimization would apply, there will be an add.

However, with ropes, I think we also avoid n^2 behavior if the rhs is a mutable string.  Is that right Alan?

Comment 4

[Alan Pierce]

If we went to the pre-558446 behavior, then we'd fix this particular case because the growing case would be [a rope] + [result of ConcatN], just like we get when we do +=. The realloc optimization doesn't ever happen anymore (bug 578189 makes dependent strings point inside their base's string buffer, so calling realloc on a string buffer is unsafe now).

We'd still get n^2 behavior in cases where the string being grown is after the first string literal, so I think undoing bug 558446 (while staying correct) isn't the right way to go.

Comment 5

[Luke Wagner [:luke]]

Good point; comment 3 was too hasty a conclusion.  At the risk of forming a second too-hasty conclusion... death to concatn, long live ropes!

Comment 6

[Luke Wagner [:luke]]

Attachment: rm concatn

Waldo, you've been with concatn its entire life; I think it only right that you sign its death warrant.

Comment 7

[Luke Wagner [:luke]]

Oh, right, I should mention that I did not observe any change in SS with this patch.

Comment 8

[Jeff Walden [:Waldo]]

Comment on attachment 460761 [details] [diff] [review]
rm concatn

I wouldn't have shifted existing opcodes, just changed the opcode to unused, but hey, your time not mine.  ;-)

Comment 9

[Luke Wagner [:luke]]

Actually, it was a form of laziness: imacros.py was complaining about the opcodes not being densely packed and I didn't know you could just stick in "JSOP_UNUSEDXXX"

Comment 10

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/fd1faf906f00