Open Bug 890329 Opened 6 years ago Updated 3 years ago

Consider self-hosting Array.prototype.splice

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

REOPENED

People

(Reporter: jandem, Assigned: till)

References

(Blocks 2 open bugs)

Details

Attachments

(3 files, 1 obsolete file)

Kraken stanford-crypto-pbkdf2 calls array.splice at least 32768 times. Here's a micro-benchmark with similar array.splice calls:

function f() {
    var res;
    for (var i=0; i<32768; i++) {
        var a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
        res = a.splice(0, 16);
    }
    return res;
}
var t = new Date;
f();
print(new Date - t);

Difference between running this benchmark with and without the splice call:

SM : 15 ms
d8 :  4 ms

We spend a lot of time in array_splice itself but also in NewDenseCopiedArray and NewArray doing lookups on the new object cache etc.

Allocating new arrays is something Ion can do much more efficiently, especially with GGC (bump allocate the elements).
Attached patch Self-host Array#splice. wip (obsolete) — Splinter Review
This version implements only the first third or half of splice: the creation and filling of the array containing the deleted elements. Right now, that version takes ~17ms instead of the ~20ms for the - fully implemented - native version, on my machine. Given that, it's not likely that we'll see a speedup from the full implementation.

GGC might change this once Ion takes full advantage of it. We should re-test at that point.
Assignee: general → till
Depends on: 890365
Last week I noticed Octane-pdfjs spends about 10% under array_splice. We should try self-hosting again, now that we have GGC etc.

One wrinkle is that Ion has an optimization to avoid creating the .splice result array in some cases, if it's unused. However, a self-hosted splice may be faster anyway (V8 is), and there are still a few things we could try to do a similar optimization in the self-hosted version.

I'll do some measurements to see how much this would help nowadays.
Blocks: 807162
Attached file Other microbenchmark
This microbenchmark is based on one of the splice calls in Octane-pdfjs. On OS X 32-bit I get:

d8:  615 ms
SM: 1217 ms
Attachment #8643070 - Attachment mime type: text/x-c → text/javascript
Depends on: 1193212
Attached file 3rd microbenchmark
Different benchmark that alternates between adding to and removing from the target array.
This fully implements Array#splice and passes all tests. Numbers for the two microbenchmarks in the bug:

First microbenchmark:
SM old: 12ms
SM new: 14ms
d8:      7ms
JSC:    14ms

Other microbenchmark:
SM old: 1110ms
SM new:  821ms
d8:      715ms
JSC:     532ms

3rd microbenchmark:
SM old: 1613ms
SM new: 1139ms
d8:     1004ms
JSC:     751ms

So this is much better already. Somewhat annoyingly, the results of the first microbenchmark got slightly worse. If I increase the iterations 10-fold, we're exactly as fast as before, so that's probably warmup. But after that, perhaps we're fully gated on allocation performance for some reason?

Also, to see what would happen if we were able to detect that the result isn't used, I just disabled the part that creates it: with that, we're down to below 200ms, while other engines don't improve at all, when not using the result. Curiously, our current implementation also doesn't improve, so it seems like maybe we're not even using that code path for some reason.

This patch is also nice because: 16 files changed, 112 insertions(+), 421 deletions(-)
Attachment #8646261 - Flags: review?(jdemooij)
Comment on attachment 8646261 [details] [diff] [review]
Self-host Array.prototype.splice

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

So beautiful! Also great performance numbers. Thanks a lot for doing this!

::: js/src/builtin/Array.js
@@ +801,5 @@
> +    var insertCount = 0;
> +    var actualDeleteCount = 0;
> +    var numArgs = arguments.length;
> +    if (numArgs === 1) {
> +        actualDeleteCount = len - actualStart;

Hm the C++ implementation has a comment here:

         * Non-standard: if start was specified but deleteCount was omitted,
         * delete to the end of the array.  See bug 668024 for discussion.

It's clearly in the spec now though. Nice.

@@ +812,5 @@
> +        actualDeleteCount = std_Math_min(std_Math_max(dc, 0), len - actualStart);
> +    }
> +
> +    // Step 11.
> +    if (len + insertCount - actualDeleteCount > 0x20000000000000 /* 2**53 */)

The spec says 2**53 - 1 so it seems we should use

0x1fffffffffffff /* 2**53-1 */

Or change > to >=, but that's an unnecessary change from the spec algorithm and less obviously correct.

