Closed Bug 789295 Opened 7 years ago Closed 7 years ago

Eliminate finalization cost of transferable ArrayBuffers

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla18

People

(Reporter: sfink, Assigned: sfink)

References

Details

(Whiteboard: [js:t])

Attachments

(6 files, 6 obsolete files)

5.69 KB, text/plain
Details
10.54 KB, text/plain
Details
18.01 KB, patch
billm
: review+
Details | Diff | Splinter Review
59.10 KB, patch
decoder
: feedback+
Details | Diff | Splinter Review
26.25 KB, patch
billm
: review+
Details | Diff | Splinter Review
27.94 KB, patch
billm
: review+
Details | Diff | Splinter Review
As bug 788205 and bug 720949 show, preventing ArrayBufferViews from being background-finalizable is a substantial perf hit.
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.
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.
Whiteboard: [js:t]
// 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.
A version that actually compiles is probably a little better for fuzzing.
Attachment #660256 - Attachment is obsolete: true
Attachment #660262 - Flags: feedback?(gary)
Attachment #660262 - Flags: feedback?(choller)
Testing this on langfuzz3 over night, will report results tomorrow :)
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 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.
Attachment #660262 - Flags: feedback?(gary)
Attachment #660262 - Flags: feedback?(choller)
> 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)
(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!
Attached file 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
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.
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)
gczeal((7));
evaluate("\
function Pattern(template) {    }\
Pattern.prototype = {\
    match: function(act) {        },\
}\
");


Crash [@  js::EncapsulatedPtr] in 64-bit debug build (no options required).
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.
Some light code cleanup.
Attachment #660946 - Flags: review?(wmccloskey)
The barrier stuff in this is a little crazy, but Terrence and I think it looks about right.
Attachment #660950 - Flags: review?(wmccloskey)
Attachment #660262 - Attachment is obsolete: true
Attachment #660946 - Attachment description: Make a BufferView superclass for ArrayBufferView types to enforce common slot numbers → Patch 2/3: Make a BufferView superclass for ArrayBufferView types to enforce common slot numbers
Attachment #660950 - Attachment description: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping → Patch 3/3: Add special multi-view array buffer sweep pass to eliminate finalizers and thus allow background sweeping
Attached patch Rollup patchSplinter Review
Rollup of the 3 patches for convenience.
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:
Attachment #660955 - Flags: feedback?(gary)
Attachment #660955 - Flags: feedback?(choller)
er, ignore that last comment. Hit the wrong flag first and didn't notice the approval request comment form.
Attachment #660945 - Flags: review?(wmccloskey) → review+
Attached file stdout (obsolete) —
Unfortunately, I hit a compile error on Linux.
Comment on attachment 660998 [details]
stdout

scratch that, my computer was overtaxed. :-/
Attachment #660998 - Attachment is obsolete: true
Comment on attachment 660955 [details] [diff] [review]
Rollup patch

Haven't seen any patch-specific failures so far :)
Attachment #660955 - Flags: feedback?(choller) → feedback+
Comment on attachment 660955 [details] [diff] [review]
Rollup patch

Nothing from me either. \o/
Attachment #660955 - Flags: feedback?(gary) → feedback+
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.
Attachment #660946 - Flags: review?(wmccloskey) → review+
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.
Attachment #660950 - Flags: review?(wmccloskey)
(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.
Attachment #661634 - Flags: review?(wmccloskey)
Attachment #660946 - Attachment is obsolete: true
Sorry, left in a redundant cast (in a line that will be replaced in the next patch, but whatever.)
Attachment #661636 - Flags: review?(wmccloskey)
Attachment #661634 - Attachment is obsolete: true
Attachment #661634 - Flags: review?(wmccloskey)
(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.
Attachment #661641 - Flags: review?(wmccloskey)
Attachment #660950 - Attachment is obsolete: true
Attachment #661636 - Flags: review?(wmccloskey) → review+
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?
Attachment #661641 - Flags: review?(wmccloskey) → review+
Depends on: 794494
Duplicate of this bug: 788205
You need to log in before you can comment on or make changes to this bug.