Closed Bug 581747 Opened 12 years ago Closed 12 years ago

Avoid n^2 performance when using JSOP_CONCATN


(Core :: JavaScript Engine, defect)

Not set





(Reporter: alangpierce, Assigned: luke)




(1 file)

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

endResult += "\n" + r;


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.
Blocks: WebJSPerf
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.

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
string "\n"
getlocal r
concatn 2

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

getlocal endResult
string "\n"
getlocal r
concatn 3

So, we can just go back to the first (without reintroducing the actual bug fixed 558446).
Assignee: general → lw
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?
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.
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!
Attached patch rm concatnSplinter Review
Waldo, you've been with concatn its entire life; I think it only right that you sign its death warrant.
Attachment #460761 - Flags: review?(jwalden+bmo)
Oh, right, I should mention that I did not observe any change in SS with this patch.
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.  ;-)
Attachment #460761 - Flags: review?(jwalden+bmo) → review+
Actually, it was a form of laziness: was complaining about the opcodes not being densely packed and I didn't know you could just stick in "JSOP_UNUSEDXXX"
Closed: 12 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.