bug 603318 - make dense array slow during array growth, not during the GC. r=bhackett
authorIgor Bukanov <igor@mir2.org>
Thu, 14 Oct 2010 16:12:19 +0200
changeset 58702 f2177f6432306326278ede5445051e03f0b9e9aa
parent 58701 0aad954c48ed8aab15c9e8f996ff3eb55ccdc637
child 58703 08c80bfca30297a0c0deed9e6083d95b88dce412
push id17407
push userrsayre@mozilla.com
push dateMon, 06 Dec 2010 22:03:37 +0000
treeherdermozilla-central@2f96714fd6d2 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs603318
milestone2.0b8pre
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
bug 603318 - make dense array slow during array growth, not during the GC. r=bhackett
js/src/jit-test/tests/basic/testDenseToSlowArray.js
js/src/jsarray.cpp
js/src/jsarray.h
js/src/jsemit.cpp
js/src/jsgc.cpp
js/src/jsgc.h
js/src/jsinterp.cpp
js/src/jsobj.h
js/src/jsobjinlines.h
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/testDenseToSlowArray.js
@@ -0,0 +1,185 @@
+// test dense -> slow array transitions during the recording and on trace
+// for various array functions and property accessors
+
+function test_set_elem() {
+
+    function f() {
+        var bag = [];
+        for (var i = 0; i != 100; ++i) {
+            var a = [0];
+            a[100*100] = i;
+            bag.push(a);
+        }
+        
+        for (var i = 0; i != 100; ++i) {
+            var a = [0];
+            a[200 + i] = i;
+            bag.push(a);
+        }
+        return bag;
+    }
+    
+    var bag = f();
+    
+    for (var i = 0; i != 100; ++i) {
+        var a = bag[i];
+        assertEq(a.length, 100 * 100 + 1);
+        assertEq(a[100*100], i);
+        assertEq(a[0], 0);
+        assertEq(1 + i in a, false);
+    }
+    
+    for (var i = 0; i != 100; ++i) {
+        var a = bag[100 + i];
+        assertEq(a.length, 200 + i + 1);
+        assertEq(a[200 + i], i);
+        assertEq(a[0], 0);
+        assertEq(1 + i in a, false);
+    }
+}
+
+function test_reverse() {
+
+    function prepare_arays() {
+        var bag = [];
+        var base_index = 245;
+        for (var i = 0; i != 50; ++i) {
+            var a = [1, 2, 3, 4, 5];
+            a.length = i + base_index;
+            bag.push(a);
+        }
+        return bag;
+    }
+
+    function test(bag) {
+        for (var i = 0; i != bag.length; ++i) {
+            var a = bag[i];
+            a.reverse();
+            a[0] = 1;
+        }
+    }
+
+    var bag = prepare_arays();
+    test(bag);
+    for (var i = 0; i != bag.length; ++i) {
+        var a = bag[i];
+        assertEq(a[0], 1);
+        for (var j = 1; j <= 5; ++j) {
+            assertEq(a[a.length - j], j);
+        }
+        for (var j = 1; j < a.length - 5; ++j) {
+            assertEq(j in a, false);
+        }
+    }
+    
+}
+
+function test_push() {
+
+    function prepare_arays() {
+        var bag = [];
+        var base_index = 245;
+        for (var i = 0; i != 50; ++i) {
+            var a = [0];
+            a.length = i + base_index;
+            bag.push(a);
+        }
+        return bag;
+    }
+
+    function test(bag) {
+        for (var i = 0; i != bag.length; ++i) {
+            var a = bag[i];
+            a.push(2);
+            a[0] = 1;
+        }
+    }
+
+    var bag = prepare_arays();
+    test(bag);
+    for (var i = 0; i != bag.length; ++i) {
+        var a = bag[i];
+        assertEq(a[0], 1); 
+        assertEq(a[a.length - 1], 2);
+        for (var j = 1; j < a.length - 1; ++j) {
+            assertEq(j in a, false);
+        }
+    }
+}
+
+function test_unshift() {
+
+    function prepare_arays() {
+        var bag = [];
+        var base_index = 245;
+        for (var i = 0; i != 50; ++i) {
+            var a = [0];
+            a.length = i + base_index;
+            bag.push(a);
+        }
+        return bag;
+    }
+
+    function test(bag) {
+        for (var i = 0; i != bag.length; ++i) {
+            var a = bag[i];
+            a.unshift(1);
+            a[2] = 2;
+        }
+    }
+
+    var bag = prepare_arays();
+    test(bag);
+    for (var i = 0; i != bag.length; ++i) {
+        var a = bag[i];
+        assertEq(a[0], 1); 
+        assertEq(a[1], 0); 
+        assertEq(a[2], 2); 
+        for (var j = 3; j < a.length; ++j) {
+            assertEq(j in a, false);
+        }
+    }
+}
+
+function test_splice() {
+
+    function prepare_arays() {
+        var bag = [];
+        var base_index = 245;
+        for (var i = 0; i != 50; ++i) {
+            var a = [1, 2];
+            a.length = i + base_index;
+            bag.push(a);
+        }
+        return bag;
+    }
+
+    function test(bag) {
+        for (var i = 0; i != bag.length; ++i) {
+            var a = bag[i];
+            a.splice(1, 0, "a", "b", "c");
+            a[2] = 100;
+        }
+    }
+
+    var bag = prepare_arays();
+    test(bag);
+    for (var i = 0; i != bag.length; ++i) {
+        var a = bag[i];
+        assertEq(a[0], 1); 
+        assertEq(a[1], "a"); 
+        assertEq(a[2], 100); 
+        assertEq(a[3], "c"); 
+        assertEq(a[4], 2); 
+        for (var j = 5; j < a.length; ++j) {
+            assertEq(j in a, false);
+        }
+    }
+}
+
+test_set_elem();
+test_reverse();
+test_push();
+test_unshift();
+test_splice();
+
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -57,19 +57,19 @@
  *
  * NB: the capacity and length of a dense array are entirely unrelated!  The
  * length may be greater than, less than, or equal to the capacity.  See
  * array_length_setter for an explanation of how the first, most surprising
  * case may occur.
  *
  * Arrays are converted to use js_SlowArrayClass when any of these conditions
  * are met:
