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 id1
push usershaver@mozilla.com
push dateTue, 04 Jan 2011 17:58:04 +0000
reviewersbhackett
bugs603318
milestone2.0b8pre
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