Closed
Bug 1263490
Opened 8 years ago
Closed 8 years ago
Make finding firstDollarIndex faster in RegExpReplace.
Categories
(Core :: JavaScript Engine, defect)
Core
JavaScript Engine
Tracking
()
RESOLVED
FIXED
mozilla49
People
(Reporter: arai, Assigned: arai)
References
Details
Attachments
(4 files)
1.29 KB,
patch
|
till
:
review+
|
Details | Diff | Splinter Review |
5.17 KB,
patch
|
till
:
review+
|
Details | Diff | Splinter Review |
16.58 KB,
patch
|
h4writer
:
review+
|
Details | Diff | Splinter Review |
4.27 KB,
patch
|
h4writer
:
review+
|
Details | Diff | Splinter Review |
In RegExpReplace, we search "$" in replaceValue string, but std_String_indexOf is not fast, as it's not inlineable. To search single character, manual loop with std_String_charCodeAt is faster, as std_String_charCodeAt is inlineable.
Assignee | ||
Comment 1•8 years ago
|
||
Or perhaps we could add dedicated inlineable intrinsic to search single character (or "$" specifically) from a string, and also fold it to a integer constant if the argument is a constant string.
Assignee | ||
Comment 2•8 years ago
|
||
Looks like, std_String_indexOf is faster than JS loop with std_String_charCodeAt if the replaceValue string is long (about 10 chars), I think in many case replaceValue string is short tho, just replacing it with JS loop should be bad. So, if we use JS loop, we should check the length of string and switch between JS loop and std_String_indexOf. Also, at least we should avoid std_String_indexOf if the length is 0 (and 1 ?). maybe, adding a dedicated intrinsic is better solution.
Assignee | ||
Updated•8 years ago
|
Summary: Find firstDollarIndex with JS loop in RegExpReplace. → Make finding firstDollarIndex faster in RegExpReplace.
Assignee | ||
Comment 3•8 years ago
|
||
In Octane RegExp, all String#replace call uses empty string as replaceValue. so, just to improve the benchmark score, what we should do is that check if the length of the replaceValue is 0, and skip std_String_indexOf call. Of course, that case could be a common usage, so it would benefit other cases. Will try applying that as a first step, then add inlinable self-hosting instrinsic. Also, we could skip std_String_indexOf if the length of the replaceValue is 1, as it cannot contain a valid substitution, even if the first character is "$". (in that case, the value of firstDollarIndex is wrong, but it doesn't matter) Then, about constant folding, RegExpReplace isn't inlined to String_replace even if the function is known to be RegExpReplace. so the value of replaceValue cannot be a constant string. Will look into how the inlining is prevented.
Assignee | ||
Comment 4•8 years ago
|
||
This improves the Octane RegExp score from 3824 to 3995. Will search the testcase that uses more than 2-length string and check the performance, for remaining parts.
Attachment #8742731 -
Flags: review?(till)
Assignee | ||
Comment 5•8 years ago
|
||
so far, the inlinable intrinsic doesn't improve much on any of Kraken/SunSpider/Octane bench :/
Assignee | ||
Comment 6•8 years ago
|
||
The length of the RegExpReplace (about 1600) prevents the inlining. maybe, we can split the generic part into different function once bug 1264264 gets resolved, as it adds optimized path for most cases.
Comment 7•8 years ago
|
||
Comment on attachment 8742731 [details] [diff] [review] Part 1: Do not search for dollar if the length of replaceValue is 0 or 1. Review of attachment 8742731 [details] [diff] [review]: ----------------------------------------------------------------- Good idea.
Attachment #8742731 -
Flags: review?(till) → review+
Assignee | ||
Comment 8•8 years ago
|
||
Thank you for reviewing :) I'll land Part 1 first, and leave this bug open, for further optimization after bug 1265992 or bug 1264264.
Keywords: leave-open
See Also: → 1264264
Assignee | ||
Comment 9•8 years ago
|
||
https://hg.mozilla.org/integration/mozilla-inbound/rev/4226c06dcf1ffa0d965bf6f8c77adf992a8b7d6b Bug 1263490 - Part 1: Do not search for dollar if the length of replaceValue is 0 or 1. r=till
Comment 10•8 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/4226c06dcf1f
Assignee | ||
Comment 11•8 years ago
|
||
bug 1264264 reduced the bytecode length of RegExpReplace and now that it can be inlined in some case (still it could hit maxInlineDepth_ tho) We could fold firstDollarIndex calculation into an integer constant. Part 1 adds intrinsic, Part 2 adds JIT inlined code, and Part 3 adds constant folding.
Attachment #8744683 -
Flags: review?(till)
Assignee | ||
Comment 12•8 years ago
|
||
Added fully inlined code for non-rope and OOL code for rope.
Attachment #8744684 -
Flags: review?(hv1989)
Assignee | ||
Comment 13•8 years ago
|
||
And added constant folding, including not-found (-1) case.
Attachment #8744685 -
Flags: review?(hv1989)
Comment 14•8 years ago
|
||
Comment on attachment 8744683 [details] [diff] [review] Part 2: Add GetFirstDollarIndex intrinsic and use it in RegExpReplace. Review of attachment 8744683 [details] [diff] [review]: ----------------------------------------------------------------- Makes sense. ::: js/src/builtin/RegExp.h @@ +133,5 @@ > +extern bool > +GetFirstDollarIndex(JSContext* cx, unsigned argc, Value* vp); > + > +extern bool > +GetFirstDollarIndexRaw(JSContext* cx, HandleString str, int32_t* index); I assume this is exposed because it's inlined in the next patch? ( Just checked: yes :) )
Attachment #8744683 -
Flags: review?(till) → review+
Comment 15•8 years ago
|
||
Comment on attachment 8744684 [details] [diff] [review] Part 3: Inline GetFirstDollarIndex intrinsic. Review of attachment 8744684 [details] [diff] [review]: ----------------------------------------------------------------- We should really try to inline more of these. (C++ and assembly code are easier to introduce errors. Adding selfhosted code doesn't increase attack surface). Since charCodeAt can be inlined in ionbuilder this could be selfhosted like: > for (var i=0; i<str.length; i++) { > if (str.charCodeAt(i) == "$".charCodeAt(0)) > return i; > } > return -1; The only reason to not do that currently, is that we will have the "isRope" check on every iteration. You did hoist it here out of the loop. Not sure how much of a difference this makes, but should be a little bit slower, depending on branch prediction etc. In the long term IonMonkey will be able to reason about this and hopefully also hoist? On ropes this will be quite bad currently (performance wise) and we need to fix ionmonkey. Therefore r+'ing this. ::: js/src/jit/CodeGenerator.cpp @@ +2229,5 @@ > + masm.load16ZeroExtend(BaseIndex(chars, output, TimesTwo), temp); > + > + masm.branch32(Assembler::Equal, temp, Imm32('$'), &done); > + > + masm.addPtr(Imm32(1), output); masm.addl(Imm32(1), output); @@ +2258,5 @@ > + > + Label isLatin1, done; > + masm.branchLatin1String(str, &isLatin1); > + { > + FindFirstDollarIndex(masm, str, len, temp0, temp1, output, false); FindFirstDollarIndex(masm, str, len, temp0, temp1, output, /* islatin1 = */ false); @@ +2263,5 @@ > + } > + masm.jump(&done); > + { > + masm.bind(&isLatin1); > + FindFirstDollarIndex(masm, str, len, temp0, temp1, output, true); FindFirstDollarIndex(masm, str, len, temp0, temp1, output, /* islatin1 = */ true);
Attachment #8744684 -
Flags: review?(hv1989) → review+
Updated•8 years ago
|
Attachment #8744685 -
Flags: review?(hv1989) → review+
Assignee | ||
Comment 17•8 years ago
|
||
https://hg.mozilla.org/integration/mozilla-inbound/rev/57cda0f2a8375f794735ac6be51f929bf068ed14 Bug 1263490 - Part 2: Add GetFirstDollarIndex intrinsic and use it in RegExpReplace. r=till https://hg.mozilla.org/integration/mozilla-inbound/rev/42dc2c780dd6c41cca64248fae97cfdc14c8cbd7 Bug 1263490 - Part 3: Inline GetFirstDollarIndex intrinsic. r=h4writer https://hg.mozilla.org/integration/mozilla-inbound/rev/f7bcef10dd89fd62076ef6585c11d4823300c2ee Bug 1263490 - Part 4: Fold GetFirstDollarIndex into a integer constant. r=h4writer
Comment 18•8 years ago
|
||
bugherder |
https://hg.mozilla.org/mozilla-central/rev/57cda0f2a837 https://hg.mozilla.org/mozilla-central/rev/42dc2c780dd6 https://hg.mozilla.org/mozilla-central/rev/f7bcef10dd89
Status: NEW → RESOLVED
Closed: 8 years ago
status-firefox49:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla49
Assignee | ||
Updated•8 years ago
|
You need to log in
before you can comment on or make changes to this bug.
Description
•