934450 - Add copy-on-write arrays

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

The Peacekeeper arrayWeighted test (bug 918746) has a "run" function with 25 array literals. Every time we call this function, we have to allocate new objects and elements and fill them.

Unfortunately, all these arrays are added to yet another array, so avoiding the object allocation completely is not trivial without an analysis that would be pretty complicated (and feels like cheating, although the benchmark is so stupid it probably deserves it).

We could follow V8 and add COW ObjectElements: we still have to allocate the objects but the ObjectElements will only be allocated/cloned once they are modified.

It's a fair amount of work: we need a new bytecode op for array initializers with constant elements, ObjectElements will have to be refcounted, the VM and JITs have to clone when writing to COW ObjectElements, etc.

OTOH it's an optimization that could help other benchmarks as well, for instance SS date-format-tofte has similar array literals.

Also, this test is very important for our total Peacekeeper score: if we could run this test as fast as V8, it'd win ~500 points, ~25% of the difference with Chrome.

Comment 1

[Terrence Cole [:terrence]]

I think splay would also benefit heavily since the tree leaves are all constant arrays.

Comment 2

[Brian Hackett [Laid off!]]

The only thing that looks annoying to do here is the ObjectElements refcounting, which would have all sorts of ramifications.  I don't see why it's necessary, though.  The arrays embedded in the script are read only, and if the arrays with read only elements kept those original arrays alive during tracing then it would be guaranteed the elements wouldn't unexpectedly disappear.  That could be done I guess by abusing one of the JSObject* pointers in the base shape for the cloned arrays' initial shape, maybe |metadata|.

Comment 3

[Jan de Mooij [:jandem]]

