693221 - Remove JSObject::capacity and JSObject::initializedLength

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

obj->capacity currently means different things depending on whether an object is a dense array or not --- it indicates the allocated element capacity for dense arrays, and the total number of available slots for other objects.  obj->initializedLength is only used for dense arrays.

These can both be removed from JSObject by (a) adding a header before dense array elements indicating the capacity, initialized length and proper length (so the privateData is not used by arrays anymore, which needs to be so in order to remove privateData itself), and (b) computing the allocated capacity for other objects as a function of the slot span and number of fixed slots.

Comment 1

[Brian Hackett [Laid off!]]

Attachment: WIP

Passes jit-tests with JITs turned off.

This also adds an 'elements' member to JSObject --- slow arrays need to use both 'slots' and 'elements', and trying to keep the two members flattened together given the elements header is pretty painful.

This partially overlaps with the changes required for bug 586842, i.e. objects *could* have both elements and named properties, but none actually do.  Jeff, I don't know what your schedule is for bug 586842, but if this stuff hasn't merged to m-c by the time you start on structural changes, you might want to do those changes in the JM branch (will save a lot of merge pain, and it will be easier to make the JIT happy).

Comment 2

[Brian Hackett [Laid off!]]

Attachment: WIP 2

Passes jit-tests -ma and -mna.

Comment 3

[Brian Hackett [Laid off!]]

Attachment: patch

Browser builds and passes some tests at least.  Still some in-browser failures, but will fix those in place.

https://hg.mozilla.org/projects/jaegermonkey/rev/838464854ec6

Comment 4

[Jeff Walden [:Waldo]]

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

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

The schedule is that I finish up getting the ObjectOps signatures done, first.  Then after that, I'm not certain yet whether I'll start working on changing the underlying storage, add utilities to extract the appropriate specialized property type from a jsid or a Value, or what.  The storage change will probably be quite large, so anything to minimize its size will be good.  So maybe that means I lean toward adding the utilities.  But I'm really not certain.  I figure I'll decide what to do on how well trying one tack or another goes.

::: js/src/jsobj.h
@@ +495,5 @@
> +    /* Set the initial property for a newborn object. */
> +    bool setInitialProperty(JSContext *cx, const js::Shape *shape);
> +
> +    /* As above, but the slot span is guaranteed to fit in the fixed slots. */
> +    void setInitialPropertyInfallible(const js::Shape *shape);

We make "infallible" a prefix for these sorts of things (cf. Vector::infallibleAppend), generally.

Comment 5

[Luke Wagner [:luke]]

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

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

Another great patch.  I like the numSlots() removal with the better slotSpan() invariant wrt reserved slots.  I also like how the growing of slots and changing of shape have been merged into a single set(Initial)Property/setSlotSpan call.  Also all the Debug_SetValueRangeToCrashOnTouch additions are great.

