Currently a native object can only store properties indexed by a Shape in its fixed / dynamically allocated slots. JSObject has a field and structures for storing a dense array of elements, but this is only used by dense arrays, which themselves do not use slots for anything. Allowing objects to make use of both their slots and elements was originally supposed to be part of bug 586842, but that bug is nearing 2.5 years old and this performance cliff is long overdue for fixing. Moreover, ObjShrink largely paved the way for this so that not a lot of additional work is required. The attached WIP makes the following changes, and passes jit-tests --no-jm --no-ion. - Removes the slow array class, and makes Arrays native objects. - Allows native objects to have a dense array of elements, in addition to the properties on their shape. Properties stored via the shape/slots can be indexed, in contrast to bug 586842's approach, with the restriction that no index can be in both the shape and the dense elements. I don't know yet if this is a good final spot to be, or if the full name/index separation should be done in the future. - Tries to use the dense elements when defining normal data properties on objects, in the same manner that is currently done only for dense arrays. The patch is pretty big but a lot of it is just fixing up uses of dense-array specific methods on JSObject.

Patch that works with jit-tests --ion, modulo bug 827449. Will chop this up for review in a minute.

Fix a few bugs around non-extensible objects and the native iterator cache, and add tests for these. Also address a potential performance issue where we could keep counting holes over and over when adding elements to an already-sparse object.

Main changes in the patch: move dense array related methods to JSObject, and allow looking up and adding dense elements to native objects in the VM.

Boring ancillary changes dependent on the previous patch.

GC related changes: mark both slots and elements for native objects, and keep track of the kind of HeapSlot to mark in ggc barriers and igc worklist.

Ion and JM changes. The JM changes are mostly just ripping out dense array stuff from the IC code.

