Closed Bug 603318 Opened 14 years ago Closed 14 years ago

attempt to schedule the GC when making arrays slow under the GC


(Core :: JavaScript Engine, defect)

Not set



Tracking Status
blocking2.0 --- betaN+


(Reporter: igor, Assigned: igor)



(Whiteboard: fixed-in-tracemonkey)


(1 file, 6 obsolete files)

JSObject::makeDenseArraySlow, when called from the GC for a big fast array, can allocate a lot of shapes which may caused a call to TriggerGC. That function assumes currently that the GC is not running leading to an assert.

This is a regression from the bug 580846.
Here is a test case:

~/m/tm/js/src> cat ~/s/x.js
var array = [];
for (var i = 0; i != 5e6; ++i)
    array[i * 5] = 0;
~/m/tm/js/src> ~/b/ -j ~/s/x.js
Assertion failure: !rt->gcRunning, at /home/igor/m/tm/js/src/jsgc.cpp:1844
Aborted (core dumped)
blocking2.0: --- → ?
We shouldn't be slowifying from GC, should we?

(In reply to comment #2)
> We shouldn't be slowifying from GC, should we?

That's what bug 580846 did.  From the POV of array accesses it was really good -- it allowed the COUNT and MINLENCAP slots to disappear, which allowed SETELEM to be inlined.  This was particularly good for Kraken which is dominated by small loops containing array accesses.
Mhm, I wonder whether this is causing some of the redness on TM.
The assert in question is harmless - the arrays are turned slow at the very end of the GC when it is OK to allocate. I plan to add a debug-only flag like rt->really_running_gc and then assert on it.
Gregor started work on the per-compartment GC, so please don't this kind of state per compartment.
As an alternative to tinkering with the GC I consider to make the array slow when it needs to grow. At that moment array's memory is copied so enumerating the array to count holes could be cheap.
Attached patch wip (obsolete) — Splinter Review
work in progress to implement the above idea of making array slow only when it grows
Blocks: 606477
Blocks: 607825
Attached patch wip (obsolete) — Splinter Review
Here is an updated patch that tries to minimize a performance loss due to the holes check during the array growth. I will test and report benchmark results later.
Attachment #482966 - Attachment is obsolete: true
The latest patch shows 6% on SS with no changes in V8. The biggest slowdown comes from tagcloud - 50% slower. What happens with the patch is that array becomes sparse much earlier as the code detects that on array growth. I will try to tune that.
Attached patch v1 (obsolete) — Splinter Review
The previous patch had a bug that effectively made NewPreallocatedArray untraceable. With this fixed SS only slows down by 0.2%. That came mostly from access-nsieve that became 3.5% slower. The slow down clearly comes from the code to count number of holes in a dense array on array growth.

To bhackett1024: could you tell if this is problematic or the forthcoming chnages would take care about it?
Attachment #486670 - Attachment is obsolete: true
Attached patch v2 (obsolete) — Splinter Review
The new version optimizes JSObject::isSparseDenseArray() to count non-hole elements and stop counting when it reaches minimal dense capacity. With that SS and V8 shows no slowdowns.
Attachment #487068 - Attachment is obsolete: true
Attachment #487085 - Flags: review?(jorendorff)
(In reply to comment #12)
> The new version optimizes JSObject::isSparseDenseArray() to count non-hole
> elements and stop counting when it reaches minimal dense capacity. 

That was suggested by Brian Hackett on irc.
blocking2.0: ? → betaN+
Attached patch v3 (obsolete) — Splinter Review
Here is a rebased patch. Asking Brian for a review as Jason is busy.
Attachment #487085 - Attachment is obsolete: true
Attachment #493677 - Flags: review?(bhackett1024)
Attachment #487085 - Flags: review?(jorendorff)
Comment on attachment 493677 [details] [diff] [review]

Looks good.  Are there test cases stressing the slowify-sparse-array paths on trace and in the Array natives which you've modified?  If not, can you add some?

>@@ -1430,19 +1464,21 @@ InitArrayElements(JSContext *cx, JSObjec
> static JSBool
> InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, const Value *vector)
> {
>     JS_ASSERT(obj->isArray());
>     JS_ASSERT(obj->isDenseArray());
>     obj->setArrayLength(length);
>     if (!vector || !length)
>         return true;
>-    if (!obj->ensureDenseArrayElements(cx, length))
>+    JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length);
>+    JS_ASSERT(result == JSObject::ED_FAILED || result == JSObject::ED_OK);
>+    if (result == JSObject::ED_FAILED)
>         return false;
>     memcpy(obj->getDenseArrayElements(), vector, length * sizeof(Value));
>     return true;
> }

I'd use ensureSlots instead of ensureDenseArrayElements here, faster and more robust.

> ArrayCompPushImpl(JSContext *cx, JSObject *obj, const Value &v)
> {
>     JS_ASSERT(obj->isDenseArray());
>     uint32_t length = obj->getArrayLength();
>     JS_ASSERT(length <= obj->getDenseArrayCapacity());
>     if (length == obj->getDenseArrayCapacity()) {
>         if (length > JS_ARGS_LENGTH_MAX) {
>             JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
>                                    JSMSG_ARRAY_INIT_TOO_BIG);
>             return JS_FALSE;
>         }
>-        if (!obj->ensureDenseArrayElements(cx, length + 1))
>-            return JS_FALSE;
>+        /*
>+         * Array comprehension cannot add holes to array and never leaks the
>+         * array before it is fully initialized. So we cannot get ED_SPARSE.
>+         */
>+        JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length + 1);
>+        JS_ASSERT(result == JSObject::ED_OK || result == JSObject::ED_FAILED);
>+        if (result != JSObject::ED_OK)
>+            return false;
>     }
>     obj->setArrayLength(length + 1);
>     obj->setDenseArrayElement(length, v);
>     return JS_TRUE;
> }

