789295 - Eliminate finalization cost of transferable ArrayBuffers

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Steve Fink [:sfink] [:s:]]

As bug 788205 and bug 720949 show, preventing ArrayBufferViews from being background-finalizable is a substantial perf hit.

Comment 1

[Steve Fink [:sfink] [:s:]]

My current crazy scheme for fixing this:

First, remove the finalizer from views.

That prevents us from pruning out dead views from ArrayBuffers' list of views, needed for transferring as well as un-inlining (for JS_GetArrayBufferData).

Instead, add a separate phase to the end of GC that scans over all still-live ArrayBuffers and prunes out their dead views.

To find the still-live ArrayBuffers, construct a list during the mark phase, storing the list header in the runtime. There's no space to thread the list through the ArrayBuffers, so thread it through the first view in each ArrayBuffer's list. (If an ArrayBuffer has no views, it doesn't need to be in the list at all.) As it turns out, views have a couple of unused slots (because I crossed over from 4 to 8 fixed slots for the transferable implementation), so this is no additional space.

Scanning over many ArrayBuffers and their views is likely to be about as slow as doing foreground finalization, so optimize by omitting ArrayBuffers with a single view (expected to be the most common case by far) from the list, and instead holding a strong pointer to that single view. This will leak the view in the unusual case that an ArrayBuffer outlives its single view, but this is expected to be rare.

An alternative would be to give ArrayBuffers their own allocKind and scan their arenas. I'll try out the idea above to see how it works in practice.

Comment 2

[Steve Fink [:sfink] [:s:]]

This, plus the stuff that's already gone in (bug 720949 and bug 785167), could use some fuzzing. ("could use" == "will likely fall apart in the face of")

I hope to attach a patch here shortly.

Comment 3

[Steve Fink [:sfink] [:s:]]

Attachment: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

// ArrayBuffers need to maintain a list of possibly-weak pointers to their
    // views. The straightforward way to update the weak pointers would be in
    // the views' finalizers, but giving views finalizers means they cannot be
    // swept in the background. This results in a very high performance cost.
    // Instead, ArrayBuffers with a single view hold a strong pointer to the
    // view. This can entrain garbage when the single view becomes otherwise
    // unreachable while the buffer is still live, but this is expected to be
    // rare. ArrayBuffers with 0-1 views are expected to be by far the most
    // common cases. ArrayBuffers with multiple views are collected into a
    // linked list during collection, and then swept to prune out their dead
    // views.

Comment 4

[Steve Fink [:sfink] [:s:]]

Attachment: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

A version that actually compiles is probably a little better for fuzzing.

Comment 5

[Christian Holler (:decoder)]

Testing this on langfuzz3 over night, will report results tomorrow :)

Comment 6

[Christian Holler (:decoder)]

Assertion failure: [barrier verifier] Unmarked edge: arraybuffer.singleview, at js/src/jsgc.cpp:5310


gczeal(4,1);
const bytes = 128;
var buf = new ArrayBuffer(bytes);
var ui8arr = new Uint8Array(buf);
var dblarr = new Float64Array(buf);

Comment 7

[Steve Fink [:sfink] [:s:]]

Comment on attachment 660262 [details] [diff] [review]
Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

Crashed and burned on try. No point in fuzzing it yet.

Comment 8

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

> Crashed and burned on try. No point in fuzzing it yet.

Yeah, I couldn't even get it past:

  File "c:\Users\fuzz1win\fuzzing\js\inspectShell.py", line 74, in testDbgOrOpt
    if shellSupports(jsShellName, ['-e', 'disassemble()']):
  File "c:\Users\fuzz1win\fuzzing\js\inspectShell.py", line 59, in shellSupports
    raise Exception('Unexpected exit code in shellSupports ' + str(retCode))
Exception: Unexpected exit code in shellSupports -1073741819

