Small performance improvements for RegExp.prototype.@@split and RegExp.prototype.@@replace

RESOLVED FIXED in Firefox 55

Status

()

Core
JavaScript: Standard Library
RESOLVED FIXED
3 months ago
3 months ago

People

(Reporter: André Bargull, Assigned: André Bargull)

Tracking

(Blocks: 1 bug)

Trunk
mozilla55
Points:
---

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(4 attachments, 1 obsolete attachment)

(Assignee)

Description

3 months ago
There are some small performance improvements possible for RegExp.prototype.@@split and RegExp.prototype.@@replace, which improved octane-regexp by 5-6% in local tests.
(Assignee)

Updated

3 months ago
Assignee: nobody → andrebargull
Status: NEW → ASSIGNED
(Assignee)

Comment 1

3 months ago
Created attachment 8870010 [details] [diff] [review]
bug1366696-part1-split-sticky.patch

We don't need to create a new RegExp when the input RegExp for RegExp.prototype.@@split doesn't have the sticky flag set. This saves a call into the runtime and an allocation. 

Drive-by fix: Changed the default limit to 2^32-1, per the current spec.

Improves the following µ-benchmark from 1200ms to 600ms for me:

    var r = /a/g;
    var s = "aaaaa";
    var q = 0;
    var t = Date.now();
    for (var i = 0; i < 1000000; ++i) {
        q += s.split(r).length;
    }
    print(Date.now() - t, q);
Attachment #8870010 - Flags: review?(till)
(Assignee)

Comment 2

3 months ago
Created attachment 8870013 [details] [diff] [review]
bug1366696-part2-local-replace.patch

Two changes:
- Adds a fast path for small input strings when no complex replacement is necessary, similar to the existing optimization for global RegExps.

Improves this µ-benchmark from 390 ms to 250 ms:

    var r = /b/;
    var s = "aabaa";
    var q = 0;
    var t = Date.now();
    for (var i = 0; i < 2000000; ++i) {
        q += s.replace(r, "").length;
    }
    print(Date.now() - t, q);

This case is hit multiple times in octane-regexp.


- Adds a separate replacement function for functional replacements. This saves us an array allocation when the number of captures is <= 4.

Improves this benchmark from 1300 ms to 1200 ms

    var r = /a/g;
    var s = "aaaaa";
    var rp = () => "";
    var q = 0;
    var t = Date.now();
    for (var i = 0; i < 1000000; ++i) {
        q += s.replace(r, rp).length;
    }
    print(Date.now() - t, q);


Drive-by compliance fix: Use `undefined` instead of `null` when calling the replacer function in RegExpGetComplexReplacement.
Attachment #8870013 - Flags: review?(till)
(Assignee)

Comment 3

3 months ago
Created attachment 8870016 [details] [diff] [review]
bug1366696-part3-global-replace.patch

js::regexp_clone is not inlinable, so it's faster for us to check the RegExp pattern and flags in every iteration than calling into the runtime. (The RegExp was cloned for `defined(SUBSTITUTION)`, but that should have been `defined(ELEMBASE)` -> bug 1343363.)

Improves this µ-benchmark from 1300 ms (or 1200 with part 2) to 570 ms:

    var r = /a/g;
    var s = "aaaaa";
    var rp = () => "";
    var q = 0;
    var t = Date.now();
    for (var i = 0; i < 1000000; ++i) {
        q += s.replace(r, rp).length;
    }
    print(Date.now() - t, q);


Drive-by changes: Use MOZ_ALWAYS_TRUE for infallible ToInt32 calls in RegExp.cpp and fix the arity for the RegExp selfhosting helpers in SelfHosting.cpp.
Attachment #8870016 - Flags: review?(till)
(Assignee)

Comment 4

3 months ago
Created attachment 8870018 [details] [diff] [review]
bug1366696-part4-sh-rooting.patch

And another drive-by change:
I noticed there's some unnecessary rooting in SelfHosting.cpp for return values, which we should remove because it isn't really necessary and may or may not save a few nanoseconds. ;-)
Attachment #8870018 - Flags: review?(till)
(Assignee)

Comment 5

3 months ago
I probably should have mentioned, that js::regexp_construct_raw_flags and js::regexp_clone both showed up in bug 1365361, which was the main motivation to reduce calls to these two functions.
(Assignee)

Updated

3 months ago
Blocks: 1365361
(Assignee)

Comment 6

3 months ago
Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=e40fa9acb4ddd40c90bf2eedb69ad50fbfd0e8ac
Comment on attachment 8870010 [details] [diff] [review]
bug1366696-part1-split-sticky.patch

Review of attachment 8870010 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice.