- *  - the load factor (COUNT / capacity) is less than 0.25, and there are
- *    more than MIN_SPARSE_INDEX slots total
- *  - a property is set that is not indexed (and not "length"); or
+ *  - there are more than MIN_SPARSE_INDEX slots total
+ *  - the load factor (COUNT / capacity) is less than 0.25
+ *  - a property is set that is not indexed (and not "length")
  *  - a property is defined that has non-default property attributes.
  *
  * Dense arrays do not track property creation order, so unlike other native
  * objects and slow arrays, enumerating an array does not necessarily visit the
  * properties in the order they were created.  We could instead maintain the
  * scope to track property enumeration order, but still use the fast slot
  * access.  That would have the same memory cost as just using a
  * js_SlowArrayClass, but have the same performance characteristics as a dense
@@ -110,40 +110,16 @@
 
 using namespace js;
 using namespace js::gc;
 
 /* 2^32 - 1 as a number and a string */
 #define MAXINDEX 4294967295u
 #define MAXSTR   "4294967295"
 
-/*
- * Use the limit on number of object slots for sanity and consistency (see the
- * assertion in JSObject::makeDenseArraySlow).
- */
-static inline bool
-INDEX_TOO_BIG(jsuint index)
-{
-    return index >= JSObject::NSLOTS_LIMIT;
-}
-
-static inline  bool
-INDEX_TOO_SPARSE(JSObject *array, jsuint index)
-{
-    /* Small arrays with less than 256 elements are dense, no matter what. */
-    if (index < 256)
-        return false;
-
-    /*
-     * Otherwise if the index becomes too large or is more than 256 past
-     * the current capacity, we have to slowify.
-     */
-    return INDEX_TOO_BIG(index) || (index > array->getDenseArrayCapacity() + 256);
-}
-
 static inline bool
 ENSURE_SLOW_ARRAY(JSContext *cx, JSObject *obj)
 {
     return obj->getClass() == &js_SlowArrayClass ||
            obj->makeDenseArraySlow(cx);
 }
 
 /*
@@ -305,16 +281,44 @@ BigIndexToId(JSContext *cx, JSObject *ob
         if (!atom)
             return JS_FALSE;
     }
 
     *idp = ATOM_TO_JSID(atom);
     return JS_TRUE;
 }
 
+bool
+JSObject::willBeSparseDenseArray(uintN requiredCapacity, uintN newElementsHint)
+{
+    JS_ASSERT(isDenseArray());
+    JS_ASSERT(requiredCapacity > MIN_SPARSE_INDEX);
+
+    uintN cap = numSlots();
+    JS_ASSERT(requiredCapacity >= cap);
+
+    if (requiredCapacity >= JSObject::NSLOTS_LIMIT)
+        return true;
+    
+    uintN minimalDenseCount = requiredCapacity / 4;
+    if (newElementsHint >= minimalDenseCount)
+        return false;
+    minimalDenseCount -= newElementsHint;
+
+    if (minimalDenseCount > cap)
+        return true;
+    
+    Value *elems = getDenseArrayElements();
+    for (uintN i = 0; i < cap; i++) {
+        if (!elems[i].isMagic(JS_ARRAY_HOLE) && !--minimalDenseCount)
+            return false;
+    }
+    return true;
+}
+
 static bool
 ReallyBigIndexToId(JSContext* cx, jsdouble index, jsid* idp)
 {
     return js_ValueToStringId(cx, DoubleValue(index), idp);
 }
 
 static bool
 IndexToId(JSContext* cx, JSObject* obj, jsdouble index, JSBool* hole, jsid* idp,
@@ -434,29 +438,33 @@ GetElements(JSContext *cx, JSObject *aob
  */
 static JSBool
 SetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, const Value &v)
 {
     JS_ASSERT(index >= 0);
 
     if (obj->isDenseArray()) {
         /* Predicted/prefetched code should favor the remains-dense case. */
-        if (index <= jsuint(-1)) {
+        JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
+        do {
+            if (index > jsuint(-1))
+                break;
             jsuint idx = jsuint(index);
-            if (!INDEX_TOO_SPARSE(obj, idx)) {
-                JS_ASSERT(idx + 1 > idx);
-                if (!obj->ensureDenseArrayElements(cx, idx + 1))
-                    return JS_FALSE;
-                if (idx >= obj->getArrayLength())
-                    obj->setArrayLength(idx + 1);
-                obj->setDenseArrayElement(idx, v);
-                return JS_TRUE;
-            }
-        }
-
+            result = obj->ensureDenseArrayElements(cx, idx, 1);
+            if (result != JSObject::ED_OK)
+                break;
+            if (idx >= obj->getArrayLength())
+                obj->setArrayLength(idx + 1);
+            obj->setDenseArrayElement(idx, v);
+            return true;
+        } while (false);
+
+        if (result == JSObject::ED_FAILED)
+            return false;
+        JS_ASSERT(result == JSObject::ED_SPARSE);
         if (!obj->makeDenseArraySlow(cx))
             return JS_FALSE;
     }
 
     AutoIdRooter idr(cx);
 
     if (!IndexToId(cx, obj, index, NULL, idr.addr(), JS_TRUE))
         return JS_FALSE;
@@ -469,23 +477,17 @@ SetArrayElement(JSContext *cx, JSObject 
 #ifdef JS_TRACER
 JSBool JS_FASTCALL
 js_EnsureDenseArrayCapacity(JSContext *cx, JSObject *obj, jsint i)
 {
 #ifdef DEBUG
     Class *origObjClasp = obj->clasp; 
 #endif
     jsuint u = jsuint(i);
-    jsuint capacity = obj->getDenseArrayCapacity();
-    if (u < capacity)
-        return true;
-    if (INDEX_TOO_SPARSE(obj, u))
-        return false;
-
-    JSBool ret = obj->ensureDenseArrayElements(cx, u + 1);
+    JSBool ret = (obj->ensureDenseArrayElements(cx, u, 1) == JSObject::ED_OK);
 
     /* Partially check the CallInfo's storeAccSet is correct. */
     JS_ASSERT(obj->clasp == origObjClasp);
     return ret;
 }
 /* This function and its callees do not touch any object's .clasp field. */
 JS_DEFINE_CALLINFO_3(extern, BOOL, js_EnsureDenseArrayCapacity, CONTEXT, OBJECT, INT32,
                      0, nanojit::ACCSET_STORE_ANY & ~tjit::ACCSET_OBJ_CLASP)
@@ -796,30 +798,39 @@ array_setProperty(JSContext *cx, JSObjec
     uint32 i;
 
     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
         return array_length_setter(cx, obj, id, vp, strict);
 
     if (!obj->isDenseArray())
         return js_SetProperty(cx, obj, id, vp, strict);
 
-    if (!js_IdIsIndex(id, &i) || js_PrototypeHasIndexedProperties(cx, obj) ||
-        INDEX_TOO_SPARSE(obj, i)) {
-        if (!obj->makeDenseArraySlow(cx))
-            return false;
-        return js_SetProperty(cx, obj, id, vp, strict);
-    }
-
-    if (!obj->ensureDenseArrayElements(cx, i + 1))
+    do {
+        if (!js_IdIsIndex(id, &i))
+            break;
+        if (js_PrototypeHasIndexedProperties(cx, obj))
+            break;
+
+        JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, i, 1);
+        if (result != JSObject::ED_OK) {
+            if (result == JSObject::ED_FAILED)
+                return false;
+            JS_ASSERT(result == JSObject::ED_SPARSE);
+            break;
+        }
+
+        if (i >= obj->getArrayLength())
+            obj->setArrayLength(i + 1);
+        obj->setDenseArrayElement(i, *vp);
+        return true;
+    } while (false);
+
+    if (!obj->makeDenseArraySlow(cx))
         return false;
-
-    if (i >= obj->getArrayLength())
-        obj->setArrayLength(i + 1);
-    obj->setDenseArrayElement(i, *vp);
-    return true;
+    return js_SetProperty(cx, obj, id, vp, strict);
 }
 
 static JSBool
 slowarray_setProperty(JSContext *cx, JSObject *obj, jsid id, Value *vp, JSBool strict)
 {
     JS_ASSERT(obj->isSlowArray());
 
     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
@@ -856,17 +867,17 @@ array_defineProperty(JSContext *cx, JSOb
 {
     uint32 i = 0;       // init to shut GCC up
     JSBool isIndex;
 
     if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
         return JS_TRUE;
 
     isIndex = js_IdIsIndex(id, &i);
-    if (!isIndex || attrs != JSPROP_ENUMERATE || !obj->isDenseArray() || INDEX_TOO_SPARSE(obj, i)) {
+    if (!isIndex || attrs != JSPROP_ENUMERATE) {
         if (!ENSURE_SLOW_ARRAY(cx, obj))
             return JS_FALSE;
         return js_DefineProperty(cx, obj, id, value, getter, setter, attrs);
     }
 
     Value tmp = *value;
     return array_setProperty(cx, obj, id, &tmp, false);
 }
@@ -910,30 +921,19 @@ array_deleteProperty(JSContext *cx, JSOb
     return JS_TRUE;
 }
 
 static void
 array_trace(JSTracer *trc, JSObject *obj)
 {
     JS_ASSERT(obj->isDenseArray());
 
-    size_t holes = 0;
     uint32 capacity = obj->getDenseArrayCapacity();
-    for (uint32 i = 0; i < capacity; i++) {
-        Value v = obj->getDenseArrayElement(i);
-        if (v.isMagic(JS_ARRAY_HOLE))
-            ++holes;
-        else
-            MarkValue(trc, obj->getDenseArrayElement(i), "dense_array_elems");
-    }
-
-    if (IS_GC_MARKING_TRACER(trc) && holes > MIN_SPARSE_INDEX && holes > capacity / 4 * 3) {
-        /* This might fail, in which case we don't slowify it. */
-        static_cast<GCMarker *>(trc)->arraysToSlowify.append(obj);
-    }
+    for (uint32 i = 0; i < capacity; i++)
+        MarkValue(trc, obj->getDenseArrayElement(i), "dense_array_elems");
 }
 
 static JSBool
 array_fix(JSContext *cx, JSObject *obj, bool *success, AutoIdVector *props)
 {
     JS_ASSERT(obj->isDenseArray());
 
     /*
@@ -1374,32 +1374,38 @@ static JSBool
 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint count, Value *vector)
 {
     JS_ASSERT(count < MAXINDEX);
 
     /*
      * Optimize for dense arrays so long as adding the given set of elements
      * wouldn't otherwise make the array slow.
      */
-    if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
-        start <= MAXINDEX - count && !INDEX_TOO_BIG(start + count)) {
-
+    do {
+        if (!obj->isDenseArray())
+            break;
+        if (js_PrototypeHasIndexedProperties(cx, obj))
+            break;
+
+        JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, start, count);
+        if (result != JSObject::ED_OK) {
+            if (result == JSObject::ED_FAILED)
+                return false;
+            JS_ASSERT(result == JSObject::ED_SPARSE);
+            break;
+        }
         jsuint newlen = start + count;
-        JS_ASSERT(jsdouble(start) + count == jsdouble(newlen));
-        if (!obj->ensureDenseArrayElements(cx, newlen))
-            return JS_FALSE;
-
         if (newlen > obj->getArrayLength())
             obj->setArrayLength(newlen);
 
         JS_ASSERT(count < uint32(-1) / sizeof(Value));
         memcpy(obj->getDenseArrayElements() + start, vector, sizeof(jsval) * count);
         JS_ASSERT_IF(count != 0, !obj->getDenseArrayElement(newlen - 1).isMagic(JS_ARRAY_HOLE));
-        return JS_TRUE;
-    }
+        return true;
+    } while (false);
 
     Value* end = vector + count;
     while (vector != end && start < MAXINDEX) {
         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
             !SetArrayElement(cx, obj, start++, *vector++)) {
             return JS_FALSE;
         }
     }
@@ -1431,17 +1437,19 @@ 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))
+
+    /* Avoid ensureDenseArrayElements to skip sparse array checks there. */
+    if (!obj->ensureSlots(cx, length))
         return false;
     memcpy(obj->getDenseArrayElements(), vector, length * sizeof(Value));
     return true;
 }
 
 /*
  * Perl-inspired join, reverse, and sort.
  */
