890329 - Consider self-hosting Array.prototype.splice

Status: REOPENED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

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

Comment 1

[Till Schneidereit [:till]]

Attachment: Self-host Array#splice. wip

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.

Comment 2

[Jan de Mooij [:jandem]]

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.

Comment 3

[Jan de Mooij [:jandem]]

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

Comment 4

[Till Schneidereit [:till]]

Attachment: 3rd microbenchmark

Different benchmark that alternates between adding to and removing from the target array.

Comment 5

[Till Schneidereit [:till]]

Attachment: Self-host Array.prototype.splice

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

Comment 6

[Till Schneidereit [:till]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=39b8cbafc99d

Comment 7

[Jan de Mooij [:jandem]]

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?

Comment 8

[Jeff Walden [:Waldo]]

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

Comment 9

[Till Schneidereit [:till]]

url:        https://hg.mozilla.org/integration/mozilla-inbound/rev/a2bb58802e72094544f22a69a31ca8aa2d266ab4
changeset:  a2bb58802e72094544f22a69a31ca8aa2d266ab4
user:       Till Schneidereit <[e-mail]>
date:       Fri Aug 14 12:40:34 2015 +0200
description:
Bug 890329 - Self-host Array.prototype.splice. r=jandem

Comment 10

[Till Schneidereit [:till]]

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.

Comment 11

[Guilherme Lima]

One of the patches on your push ended up regressing pdfjs on AWFY (both 32-bit and 64-bit).

Comment 12

[Till Schneidereit [: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.

Comment 13

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/a2bb58802e72

Comment 14

[Gary [:streetwolf52]]

Is there a bug report opened for comment 12?

Comment 15

[Sean Stangl [:sstangl]]

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

Comment 16

[Ryan VanderMeulen [:RyanVM]]

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

Comment 17

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

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?

Comment 18

[Till Schneidereit [: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.

Comment 19

[Jan de Mooij [:jandem]]

Splice performance still shows up unfortunately :/ Till can we land this if we fix the issue in comment 18?

Comment 20

[Jan de Mooij [:jandem]]

This is a bit less urgent once bug 1344173 is fixed. Bug 1344177 is more important atm.

Comment 21

[Till Schneidereit [: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.