(In reply to Brian Hackett (:bhackett) from comment #2)
> The only thing that looks annoying to do here is the ObjectElements
> refcounting, which would have all sorts of ramifications.  I don't see why
> it's necessary, though.  The arrays embedded in the script are read only,
> and if the arrays with read only elements kept those original arrays alive
> during tracing then it would be guaranteed the elements wouldn't
> unexpectedly disappear.

True; that does seem simpler and nicer than refcounting.

Comment 4

[Terrence Cole [:terrence]]

(In reply to Jan de Mooij [:jandem] from comment #3)
> (In reply to Brian Hackett (:bhackett) from comment #2)
> > The only thing that looks annoying to do here is the ObjectElements
> > refcounting, which would have all sorts of ramifications.  I don't see why
> > it's necessary, though.  The arrays embedded in the script are read only,
> > and if the arrays with read only elements kept those original arrays alive
> > during tracing then it would be guaranteed the elements wouldn't
> > unexpectedly disappear.
> 
> True; that does seem simpler and nicer than refcounting.

Agreed!

Another approach to avoid refcounting would be to make array elements into GC things -- more work to implement, but might have significantly more impact as well.

Comment 5

[Brian Hackett [Laid off!]]

Attachment: patch

This patch allows objects to have copy on write elements.  Right now this is restricted to array literals that are not in run once code; I suppose we could do Array(1, 2, 3, 4) too though that would require more heavy lifting in IonBuilder --- all the work to recognize copyable arrays is done in the bytecode emitter.  Copy on write element arrays hold a pointer to their owning JSObject at the end (doing things via the Shape didn't work because when objects are finalized their shape/type may have been destroyed already).  When tracing an object with copy on write elements we either trace all the elements or trace the pointer to the owner, depending on whether the referring object owns those elements.

On x86 my base splay score improves from 17.5k to 27k, and my splay latency score goes from 12.5k to 15k.  I haven't tested other benchmarks, but this should help similarly stupid benchmarks like the peacekeeper one in comment 0 and maybe even some real code, and shouldn't have much effect when we write to non-copy-on-write arrays --- we track copy-on-write-ness in type information and are able to loop hoist / consolidate checks when the elements might need to be copied.

Comment 6

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

Comment on attachment 8467208 [details] [diff] [review]
patch

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

Sorry for the slow review. This looks nice. All the maybeCopyElementsForWrite calls are unfortunate, but they seem necessary. And the assertions look like they'll provide good coverage if we accidentally try to change COW elements.

::: js/src/frontend/BytecodeEmitter.cpp
@@ +3878,5 @@
>          RootedValue value(cx);
>          unsigned count;
>          ParseNode *pn;
>  
> +        if (!allowObjects)

Would be clearer to compare against DontAllowObjects.

@@ +3915,5 @@
>        case PNK_OBJECT: {
>          JS_ASSERT(isOp(JSOP_NEWINIT));
>          JS_ASSERT(!(pn_xflags & PNX_NONCONST));
>  
> +        if (!allowObjects)

Same as above.

::: js/src/gc/Barrier.h
@@ +949,3 @@
>  
>    public:
> +    explicit HeapSlotArray(HeapSlot *array, bool allowWrite)

Please add a comment explaining what allowWrite is for.

@@ +960,2 @@
>  
> +    bool allowWrite() const {

Can we make this method private?

::: js/src/jsobj.cpp
@@ +3420,5 @@
>      elements = newheader->elements();
>  }
>  
> +/* static */ bool
> +JSObject::CopyElementsForWrite(ThreadSafeContext *cx, JSObject *obj)

Won't this break if |obj| is the owner of its elements? If that's not possible, can you assert as such?

::: js/src/jsobjinlines.h
@@ +593,5 @@
>      return &obj->as<js::ArrayObject>();
>  }
>  
> +/* static */ inline js::ArrayObject *
> +JSObject::createArray(js::ExclusiveContext *cx, js::gc::InitialHeap heap,

I feel like we should share this code with the above function. Maybe have createArrayInternal that takes allocKind and elements. If elements is null, it would initialize a header in the fixed slots.

::: js/src/vm/ObjectImpl.cpp
@@ +112,5 @@
> +/* static */ bool
> +ObjectElements::MakeElementsCopyOnWrite(ExclusiveContext *cx, JSObject *obj)
> +{
> +    // Make sure there is enough room for the owner object pointer at the end
> +    // of the elements.

Maybe assert that sizeof(HeapSlot) >= sizeof(HeapPtrObject) here?

Comment 7

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

> Copy on write element arrays hold a pointer to their owning JSObject at the end
> (doing things via the Shape didn't work because when objects are finalized their
> shape/type may have been destroyed already).

I forgot to mention: I'm pretty sure this isn't true anymore. It's possible that we'll have removed an object's shape from the shape tree before the object is swept (in Shape::sweep), but the shape should otherwise be safe to use. We finalize shapes on the background in a phase that comes after object finalization.

Comment 8

[Jan de Mooij [:jandem]]

Comment on attachment 8467208 [details] [diff] [review]
patch

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

Sorry for the delay. Overall this looks less complicated than I thought it'd be; glad we don't need the refcounting mechanism.

::: js/src/jit/MCallOptimize.cpp
@@ +414,5 @@
>          return InliningStatus_NotInlined;
>  
>      callInfo.setImplicitlyUsedUnchecked();
>  
> +    obj = addMaybeCopyElementsForWrite(obj);

Please make sure we have jit-tests for these push/pop/shift COW cases.

::: js/src/vm/Opcodes.h
@@ +901,5 @@
> +     *   Type: Array
> +     *   Operands: uint32_t objectIndex
> +     *   Stack: => obj
> +     */ \
> +    macro(JSOP_NEWARRAY_COPYONWRITE, 102, "newarray_copyonwrite", NULL, 5, 0, 1, JOF_OBJECT) \

Nit: bump XDR_BYTECODE_VERSION in vm/Xdr.h

Comment 9

[Brian Hackett [Laid off!]]

(In reply to Bill McCloskey (:billm) from comment #7)
> > Copy on write element arrays hold a pointer to their owning JSObject at the end
> > (doing things via the Shape didn't work because when objects are finalized their
> > shape/type may have been destroyed already).
> 
> I forgot to mention: I'm pretty sure this isn't true anymore. It's possible
> that we'll have removed an object's shape from the shape tree before the
> object is swept (in Shape::sweep), but the shape should otherwise be safe to
> use. We finalize shapes on the background in a phase that comes after object
> finalization.

Yeah, I forgot about this; we already need to access the type to get the clasp when doing background finalization of objects with finalizers.  I like what this patch ends up doing more though, since it doesn't require modifying any fields of the base shape or type object, and storing the owning object pointer in the dense elements fits in nicely with the mark patch for them.

Comment 10

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9605a571ca8a

Try: https://tbpl.mozilla.org/?tree=Try&rev=98127a80c984

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/9605a571ca8a

Comment 12

[Florian Bender]

This is enabled by default, right?

Comment 13

[Brian Hackett [Laid off!]]

(In reply to Florian Bender from comment #12)
> This is enabled by default, right?

Yes.

Comment 14

[Florian Bender]

Awesome, thanks!

I think this should at least go into the Release Information on MDN (hence dev-doc-needed, but also because this should be documented for SM and maybe Array & friends). Dunno if this qualifies for relnote?, though, please advise.