@@ -1465,47 +1473,57 @@ static JSBool
 array_reverse(JSContext *cx, uintN argc, Value *vp)
 {
     jsuint len;
     JSObject *obj = ComputeThisFromVp(cx, vp);
     if (!obj || !js_GetLengthProperty(cx, obj, &len))
         return JS_FALSE;
     vp->setObject(*obj);
 
-    if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj)) {
+    do {
+        if (!obj->isDenseArray())
+            break;
+        if (js_PrototypeHasIndexedProperties(cx, obj))
+            break;
+        
         /* An empty array or an array with no elements is already reversed. */
         if (len == 0 || obj->getDenseArrayCapacity() == 0)
             return JS_TRUE;
 
         /*
          * It's actually surprisingly complicated to reverse an array due to the
          * orthogonality of array length and array capacity while handling
          * leading and trailing holes correctly.  Reversing seems less likely to
          * be a common operation than other array mass-mutation methods, so for
          * now just take a probably-small memory hit (in the absence of too many
          * holes in the array at its start) and ensure that the capacity is
          * sufficient to hold all the elements in the array if it were full.
          */
-        if (!obj->ensureDenseArrayElements(cx, len))
-            return JS_FALSE;
+        JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, len, 0);
+        if (result != JSObject::ED_OK) {
+            if (result == JSObject::ED_FAILED)
+                return false;
+            JS_ASSERT(result == JSObject::ED_SPARSE);
+            break;
+        }
 
         uint32 lo = 0, hi = len - 1;
         for (; lo < hi; lo++, hi--) {
             Value tmp = obj->getDenseArrayElement(lo);
             obj->setDenseArrayElement(lo, obj->getDenseArrayElement(hi));
             obj->setDenseArrayElement(hi, tmp);
         }
 
         /*
          * Per ECMA-262, don't update the length of the array, even if the new
          * array has trailing holes (and thus the original array began with
          * holes).
          */
         return JS_TRUE;
-    }
+    } while (false);
 
     AutoValueRooter tvr(cx);
     for (jsuint i = 0, half = len / 2; i < half; i++) {
         JSBool hole, hole2;
         if (!JS_CHECK_OPERATION_LIMIT(cx) ||
             !GetElement(cx, obj, i, &hole, tvr.addr()) ||
             !GetElement(cx, obj, len - i - 1, &hole2, vp) ||
             !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, tvr.value()) ||
@@ -2000,49 +2018,60 @@ array_push_slowly(JSContext *cx, JSObjec
     rval->setNumber(newlength);
     return js_SetLengthProperty(cx, obj, newlength);
 }
 
 static JSBool
 array_push1_dense(JSContext* cx, JSObject* obj, const Value &v, Value *rval)
 {
     uint32 length = obj->getArrayLength();
-    if (INDEX_TOO_SPARSE(obj, length)) {
-        if (!obj->makeDenseArraySlow(cx))
-            return JS_FALSE;
-        Value tmp = v;
-        return array_push_slowly(cx, obj, 1, &tmp, rval);
-    }
-
-    if (!obj->ensureDenseArrayElements(cx, length + 1))
-        return JS_FALSE;
-    obj->setArrayLength(length + 1);
-
-    JS_ASSERT(obj->getDenseArrayElement(length).isMagic(JS_ARRAY_HOLE));
-    obj->setDenseArrayElement(length, v);
-    rval->setNumber(obj->getArrayLength());
-    return JS_TRUE;
+    do {
+        JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, 1);
+        if (result != JSObject::ED_OK) {
+            if (result == JSObject::ED_FAILED)
+                return false;
+            JS_ASSERT(result == JSObject::ED_SPARSE);
+            break;
+        }
+
+        obj->setArrayLength(length + 1);
+
+        JS_ASSERT(obj->getDenseArrayElement(length).isMagic(JS_ARRAY_HOLE));
+        obj->setDenseArrayElement(length, v);
+        rval->setNumber(obj->getArrayLength());
+        return true;
+    } while (false);
+
+    if (!obj->makeDenseArraySlow(cx))
+        return false;
+    Value tmp = v;
+    return array_push_slowly(cx, obj, 1, &tmp, rval);
 }
 
 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 the array and never leaks
