Closed Bug 1362753 Opened 3 years ago Closed 3 years ago

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

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: anba, Assigned: anba)

References

Details

Attachments

(3 files, 3 obsolete files)

+    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.
Or maybe just:
    if (!IsBoxedOrUnboxedArray(origArray))
        return !origArray->is<ProxyObject>();
Assignee: nobody → andrebargull
Status: NEW → ASSIGNED
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.
Attachment #8866835 - Flags: review?(jdemooij)
Attached patch bug1362753-part2-array-opt.patch (obsolete) — Splinter Review
- 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.
Attachment #8866837 - Flags: review?(jdemooij)
s/return [Date.now() - t];/print(Date.now() - t)/g
Attached patch bug1362753-part2-array-opt.patch (obsolete) — Splinter Review
Ugh, attached a stale patch (one DefineElement() call used the uint32 instead of the uint64 version). Sorry about that!
Attachment #8866837 - Attachment is obsolete: true
Attachment #8866837 - Flags: review?(jdemooij)
Attachment #8866851 - Flags: review?(jdemooij)
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.
Attachment #8866835 - Flags: review?(jdemooij) → review+
(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 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.
Attachment #8866851 - Flags: review?(jdemooij) → review+
(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?
(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.
Blocks: 1364345
Apply review comments, carrying r+ from jandem.
Attachment #8866835 - Attachment is obsolete: true
Attachment #8867749 - Flags: review+
Apply review comments, carrying r+.
Attachment #8866851 - Attachment is obsolete: true
Attachment #8867751 - Flags: review+
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);
Attachment #8867755 - Flags: review?(jdemooij)
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.
Attachment #8867755 - Flags: review?(jdemooij) → review+
Pushed by ryanvm@gmail.com:
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
Keywords: checkin-needed
Duplicate of this bug: 699323
You need to log in before you can comment on or make changes to this bug.