Last Comment Bug 835102 - Densify sparse arrays that have enough indexed properties
: Densify sparse arrays that have enough indexed properties
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:
Depends on: 827490 832364 836563 836623
Blocks: 817446
  Show dependency treegraph
 
Reported: 2013-01-26 17:52 PST by Brian Hackett (:bhackett)
Modified: 2013-02-06 03:41 PST (History)
4 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
patch (22.47 KB, patch)
2013-01-26 17:52 PST, Brian Hackett (:bhackett)
no flags Details | Diff | Review
updated (23.27 KB, patch)
2013-01-29 05:04 PST, Brian Hackett (:bhackett)
wmccloskey: review+
Details | Diff | Review

Description Brian Hackett (:bhackett) 2013-01-26 17:52:51 PST
Created attachment 706826 [details] [diff] [review]
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 (:billm) 2013-01-28 17:45:28 PST
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 (:bhackett) 2013-01-29 05:04:39 PST
Created attachment 707577 [details] [diff] [review]
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 (:bhackett) 2013-01-29 06:01:03 PST
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 (:billm) 2013-01-29 14:04:36 PST
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 (:bhackett) 2013-01-29 18:52:29 PST
(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] 2013-01-30 05:18:25 PST
https://hg.mozilla.org/mozilla-central/rev/7d45649de683

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