Last Comment Bug 827490 - Allow native objects to have both slots and elements
: Allow native objects to have both slots and elements
Status: RESOLVED FIXED
[MemShrink]
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Other Branch
: x86 Mac OS X
: -- normal (vote)
: mozilla21
Assigned To: Brian Hackett (:bhackett)
:
Mentors:
: 602477 628710 869680 (view as bug list)
Depends on: 827449 829795 829813 829821 830049 830573 830967 835496 876114 895223
Blocks: 586842 679710 611423 832360 835102
  Show dependency treegraph
 
Reported: 2013-01-07 13:11 PST by Brian Hackett (:bhackett)
Modified: 2015-10-08 08:51 PDT (History)
17 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
WIP (663bfe4a4c2c) (264.85 KB, patch)
2013-01-07 13:11 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (663bfe4a4c2c) (267.33 KB, patch)
2013-01-07 16:11 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
patch (663bfe4a4c2c) (270.93 KB, patch)
2013-01-08 07:49 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Splinter Review
main changes (168.39 KB, patch)
2013-01-08 08:21 PST, Brian Hackett (:bhackett)
wmccloskey: review+
Details | Diff | Splinter Review
boring changes (39.36 KB, patch)
2013-01-08 08:22 PST, Brian Hackett (:bhackett)
wmccloskey: review+
Details | Diff | Splinter Review
GC changes (25.12 KB, patch)
2013-01-08 08:26 PST, Brian Hackett (:bhackett)
wmccloskey: review+
Details | Diff | Splinter Review
JIT changes (38.00 KB, patch)
2013-01-08 08:27 PST, Brian Hackett (:bhackett)
dvander: review+
Details | Diff | Splinter Review

Description Brian Hackett (:bhackett) 2013-01-07 13:11:37 PST
Created attachment 698824 [details] [diff] [review]
WIP (663bfe4a4c2c)

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.
Comment 1 Brian Hackett (:bhackett) 2013-01-07 16:11:03 PST
Created attachment 698938 [details] [diff] [review]
patch (663bfe4a4c2c)

Patch that works with jit-tests --ion, modulo bug 827449.  Will chop this up for review in a minute.
Comment 2 Brian Hackett (:bhackett) 2013-01-08 07:49:13 PST
Created attachment 699212 [details] [diff] [review]
patch (663bfe4a4c2c)

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.
Comment 3 Brian Hackett (:bhackett) 2013-01-08 08:21:49 PST
Created attachment 699233 [details] [diff] [review]
main changes

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.
Comment 4 Brian Hackett (:bhackett) 2013-01-08 08:22:37 PST
Created attachment 699234 [details] [diff] [review]
boring changes

Boring ancillary changes dependent on the previous patch.
Comment 5 Brian Hackett (:bhackett) 2013-01-08 08:26:06 PST
Created attachment 699237 [details] [diff] [review]
GC changes

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.
Comment 6 Brian Hackett (:bhackett) 2013-01-08 08:27:22 PST
Created attachment 699240 [details] [diff] [review]
JIT changes

Ion and JM changes.  The JM changes are mostly just ripping out dense array stuff from the IC code.
Comment 7 Tom Schuster [:evilpie] 2013-01-08 08:28:32 PST
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?
Comment 8 Luke Wagner [:luke] 2013-01-08 08:35:20 PST
Sorry, I'm swamped for the next few months.  Waldo's working on bug 586842 so perhaps he'd be the best reviewer anyway.
Comment 9 Brian Hackett (:bhackett) 2013-01-08 08:37:23 PST
(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.
Comment 10 Tom Schuster [:evilpie] 2013-01-08 08:48:17 PST
(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.
Comment 11 Brian Hackett (:bhackett) 2013-01-08 09:08:12 PST
(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 12 Bill McCloskey (:billm) 2013-01-08 11:44:33 PST
Comment on attachment 699234 [details] [diff] [review]
boring changes

Talked to David. He and I can review.
Comment 13 Bill McCloskey (:billm) 2013-01-08 11:50:30 PST
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 14 Bill McCloskey (:billm) 2013-01-08 18:08:29 PST
Comment on attachment 699234 [details] [diff] [review]
boring changes

Actually, it makes sense for the same person to review both of these.
Comment 15 Bill McCloskey (:billm) 2013-01-09 16:11:26 PST
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.
Comment 16 Brian Hackett (:bhackett) 2013-01-10 16:53:34 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/f4671ccc4502
Comment 17 Bill McCloskey (:billm) 2013-01-10 17:30:28 PST
How does this affect performance on some of those benchmarks that put named properties on arrays?
Comment 18 Brian Hackett (:bhackett) 2013-01-10 17:36:33 PST
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.
Comment 19 Nicholas Nethercote [:njn] 2013-01-10 17:47:40 PST
Where does this leave bug 586842?
Comment 20 Brian Hackett (:bhackett) 2013-01-10 17:55:16 PST
(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.
Comment 21 Nicholas Nethercote [:njn] 2013-01-10 17:57:53 PST
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.
Comment 22 Brian Hackett (:bhackett) 2013-01-10 18:12:37 PST
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.
Comment 23 Ed Morley [:emorley] 2013-01-11 06:28:30 PST
https://hg.mozilla.org/mozilla-central/rev/f4671ccc4502
Comment 24 Ed Morley [:emorley] 2013-01-11 06:57:45 PST
https://hg.mozilla.org/mozilla-central/rev/f4671ccc4502
Comment 25 Ed Morley [:emorley] 2013-01-11 07:46:02 PST
https://hg.mozilla.org/mozilla-central/rev/f4671ccc4502
Comment 26 Dave Townsend [:mossop] 2013-01-14 17:21:02 PST
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.
Comment 27 Brian Hackett (:bhackett) 2013-01-14 20:41:38 PST
(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?
Comment 28 Irakli Gozalishvili [:irakli] [:gozala] [@gozala] 2013-01-15 10:50:16 PST
(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
Comment 29 Irakli Gozalishvili [:irakli] [:gozala] [@gozala] 2013-01-15 10:52:12 PST
BTW I believe same exceptions would have being thrown on non-objects without this change, so our tests would have being failing already.
Comment 30 Dave Townsend [:mossop] 2013-01-15 12:34:41 PST
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.
Comment 31 Dave Townsend [:mossop] 2013-01-15 12:45:54 PST
(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.
Comment 32 Brian Hackett (:bhackett) 2013-01-15 13:17:02 PST
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.
Comment 33 Boris Zbarsky [:bz] 2013-05-08 07:21:10 PDT
*** Bug 869680 has been marked as a duplicate of this bug. ***
Comment 34 André Bargull 2015-09-21 09:37:50 PDT
*** Bug 602477 has been marked as a duplicate of this bug. ***
Comment 35 André Bargull 2015-10-08 08:51:03 PDT
*** Bug 628710 has been marked as a duplicate of this bug. ***

Note You need to log in before you can comment on or make changes to this bug.