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

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, enhancement)

Description

[André Bargull [:anba]]

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.

Comment 1

[André Bargull [:anba]]

Attachment: 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);

Comment 2

[André Bargull [:anba]]

Attachment: 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.

Comment 3

[André Bargull [:anba]]

Attachment: 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.

Comment 4

[André Bargull [:anba]]

Attachment: 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. ;-)

Comment 5

[André Bargull [:anba]]

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.

Comment 6

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=e40fa9acb4ddd40c90bf2eedb69ad50fbfd0e8ac

Comment 7

[Till Schneidereit [:till]]

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.

Comment 8

[Till Schneidereit [:till]]

Comment on attachment 8870013 [details] [diff] [review]
bug1366696-part2-local-replace.patch

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

r=me

Comment 9

[Till Schneidereit [:till]]

Comment on attachment 8870016 [details] [diff] [review]
bug1366696-part3-global-replace.patch

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

r=me

Comment 10

[Till Schneidereit [:till]]

Comment on attachment 8870018 [details] [diff] [review]
bug1366696-part4-sh-rooting.patch

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

Gotta save those nanoseconds ;)

Comment 11

[André Bargull [:anba]]

Attachment: bug1366696-part1-split-sticky.patch

Updated per review comments. Carrying r+.

Comment 12

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=c62d2bcf6a7cf4f0d933b5e47d8b56b0d1c03eb4

Comment 13

[Pulsebot]

Pushed by [e-mail]:
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

Comment 14

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

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

Comment 15

[Jan de Mooij [:jandem]]

(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.

Comment 16

[André Bargull [:anba]]

(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.

Comment 17

[Till Schneidereit [:till]]

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.

Comment 18

[André Bargull [:anba]]

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.

Comment 19

[Ted Campbell [:tcampbell]]

This is quite likely my bug, I'll reopen Bug 1365782 and investigate.