on Windows. (this doesn't occur without the patch)

Comment 9

[Steve Fink [:sfink] [:s:]]

(In reply to Christian Holler (:decoder) from comment #6)
> Assertion failure: [barrier verifier] Unmarked edge: arraybuffer.singleview,
> at js/src/jsgc.cpp:5310
> 
> 
> gczeal(4,1);
> const bytes = 128;
> var buf = new ArrayBuffer(bytes);
> var ui8arr = new Uint8Array(buf);
> var dblarr = new Float64Array(buf);

Oh, hey, that's useful. Thanks!

Comment 10

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

Attachment: stack

x = ArrayBuffer()
Object.defineProperty(this, "w", {
  get: function() {
	return z.subarray()
  }
})
y = ArrayBuffer()
Float32Array(y)
Int16Array(y)
Object.defineProperty(this, "z", {
  get: function() {
	return Int16Array(x)
  }
})
w
verifyprebarriers()
for (p in z) {}

(pass in the testcase as a CLI argument)

Crash [@ js::ArrayBufferObject::sweepAll] or "Assertion failure: *views," - tested on m-c changeset fdfaef738a00

Comment 11

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

Attachment: stack from opt-only crash

Object.defineProperty(this, "t1", {
    get: function() {
        return t2.subarray()
    }
})
t2 = Uint8ClampedArray()
try {
    (function() {
        g
    })()
} catch (e) {}
try {
    gczeal(8, 2), [z]
} catch (e) {}
try {
    for (yqsesl = 0; yqsesl < 8; l) {
        i = t1[2]
    }
} catch (e) {}
try {
    (function() {
        with(yield) {}
    }())
    x = ArrayBuffer()
    Uint8Array(x)
    Float32Array(x)
    r = Int16Array(x)
    for (y in [x[0]()]) {}
} catch (e) {}a

(pass in the testcase as a CLI argument)

Crash [@ js::ArrayBufferObject::obj_trace] in 64-bit opt builds on m-c changeset fdfaef738a00 with this patch.

Comment 12

[Christian Holler (:decoder)]

function jit(on) {}
gczeal(7);
for (var loopa2 = 0; loopa2 < 13; (jit(false))) {}

Crash [@ js::ion::CanEnter] in 64-bit debug build (no options required)

Comment 13

[Christian Holler (:decoder)]

gczeal((7));
evaluate("\
function Pattern(template) {    }\
Pattern.prototype = {\
    match: function(act) {        },\
}\
");


Crash [@  js::EncapsulatedPtr] in 64-bit debug build (no options required).

Comment 14

[Steve Fink [:sfink] [:s:]]

I have a series of 3 patches (sorry, I know it's harder to apply that way) that seems to pass all of the tests posted above as well as looking green on tryserver. Oh, and BananaBread was nice and smooth with it; no GC pauses more than 40ms.

I still don't trust it.

Comment 15

[Steve Fink [:sfink] [:s:]]

Attachment: Patch 1/3: Reformat class method declarations to look like rest of spidermonkey

Trivial reformatting

Comment 16

[Steve Fink [:sfink] [:s:]]

Attachment: Patch 2/3: Make a BufferView superclass for ArrayBufferView types to enforce common slot numbers

Some light code cleanup.

Comment 17

[Steve Fink [:sfink] [:s:]]

Attachment: Patch 3/3: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

The barrier stuff in this is a little crazy, but Terrence and I think it looks about right.

Comment 18

[Steve Fink [:sfink] [:s:]]

Attachment: Rollup patch

Rollup of the 3 patches for convenience.

Comment 19

[Steve Fink [:sfink] [:s:]]

Comment on attachment 660955 [details] [diff] [review]
Rollup patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 
User impact if declined: 
Testing completed (on m-c, etc.): 
Risk to taking this patch (and alternatives if risky): 
String or UUID changes made by this patch:

Comment 20

[Steve Fink [:sfink] [:s:]]

er, ignore that last comment. Hit the wrong flag first and didn't notice the approval request comment form.

Comment 21

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

Attachment: stdout

Unfortunately, I hit a compile error on Linux.

Comment 22

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

Comment on attachment 660998 [details]
stdout

scratch that, my computer was overtaxed. :-/

Comment 23

[Christian Holler (:decoder)]

Comment on attachment 660955 [details] [diff] [review]
Rollup patch

Haven't seen any patch-specific failures so far :)

Comment 24

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

Comment on attachment 660955 [details] [diff] [review]
Rollup patch

Nothing from me either. \o/

Comment 25

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 660946 [details] [diff] [review]
Patch 2/3: Make a BufferView superclass for ArrayBufferView types to enforce common slot numbers

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

::: js/src/jstypedarray.cpp
@@ +257,4 @@
>  static JSObject *
>  NextView(JSObject *obj)
>  {
> +    return static_cast<JSObject*>(obj->getFixedSlot(BufferView::NEXT_VIEW_SLOT).toPrivate());

Don't you want toObjectOrNull()?

::: js/src/jstypedarray.h
@@ +206,5 @@
> +     * all ArrayBufferViews.
> +     */
> +    static const size_t LENGTH_SLOT     = BufferView::NUM_SLOTS;
> +    static const size_t TYPE_SLOT       = BufferView::NUM_SLOTS + 1;
> +    static const size_t MAX_SLOT        = BufferView::NUM_SLOTS + 2;

What about calling this NUM_SLOTS, so that it would replace BufferView::NUM_SLOTS?

@@ +207,5 @@
> +     */
> +    static const size_t LENGTH_SLOT     = BufferView::NUM_SLOTS;
> +    static const size_t TYPE_SLOT       = BufferView::NUM_SLOTS + 1;
> +    static const size_t MAX_SLOT        = BufferView::NUM_SLOTS + 2;
> +    static const size_t NUM_FIXED_SLOTS = 7;

Maybe call this DATA_SLOT, and have a comment that it's the private slot, and thus outside the range of the other slots.

Comment 26

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 660950 [details] [diff] [review]
Patch 3/3: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

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

This seems good, but I'd like the see a version with the different iteration order.

::: js/src/jstypedarray.cpp
@@ +341,5 @@
> +    }
> +};
> +#endif
> +
> +static void WeakObjectSlotBarrierPost(JSObject *obj, size_t slot, const char *desc)

static void should be on a separate line. Also, please comment that a custom barrier is needed here because you're using private slots, which are not normally traced.

@@ +367,5 @@
> +        WeakObjectSlotBarrierPost(view, BufferView::NEXT_VIEW_SLOT, "arraybuffer.nextview");
> +
> +        // Move the multiview buffer list link into this view since we're
> +        // prepending it to the list
> +        size_t nextBufSlot = BufferView::NEXT_BUFFER_SLOT;

Why do you always store NEXT_BUFFER_SLOT in a variable before using it? Line length?

@@ +370,5 @@
> +        // prepending it to the list
> +        size_t nextBufSlot = BufferView::NEXT_BUFFER_SLOT;
> +        view->setFixedSlot(nextBufSlot, (*views)->getFixedSlot(nextBufSlot));
> +        WeakObjectSlotBarrierPost(view, nextBufSlot, "view.nextbuffer");
> +        (*views)->setFixedSlot(nextBufSlot, PrivateValue(NULL));

I'd prefer to omit this line.

@@ +532,5 @@
> +        // adding this buffer to the list multiple times
> +        if (firstView->getFixedSlot(BufferView::NEXT_BUFFER_SLOT).toPrivate() == NULL)  {
> +            JSObject **bufList = &trc->runtime->liveArrayBuffers;
> +            // mark the end of the buffer list with a self-loop since NULL
> +            // means not yet visited

Could you use a special terminator like 0x2? I think it would be simpler.

@@ +607,5 @@
> +            iter.advance();
> +            if (!JS_IsAboutToBeFinalized(obj)) {
> +                insert.set(obj);
> +                insert.advance();
> +            }

Could you try rebuilding the list in reverse? I think it would be simpler that way and would allow the removal of the iterator.

Comment 27

[Steve Fink [:sfink] [:s:]]

Attachment: Make a BufferView superclass for ArrayBufferView types to enforce common slot numbers

(In reply to Bill McCloskey (:billm) from comment #25)
> Comment on attachment 660946 [details] [diff] [review]
> Patch 2/3: Make a BufferView superclass for ArrayBufferView types to enforce
> common slot numbers
> 
> Review of attachment 660946 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jstypedarray.cpp
> @@ +257,4 @@
> >  static JSObject *
> >  NextView(JSObject *obj)
> >  {
> > +    return static_cast<JSObject*>(obj->getFixedSlot(BufferView::NEXT_VIEW_SLOT).toPrivate());
> 
> Don't you want toObjectOrNull()?

Oh, sorry, that was a piece of the next patch that crept in. You are correct, though it'll change in patch #3. There was one other place I did this (changed NullValue() to PrivateValue().)

> ::: js/src/jstypedarray.h
> @@ +206,5 @@
> > +     * all ArrayBufferViews.
> > +     */
> > +    static const size_t LENGTH_SLOT     = BufferView::NUM_SLOTS;
> > +    static const size_t TYPE_SLOT       = BufferView::NUM_SLOTS + 1;
> > +    static const size_t MAX_SLOT        = BufferView::NUM_SLOTS + 2;
> 
> What about calling this NUM_SLOTS, so that it would replace
> BufferView::NUM_SLOTS?

Yeah, that probably makes more sense. But I called it RESERVED_SLOTS, since it's more precise and matches the other uses I could find in the tree.

> 
> @@ +207,5 @@
> > +     */
> > +    static const size_t LENGTH_SLOT     = BufferView::NUM_SLOTS;
> > +    static const size_t TYPE_SLOT       = BufferView::NUM_SLOTS + 1;
> > +    static const size_t MAX_SLOT        = BufferView::NUM_SLOTS + 2;
> > +    static const size_t NUM_FIXED_SLOTS = 7;
> 
> Maybe call this DATA_SLOT, and have a comment that it's the private slot,
> and thus outside the range of the other slots.

Ok, now instead of MAX_SLOT and NUM_FIXED_SLOTS, I have RESERVED_SLOTS and DATA_SLOT. I think all these things are sort of making sense to me finally.

Comment 28

[Steve Fink [:sfink] [:s:]]

Attachment: Make a BufferView superclass for ArrayBufferView types to enforce common slot numbers

Sorry, left in a redundant cast (in a line that will be replaced in the next patch, but whatever.)

Comment 29

[Steve Fink [:sfink] [:s:]]

Attachment: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

(In reply to Bill McCloskey (:billm) from comment #26)
> Comment on attachment 660950 [details] [diff] [review]
> Patch 3/3: Add special multi-view array buffer sweep pass to eliminate
> finalizers and thus allow background sweeping
> 
> Review of attachment 660950 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> This seems good, but I'd like the see a version with the different iteration
> order.
> 
> ::: js/src/jstypedarray.cpp
> @@ +341,5 @@
> > +    }
> > +};
> > +#endif
> > +
> > +static void WeakObjectSlotBarrierPost(JSObject *obj, size_t slot, const char *desc)
> 
> static void should be on a separate line. Also, please comment that a custom
> barrier is needed here because you're using private slots, which are not
> normally traced.

done

> @@ +367,5 @@
> > +        WeakObjectSlotBarrierPost(view, BufferView::NEXT_VIEW_SLOT, "arraybuffer.nextview");
> > +
> > +        // Move the multiview buffer list link into this view since we're
> > +        // prepending it to the list
> > +        size_t nextBufSlot = BufferView::NEXT_BUFFER_SLOT;
> 
> Why do you always store NEXT_BUFFER_SLOT in a variable before using it? Line
> length?

Yes. I've switched to helper routines instead.

> @@ +370,5 @@
> > +        // prepending it to the list
> > +        size_t nextBufSlot = BufferView::NEXT_BUFFER_SLOT;
> > +        view->setFixedSlot(nextBufSlot, (*views)->getFixedSlot(nextBufSlot));
> > +        WeakObjectSlotBarrierPost(view, nextBufSlot, "view.nextbuffer");
> > +        (*views)->setFixedSlot(nextBufSlot, PrivateValue(NULL));
> 
> I'd prefer to omit this line.

Ok.

> @@ +532,5 @@
> > +        // adding this buffer to the list multiple times
> > +        if (firstView->getFixedSlot(BufferView::NEXT_BUFFER_SLOT).toPrivate() == NULL)  {
> > +            JSObject **bufList = &trc->runtime->liveArrayBuffers;
> > +            // mark the end of the buffer list with a self-loop since NULL
> > +            // means not yet visited
> 
> Could you use a special terminator like 0x2? I think it would be simpler.

Ok. It just felt a little weird to depend on the implementation details of private values, but I guess this'll explode pretty quickly if that ever changes.

One subtlety with this -- I could almost change the while(buffer) loop to while(buffer != BUFFER_LIST_END), but if there are no arraybuffers in existence then rt->liveArrayBuffers will be NULL and it'll crash. To avoid exposing my sentinel value through some header so that jscntxt.cpp could initialize rt->liveArrayBuffers with it, I instead switched to using NULL as the end of the list and making an UNSET_BUFFER_LINK sentinel value to initialize views with.

> @@ +607,5 @@
> > +            iter.advance();
> > +            if (!JS_IsAboutToBeFinalized(obj)) {
> > +                insert.set(obj);
> > +                insert.advance();
> > +            }
> 
> Could you try rebuilding the list in reverse? I think it would be simpler
> that way and would allow the removal of the iterator.

You were right. Not sure why I didn't do it that way in the first place. Much, much simpler.

Comment 30

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 661641 [details] [diff] [review]
Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping

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

Looks great!

::: js/src/jsgc.cpp
@@ +3754,5 @@
>      /* Finalize unreachable (key,value) pairs in all weak maps. */
>      WeakMapBase::sweepAll(&rt->gcMarker);
>      rt->debugScopes->sweep();
>  
> +    /* Prune out dead views from ArrayBuffer's view lists */

Period at the end (since I guess we could consider this an imperative sentence).

::: js/src/jstypedarray.cpp
@@ +535,5 @@
> +        return;
> +
> +    JSObject *firstView = *views;
> +    if (NextView(firstView) == NULL) {
> +        // single view: mark it, but only if we're actually doing a GC pass

Capitalize the start of the sentence.

@@ +541,5 @@
> +        // fail if we add another view and the pointer becomes weak.
> +        if (IS_GC_MARKING_TRACER(trc))
> +            MarkObjectUnbarriered(trc, views, "arraybuffer.singleview");
> +    } else {
> +        // multiple views: do not mark, but append buffer to list

Capitalize and period at the end.

@@ +544,5 @@
> +    } else {
> +        // multiple views: do not mark, but append buffer to list
> +
> +        // obj_trace may be called multiple times before sweepAll(), so avoid
> +        // adding this buffer to the list multiple times

Period at the end.

::: js/src/jstypedarray.h
@@ +169,5 @@
>      static const size_t BYTEOFFSET_SLOT  = 0;
>      static const size_t BYTELENGTH_SLOT  = 1;
>      static const size_t BUFFER_SLOT      = 2;
>      static const size_t NEXT_VIEW_SLOT   = 3;
> +    static const size_t NEXT_BUFFER_SLOT = 4;

Could you add a comment here about the meaning of the last two slots?

::: js/src/jstypedarrayinlines.h
@@ +14,5 @@
>  #include "jsobjinlines.h"
>  
> +// Sentinel value used to initialize ArrayBufferViews' NEXT_BUFFER_SLOTs to
> +// show that they have not yet been added to any ArrayBuffer list
> +#define UNSET_BUFFER_LINK (JSObject*)0x2

Can you make this a const?

Comment 31

[Steve Fink [:sfink] [:s:]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/9382a5a45acb
http://hg.mozilla.org/integration/mozilla-inbound/rev/b5273d58d158
http://hg.mozilla.org/integration/mozilla-inbound/rev/9367895cc67f

Comment 32

[Mounir Lamouri (:mounir)]

https://hg.mozilla.org/mozilla-central/rev/9367895cc67f
https://hg.mozilla.org/mozilla-central/rev/b5273d58d158
https://hg.mozilla.org/mozilla-central/rev/9382a5a45acb