If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

Avoid n^2 performance when using JSOP_CONCATN

RESOLVED FIXED

Status

()

Core
JavaScript Engine
RESOLVED FIXED
7 years ago
7 years ago

People

(Reporter: Alan Pierce, Assigned: luke)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

7 years ago
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.
(Reporter)

Updated

7 years ago
Blocks: 579390
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
(Assignee)

Comment 2

7 years ago
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
(Assignee)

Comment 3

7 years ago
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?
(Reporter)

Comment 4

7 years ago
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.
(Assignee)

Comment 5

7 years ago
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!
(Assignee)

Comment 6

7 years ago
Created attachment 460761 [details] [diff] [review]
rm concatn

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)
(Assignee)

Comment 7

7 years ago
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+
(Assignee)

Comment 9

7 years ago
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

7 years ago
http://hg.mozilla.org/mozilla-central/rev/fd1faf906f00
Status: NEW → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.