::: js/src/jsarray.cpp
@@ +1378,2 @@
>          if (!addDataProperty(cx, id, next, JSPROP_ENUMERATE)) {
> +            JS_ALWAYS_TRUE(setLastProperty(cx, oldShape));

Why not setLastPropertyInfallible?

::: js/src/jsobj.cpp
@@ +4621,1 @@
>      if (!tmpslots)

I assume by 'tmpslots' you mean "a temporary slots variable which will be assigned to the real 'slots' later", but it reads like "a pointer to temporary storage".  'new' matches the 'old'/'new' naming scheme, so perhaps s/tmpslots/newslots/ ?

@@ +4700,5 @@
> +    size_t oldSize = Probes::objectResizeActive() ? slotsAndStructSize() : 0;
> +
> +    uint32 nextsize = (oldcap <= CAPACITY_DOUBLING_MAX)
> +                    ? oldcap * 2
> +                    : oldcap + (oldcap >> 3);

Preexisting: SM style is to align ? with condition (so the ( )

@@ +4726,5 @@
> +                         (actualCapacity + 2) * sizeof(Value));
> +        if (!tmpheader)
> +            return false;  /* Leave elements as its old size. */
> +    } else {
> +        tmpheader = (ObjectElements *) cx->malloc_((actualCapacity + 2) * sizeof(Value));

Similarly, s/tmpheader/newheader/

@@ +4762,5 @@
> +
> +    JS_STATIC_ASSERT(sizeof(ObjectElements) == 2 * sizeof(js::Value));
> +
> +    ObjectElements *tmpheader = (ObjectElements *)
> +        cx->realloc_(getElementsHeader(), (newcap + 2) * sizeof(Value));

Instead of this static+assert + magic constant (which I think I've seen 3 or 4 times), could you instead have a global:

  static VALUES_PER_OBJECT_HEADER = sizeof(ObjectHeader) / sizeof(Value);
  JS_STATIC_ASSERT(sizeof(ObjectHeader) % sizeof(Value) == 0);

In jsobj.h and use VALUES_PER_OBJECT_HEADER in all the alloc calls?  (This is pattern is used for VALUES_PER_STACK_FRAME/VALUES_PER_STACK_SEGMENT so clearly I am biased towards it ;)

::: js/src/jsobj.h
@@ +356,5 @@
> + * followed by an array of elements, with the elements member in an object
> + * pointing to the beginning of that array (the end of this structure).
> + * See below for usage of this structure.
> + */
> +struct ObjectElements

For new structures, I'd really like to start with "class ObjectElements" and have all the fields private (with suffixed by _ so that the getters don't need to be prefixed by 'get' to avoid clash).

@@ +412,5 @@
>   * object and the possible types of its properties.
>   *
> + * The rest of the object stores its named properties and indexed elements.
> + * These are stored separately from one another, and either may make use of a
> + * variable-sized array of fixed slots immediately following the object.

The last sentence introduces the term "fixed slots" which is used below.  I missed it the first time and had to re-read; perhaps you can end the sentence after "another" and start a new one sentence: "The GC allocation for an object includes a variable number of slots following the object header; these are called "fixed slots".  The fixed slots of an object can be used to store either properties are elements."

@@ +421,5 @@
> + * Named property storage can be split between fixed slots and a dynamically
> + * allocated array (the slots member). For an object with N fixed slots, shapes
> + * with slots [0..N-1] are stored in the fixed slots, and the remainder are
> + * stored in the dynamic array. If all properties fit in the fixed slots, the
> + * properties member is NULL.

I'd add quotes, making it "the 'properties' member is NULL."

@@ +426,2 @@
>   *
> + * Elements are indexed via the elements member. This member can point to

'elements'

@@ +460,3 @@
>      /*
>       * Private pointer to the last added property and methods to manipulate the
>       * list it links among properties in this scope.

Perhaps you could you freshen up this comment as well?  Perhaps stating that 'shape_'  describes the layout of the entire object and that this layout is encoded as a linked list of js::Shape records where each Shape describes a non-element property.

@@ +550,3 @@
>  
>    private:
> +    js::Value   *slots;                     /* Slots for object properties. */

Do you have any plans in this stack of patches to s/slots/properties/?  Similarly, there are a lot of JSObject member functions that have "Slots" in the name where it would be nice to have "PropertySlots" or "Properties" or something instead.  If you'd rather not, that's ok, I imagine Waldo will, but since you're touching so much of it all anyway...

@@ +699,5 @@
> +    void shrinkSlots(JSContext *cx, uint32 oldCount, uint32 newCount);
> +    bool changeSlots(JSContext *cx, uint32 oldCount, uint32 newCount) {
> +        if (oldCount < newCount)
> +            return growSlots(cx, oldCount, newCount);
> +        else if (oldCount > newCount)

SM style is to take out the 'else'.

::: js/src/jsobjinlines.h
@@ +429,5 @@
> +
> +    size_t log2;
> +    JS_FLOOR_LOG2(log2, span - 1);
> +    size_t slots = 1 << (log2 + 1);
> +    JS_ASSERT(slots >= span);

Can you use js::RoundUpPow2 instead?

On a more general note: it looks like this is committing to always use doubling for property slots.  Do we have any about:memory instrumentation to measure the amount of memory wasted in this manner (rather than just lumping it all into "object slots")?  It looks like, before, we stopped doubling at 1M entries, so this seems like something we should measure when doing the final obj-shrink measurements.

@@ +485,5 @@
>      /*
>       * Check that the range [start, start+count) is either all inline or all
>       * out of line.
>       */
> +    JS_ASSERT(slotInRange(start + count, /* sentinelAllowed = */ true));

Rather than using a comment, can you just make slotInRange take an enum, allowing this to read slotInRange(start + count, SENTINEL_ALLOWED)?

@@ +935,4 @@
>  
> +    JS_STATIC_ASSERT(sizeof(js::ObjectElements) == 2 * sizeof(js::Value));
> +
> +    uint32 numSlots = numFixedSlots();

Could you have fixed or nfixed instead?

@@ +939,4 @@
>  
>      /*
>       * Fill the fixed slots with undefined if needed.  This object must
> +     * already have its numFixedSlots() filled in, as by js_NewGCObject.

Seems like the comment should go before the numFixedSlots() call above.

::: js/src/jsscope.cpp
@@ -965,5 @@
> -        JS_ASSERT(shape == lastProp);
> -        removeLastProperty();
> -    }
> -
> -    /* Consider shrinking object slots if 25% or more are unused. */

Is there a reason to remove this other than that you don't think it helps?  The "unused slot capacity" measurement should also help measure this.

::: js/src/jsscope.h
@@ +717,5 @@
>  
> +    uint32 slotSpan() const {
> +        JS_ASSERT(!inDictionary());
> +        uint32 free = JSSLOT_FREE(getClass());
> +        return hasMissingSlot() ? free : Max(free, maybeSlot() + 1);

Can you s/maybeSlot()/slot()/ (or maybe slot_, I don't know whether hasSlot() must be true here...) ?

::: js/src/jstypedarray.cpp
@@ +171,3 @@
>              return false;
> +        elements = tmpheader->elements();
> +        tmpheader->length = size;

Also s/tempheader/newheader/

Comment 6

[Brian Hackett [Laid off!]]

Sorry for the late response, forgot to apply these.

(In reply to Luke Wagner [:luke] from comment #5)
> ::: js/src/jsarray.cpp
> @@ +1378,2 @@
> >          if (!addDataProperty(cx, id, next, JSPROP_ENUMERATE)) {
> > +            JS_ALWAYS_TRUE(setLastProperty(cx, oldShape));
> 
> Why not setLastPropertyInfallible?

setLastPropertyInfallible can only be used on shape changes that don't change the slot span (changing info describing the object itself, typically).  In this case the slot span can shrink, and shrinking property changes can't fail.

> @@ +550,3 @@
> >  
> >    private:
> > +    js::Value   *slots;                     /* Slots for object properties. */
> 
> Do you have any plans in this stack of patches to s/slots/properties/? 
> Similarly, there are a lot of JSObject member functions that have "Slots" in
> the name where it would be nice to have "PropertySlots" or "Properties" or
> something instead.  If you'd rather not, that's ok, I imagine Waldo will,
> but since you're touching so much of it all anyway...

Most of the users of the *Slots members have not themselves changed, and I'd like to save renaming the members for a followup cleanup to reduce the diff size against trunk.

> ::: js/src/jsobjinlines.h
> @@ +429,5 @@
> > +
> > +    size_t log2;
> > +    JS_FLOOR_LOG2(log2, span - 1);
> > +    size_t slots = 1 << (log2 + 1);
> > +    JS_ASSERT(slots >= span);
> 
> Can you use js::RoundUpPow2 instead?
> 
> On a more general note: it looks like this is committing to always use
> doubling for property slots.  Do we have any about:memory instrumentation to
> measure the amount of memory wasted in this manner (rather than just lumping
> it all into "object slots")?  It looks like, before, we stopped doubling at
> 1M entries, so this seems like something we should measure when doing the
> final obj-shrink measurements.

Objects with one million properties will also have one million shapes (such objects will use ~30MB of data each on 32 bit), and the size of those shapes will be a good deal larger than the space saved by a smarter sizing strategy).  I think the slower growth strategy was designed for arrays, which can get very large without making new shapes.  The allocation mechanism for these has moved to JSObject::growElements, which retains the original behavior of growing slower for larger arrays.

> ::: js/src/jsscope.cpp
> @@ -965,5 @@
> > -        JS_ASSERT(shape == lastProp);
> > -        removeLastProperty();
> > -    }
> > -
> > -    /* Consider shrinking object slots if 25% or more are unused. */
> 
> Is there a reason to remove this other than that you don't think it helps? 
> The "unused slot capacity" measurement should also help measure this.

Slot arrays can still shrink when properties get removed, but this now happens when the slot span changes rather than in removeProperty.