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

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

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.

Comment 1

[Igor Bukanov]

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;
gc();
~/m/tm/js/src> ~/b/js32dbg.tm/js -j ~/s/x.js
Assertion failure: !rt->gcRunning, at /home/igor/m/tm/js/src/jsgc.cpp:1844
Aborted (core dumped)

Comment 2

[Brendan Eich [:brendan]]

We shouldn't be slowifying from GC, should we?

/be

Comment 3

[Nicholas Nethercote [inactive]]

(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.

Comment 4

[Andreas Gal :gal]

Mhm, I wonder whether this is causing some of the redness on TM.

Comment 5

[Igor Bukanov]

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.

Comment 6

[Andreas Gal :gal]

Gregor started work on the per-compartment GC, so please don't this kind of state per compartment.

Comment 7

[Igor Bukanov]

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.

Comment 8

[Igor Bukanov]

Attachment: wip

work in progress to implement the above idea of making array slow only when it grows

Comment 9

[Igor Bukanov]

Attachment: wip

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.

Comment 10

[Igor Bukanov]

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.

Comment 11

[Igor Bukanov]

Attachment: v1

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?

Comment 12

[Igor Bukanov]

Attachment: v2

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.

Comment 13

[Igor Bukanov]

(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.

Comment 14

[Igor Bukanov]

Attachment: v3

Here is a rebased patch. Asking Brian for a review as Jason is busy.

Comment 15

[Brian Hackett [Laid off!]]

Comment on attachment 493677 [details] [diff] [review]
v3

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.

> JS_ALWAYS_INLINE JSBool
> 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;
> }

Ditto.

Comment 16

[Igor Bukanov]

Attachment: v4

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.

Comment 17

[Igor Bukanov]

Attachment: v5

The new patch includes a trace test to test dense->slow transition both during recording and on trace.

Comment 18

[Brian Hackett [Laid off!]]

Comment on attachment 494386 [details] [diff] [review]
v5

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)?

>+bool
>+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.

Comment 19

[Igor Bukanov]

http://hg.mozilla.org/tracemonkey/rev/f2177f643230 - landed with extra tests and nits addressed.

Comment 21

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/f2177f643230