Attachment #493677 - Flags: review?(bhackett1024) → review+
Attached patch v4 (obsolete) — Splinter Review
While addressing the nits above I noticed that the INDEX_TOO_SPARSE check almost always followed by the ensureDenseArrayElements call. The only exception was array_defineProperty where the INDEX_TOO_SPARSE check duplicated the checks that array_setProperty would do.

So the new version merges INDEX_TOO_BIG/INDEX_TOO_SPARSE with ensureDenseArrayElements which does now all the index checks.

As regarding the test coverage it seems we do not have one to test for fast->slow transitions on the trace. I will update the patch with few test cases.
Attachment #493677 - Attachment is obsolete: true
Attachment #494071 - Flags: review?(bhackett1024)
Attached patch v5Splinter Review
The new patch includes a trace test to test dense->slow transition both during recording and on trace.
Attachment #494071 - Attachment is obsolete: true
Attachment #494386 - Flags: review?(bhackett1024)
Attachment #494071 - Flags: review?(bhackett1024)
Comment on attachment 494386 [details] [diff] [review]

Nice simplification.  I see the test for slowify on trace now, are there tests for slowify in the middle of natives like reverse() and push() (and other ones modified in the patch)?

>+JSObject::willBeSparseDenseArray(uintN requiredCapacity, uintN newElelementsHint)

Can you fix the name for newElelementsHint?

>         /*
>          * Use the slower NEWINIT for arrays in scripts containing sharps, and when
>          * the array length exceeds MIN_SPARSE_INDEX and can be slowified during GC.
>          * :FIXME: bug 607825 handle slowify case.
>          */
>-        if (cg->hasSharps() || pn->pn_count >= MIN_SPARSE_INDEX) {
>+        if (cg->hasSharps() || pn->pn_count > MIN_SPARSE_INDEX) {
>             if (!EmitNewInit(cx, cg, JSProto_Array, pn, sharpnum))
>                 return JS_FALSE;

Since you've fixed JSOP_NEWARRAY in the interpreter and tracer to use ensureSlots, and the method JIT already does use ensureSlots, you should be able to remove the MIN_SPARSE_INDEX check and FIXME here, and resolve bug 607825.
Attachment #494386 - Flags: review?(bhackett1024) → review+ - landed with extra tests and nits addressed.
Whiteboard: fixed-in-tracemonkey
Closed: 14 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.