835102 - Densify sparse arrays that have enough indexed properties

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

If we are adding elements to an object and find that its dense elements are too sparse, we sparsify its contents to save memory on giant arrays.  If the remainder of the array ends up being filled in, however, we never reverse this operation and densify its contents.  Doing so would be a big gain for both performance and memory usage.

With bug 827490 fixed this is now possible to do, and with bug 832364 fixed Ion can now generate optimized paths for accessing non-hole elements of arrays that have been densified (hole accesses still need to be stubbed because the TI information will indicate the object may have sparse indexes).

The attached patch makes this change, and tweaks heuristics a bit so we sparsify less often.  When adding properties to an object, we occasionally check to see if the object's indexed properties fill more than 1/8 of the space it would require were it dense.  If so, the sparse indexes are converted to dense elements.

Comment 1

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

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

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

I like the DefinePropertyOrElement refactoring, but the old code is gross enough that I'd like to see the patch again after the comments are addressed. Also, please let me know if I'm wrong about any of the comments; I've never had a very strong grasp about how all this stuff worked.

::: js/src/jsobj.cpp
@@ +2579,5 @@
> +
> +    RootedShape shape(cx, obj->lastProperty());
> +    while (!shape->isEmptyShape()) {
> +        uint32_t index;
> +        if (js_IdIsIndex(shape->propid(), &index)) {

It looks like it would be possible, and a little faster and clearer, to use JSID_IS_INT and JSID_TO_INT here.

Also, as an aside, it looks like the |i < 0| check in js_IdIsIndex is unnecessary. If you have a chance, could you turn it into an assertion?

@@ +2587,5 @@
> +            {
> +                numDenseElements++;
> +                newInitializedLength = Max(newInitializedLength, index + 1);
> +            } else {
> +                /* It must be possible to convert all sparse indexes. */

Why is this? Can't we just stick a hole in these positions? I don't really care what we do, but the comment is confusing.

@@ +2594,5 @@
> +        }
> +        shape = shape->previous();
> +    }
> +
> +    if (numDenseElements * 8 < newInitializedLength)

Since this 8 constant now appears in two places, could you please give it a name?

@@ +2616,5 @@
> +    shape = obj->lastProperty();
> +    while (!shape->isEmptyShape()) {
> +        jsid id = shape->propid();
> +        uint32_t index;
> +        if (js_IdIsIndex(id, &index)) {

Same here as above.

@@ +3201,5 @@
>  }
>  
> +static inline bool
> +DefinePropertyOrElement(JSContext *cx, HandleObject obj, HandleId id,
> +                        const PropertyOp *getter, const StrictPropertyOp *setter,

I don't understand why getter and setter are passed by address. Can they just be normal parameters?

@@ +3248,5 @@
> +    if (!CallAddPropertyHook(cx, obj->getClass(), obj, shape, value))
> +        return false;
> +
> +    if (callSetterAfterwards && *setter != JS_StrictPropertyStub) {
> +        JS_ASSERT(!(attrs & JSPROP_SETTER));

I don't understand this assertion. I don't see anything to guarantee that we don't have a value setter from SetPropertyHelper.

@@ +3250,5 @@
> +
> +    if (callSetterAfterwards && *setter != JS_StrictPropertyStub) {
> +        JS_ASSERT(!(attrs & JSPROP_SETTER));
> +        RootedValue nvalue(cx, value);
> +        return CallJSPropertyOpSetter(cx, *setter, obj, id, setterIsStrict, &nvalue);

I think you need to do what js_NativeSet does here and do a setSlot with nvalue.

@@ +4184,5 @@
>          if (!js_PurgeScopeChain(cx, obj, id))
> +            return false;
> +
> +        if (getter == JS_PropertyStub)
> +            AddTypePropertyId(cx, obj, id, vp);

Don't we want to be doing the check on the setter rather than the getter? That's what js_NativeSet does, at least.

@@ +4192,3 @@
>      }
>  
> +    if ((defineHow & DNP_CACHE_RESULT))

Double parens not needed.

Comment 2

[Brian Hackett [Laid off!]]

Attachment: updated

Thanks for the comments.  The js_IdIsIndex thing is because the INDEXED flag should indicate whether an object has any indexed properties, not just any JSID_IS_INT properties, and I'd like to ensure the process bails on super high indexes.

Comment 3

[Brian Hackett [Laid off!]]

Oh, also, the '(getter == JS_PropertyStub)' test is to follow along with what DefineNativeProperty does in this case.  Type information only describes normal data properties, so if there is a getter involved then it is fine if there is no type info.  The AddTypePropertyId in js_NativeSet under (shape->hasDefaultSetter()) is to handle the early return immediately afterwards.

Comment 4

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

Comment on attachment 707577 [details] [diff] [review]
updated

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

Thanks, I see what you mean about the type stuff.

::: js/src/jsobj.cpp
@@ +3246,5 @@
> +        JSObject::EnsureDenseResult result = JSObject::maybeDensifySparseElements(cx, obj);
> +        if (result == JSObject::ED_FAILED)
> +            return false;
> +        if (result == JSObject::ED_OK)
> +            return CallAddPropertyHookDense(cx, obj->getClass(), obj, index, value);

I think it's possible for their to be a setter in this case, in which case we'll fail to call it. Is there any reason this path needs to return early? It seems like maybe we only need to check for ED_FAILED.

::: js/src/jsobj.h
@@ +629,5 @@
> +    static const unsigned MIN_SPARSE_INDEX = 1000;
> +
> +    /*
> +     * Maximum ratio for elements / non-hole elements in an object, above
> +     * which the object will be sparse.

This comment was a little confusing to me. Maybe something like "Element storage will be sparse if fewer than 1/8 of elements are present."

Comment 5

[Brian Hackett [Laid off!]]

(In reply to Bill McCloskey (:billm) from comment #4)
> Comment on attachment 707577 [details] [diff] [review]
> updated
> 
> Review of attachment 707577 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Thanks, I see what you mean about the type stuff.
> 
> ::: js/src/jsobj.cpp
> @@ +3246,5 @@
> > +        JSObject::EnsureDenseResult result = JSObject::maybeDensifySparseElements(cx, obj);
> > +        if (result == JSObject::ED_FAILED)
> > +            return false;
> > +        if (result == JSObject::ED_OK)
> > +            return CallAddPropertyHookDense(cx, obj->getClass(), obj, index, value);
> 
> I think it's possible for their to be a setter in this case, in which case
> we'll fail to call it. Is there any reason this path needs to return early?
> It seems like maybe we only need to check for ED_FAILED.

We will only succeed in densifying here if all indexed properties (including the one currently being added) are normal data properties with no setter.

https://hg.mozilla.org/integration/mozilla-inbound/rev/7d45649de683

Comment 6

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/7d45649de683