::: js/src/builtin/RegExp.js
@@ +762,5 @@
>  
>      // Step 13.
>      var lim;
>      if (limit === undefined)
> +        lim = 0xffffffff;

Nit: please introduce a constant and use it here.
Attachment #8870010 - Flags: review?(till) → review+
Comment on attachment 8870013 [details] [diff] [review]
bug1366696-part2-local-replace.patch

Review of attachment 8870013 [details] [diff] [review]:
-----------------------------------------------------------------

r=me
Attachment #8870013 - Flags: review?(till) → review+
Comment on attachment 8870016 [details] [diff] [review]
bug1366696-part3-global-replace.patch

Review of attachment 8870016 [details] [diff] [review]:
-----------------------------------------------------------------

r=me
Attachment #8870016 - Flags: review?(till) → review+
Comment on attachment 8870018 [details] [diff] [review]
bug1366696-part4-sh-rooting.patch

Review of attachment 8870018 [details] [diff] [review]:
-----------------------------------------------------------------

Gotta save those nanoseconds ;)
Attachment #8870018 - Flags: review?(till) → review+
(Assignee)

Comment 11

3 months ago
Created attachment 8870556 [details] [diff] [review]
bug1366696-part1-split-sticky.patch

Updated per review comments. Carrying r+.
Attachment #8870010 - Attachment is obsolete: true
Attachment #8870556 - Flags: review+
(Assignee)

Comment 12

3 months ago
Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=c62d2bcf6a7cf4f0d933b5e47d8b56b0d1c03eb4
Keywords: checkin-needed

Comment 13

3 months ago
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3fe3c5c6e251
Part 1: Only create new splitter if sticky flag is present in input regexp. r=till
https://hg.mozilla.org/integration/mozilla-inbound/rev/82fdb7ec638e
Part 2: Improve performance of RegExp.prototype.@@replace with non-global regexp. r=till
https://hg.mozilla.org/integration/mozilla-inbound/rev/a8bf1340824b
Part 3: Improve performance of RegExp.prototype.@@replace with global regexp. r=till
https://hg.mozilla.org/integration/mozilla-inbound/rev/afcf9a101dfa
Part 4: Remove unnecessary rooting in SelfHosting.cpp for return values. r=till
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/3fe3c5c6e251
https://hg.mozilla.org/mozilla-central/rev/82fdb7ec638e
https://hg.mozilla.org/mozilla-central/rev/a8bf1340824b
https://hg.mozilla.org/mozilla-central/rev/afcf9a101dfa
Status: ASSIGNED → RESOLVED
Last Resolved: 3 months ago
status-firefox55: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
(In reply to André Bargull from comment #0)
> There are some small performance improvements possible for
> RegExp.prototype.@@split and RegExp.prototype.@@replace, which improved
> octane-regexp by 5-6% in local tests.

Seems to be at least 7% on the Mac slaves on AWFY? Very nice.
(Assignee)

Comment 16

3 months ago
(In reply to Jan de Mooij [:jandem] from comment #15)
> (In reply to André Bargull from comment #0)
> > There are some small performance improvements possible for
> > RegExp.prototype.@@split and RegExp.prototype.@@replace, which improved
> > octane-regexp by 5-6% in local tests.
> 
> Seems to be at least 7% on the Mac slaves on AWFY? Very nice.

\o/

Any next improvements are probably harder to achieve. For example the String.prototype.replace calls in Octane-RegExp spend quite some time concatenating strings (http://searchfox.org/mozilla-central/rev/2933592c4a01b634ab53315ce2d0e43fccb82181/js/src/builtin/RegExpGlobalReplaceOpt.h.js#107-109,123-127). And since we don't have something like a StringBuilder for self-hosted code, we're creating lots of dependent and rope strings here.
Unfortunately it looks like this also caused a 1100% (!) slowdown in sixspeed-templatestring-es6, and some less pronounced slowdowns in the other template strings tests:

https://arewefastyet.com/#machine=29&view=single&suite=six-speed&subtest=templatestring-es6

I have no idea what might be going on, but it seems like some light profiling should make it obvious.
Flags: needinfo?(andrebargull)
(Assignee)

Comment 18

3 months ago
I've investigated the slowdown with local awfy-builds and it seems to start with https://hg.mozilla.org/integration/mozilla-inbound/rev/882d55c60444 (bug 1365782), which seems much more likely than the changes from this bug. Setting NI for :tcampbell to verify it.
Flags: needinfo?(andrebargull) → needinfo?(tcampbell)
This is quite likely my bug, I'll reopen Bug 1365782 and investigate.
Flags: needinfo?(tcampbell)
You need to log in before you can comment on or make changes to this bug.