1094255 - Need a faster path for Array.prototype.push.apply(arr, domList)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Boris Zbarsky [:bzbarsky]]

Attachment: Microbenchmark

jQuery 2.0.x has this code in it:

  // Speed-up: Sizzle("TAG")
  } else if ( match[2] ) {
    push.apply( results, context.getElementsByTagName( selector ) );
    return results;

In SpiderMonkey, we end up in js_fun_apply which then takes a while doing js::GetElements.

But js::GetElements is a kinda slow path, certainly for DOM lists.

We have fast paths of various sorts for slice.  Can we do something similar for this case?

For example, in the case when "arr" is already empty, seems like we could even just reuse the slice() code...

For reference, this push.apply() bit is about 41% of the time on the BrowserMark 2.1 dom search test.  Of those 41%, 14% s spent in HTMLCollectionBinding::DOMProxyHandler::get, and another 11% actually calling array_push.  The other 16% is basically this overhead.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Also, it seems like we could maybe special-case the push.apply pattern in various ways by just putting the values directly into "this" instead of first putting them on the stack and then calling push().

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Testcase actually using jQuery

At first glance, we are NOT running in ion when we do that push.apply() bit.  Though I could be wrong, of course.

Comment 3

[Jan de Mooij [:jandem]]

I think as a first step, we should generalize the SliceOp hook. Most of the time is spent in GetElements, and once we have a class hook for that we can also use it for typed arrays etc; pretty sure we have bugs on file for apply([], typedArray).

We could pass a pointer to something that can append elements to either an array (for slice) or a Vector (for GetElements). Or something else in the future. Like this:

class ElementAdder
{
    uint32_t index;
    // Only one of those is used:
    RootedObject resObj;
    Value *vp;

  public:
    bool append(JSContext *cx, HandleValue v) {
        if (resObj)
            return UnsafeDefineElement(cx, resObj, index++, v);
        vp[index++] = v;
        return true;
    }
};

The signature becomes:

bool
GetElementsOp(JSContext *cx, HandleObject obj, uint32_t begin, uint32_t end, ElementAdder *adder);

Then, for the slice thing, we do:

    ElementAdder adder(narr);
    if (!op(cx, obj, begin, end, &adder))
    ...

And in GetElementsSlow we do:

    ElementAdder adder(vp);
    if (!op(cx, obj, 0, length, &adder))
    ...

Boris, does this sound reasonable? I'll try to cook up a WIP...

Comment 4

[Boris Zbarsky [:bzbarsky]]

I think that seems reasonable yes.  Nice and clean!

Comment 5

[Jan de Mooij [:jandem]]

I implemented what I described in comment 3, numbers are as follows (64-bit build on OS X):

Attached microbench:

Before:     Control: 20  With push: 3680
After:      Control: 20  With push: 2440
Chrome-dev: Control: 60  With push: 4490 (varies a lot)
Safari 8:   Control: 50  With push: 2760

Attached jQuery testcase:

Before:      5820
After:       4440
Chrome-dev: 14320
Safari 8:    4470

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Patch

See comments 3-5 for how this works.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8519002 [details] [diff] [review]
Patch

> GetElementsSlow(JSContext *cx, HandleObject aobj, uint32_t length, Value *vp)

Should this new block go into GetElements?  In general, the split between GetElements and GetElementsSlow doesn't seem to make much sense to me, since GetElements is the only caller of GetElementsSlow.

>+ElementAdder::append(JSContext *cx, HandleValue v)

In the resObj case, could we keep the asserts about isNative and initialized length that js::UnsafeDefineElement has?

I assume we don't need to worry about barriers on vp because it's in a stack autorooter?

r=me

Comment 8

[Jan de Mooij [:jandem]]

(In reply to Boris Zbarsky [:bz] from comment #7)
> Should this new block go into GetElements?  In general, the split between
> GetElements and GetElementsSlow doesn't seem to make much sense to me, since
> GetElements is the only caller of GetElementsSlow.

Good point, I'll move the code in GetElementsSlow to GetElements and remove GetElementsSlow.

> In the resObj case, could we keep the asserts about isNative and initialized
> length that js::UnsafeDefineElement has?

They are redundant: obj->as<NativeObject>() asserts isNative() and setDenseElementWithType ends up calling setDenseElement, which asserts index < getDenseInitializedLength().

> I assume we don't need to worry about barriers on vp because it's in a stack
> autorooter?

Right.

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 8519002 [details] [diff] [review]
Patch

Hm just realized this patch is not entirely correct.

Comment 10

[Jan de Mooij [:jandem]]

The problem is that for slice, we don't want to call JSObject::getElement but GetElement, which also returns whether there's a hole, and in that case we don't want to call setDenseElementWithType.

GetElementsSlow OTOH calls JSObject::getElement and treats holes as |undefined| I think.

Especially with proxies this is all observable of course. I'll probably have to pass an enum to specify which behavior we want...

Comment 11

[Boris Zbarsky [:bzbarsky]]

We could store that state on the adder, perhaps?  Note that we need that anyway in some sense to decide whether to setDenseElementWithType or fall back to defineElement once we've gone maybe-sparse...

Comment 12

[Jan de Mooij [:jandem]]

Attachment: Patch v2

Updated patch. This adds an enum to ElementAdder to specify the behavior we want.

I also added a test for fun.apply(null, proxy). It's similar to jit-test/tests/arrays/slice.js; that test caught the bug in the previous patch but somehow I forgot to run jit-tests.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8519422 [details] [diff] [review]
Patch v2

>+    GetBehavior getBehavior_;

Can we make this a const GetBehavior?  That might make it clear to compilers that they can loop-hoist the checks for it, assuming we don't loop-hoist them ourselves, of course, in js::GetElementsSlow.

r=me

It's probably a good idea to have a JS peer at least glance at this.

Comment 14

[Luke Wagner [:luke]]

Whoa, a proxy hook!  Do you suppose the reviewer of the proxy-slice hook patch should review this one as well?

Comment 15

[Jan de Mooij [:jandem]]

Comment on attachment 8519422 [details] [diff] [review]
Patch v2

(In reply to Luke Wagner [:luke] from comment #14)
> Whoa, a proxy hook!  Do you suppose the reviewer of the proxy-slice hook
> patch should review this one as well?

That'd be Boris and me, bug 697343 :) I think Tom wrote that patch so switching to him...

Comment 16

[Tom S [:evilpie]]

Comment on attachment 8519422 [details] [diff] [review]
Patch v2

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

This is pretty much what I thought this would look like. I didn't really think about that special [[Has]] and [[Get]] behavior before. I would probably have gone with a different name here and called that hook subarray or something like that.

::: js/public/Class.h
@@ +272,5 @@
> +    ElementAdder(JSContext *cx, JS::Value *vp, uint32_t length, GetBehavior getBehavior)
> +      : resObj_(cx), vp_(vp), index_(0), length_(length), getBehavior_(getBehavior)
> +    {}
> +
> +    GetBehavior getBehavior() const { return getBehavior_; }

This makes for an awkward name.

::: js/src/jsfriendapi.h
@@ +2583,2 @@
>  JS_FRIEND_API(bool)
> +GetElementsSlow(JSContext *cx, JS::HandleObject obj, JS::HandleObject receiver,

Usually GetElementsSlow would be used in GetElements. I would call this GetElementsWithAdder

Comment 17

[Jan de Mooij [:jandem]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a3fc456298ac

(In reply to Tom Schuster [:evilpie] from comment #16)
> Usually GetElementsSlow would be used in GetElements. I would call this
> GetElementsWithAdder

Done.

Comment 18

[Ryan VanderMeulen [:RyanVM]]

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