+         * the array before it is fully initialized. So we can use ensureSlots
+         * instead of ensureDenseArrayElements.
+         */
+        if (!obj->ensureSlots(cx, length + 1))
+            return false;
     }
     obj->setArrayLength(length + 1);
     obj->setDenseArrayElement(length, v);
     return JS_TRUE;
 }
 
 JSBool
 js_ArrayCompPush(JSContext *cx, JSObject *obj, const Value &vp)
@@ -2190,26 +2219,37 @@ array_unshift(JSContext *cx, uintN argc,
     JSObject *obj = ComputeThisFromVp(cx, vp);
     if (!obj || !js_GetLengthProperty(cx, obj, &length))
         return JS_FALSE;
     newlen = length;
     if (argc > 0) {
         /* Slide up the array to make room for argc at the bottom. */
         argv = JS_ARGV(cx, vp);
         if (length > 0) {
-            if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
-                !INDEX_TOO_SPARSE(obj, unsigned(newlen + argc))) {
-                JS_ASSERT(newlen + argc == length + argc);
-                if (!obj->ensureDenseArrayElements(cx, length + argc))
-                    return JS_FALSE;
+            bool optimized = false;
+            do {
+                if (!obj->isDenseArray())
+                    break;
+                if (js_PrototypeHasIndexedProperties(cx, obj))
+                    break;
+                JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, argc);
+                if (result != JSObject::ED_OK) {
+                    if (result == JSObject::ED_FAILED)
+                        return false;
+                    JS_ASSERT(result == JSObject::ED_SPARSE);
+                    break;
+                }
                 Value *elems = obj->getDenseArrayElements();
                 memmove(elems + argc, elems, length * sizeof(jsval));
                 for (uint32 i = 0; i < argc; i++)
                     obj->setDenseArrayElement(i, MagicValue(JS_ARRAY_HOLE));
-            } else {
+                optimized = true;
+            } while (false);
+
+            if (!optimized) {
                 last = length;
                 jsdouble upperIndex = last + argc;
                 AutoValueRooter tvr(cx);
                 do {
                     --last, --upperIndex;
                     if (!JS_CHECK_OPERATION_LIMIT(cx) ||
                         !GetElement(cx, obj, last, &hole, tvr.addr()) ||
                         !SetOrDeleteArrayElement(cx, obj, upperIndex, hole, tvr.value())) {
@@ -2319,31 +2359,45 @@ array_splice(JSContext *cx, uintN argc, 
                 return JS_FALSE;
         }
     }
 
     /* Find the direction (up or down) to copy and make way for argv. */
     if (argc > count) {
         delta = (jsuint)argc - count;
         last = length;
-        if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
-            length <= obj->getDenseArrayCapacity() &&
-            (length == 0 || !obj->getDenseArrayElement(length - 1).isMagic(JS_ARRAY_HOLE))) {
-            if (!obj->ensureDenseArrayElements(cx, length + delta))
-                return JS_FALSE;
-
+        bool optimized = false;
+        do {
+            if (!obj->isDenseArray())
+                break;
+            if (js_PrototypeHasIndexedProperties(cx, obj))
+                break;
+            if (length > obj->getDenseArrayCapacity())
+                break;
+            if (length != 0 && obj->getDenseArrayElement(length - 1).isMagic(JS_ARRAY_HOLE))
+                break;
+            JSObject::EnsureDenseResult result = obj->ensureDenseArrayElements(cx, length, delta);
+            if (result != JSObject::ED_OK) {
+                if (result == JSObject::ED_FAILED)
+                    return false;
+                JS_ASSERT(result == JSObject::ED_SPARSE);
+                break;
+            }
             Value *arraybeg = obj->getDenseArrayElements();
             Value *srcbeg = arraybeg + last - 1;
             Value *srcend = arraybeg + end - 1;
             Value *dstbeg = srcbeg + delta;
             for (Value *src = srcbeg, *dst = dstbeg; src > srcend; --src, --dst)
                 *dst = *src;
 
             obj->setArrayLength(obj->getArrayLength() + delta);
-        } else {
+            optimized = true;
+        } while (false);
+
+        if (!optimized) {
             /* (uint) end could be 0, so we can't use a vanilla >= test. */
             while (last-- > end) {
                 if (!JS_CHECK_OPERATION_LIMIT(cx) ||
                     !GetElement(cx, obj, last, &hole, tvr.addr()) ||
                     !SetOrDeleteArrayElement(cx, obj, last + delta, hole, tvr.value())) {
                     return JS_FALSE;
                 }
             }
@@ -2974,17 +3028,19 @@ JS_DEFINE_CALLINFO_3(extern, OBJECT, js_
 #endif
 
 JSObject* JS_FASTCALL
 js_NewPreallocatedArray(JSContext* cx, JSObject* proto, int32 len)
 {
     JSObject *obj = js_NewEmptyArray(cx, proto, len);
     if (!obj)
         return NULL;
-    if (!obj->ensureDenseArrayElements(cx, len))
+
+    /* Avoid ensureDenseArrayElements to skip sparse array checks there. */
+    if (!obj->ensureSlots(cx, len))     
         return NULL;
     return obj;
 }
 #ifdef JS_TRACER
 JS_DEFINE_CALLINFO_3(extern, OBJECT, js_NewPreallocatedArray, CONTEXT, OBJECT, INT32,
                      0, nanojit::ACCSET_STORE_ANY)
 #endif
 
--- a/js/src/jsarray.h
+++ b/js/src/jsarray.h
@@ -41,16 +41,56 @@
 #define jsarray_h___
 /*
  * JS Array interface.
  */
 #include "jsprvtd.h"
 #include "jspubtd.h"
 #include "jsobj.h"
 
+/* Small arrays are dense, no matter what. */
+const uintN MIN_SPARSE_INDEX = 256;
+
+inline JSObject::EnsureDenseResult
+JSObject::ensureDenseArrayElements(JSContext *cx, uintN index, uintN extra)
+{
+    JS_ASSERT(isDenseArray());
+    uintN currentCapacity = numSlots();
+
+    uintN requiredCapacity;
+    if (extra == 1) {
+        /* Optimize for the common case. */
+        if (index < currentCapacity)
+            return ED_OK;
+        requiredCapacity = index + 1;
+        if (requiredCapacity == 0) {
+            /* Overflow. */
+            return ED_SPARSE;
+        }
+    } else {
+        requiredCapacity = index + extra;
+        if (requiredCapacity < index) {
+            /* Overflow. */
+            return ED_SPARSE;
+        }
+        if (requiredCapacity <= currentCapacity)
+            return ED_OK;
+    }
+
+    /*
+     * We use the extra argument also as a hint about number of non-hole
+     * elements to be inserted.
+     */
+    if (requiredCapacity > MIN_SPARSE_INDEX &&
+        willBeSparseDenseArray(requiredCapacity, extra)) {
+        return ED_SPARSE;
+    }
+    return growSlots(cx, requiredCapacity) ? ED_OK : ED_FAILED;
+}
+
 extern JSBool
 js_StringIsIndex(JSString *str, jsuint *indexp);
 
 inline JSBool
 js_IdIsIndex(jsid id, jsuint *indexp)
 {
     if (JSID_IS_INT(id)) {
         jsint i;
@@ -139,19 +179,16 @@ js_InitContextBusyArrayTable(JSContext *
 
 extern JSObject *
 js_NewArrayObject(JSContext *cx, jsuint length, const js::Value *vector);
 
 /* Create an array object that starts out already made slow/sparse. */
 extern JSObject *
 js_NewSlowArrayObject(JSContext *cx);
 
-/* Minimum size at which a dense array can be made sparse. */
-const uint32 MIN_SPARSE_INDEX = 256;
-
 extern JSBool
 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp);
 
 extern JSBool
 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsdouble length);
 
 extern JSBool
 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp);
--- a/js/src/jsemit.cpp
+++ b/js/src/jsemit.cpp
@@ -6804,22 +6804,18 @@ js_EmitTree(JSContext *cx, JSCodeGenerat
 
             /* Emit the usual op needed for decompilation. */
             if (!EmitEndInit(cx, cg, 1))
                 return JS_FALSE;
             break;
         }
 #endif /* JS_HAS_GENERATORS */
 
-        /*
-         * 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) {
+        /* Use the slower NEWINIT for arrays in scripts containing sharps. */
+        if (cg->hasSharps()) {
             if (!EmitNewInit(cx, cg, JSProto_Array, pn, sharpnum))
                 return JS_FALSE;
         } else {
             ptrdiff_t off = js_EmitN(cx, cg, JSOP_NEWARRAY, 3);
             if (off < 0)
                 return JS_FALSE;
             pc = CG_CODE(cg, off);
             SET_UINT24(pc, pn->pn_count);
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -1369,26 +1369,16 @@ GCMarker::markDelayedChildren()
             default:
                 JS_NOT_REACHED("wrong thingkind");
         }
     }
     JS_ASSERT(markLaterCount == 0);
     JS_ASSERT(!unmarkedArenaStackTop);
 }
 
-void
-GCMarker::slowifyArrays()
-{
-    while (!arraysToSlowify.empty()) {
-        JSObject *obj = arraysToSlowify.back();
-        arraysToSlowify.popBack();
-        if (obj->isMarked())
-            obj->makeDenseArraySlow(context);
-    }
-}
 } /* namespace js */
 
 static void
 gc_root_traversal(JSTracer *trc, const RootEntry &entry)
 {
 #ifdef DEBUG
     void *ptr;
     if (entry.value.type == JS_GC_ROOT_GCTHING_PTR) {
@@ -2238,19 +2228,16 @@ MarkAndSweep(JSContext *cx, JSGCInvocati
     /*
      * Sweep script filenames after sweeping functions in the generic loop
      * above. In this way when a scripted function's finalizer destroys the
      * script and calls rt->destroyScriptHook, the hook can still access the
      * script's filename. See bug 323267.
      */
     js_SweepScriptFilenames(rt);
 
-    /* Slowify arrays we have accumulated. */
-    gcmarker.slowifyArrays();
-
     /*
      * Destroy arenas after we finished the sweeping so finalizers can safely
      * use js_IsAboutToBeFinalized().
      */
     ExpireGCChunks(rt);
     TIMESTAMP(sweepDestroyEnd);
 
     if (rt->gcCallback)
--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -978,18 +978,16 @@ struct GCMarker : public JSTracer {
 #ifdef JS_DUMP_CONSERVATIVE_GC_ROOTS
     struct ConservativeRoot { void *thing; uint32 thingKind; };
     Vector<ConservativeRoot, 0, SystemAllocPolicy> conservativeRoots;
     const char *conservativeDumpFileName;
 
     void dumpConservativeRoots();
 #endif
 
-    js::Vector<JSObject *, 0, js::SystemAllocPolicy> arraysToSlowify;
-
   public:
     explicit GCMarker(JSContext *cx);
     ~GCMarker();
 
     uint32 getMarkColor() const {
         return color;
     }
 
@@ -1000,18 +998,16 @@ struct GCMarker : public JSTracer {
          */
         markDelayedChildren();
         color = newColor;
     }
 
     void delayMarkingChildren(void *thing);
 
     JS_FRIEND_API(void) markDelayedChildren();
-
-    void slowifyArrays();
 };
 
 void
 MarkStackRangeConservatively(JSTracer *trc, Value *begin, Value *end);
 
 } /* namespace js */
 
 extern void
--- a/js/src/jsinterp.cpp
+++ b/js/src/jsinterp.cpp
@@ -5906,17 +5906,18 @@ BEGIN_CASE(JSOP_NEWINIT)
 }
 END_CASE(JSOP_NEWINIT)
 
 BEGIN_CASE(JSOP_NEWARRAY)
 {
     unsigned count = GET_UINT24(regs.pc);
     JSObject *obj = js_NewArrayObject(cx, count, NULL);
 
-    if (!obj || !obj->ensureDenseArrayElements(cx, count))
+    /* Avoid ensureDenseArrayElements to skip sparse array checks there. */
+    if (!obj || !obj->ensureSlots(cx, count))
         goto error;
 
     PUSH_OBJECT(*obj);
     CHECK_INTERRUPT_HANDLER();
 }
 END_CASE(JSOP_NEWARRAY)
 
 BEGIN_CASE(JSOP_NEWOBJECT)
--- a/js/src/jsobj.h
+++ b/js/src/jsobj.h
@@ -745,19 +745,34 @@ struct JSObject : js::gc::Cell {
     inline uint32 getArrayLength() const;
     inline void setArrayLength(uint32 length);
 
     inline uint32 getDenseArrayCapacity();
     inline js::Value* getDenseArrayElements();
     inline const js::Value &getDenseArrayElement(uintN idx);
     inline js::Value* addressOfDenseArrayElement(uintN idx);
     inline void setDenseArrayElement(uintN idx, const js::Value &val);
-    inline bool ensureDenseArrayElements(JSContext *cx, uintN cap);
     inline void shrinkDenseArrayElements(JSContext *cx, uintN cap);
 
+    /*
+     * ensureDenseArrayElements ensures that the dense array can hold at least
+     * index + extra elements. It returns ED_OK on success, ED_FAILED on
+     * failure to grow the array, ED_SPARSE when the array is too sparse to
+     * grow (this includes the case of index + extra overflow). In the last
+     * two cases the array is kept intact.
+     */
+    enum EnsureDenseResult { ED_OK, ED_FAILED, ED_SPARSE };
+    inline EnsureDenseResult ensureDenseArrayElements(JSContext *cx, uintN index, uintN extra);
+
+    /*
+     * Check if after growing the dense array will be too sparse.
+     * newElementsHint is an estimated number of elements to be added.
+     */
+    bool willBeSparseDenseArray(uintN requiredCapacity, uintN newElementsHint);
+
     JSBool makeDenseArraySlow(JSContext *cx);
 
     /*
      * Arguments-specific getters and setters.
      */
 
   private:
     /*
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -324,23 +324,16 @@ JSObject::addressOfDenseArrayElement(uin
 
 inline void
 JSObject::setDenseArrayElement(uintN idx, const js::Value &val)
 {
     JS_ASSERT(isDenseArray());
     setSlot(idx, val);
 }
 
-inline bool
-JSObject::ensureDenseArrayElements(JSContext *cx, uintN cap)
-{
-    JS_ASSERT(isDenseArray());
-    return ensureSlots(cx, cap);
-}
-
 inline void
 JSObject::shrinkDenseArrayElements(JSContext *cx, uintN cap)
 {
     JS_ASSERT(isDenseArray());
     shrinkSlots(cx, cap);
 }
 
 inline void