Comment on attachment 699212 [details] [diff] [review] patch (663bfe4a4c2c) Review of attachment 699212 [details] [diff] [review]: ----------------------------------------------------------------- Awesome! Really looking forward for this getting landed. It's really shameful that our current api requires us to have hacks like ImplicitProperty. The removal of dense arrays is just lovely. Did you make some performance measurements, yet? I have a few comments while skimming through this. ::: js/src/builtin/RegExp.cpp @@ +64,5 @@ > * 1..pairCount-1: paren matches > * input: input string > * index: start index for the match > */ > + RootedObject array(cx, NewDenseEmptyArray(cx)); I think we already know the resulting size. NewDenseAllocatedArray(cx, matches.length()) I think v8-regexp or some other benchmark should get better when our result array of regexp matches stays fast. Exciting! ::: js/src/ion/IonCaches.cpp @@ +1607,5 @@ > return true; > } > > bool > +IonCacheGetElement::attachDenseElement(JSContext *cx, IonScript *ion, JSObject *obj, const Value &idval) Is this still doing the right thing? The comment in ObjectImpl mentions that we don't use length for non-arrays. @@ +1712,5 @@ > if (idval.isString() && JSID_IS_ATOM(id) && !JSID_TO_ATOM(id)->isIndex(&dummy)) { > if (!cache.attachGetProp(cx, ion, obj, idval, JSID_TO_ATOM(id)->asPropertyName())) > return false; > } > + } else if (!cache.hasDenseStub() && obj->isNative() && idval.isInt32()) { Shouldn't you make sure that we actually have dense elements?

Sorry, I'm swamped for the next few months. Waldo's working on bug 586842 so perhaps he'd be the best reviewer anyway.

(In reply to Tom Schuster [:evilpie] from comment #7) > ::: js/src/ion/IonCaches.cpp > @@ +1607,5 @@ > > return true; > > } > > > > bool > > +IonCacheGetElement::attachDenseElement(JSContext *cx, IonScript *ion, JSObject *obj, const Value &idval) > > Is this still doing the right thing? The comment in ObjectImpl mentions that > we don't use length for non-arrays. This stub just uses the initialized length, rather than the length itself. The initialized length is valid for all native objects. > @@ +1712,5 @@ > > if (idval.isString() && JSID_IS_ATOM(id) && !JSID_TO_ATOM(id)->isIndex(&dummy)) { > > if (!cache.attachGetProp(cx, ion, obj, idval, JSID_TO_ATOM(id)->asPropertyName())) > > return false; > > } > > + } else if (!cache.hasDenseStub() && obj->isNative() && idval.isInt32()) { > > Shouldn't you make sure that we actually have dense elements? If an object doesn't have dense elements then its .elements will point to js::emptyObjectElements, which has an initialized length and capacity of zero so that the attachDenseElement stub will bail out. attachDenseElement only catches cases where the element is present.

(In reply to Brian Hackett (:bhackett) from comment #9) > (In reply to Tom Schuster [:evilpie] from comment #7) > > ::: js/src/ion/IonCaches.cpp > > @@ +1607,5 @@ > > > return true; > > > } > > > > > > bool > > > +IonCacheGetElement::attachDenseElement(JSContext *cx, IonScript *ion, JSObject *obj, const Value &idval) > > > > Is this still doing the right thing? The comment in ObjectImpl mentions that > > we don't use length for non-arrays. > > This stub just uses the initialized length, rather than the length itself. > The initialized length is valid for all native objects. > I am sorry. I was looking at the length stub O_o. > > @@ +1712,5 @@ > > > if (idval.isString() && JSID_IS_ATOM(id) && !JSID_TO_ATOM(id)->isIndex(&dummy)) { > > > if (!cache.attachGetProp(cx, ion, obj, idval, JSID_TO_ATOM(id)->asPropertyName())) > > > return false; > > > } > > > + } else if (!cache.hasDenseStub() && obj->isNative() && idval.isInt32()) { > > > > Shouldn't you make sure that we actually have dense elements? > > If an object doesn't have dense elements then its .elements will point to > js::emptyObjectElements, which has an initialized length and capacity of > zero so that the attachDenseElement stub will bail out. attachDenseElement > only catches cases where the element is present. Not sure how useful a stub that is not going to be hit really is. But we can worry about this later.

(In reply to Tom Schuster [:evilpie] from comment #10) > Not sure how useful a stub that is not going to be hit really is. But we can > worry about this later. Well, it can still be hit. Whether an object has dense elements or not is independent from its shape, so even if the initial object has no dense elements there can be hits later for objects which do have elements. This does prevent stubs from being generated for specific sparse indexes, but that doesn't seem like a case where we really want to generate a stub anyways.

Comment on attachment 699234 [details] [diff] [review] boring changes Talked to David. He and I can review.

Comment on attachment 699237 [details] [diff] [review] GC changes Review of attachment 699237 [details] [diff] [review]: ----------------------------------------------------------------- This might break some generational write barrier code that's disabled right now, but I guess we can fix that up later. ::: js/src/gc/Marking.cpp @@ +1171,5 @@ > { > for (uintptr_t *p = stack.tos; p > stack.stack; ) { > uintptr_t tag = *--p & StackTagMask; > if (tag == ValueArrayTag) { > p -= 2; While reviewing this, I noticed a problem in this code (though it doesn't actually cause any trouble). Could you add this line: *p &= ~StackTagMask; before the |p -= 2| line? It won't actually make a difference since ValueArrayTag == 0, but it reads better. I think it should be completely optimized away.

Comment on attachment 699234 [details] [diff] [review] boring changes Actually, it makes sense for the same person to review both of these.

Comment on attachment 699233 [details] [diff] [review] main changes Review of attachment 699233 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/jsarray.cpp @@ +264,5 @@ > bool > js::GetElements(JSContext *cx, HandleObject aobj, uint32_t length, Value *vp) > { > + if (aobj->isArray() && length <= aobj->getDenseInitializedLength() && > + !ObjectHasExtraIndexedProperties(aobj)) { Please move the brace to its own line. @@ +521,5 @@ > if (!js_IdIsIndex(id, &index)) > return JS_TRUE; > length = obj->getArrayLength(); > if (index >= length) > JSObject::setArrayLength(cx, obj, index + 1); I was trying to understand this length-setting code, and it looks like there's duplicate functionality for this in DefinePropertyOnArray in jsobj.cpp. If you agree, can you remove that section in DefinePropertyOnArray? @@ +526,5 @@ > return JS_TRUE; > } > > +JSBool > +js::ObjectHasExtraIndexedProperties(JSObject *obj) If I understand correctly, this is a conservative test (i.e., it might return true even if there are no extra indexed properties). Could you call this ObjectMayHaveExtraIndexedProperties to be extra clear? @@ -2351,5 @@ > - JSObject::setArrayLength(cx, obj, index); > - return true; > - } > - > - return SetLengthProperty(cx, obj, index); I don't really understand the original purpose of this code. As far as I can tell, Array objects cannot have custom length properties. Do you know why we ever needed to worry about this? @@ +1626,5 @@ > length--; > > + if (obj->isArray() && !ObjectHasExtraIndexedProperties(obj) && > + length < obj->getDenseCapacity() && > + 0 < obj->getDenseInitializedLength()) { Please move the brace down. @@ +1753,5 @@ > /* If the desired properties overflow dense storage, we can't optimize. */ > if (UINT32_MAX - startingIndex < count) > return false; > > /* There's no optimizing possible if it's not a dense array. */ Please fix the comment. @@ +2124,5 @@ > > RootedObject nobj(cx); > > + if (obj->isArray() && end <= obj->getDenseInitializedLength() && > + !ObjectHasExtraIndexedProperties(obj)) { Please move the brace down. ::: js/src/jsinfer.cpp @@ -5804,5 @@ > * looking at the class prototype key. > */ > > - if (self->isSlowArray()) > - type->flags |= OBJECT_FLAG_NON_DENSE_ARRAY | OBJECT_FLAG_NON_PACKED_ARRAY; It seems like you still need to set OBJECT_FLAG_NON_DENSE_ARRAY if there are indexed properties stored in |slots|. Could you set this flag based in isIndexed()? ::: js/src/jsinterpinlines.h @@ -746,5 @@ > - break; > - } > - } else if (obj->isArguments()) { > - if (obj->asArguments().maybeGetElement(index, res)) > - break; This appears to be some sort of fast path. I guess we don't need it any more? ::: js/src/jsobj.cpp @@ +2477,5 @@ > + > + /* > + * Reduce storage for dense elements which are now holes. Explicitly mark > + * the elements capacity as zero, so that any attempts to add dense > + * elements will use growElements() and test obj->isExtensible, as required Is this comment right? growElements doesn't check isExtensible. It looks like ensureDenseElements does though. Is that what you meant? @@ +3908,5 @@ > + JSObject::setDenseElementHole(cx, obj, index); > + return false; > + } > + JSObject::setDenseElementWithType(cx, obj, index, vp); > + return true; This code looks pretty much identical to some code you added to DefineNativeProperty (except for an extra check). Can you maybe move this sequence to its own function? Maybe AddPropertyDense or something? ::: js/src/jsscopeinlines.h @@ +500,5 @@ > + * not actually represented by a Shape (dense elements, properties of > + * non-native objects), use a dummy value. > + */ > +static inline void > +MarkImplicitPropertyFound(MutableHandleShape propp) I think it would be cleaner to keep MarkNonNativePropertyFound as it is and create a new version called MarkIndexPropertyFound/IsIndexProperty. That way, when you're reading the code, it's clear which kind of property you're dealing with. ::: js/src/vm/ObjectImpl.h @@ +412,5 @@ > static const size_t ValuesPerHeader = 2; > }; > > +/* > + * Elements header used for all native objects. The elements component of such I think that this comment is in the wrong place. There are two kinds of elements headers we have right now: ElementsHeader and ObjectElements. We currently use only ObjectElements, so I think that the comment should go above there. Maybe you could also add a comment above ElementsHeader saying that it's currently unused but we're planning to use it in the future? @@ +418,5 @@ > + * properties of the object, using a flat array of Values rather than a shape > + * hierarchy stored in the object's properties. > + * > + * The sets of properties represented by an object's elements and properties > + * are disjoint. The elements contain only indexes, while the properties can "contains indexes" seems confusing. Maybe "contains indexed properties"? @@ +420,5 @@ > + * > + * The sets of properties represented by an object's elements and properties > + * are disjoint. The elements contain only indexes, while the properties can > + * contain both names and indexes; any indexes in the properties are distinct > + * from those in the elements. It would be helpful to mention what you told me on IRC: that an indexed property is stored in |elements| if JSObject::ensureDenseElements returns ED_OK. Also, it would be nice to mention that all indexed own properties will be stored in dense elements if isIndexed() is false. And if it's true, then nothing is certain. @@ +462,5 @@ > + * Indexes will be stored in the object's properties instead of its elements in > + * the following case: > + * - there are more than MIN_SPARSE_INDEX slots total and the load factor > + * (COUNT / capacity) is less than 0.25 > + * - a property is defined that has non-default property attributes. I think this should be moved up in the comment (near the discussion of elements versus slots). @@ +1015,4 @@ > * > + * - For native objects, properties and elements may both be non-empty. The > + * properties may be either names or indexes; any indexes in the properties > + * will not be in the elements. ...and any indexes in the elements will not be in the properties.

How does this affect performance on some of those benchmarks that put named properties on arrays?

I didn't test any of the benchmarks specifically, but looked at microbenchmarks to make sure things were behaving sensibly. About the only problem right now is that when accessing dense elements of a non-array native we have to use the dense element cache for Ion rather than type specialized paths, which is about 2x as slow as the type specialized path and only works for GETELEM. I want to fix that as a followup (though need to get in some other changes first) but even so this is far faster than what we had previously.

Where does this leave bug 586842?

(In reply to Nicholas Nethercote [:njn] from comment #19) > Where does this leave bug 586842? I'm not sure. There is still a lot of work to reorganize and clean up the object APIs to separate named and indexed property accesses, which seems to be the focus of bug 586842's dependents. It also still remains to do a full split in the object representation between named and indexed properties, I think now that going this route would not benefit performance, though in concert with the API fixes it should help with simplicity.

How many of the bugs that bug 586842 blocks are fixed by this bug? For example, bug 687935 is one that I've been following.

Hopefully this should fix any performance/memory bugs attached to bug 586842, including bug 687935. If there are still workloads that are running slow or chewing too much memory, I'd like to know.

This seems to have caused test failures in the add-on SDK code, was it expected to have visible effects in JS? AT first glance it looks like Object.getOwnPropertyNames is failing now when it wasn't before with the exception "source is not an object" but I'm getting strange results trying to narrow down exactly what cases right now.

(In reply to Dave Townsend (:Mossop) from comment #26) > This seems to have caused test failures in the add-on SDK code, was it > expected to have visible effects in JS? AT first glance it looks like > Object.getOwnPropertyNames is failing now when it wasn't before with the > exception "source is not an object" but I'm getting strange results trying > to narrow down exactly what cases right now. This patch can change enumeration order for 'for in' loops. Do you know whether Object.getOwnPropertyNames is actually being called with a non-object?

(In reply to Brian Hackett (:bhackett) from comment #27) > (In reply to Dave Townsend (:Mossop) from comment #26) > > This seems to have caused test failures in the add-on SDK code, was it > > expected to have visible effects in JS? AT first glance it looks like > > Object.getOwnPropertyNames is failing now when it wasn't before with the > > exception "source is not an object" but I'm getting strange results trying > > to narrow down exactly what cases right now. > > This patch can change enumeration order for 'for in' loops. Do you know > whether Object.getOwnPropertyNames is actually being called with a > non-object? I don't think we do at least that's not intentional. We do use objects with `null` __proto__ though and objects may be also from diff compartments, maybe that's what causing race condition. I believe Eddy will be looking into this and will tell us for sure

BTW I believe same exceptions would have being thrown on non-objects without this change, so our tests would have being failing already.

I've narrowed this down to a regression involving Array.concat and frozen arrays: Array.concat(Object.freeze([{}]))[0] In Aurora this returns {} as expected. In current nightlies though it returns undefined.

(In reply to Dave Townsend (:Mossop) from comment #30) > I've narrowed this down to a regression involving Array.concat and frozen > arrays: > > Array.concat(Object.freeze([{}]))[0] > > In Aurora this returns {} as expected. In current nightlies though it > returns undefined. Also on Nightly Array.concat(Object.freeze([{}])) returns [,] but claims to have a length of 1.

Thanks! Filed bug 830967 for the Array.concat bug. The '[,]' is how an array with a length of 1 but no actual indexed property gets printed.