The default bug view has changed. See this FAQ.

Add copy-on-write arrays

RESOLVED FIXED in mozilla34

Status

()

Core
JavaScript Engine
RESOLVED FIXED
3 years ago
2 years ago

People

(Reporter: jandem, Assigned: bhackett)

Tracking

(Blocks: 2 bugs, {dev-doc-needed})

unspecified
mozilla34
dev-doc-needed
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

3 years ago
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.
Blocks: 1008333
Blocks: 1025085
I think splay would also benefit heavily since the tree leaves are all constant arrays.
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|.
(Reporter)

Comment 3

3 years ago
(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.
(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.
Created attachment 8467208 [details] [diff] [review]
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.
Assignee: nobody → bhackett1024
Attachment #8467208 - Flags: review?(wmccloskey)
Attachment #8467208 - Flags: review?(jdemooij)
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?
Attachment #8467208 - Flags: review?(wmccloskey) → review+
> 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.
(Reporter)

Comment 8

3 years ago
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
Attachment #8467208 - Flags: review?(jdemooij) → review+
(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.
https://hg.mozilla.org/integration/mozilla-inbound/rev/9605a571ca8a

Try: https://tbpl.mozilla.org/?tree=Try&rev=98127a80c984
https://hg.mozilla.org/mozilla-central/rev/9605a571ca8a
Status: NEW → RESOLVED
Last Resolved: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla34
Blocks: 919658
Depends on: 1056898
Depends on: 1056899

Comment 12

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

Yes.

Comment 14

3 years ago
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.
Keywords: dev-doc-needed
Depends on: 1057219

Updated

3 years ago
Depends on: 1063488
Depends on: 1062830
Depends on: 1115246
You need to log in before you can comment on or make changes to this bug.