Also, if this is a new TypeError, can you add a test for it?
Attachment #8646261 - Flags: review?(jdemooij) → review+
(In reply to Jan de Mooij [:jandem] from comment #7)
> @@ +812,5 @@
> > +        actualDeleteCount = std_Math_min(std_Math_max(dc, 0), len - actualStart);
> > +    }
> > +
> > +    // Step 11.
> > +    if (len + insertCount - actualDeleteCount > 0x20000000000000 /* 2**53 */)
> 
> The spec says 2**53 - 1 so it seems we should use
> 
> 0x1fffffffffffff /* 2**53-1 */
> 
> Or change > to >=, but that's an unnecessary change from the spec algorithm
> and less obviously correct.

JS has a ** operator now, and our implementation isn't restricted to nightly or alpha builds.  Write out |2**53 - 1| literally.  :-)  I assure you that it'll constant-fold to the single numeric constant.

We should probably do a pass over a bunch of our self-hosted code looking for these inartfully-written constants to fix up, sometime.
url:        https://hg.mozilla.org/integration/mozilla-inbound/rev/a2bb58802e72094544f22a69a31ca8aa2d266ab4
changeset:  a2bb58802e72094544f22a69a31ca8aa2d266ab4
user:       Till Schneidereit <till@tillschneidereit.net>
date:       Fri Aug 14 12:40:34 2015 +0200
description:
Bug 890329 - Self-host Array.prototype.splice. r=jandem
Comment on attachment 771435 [details] [diff] [review]
Self-host Array#splice. wip

> We should probably do a pass over a bunch of our self-hosted code looking for > these inartfully-written constants to fix up, sometime.

I changed all occurrences of this in builtin/*.js to use `2 ** 53 - 1` instead. Jandem did an rs on IRC for that.
Attachment #771435 - Attachment is obsolete: true
One of the patches on your push ended up regressing pdfjs on AWFY (both 32-bit and 64-bit).
Flags: needinfo?(till)
(In reply to Guilherme Lima from comment #11)
> One of the patches on your push ended up regressing pdfjs on AWFY (both
> 32-bit and 64-bit).

I saw, thanks. Investigating.
Flags: needinfo?(till)
https://hg.mozilla.org/mozilla-central/rev/a2bb58802e72
Status: NEW → RESOLVED
Closed: 4 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla43
Is there a bug report opened for comment 12?
Depends on: 1195030
Bug 1195030 Comment 7 notes that this bug was backed out for rendering gmail unusable (which I'm hitting with today's Nightly).

The backout push is here:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9b34691fd5cd
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Merge of backout:
https://hg.mozilla.org/mozilla-central/rev/9b34691fd5cd

Ms2ger also backed this out directly from m-c so nightlies would pick it up sooner:
https://hg.mozilla.org/mozilla-central/rev/0876695d1abd
Target Milestone: mozilla43 → ---
Prior to the backout:

try {
    for (var x = 0; x < 2; ++x) {
        Array.prototype.splice.call([], -1, -0);
    }
} catch (e) {
    print(e);
}


$ ~/shell-cache/js-64-dm-windows-2ddfc9180971/js-64-dm-windows-2ddfc9180971.exe --fuzzing-safe --no-threads --baseline-eager testcase.js

$ ~/shell-cache/js-64-dm-windows-2ddfc9180971/js-64-dm-windows-2ddfc9180971.exe --fuzzing-safe --no-threads --ion-eager testcase.js
Error: Expected int32 as second argument

Configure command:

MAKE=mozmake AR=ar sh ./configure --host=x86_64-pc-mingw32 --target=x86_64-pc-mingw32 --disable-threadsafe --enable-more-deterministic --enable-gczeal --enable-debug-symbols --disable-tests

Till, perhaps this might help you?
Flags: needinfo?(till)
Thanks, with anba's help we have figured out what's the problem: NewDenseArray has a check that's too strict and relies on the first (and only) argument being an int32 even in the internal representation.
Depends on: 1195298
Flags: needinfo?(till)
See Also: → 1165052
Splice performance still shows up unfortunately :/ Till can we land this if we fix the issue in comment 18?
Flags: needinfo?(till)
Blocks: 1342797
This is a bit less urgent once bug 1344173 is fixed. Bug 1344177 is more important atm.
Flags: needinfo?(till)
(In reply to Jan de Mooij [:jandem] from comment #19)
> Splice performance still shows up unfortunately :/ Till can we land this if
> we fix the issue in comment 18?

I'm pretty sure that this'd need further tweaking before we could land it, even with comment 18 addressed. The pdfjs regressions are concerning, and in general, splice is so perf-sensitive that landing this would require careful investigation of real-world impact.
You need to log in before you can comment on or make changes to this bug.