1362753 - Array.prototype.slice and Array.prototype.splice should always take the fast path for non-Array native objects

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[André Bargull [:anba]]

+    if (origArray.is<NativeObject>() && !origArray.is<ArrayObject>())
+        return true

should be added to http://searchfox.org/mozilla-central/rev/6580dd9a4eb0224773897388dba2ddf5ed7f4216/js/src/jsarray.cpp#939, so we can take the fast path for more native objects.

Comment 1

[André Bargull [:anba]]

Or maybe just:
    if (!IsBoxedOrUnboxedArray(origArray))
        return !origArray->is<ProxyObject>();

Comment 2

[André Bargull [:anba]]

Attachment: bug1362753-part1-array-species.patch

Applies on top of bug 924058.

We can always use the standard Array constructor if the input object isn't an array per the IsArray operation (https://tc39.github.io/ecma262/#sec-arrayspeciescreate, steps 3-4). And since it's not observable if we call IsArray twice, we can avoid entering self-hosted code by calling IsArray in IsArraySpecies.

Furthermore we can also avoid entering self-hosted code, if the constructor property was found and has the value |undefined| (https://tc39.github.io/ecma262/#sec-arrayspeciescreate, step 8).


    function fn() { Array.prototype.slice.call(arguments, 0); }

    var t = Date.now();
    for (var i = 0; i < 1000000; ++i) fn(0,1,2,3,4)
    return [Date.now() - t];

Improves from 1390ms to 850ms with this change.

Comment 3

[André Bargull [:anba]]

Attachment: bug1362753-part2-array-opt.patch

- Removes the unused "length" parameter from ArraySliceOrdinary

- New CopyArrayElements method: Inlines one ArraySpliceCopy call into array_splice_impl, because the |arr| object in this case is potentially user controllable. Now we only call ArraySpliceCopy with a newly allocated array. This makes it possible to merge ArraySpliceCopy and SliceSlowly, because in both cases we copy elements into a fresh array. And to improve performance, we can try to store the new elements into dense storage.

    function fn() { Array.prototype.slice.call(arguments, 0); }

    var t = Date.now();
    for (var i = 0; i < 1000000; ++i) fn(0,1,2,3,4)
    return [Date.now() - t];

Improves from 850ms (see above) to 435ms with this change.


- New CopyDenseArrayElements method: Both, ArraySliceOrdinary and array_splice_impl, called CopyAnyBoxedOrUnboxedDenseElements to copy dense elements into a new array. But the version in array_splice_impl was more restricted (only worked when called with boxed/unboxed arrays, the array mustn't be frozen, not participating in iteration, etc.). This patch adds CopyDenseArrayElements to perform the copying, so we can also use the more intelligent approach from ArraySliceOrdinary in array_splice_impl.


- CanOptimizeForDenseStorage: Some of the restrictions only make sense for write-access to an array (frozen array check, iteration check, etc.), so we now differentiate between read- and write-access when calling CanOptimizeForDenseStorage. Also we don't actually need to check for indexed properties on the prototype-chain when the array is packed. And the "Note that non-writable length is subsumed by the initializedLength comparison." comment in CanOptimizeForDenseStorage was wrong, instead added a check for lengthIsWritable(). 

    var o = [];
    for (var i = 0; i < 100; ++i) o[i] = 1;

    // Indexed property on the proto-chain of |o|.
    Array.prototype[0] = 2;

    var t = Date.now();
    for (var i = 0; i < 100000; ++i) Array.prototype.slice.call(o);
    print(Date.now() - t);

Improves from 1120ms to 65ms with the packed-array check.

Comment 4

[André Bargull [:anba]]

s/return [Date.now() - t];/print(Date.now() - t)/g

Comment 5

[André Bargull [:anba]]

Attachment: bug1362753-part2-array-opt.patch

Ugh, attached a stale patch (one DefineElement() call used the uint32 instead of the uint64 version). Sorry about that!

Comment 6

[Jan de Mooij [:jandem]]

Comment on attachment 8866835 [details] [diff] [review]
bug1362753-part1-array-species.patch

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

Very nice.

::: js/src/jsarray.cpp
@@ +1040,5 @@
>  {
> +    *arraySpecies = false;
> +
> +    bool isArray;
> +    if (!IsArray(cx, origArray, &isArray))

Wouldn't it be simpler (IsArraySpecies can stay infallible) and faster (this code is quite perf-sensitive) to do:

if (origArray->isNative() && !origArray->is<ArrayObject>())
    return true;

This will do the right thing for unboxed arrays, and proxies are going to fail here anyway (GetPropertyPure below).

@@ +1484,5 @@
>  
>      if (count == 0)
>          return true;
>  
> +    // TODO: Is this call still needed? If it is needed, it deserves a comment.

I doubt it and blame suggests it's very old. We should remove it IMO.

Comment 7

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #6)
> Comment on attachment 8866835 [details] [diff] [review]
> bug1362753-part1-array-species.patch
> 
> Review of attachment 8866835 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Very nice.
> 
> ::: js/src/jsarray.cpp
> @@ +1040,5 @@
> >  {
> > +    *arraySpecies = false;
> > +
> > +    bool isArray;
> > +    if (!IsArray(cx, origArray, &isArray))
> 
> Wouldn't it be simpler (IsArraySpecies can stay infallible) and faster (this
> code is quite perf-sensitive) to do:
> 
> if (origArray->isNative() && !origArray->is<ArrayObject>())
>     return true;
> 
> This will do the right thing for unboxed arrays, and proxies are going to
> fail here anyway (GetPropertyPure below).

This was also my first idea, but then I took a look at the IsArray implementation (http://searchfox.org/mozilla-central/source/js/src/jsarray.cpp#71) and considered an additional call to IsArray to be performance-wise negligent, because I assume |obj->is<ProxyObject>()| is fast and if proxies are involved, things already get slow, so calling |Proxy::isArray(...)| two times won't affect performance much.

> @@ +1484,5 @@
> >  
> >      if (count == 0)
> >          return true;
> >  
> > +    // TODO: Is this call still needed? If it is needed, it deserves a comment.
> 
> I doubt it and blame suggests it's very old. We should remove it IMO.

Great!

Comment 8

[Jan de Mooij [:jandem]]

Comment on attachment 8866851 [details] [diff] [review]
bug1362753-part2-array-opt.patch

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

Great results! Using slice with arguments objects etc is very common.

::: js/src/jsarray.cpp
@@ +2650,1 @@
>             startingIndex + count <= GetAnyBoxedOrUnboxedInitializedLength(arr);

Nit: this would be a bit more explicit:

--
if (Access == ArrayAccess::Write &&
    startingIndex + count > GetAnyBoxedOrUnboxedInitializedLength(arr))
{
    return false;
}

return true;
--

Maybe we can move this into the "if (Access == ArrayAccess::Write)" branch?

@@ +2658,5 @@
> +    uint32_t newlength = 0;
> +    if (initlen > begin)
> +        newlength = Min<uint32_t>(initlen - begin, count);
> +
> +    RootedObject narr(cx, NewFullyAllocatedArrayTryReuseGroup(cx, obj, newlength));

Nit: none of the calls below can GC, so we could use JSObject* narr here.

@@ +2704,5 @@
> +                    nresult->setDenseElementWithType(cx, index, value);
> +                    continue;
> +                }
> +
> +                if (!DefineElement(cx, nresult, index, value))

I think ensureDenseElements will succeed in most cases we care about, so maybe simplify to this?

if (edResult != DenseElementResult::Success)
    break;

nresult->setDenseElementWithType(cx, index, value);

Either way WFM.

Comment 9

[Jan de Mooij [:jandem]]

(In reply to André Bargull from comment #7)
> This was also my first idea, but then I took a look at the IsArray
> implementation
> (http://searchfox.org/mozilla-central/source/js/src/jsarray.cpp#71) and
> considered an additional call to IsArray to be performance-wise negligent,
> because I assume |obj->is<ProxyObject>()| is fast and if proxies are
> involved, things already get slow, so calling |Proxy::isArray(...)| two
> times won't affect performance much.

Some compilers may not inline that IsArray call and call overhead does matter. Do you see any perf differences on your micro-benchmarks with the simpler version?

Comment 10

[André Bargull [:anba]]

(In reply to Jan de Mooij [:jandem] from comment #9)
> (In reply to André Bargull from comment #7)
> > This was also my first idea, but then I took a look at the IsArray
> > implementation
> > (http://searchfox.org/mozilla-central/source/js/src/jsarray.cpp#71) and
> > considered an additional call to IsArray to be performance-wise negligent,
> > because I assume |obj->is<ProxyObject>()| is fast and if proxies are
> > involved, things already get slow, so calling |Proxy::isArray(...)| two
> > times won't affect performance much.
> 
> Some compilers may not inline that IsArray call and call overhead does
> matter. Do you see any perf differences on your micro-benchmarks with the
> simpler version?

Well okay, I give in. I saw a performance difference between calling IsArray and the simpler isNative() check. (840ms vs 910ms for 10 million calls to slice on an empty array on my laptop). So I'll revert it to the isNative() version.

Comment 11

[André Bargull [:anba]]

Attachment: bug1362753-part1-array-species.patch

Apply review comments, carrying r+ from jandem.

Comment 12

[André Bargull [:anba]]

Attachment: bug1362753-part2-array-opt.patch

Apply review comments, carrying r+.

Comment 13

[André Bargull [:anba]]

Attachment: bug1362753-part3-atomize-species.patch

I think it makes sense to add this change to this patch set, too.

Calling CallSelfHostedFunction instead of GetSelfHostedFunction avoids repeated calls to Atomize which improves the following µ-benchmark from 660ms to 510ms for me:

var a = [];
a.constructor = {
  [Symbol.species]: function(n) {
    return new Array(n);
  }
};

var t = Date.now();
for (var i = 0; i < 1000000; ++i) a.splice();
print(Date.now() - t);

Comment 14

[Till Schneidereit [:till]]

Comment on attachment 8867755 [details] [diff] [review]
bug1362753-part3-atomize-species.patch

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

Stealing review. Thank you, much better.

Comment 15

[André Bargull [:anba]]

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

Comment 16

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2e3e20b3d7f7
Part 1: Use array species fast path in Array.p.slice/splice when input argument isn't an array. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/026c02671403
Part 2: Take Array.prototype.slice/splice fast paths in more cases. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/6ad2a06489e9
Part 3: Use CallSelfHostedFunction to call ArraySpeciesCreate. r=till

Comment 17

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/2e3e20b3d7f7
https://hg.mozilla.org/mozilla-central/rev/026c02671403
https://hg.mozilla.org/mozilla-central/rev/6ad2a06489e9