Make finding firstDollarIndex faster in RegExpReplace.

RESOLVED FIXED in Firefox 49

Status

()

defect
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: arai, Assigned: arai)

Tracking

Trunk
mozilla49
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox48 affected, firefox49 fixed)

Details

Attachments

(4 attachments)

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.
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.
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.
Summary: Find firstDollarIndex with JS loop in RegExpReplace. → Make finding firstDollarIndex faster in RegExpReplace.
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.
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)
so far, the inlinable intrinsic doesn't improve much on any of Kraken/SunSpider/Octane bench :/
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.
See Also: → 1265992
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+
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
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
See Also: → 1266764
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)
Added fully inlined code for non-rope and OOL code for rope.
Attachment #8744684 - Flags: review?(hv1989)
And added constant folding, including not-found (-1) case.
Attachment #8744685 - Flags: review?(hv1989)
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 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+
Attachment #8744685 - Flags: review?(hv1989) → review+
Thank you for reviewing :)
Keywords: leave-open
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
See Also: → 1271857
Depends on: 1271857
See Also: 1271857
You need to log in before you can comment on or make changes to this bug.