Closed Bug 581747 Opened 11 years ago Closed 11 years ago
Avoid n^2 performance when using JSOP
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.
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
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).
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!
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: imacros.py was complaining about the opcodes not being densely packed and I didn't know you could just stick in "JSOP_UNUSEDXXX"
Status: NEW → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.