Implement optimized object-ops for dense arrays, b=322889, r+a=brendan.
authorshaver@mozilla.org
Mon, 18 Feb 2008 13:01:47 -0800
changeset 11835 f3fa0f0a7091f3f9e351bb573d3fde6518d962af
parent 11834 df22702ce6964718bb2ed6faba3fea051b9f5c52
child 11836 dff50cd33647f6f7f52d64bcdfef4c12dd8a9bf2
push id1
push userroot
push dateTue, 26 Apr 2011 22:38:44 +0000
treeherdermozilla-beta@bfdb6e623a36 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs322889
milestone1.9b4pre
Implement optimized object-ops for dense arrays, b=322889, r+a=brendan.
js/src/config.mk
js/src/js.c
js/src/js.msg
js/src/jsapi.c
js/src/jsarray.c
js/src/jsarray.h
js/src/jsinterp.c
js/src/jsiter.c
js/src/jsobj.c
js/src/jsobj.h
js/src/jsregexp.c
js/src/jsscope.c
js/src/jsstr.c
--- a/js/src/config.mk
+++ b/js/src/config.mk
@@ -124,17 +124,17 @@ else
 OPTIMIZER  = -Os
 endif
 DEFINES    += -UDEBUG -DNDEBUG -UDEBUG_$(USER)
 OBJDIR_TAG = _OPT
 else
 ifdef USE_MSVC
 OPTIMIZER  = -Zi
 else
-OPTIMIZER  = -g
+OPTIMIZER  = -g3
 endif
 DEFINES    += -DDEBUG -DDEBUG_$(USER)
 OBJDIR_TAG = _DBG
 endif
 
 SO_SUFFIX = so
 
 NS_USE_NATIVE = 1
--- a/js/src/js.c
+++ b/js/src/js.c
@@ -47,16 +47,17 @@
 #include <stdlib.h>
 #include <string.h>
 #include <locale.h>
 #include "jstypes.h"
 #include "jsarena.h"
 #include "jsutil.h"
 #include "jsprf.h"
 #include "jsapi.h"
+#include "jsarray.h"
 #include "jsatom.h"
 #include "jscntxt.h"
 #include "jsdbgapi.h"
 #include "jsemit.h"
 #include "jsfun.h"
 #include "jsgc.h"
 #include "jslock.h"
 #include "jsobj.h"
@@ -320,17 +321,21 @@ Process(JSContext *cx, JSObject *obj, ch
         fclose(file);
     return;
 }
 
 static int
 usage(void)
 {
     fprintf(gErrFile, "%s\n", JS_GetImplementationVersion());
-    fprintf(gErrFile, "usage: js [-PswWxCi] [-b branchlimit] [-c stackchunksize] [-o option] [-v version] [-f scriptfile] [-e script] [-S maxstacksize] [scriptfile] [scriptarg...]\n");
+    fprintf(gErrFile, "usage: js [-zKPswWxCi] [-b branchlimit] [-c stackchunksize] [-o option] [-v version] [-f scriptfile] [-e script] [-S maxstacksize] "
+#ifdef JS_GC_ZEAL
+"[-Z gczeal] "
+#endif
+"[scriptfile] [scriptarg...]\n");
     return 2;
 }
 
 static struct {
     const char  *name;
     uint32      flag;
 } js_options[] = {
     {"strict",          JSOPTION_STRICT},
@@ -366,16 +371,19 @@ ProcessArgs(JSContext *cx, JSObject *obj
         }
         switch (argv[i][1]) {
           case 'b':
           case 'c':
           case 'f':
           case 'e':
           case 'v':
           case 'S':
+#ifdef JS_GC_ZEAL
+          case 'Z':
+#endif
             ++i;
             break;
           default:;
         }
     }
 
     /*
      * Create arguments early and define it to root it, so it's safe from any
@@ -410,16 +418,24 @@ ProcessArgs(JSContext *cx, JSObject *obj
         switch (argv[i][1]) {
         case 'v':
             if (++i == argc)
                 return usage();
 
             JS_SetVersion(cx, (JSVersion) atoi(argv[i]));
             break;
 
+#ifdef JS_GC_ZEAL
+        case 'Z':
+            if (++i == argc)
+                return usage();
+            JS_SetGCZeal(cx, atoi(argv[i]));
+            break;
+#endif
+
         case 'w':
             reportWarnings = JS_TRUE;
             break;
 
         case 'W':
             reportWarnings = JS_FALSE;
             break;
 
@@ -2527,16 +2543,19 @@ static JSFunctionSpec shell_functions[] 
     JS_FN("toint32",        ToInt32,        1,1,0),
     JS_FS("evalcx",         EvalInContext,  1,0,0),
 #ifdef MOZ_SHARK
     JS_FS("startShark",      js_StartShark,      0,0,0),
     JS_FS("stopShark",       js_StopShark,       0,0,0),
     JS_FS("connectShark",    js_ConnectShark,    0,0,0),
     JS_FS("disconnectShark", js_DisconnectShark, 0,0,0),
 #endif
+#ifdef DEBUG_ARRAYS
+    JS_FS("arrayInfo",       js_ArrayInfo,       1,0,0),
+#endif
     JS_FS_END
 };
 
 static const char shell_help_header[] =
 "Command                  Description\n"
 "=======                  ===========\n";
 
 static const char *const shell_help_messages[] = {
@@ -2597,16 +2616,19 @@ static const char *const shell_help_mess
 #ifdef MOZ_SHARK
 "startShark()             Start a Shark session.\n"
 "                         Shark must be running with programatic sampling.",
 "stopShark()              Stop a running Shark session.",
 "connectShark()           Connect to Shark.\n"
 "                         The -k switch does this automatically.",
 "disconnectShark()        Disconnect from Shark.",
 #endif
+#ifdef DEBUG_ARRAYS
+"arrayInfo(a1, a2, ...)   Report statistics about arrays.",
+#endif
 };
 
 /* Help messages must match shell functions. */
 JS_STATIC_ASSERT(JS_ARRAY_LENGTH(shell_help_messages) + 1 ==
                  JS_ARRAY_LENGTH(shell_functions));
 
 #ifdef DEBUG
 static void
--- a/js/src/js.msg
+++ b/js/src/js.msg
@@ -299,8 +299,9 @@ MSG_DEF(JSMSG_ARRAY_COMP_LEFTSIDE,    21
 MSG_DEF(JSMSG_NON_XML_FILTER,         217, 1, JSEXN_TYPEERR, "XML filter is applied to non-XML value {0}")
 MSG_DEF(JSMSG_EMPTY_ARRAY_REDUCE,     218, 0, JSEXN_TYPEERR, "reduce of empty array with no initial value")
 MSG_DEF(JSMSG_NON_LIST_XML_METHOD,    219, 2, JSEXN_TYPEERR, "cannot call {0} method on an XML list with {1} elements")
 MSG_DEF(JSMSG_BAD_DELETE_OPERAND,     220, 0, JSEXN_SYNTAXERR, "invalid delete operand")
 MSG_DEF(JSMSG_BAD_INCOP_OPERAND,      221, 0, JSEXN_SYNTAXERR, "invalid increment/decrement operand")
 MSG_DEF(JSMSG_NULL_OR_UNDEFINED,      222, 2, JSEXN_TYPEERR, "{0} is {1}")
 MSG_DEF(JSMSG_LET_DECL_NOT_IN_BLOCK,  223, 0, JSEXN_SYNTAXERR, "let declaration not directly within block")
 MSG_DEF(JSMSG_BAD_OBJECT_INIT,        224, 0, JSEXN_SYNTAXERR, "invalid object initializer")
+MSG_DEF(JSMSG_CANT_SET_ARRAY_ATTRS,   225, 0, JSEXN_INTERNALERR, "can't set attributes on indexed array properties")
--- a/js/src/jsapi.c
+++ b/js/src/jsapi.c
@@ -3660,17 +3660,17 @@ JS_NewArrayObject(JSContext *cx, jsint l
     CHECK_REQUEST(cx);
     /* NB: jsuint cast does ToUint32. */
     return js_NewArrayObject(cx, (jsuint)length, vector);
 }
 
 JS_PUBLIC_API(JSBool)
 JS_IsArrayObject(JSContext *cx, JSObject *obj)
 {
-    return OBJ_GET_CLASS(cx, obj) == &js_ArrayClass;
+    return OBJ_IS_ARRAY(cx, obj);
 }
 
 JS_PUBLIC_API(JSBool)
 JS_GetArrayLength(JSContext *cx, JSObject *obj, jsuint *lengthp)
 {
     CHECK_REQUEST(cx);
     return js_GetLengthProperty(cx, obj, lengthp);
 }
--- a/js/src/jsarray.c
+++ b/js/src/jsarray.c
@@ -35,41 +35,106 @@
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 /*
  * JS array class.
+ *
+ * Array objects begin as "dense" arrays, optimized for numeric-only property
+ * access over a vector of slots (obj->dslots) with high load factor.  Array
+ * methods optimize for denseness by testing that the object's class is
+ * &js_ArrayClass, and can then directly manipulate the slots for efficiency.
+ * 
+ * We track these pieces of metadata for arrays in dense mode:
+ *  - the array's length property as a uint32, in JSSLOT_ARRAY_LENGTH,
+ *  - the number of indices that are filled (non-holes), in JSSLOT_ARRAY_COUNT,
+ *  - the net number of slots starting at dslots (DENSELEN), in dslots[-1] if
+ *    dslots is non-NULL.
+ * 
+ * In dense mode, holes in the array are represented by JSVAL_HOLE.  The final
+ * slot in fslots (JSSLOT_ARRAY_LOOKUP_HOLDER) is used to store the single jsid
+ * "in use" by a lookupProperty caller.
+ * 
+ * Arrays are converted to use js_SlowArrayClass when any of these conditions
+ * are met:
+ *  - the load factor (COUNT / DENSELEN) is less than 0.25, and there are
+ *    more than MIN_SPARSE_INDEX slots total
+ *  - a property is set that is non-numeric (and not "length"); or
+ *  - a hole is filled below DENSELEN (possibly implicitly through methods like
+ *    |reverse| or |splice|).
+ *
+ * In the latter two cases, property creation order is no longer index order,
+ * which necessitates use of a structure that keeps track of property creation
+ * order.  (ES4, due to expectations baked into web script, requires that
+ * enumeration order be the order in which properties were created.)
+ * 
+ * An alternative in the latter case (out-of-order index set) would be to
+ * 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 array for slot accesses, at some cost in code complexity.
  */
 #include "jsstddef.h"
 #include <stdlib.h>
 #include <string.h>
 #include "jstypes.h"
 #include "jsutil.h" /* Added by JSIFY */
 #include "jsapi.h"
 #include "jsarray.h"
 #include "jsatom.h"
+#include "jsbit.h"
 #include "jsbool.h"
 #include "jscntxt.h"
 #include "jsconfig.h"
+#include "jsdbgapi.h" /* for js_TraceWatchPoints */
 #include "jsdtoa.h"
 #include "jsfun.h"
 #include "jsgc.h"
 #include "jsinterp.h"
 #include "jslock.h"
 #include "jsnum.h"
 #include "jsobj.h"
+#include "jsscope.h"
 #include "jsstr.h"
 
 /* 2^32 - 1 as a number and a string */
 #define MAXINDEX 4294967295u
 #define MAXSTR   "4294967295"
 
+#define ARRAY_SET_LENGTH(obj, len)                                             \
+    STOBJ_SET_SLOT((obj), JSSLOT_ARRAY_LENGTH, (uint32)len)
+#define ARRAY_LENGTH(obj)   (uint32)STOBJ_GET_SLOT((obj), JSSLOT_ARRAY_LENGTH)
+#define ARRAY_SET_COUNT(obj, count)                                            \
+    STOBJ_SET_SLOT((obj), JSSLOT_ARRAY_COUNT, (jsval)(count))
+#define ARRAY_COUNT(obj)    (uint32)(STOBJ_GET_SLOT((obj), JSSLOT_ARRAY_COUNT))
+
+#define ARRAY_SET_DENSELEN(obj, max)                                           \
+    (JS_ASSERT((obj)->dslots), (obj)->dslots[-1] = (jsval)(max))
+#define ARRAY_DENSELEN(obj) ((obj)->dslots ? (uint32)(obj)->dslots[-1] : 0)
+
+/* Small arrays are dense, no matter what. */
+#define MIN_SPARSE_INDEX 32
+
+#define INDEX_TOO_BIG(index) ((index) > JS_BIT(29) - 1)
+#define INDEX_TOO_SPARSE(array, index)                                         \
+    (INDEX_TOO_BIG(index) ||                                                   \
+     ((index) > ARRAY_DENSELEN(array) && (index) >= MIN_SPARSE_INDEX &&        \
+      (index) > (ARRAY_COUNT(array) + 1) * 4))
+
+JS_STATIC_ASSERT(sizeof(JSScopeProperty) > 4 * sizeof(jsval));
+
+static JSBool
+MakeArraySlow(JSContext *cx, JSObject *obj);
+
+#define ENSURE_SLOW_ARRAY(cx, obj)                                             \
+    (OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass || MakeArraySlow(cx, obj))
+
 /*
  * Determine if the id represents an array index or an XML property index.
  *
  * An id is an array index according to ECMA by (15.4):
  *
  * "Array objects give special treatment to a certain class of property names.
  * A property name P (in the form of a string value) is an array index if and
  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
@@ -162,16 +227,21 @@ ValueIsLength(JSContext *cx, jsval v, js
 
 JSBool
 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp)
 {
     JSTempValueRooter tvr;
     jsid id;
     JSBool ok;
     jsint i;
+    
+    if (OBJ_IS_ARRAY(cx, obj)) {
+        *lengthp = ARRAY_LENGTH(obj);
+        return JS_TRUE;
+    }
 
     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
     id = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
     ok = OBJ_GET_PROPERTY(cx, obj, id, &tvr.u.value);
     if (ok) {
         /*
          * Short-circuit, because js_ValueToECMAUint32 fails when called
          * during init time.
@@ -214,20 +284,22 @@ BigIndexToId(JSContext *cx, JSObject *ob
         *start = (jschar)('0' + index % 10);
         index /= 10;
     } while (index != 0);
 
     /*
      * Skip the atomization if the class is known to store atoms corresponding
      * to big indexes together with elements. In such case we know that the
      * array does not have an element at the given index if its atom does not
-     * exist.
+     * exist.  Fast arrays (clasp == &js_ArrayClass) don't use atoms for
+     * any indexes, though it would be rare to see them have a big index
+     * in any case.
      */
     if (!createAtom &&
-        ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_ArrayClass ||
+        ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_SlowArrayClass ||
          clasp == &js_ArgumentsClass ||
          clasp == &js_ObjectClass)) {
         atom = js_GetExistingStringAtom(cx, start, JS_ARRAY_END(buf) - start);
         if (!atom) {
             *idp = JSVAL_VOID;
             return JS_TRUE;
         }
     } else {
@@ -235,30 +307,93 @@ BigIndexToId(JSContext *cx, JSObject *ob
         if (!atom)
             return JS_FALSE;
     }
 
     *idp = ATOM_TO_JSID(atom);
     return JS_TRUE;
 }
 
+static JSBool
+ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 len)
+{
+    jsval *slots, *newslots;
+    
+    if (len == 0) {
+        if (obj->dslots) {
+            JS_free(cx, obj->dslots - 1);
+            obj->dslots = NULL;
+        }
+        return JS_TRUE;
+    } 
+
+    if (len > ~(uint32)0 / sizeof(jsval)) {
+        JS_ReportOutOfMemory(cx);
+        return JS_FALSE;
+    }
+
+    slots = obj->dslots ? obj->dslots - 1 : NULL;
+    newslots = JS_realloc(cx, slots, sizeof (jsval) * (len + 1));
+    if (!newslots)
+        return JS_FALSE;
+    
+    obj->dslots = newslots + 1;
+    ARRAY_SET_DENSELEN(obj, len);
+
+    for (slots = obj->dslots + oldlen; slots < obj->dslots + len; slots++)
+        *slots = JSVAL_HOLE;
+    
+    return JS_TRUE;
+}
+
+#define ARRAY_GROWBY 8 
+
+static JSBool
+EnsureLength(JSContext *cx, JSObject *obj, uint32 len)
+{
+    uint32 oldlen = ARRAY_DENSELEN(obj);
+
+    if (len > oldlen) {
+        return ResizeSlots(cx, obj, oldlen,
+                           len + ARRAY_GROWBY - (len % ARRAY_GROWBY));
+    }
+    return JS_TRUE;
+}
+
 /*
  * If the property at the given index exists, get its value into location
  * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
  * to JSVAL_VOID. This function assumes that the location pointed by vp is
  * properly rooted and can be used as GC-protected storage for temporaries.
  */
 static JSBool
 GetArrayElement(JSContext *cx, JSObject *obj, jsuint index, JSBool *hole,
                 jsval *vp)
 {
     jsid id;
     JSObject *obj2;
     JSProperty *prop;
 
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        if (index >= ARRAY_DENSELEN(obj)) {
+            *vp = JSVAL_VOID;
+            *hole = JS_TRUE;
+            return JS_TRUE;
+        }
+
+        *vp = obj->dslots[index];
+        if (*vp == JSVAL_HOLE) {
+            *vp = JSVAL_VOID;
+            *hole = JS_TRUE;
+        } else {
+            *hole = JS_FALSE;
+        }
+        return JS_TRUE;
+    }
+
     if (index <= JSVAL_INT_MAX) {
         id = INT_TO_JSID(index);
     } else {
         if (!BigIndexToId(cx, obj, index, JS_FALSE, &id))
             return JS_FALSE;
         if (id == JSVAL_VOID) {
             *hole = JS_TRUE;
             *vp = JSVAL_VOID;
@@ -283,32 +418,58 @@ GetArrayElement(JSContext *cx, JSObject 
 /*
  * Set the value of the property at the given index to v assuming v is rooted.
  */
 static JSBool
 SetArrayElement(JSContext *cx, JSObject *obj, jsuint index, jsval v)
 {
     jsid id;
 
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        if (INDEX_TOO_SPARSE(obj, index)) {
+            if (!MakeArraySlow(cx, obj))
+                return JS_FALSE;
+        } else {
+
+            if (!EnsureLength(cx, obj, index + 1))
+                return JS_FALSE;
+            if (index >= ARRAY_LENGTH(obj))
+                ARRAY_SET_LENGTH(obj, index + 1);
+            if (obj->dslots[index] == JSVAL_HOLE)
+                ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) + 1);
+            obj->dslots[index] = v;
+            return JS_TRUE;
+        }
+    }
+
     if (index <= JSVAL_INT_MAX) {
         id = INT_TO_JSID(index);
     } else {
         if (!BigIndexToId(cx, obj, index, JS_TRUE, &id))
             return JS_FALSE;
         JS_ASSERT(id != JSVAL_VOID);
     }
     return OBJ_SET_PROPERTY(cx, obj, id, &v);
 }
 
 static JSBool
 DeleteArrayElement(JSContext *cx, JSObject *obj, jsuint index)
 {
     jsid id;
     jsval junk;
 
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        if (index < ARRAY_DENSELEN(obj)) {
+            if (obj->dslots[index] != JSVAL_HOLE)
+                ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) - 1);
+            obj->dslots[index] = JSVAL_HOLE;
+        }
+        return JS_TRUE;
+    }
+
     if (index <= JSVAL_INT_MAX) {
         id = INT_TO_JSID(index);
     } else {
         if (!BigIndexToId(cx, obj, index, JS_FALSE, &id))
             return JS_FALSE;
         if (id == JSVAL_VOID)
             return JS_TRUE;
     }
@@ -321,19 +482,18 @@ DeleteArrayElement(JSContext *cx, JSObje
  */
 static JSBool
 SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsuint index,
                         JSBool hole, jsval v)
 {
     if (hole) {
         JS_ASSERT(v == JSVAL_VOID);
         return DeleteArrayElement(cx, obj, index);
-    } else {
-        return SetArrayElement(cx, obj, index, v);
     }
+    return SetArrayElement(cx, obj, index, v);
 }
 
 JSBool
 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length)
 {
     jsval v;
     jsid id;
 
@@ -363,17 +523,18 @@ js_HasLengthProperty(JSContext *cx, JSOb
 }
 
 JSBool
 js_IsArrayLike(JSContext *cx, JSObject *obj, JSBool *answerp, jsuint *lengthp)
 {
     JSClass *clasp;
 
     clasp = OBJ_GET_CLASS(cx, obj);
-    *answerp = (clasp == &js_ArgumentsClass || clasp == &js_ArrayClass);
+    *answerp = (clasp == &js_ArgumentsClass || clasp == &js_ArrayClass ||
+                clasp == &js_SlowArrayClass);
     if (!*answerp) {
         *lengthp = 0;
         return JS_TRUE;
     }
     return js_GetLengthProperty(cx, obj, lengthp);
 }
 
 /*
@@ -387,122 +548,556 @@ js_IsArrayLike(JSContext *cx, JSObject *
  * not of Array class. For the getter, we search obj's prototype chain for the
  * array that caused this getter to be invoked. In the setter case to overcome
  * the JSPROP_SHARED attribute, we must define a shadowing length property.
  */
 static JSBool
 array_length_getter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
 {
     do {
-        if (OBJ_GET_CLASS(cx, obj) == &js_ArrayClass) {
-            *vp = STOBJ_GET_SLOT(obj, JSSLOT_ARRAY_LENGTH);
-            break;
-        }
+        if (OBJ_IS_ARRAY(cx, obj))
+            return IndexToValue(cx, ARRAY_LENGTH(obj), vp);
     } while ((obj = OBJ_GET_PROTO(cx, obj)) != NULL);
     return JS_TRUE;
 }
 
 static JSBool
 array_length_setter(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
 {
     jsuint newlen, oldlen, gap, index;
     jsval junk;
     JSObject *iter;
     JSTempValueRooter tvr;
     JSBool ok;
 
-    if (OBJ_GET_CLASS(cx, obj) != &js_ArrayClass) {
+    if (!OBJ_IS_ARRAY(cx, obj)) {
         jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
 
         return OBJ_DEFINE_PROPERTY(cx, obj, lengthId, *vp, NULL, NULL,
                                    JSPROP_ENUMERATE, NULL);
     }
 
     if (!ValueIsLength(cx, *vp, &newlen))
         return JS_FALSE;
-    if (!js_GetLengthProperty(cx, obj, &oldlen))
+    oldlen = ARRAY_LENGTH(obj);
+
+    if (oldlen == newlen)
+        return JS_TRUE;
+    
+    if (!IndexToValue(cx, newlen, vp))
         return JS_FALSE;
-    if (oldlen > newlen) {
-        if (oldlen - newlen < (1 << 24)) {
-            do {
-                --oldlen;
-                if (!JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) ||
-                    !DeleteArrayElement(cx, obj, oldlen)) {
-                    return JS_FALSE;
-                }
-            } while (oldlen != newlen);
-        } else {
-            /*
-             * We are going to remove a lot of indexes in a presumably sparse
-             * array. So instead of looping through indexes between newlen and
-             * oldlen, we iterate through all properties and remove those that
-             * correspond to indexes in the half-open range [newlen, oldlen).
-             * See bug 322135.
-             */
-            iter = JS_NewPropertyIterator(cx, obj);
-            if (!iter)
+
+    if (oldlen < newlen) {
+        ARRAY_SET_LENGTH(obj, newlen);
+        return JS_TRUE;
+    }
+
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        if (ARRAY_DENSELEN(obj) && !ResizeSlots(cx, obj, oldlen, newlen))
+            return JS_FALSE;
+    } else if (oldlen - newlen < (1 << 24)) {
+        do {
+            --oldlen;
+            if (!JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) ||
+                !DeleteArrayElement(cx, obj, oldlen)) {
                 return JS_FALSE;
-
-            /* Protect iter against GC in OBJ_DELETE_PROPERTY. */
-            JS_PUSH_TEMP_ROOT_OBJECT(cx, iter, &tvr);
-            gap = oldlen - newlen;
-            for (;;) {
-                ok = (JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) &&
-                      JS_NextProperty(cx, iter, &id));
+            }
+        } while (oldlen != newlen);
+    } else {
+        /*
+         * We are going to remove a lot of indexes in a presumably sparse
+         * array. So instead of looping through indexes between newlen and
+         * oldlen, we iterate through all properties and remove those that
+         * correspond to indexes in the half-open range [newlen, oldlen).  See
+         * bug 322135.
+         */
+        iter = JS_NewPropertyIterator(cx, obj);
+        if (!iter)
+            return JS_FALSE;
+        
+        /* Protect iter against GC in OBJ_DELETE_PROPERTY. */
+        JS_PUSH_TEMP_ROOT_OBJECT(cx, iter, &tvr);
+        gap = oldlen - newlen;
+        for (;;) {
+            ok = (JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) &&
+                  JS_NextProperty(cx, iter, &id));
+            if (!ok)
+                break;
+            if (id == JSVAL_VOID)
+                break;
+            if (js_IdIsIndex(id, &index) && index - newlen < gap) {
+                ok = OBJ_DELETE_PROPERTY(cx, obj, id, &junk);
                 if (!ok)
                     break;
-                if (id == JSVAL_VOID)
-                    break;
-                if (js_IdIsIndex(id, &index) && index - newlen < gap) {
-                    ok = OBJ_DELETE_PROPERTY(cx, obj, id, &junk);
-                    if (!ok)
-                        break;
-                }
             }
-            JS_POP_TEMP_ROOT(cx, &tvr);
-            if (!ok)
-                return JS_FALSE;
+        }
+        JS_POP_TEMP_ROOT(cx, &tvr);
+        if (!ok)
+            return JS_FALSE;
+    }
+
+    ARRAY_SET_LENGTH(obj, newlen);
+    return JS_TRUE;
+}
+
+static JSBool
+array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
+                     JSProperty **propp)
+{
+    uint32 i;
+
+    if (!ARRAY_IS_DENSE(cx, obj))
+        return js_LookupProperty(cx, obj, id, objp, propp);
+
+    /* 
+     * We have only indexed properties up to DENSELEN (excepting holes), plus
+     * the length property. For all else, we delegate to the prototype.
+     */
+    if ((!js_IdIsIndex(id, &i) &&
+         id != ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) ||
+        ARRAY_LENGTH(obj) == 0 || i >= ARRAY_DENSELEN(obj) ||
+        obj->dslots[i] == JSVAL_HOLE) {
+        JSObject *proto = STOBJ_GET_PROTO(obj);
+
+        if (!proto) {
+            *objp = NULL;
+            *propp = NULL;
+            return JS_TRUE;
+        }
+
+        return OBJ_LOOKUP_PROPERTY(cx, proto, id, objp, propp);
+    }
+
+    /* FIXME 417501: threadsafety: could race with a lookup on another thread.
+     * If we can only have a single lookup active per context, we could
+     * pigeonhole this on the context instead. */
+    JS_ASSERT(STOBJ_GET_SLOT(obj, JSSLOT_ARRAY_LOOKUP_HOLDER) == JSVAL_VOID);
+    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LOOKUP_HOLDER, (jsval)id);
+    *propp = (JSProperty *)&(obj->fslots[JSSLOT_ARRAY_LOOKUP_HOLDER]);
+    *objp = obj;
+    return JS_TRUE;
+}
+
+static void
+array_dropProperty(JSContext *cx, JSObject *obj, JSProperty *prop)
+{
+    JS_ASSERT(!ARRAY_IS_DENSE(cx, obj) ||
+              STOBJ_GET_SLOT(obj, JSSLOT_ARRAY_LOOKUP_HOLDER) != JSVAL_VOID);
+#ifdef DEBUG
+    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LOOKUP_HOLDER, JSVAL_VOID);
+#endif
+}
+
+static JSBool
+array_getProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
+{
+    uint32 i;
+
+    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
+        return IndexToValue(cx, ARRAY_LENGTH(obj), vp);
+
+    if (id == ATOM_TO_JSID(cx->runtime->atomState.protoAtom)) {
+        *vp = STOBJ_GET_SLOT(obj, JSSLOT_PROTO);
+        return JS_TRUE;
+    }
+
+    if (!ARRAY_IS_DENSE(cx, obj))
+        return js_GetProperty(cx, obj, id, vp);
+
+    if (!js_IdIsIndex(ID_TO_VALUE(id), &i) || i >= ARRAY_DENSELEN(obj) ||
+        obj->dslots[i] == JSVAL_HOLE) {
+        JSObject *proto = STOBJ_GET_PROTO(obj);
+        if (!proto) {
+            *vp = JSVAL_VOID;
+            return JS_TRUE;
         }
+
+        return OBJ_GET_PROPERTY(cx, proto, id, vp);
     }
-    if (!IndexToValue(cx, newlen, vp))
+
+    *vp = obj->dslots[i];
+    return JS_TRUE;
+}
+
+static JSBool
+slowarray_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
+{
+    jsuint index, length;
+    
+    if (!js_IdIsIndex(id, &index))
+        return JS_TRUE;
+    length = ARRAY_LENGTH(obj);
+    if (index >= length)
+        ARRAY_SET_LENGTH(obj, index + 1);
+    return JS_TRUE;
+}
+
+static void
+slowarray_trace(JSTracer *trc, JSObject *obj)
+{
+    uint32 length = ARRAY_LENGTH(obj);
+
+    JS_ASSERT(STOBJ_GET_CLASS(obj) == &js_SlowArrayClass);
+
+    /*
+     * Move JSSLOT_ARRAY_LENGTH aside to prevent the GC from treating
+     * untagged integer values as objects or strings.
+     */
+    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, JSVAL_VOID);
+    js_TraceObject(trc, obj);
+    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, length);
+}
+
+static JSObjectOps js_SlowArrayObjectOps;
+
+static JSObjectOps *
+slowarray_getObjectOps(JSContext *cx, JSClass *clasp)
+{
+    return &js_SlowArrayObjectOps;
+}
+
+static JSBool
+array_setProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
+{
+    uint32 i;
+
+    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
+        return array_length_setter(cx, obj, id, vp);
+
+    if (!ARRAY_IS_DENSE(cx, obj))
+        return js_SetProperty(cx, obj, id, vp);
+
+    if (!js_IdIsIndex(id, &i) || INDEX_TOO_SPARSE(obj, i)) {
+        if (!MakeArraySlow(cx, obj))
+            return JS_FALSE;
+        return js_SetProperty(cx, obj, id, vp);
+    }
+
+    if (!EnsureLength(cx, obj, i + 1))
         return JS_FALSE;
-    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, *vp);
+
+    if (i >= ARRAY_LENGTH(obj))
+        ARRAY_SET_LENGTH(obj, i + 1);
+    if (obj->dslots[i] == JSVAL_HOLE)
+        ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) + 1);
+    obj->dslots[i] = *vp;
+    return JS_TRUE;
+}
+
+static JSBool
+array_defineProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
+                     JSPropertyOp getter, JSPropertyOp setter, uintN attrs,
+                     JSProperty **propp)
+{
+    uint32 i;
+
+    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
+        return JS_TRUE;
+
+    if (!js_IdIsIndex(ID_TO_VALUE(id), &i) || attrs != JSPROP_ENUMERATE) { 
+        if (!ENSURE_SLOW_ARRAY(cx, obj))
+            return JS_FALSE;
+        return js_DefineProperty(cx, obj, id, value, getter, setter, attrs,
+                                 propp);
+    }
+
+    return array_setProperty(cx, obj, id, &value);
+}
+
+static JSBool
+array_getAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
+                    uintN *attrsp)
+{
+    *attrsp = id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)
+        ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
     return JS_TRUE;
 }
 
 static JSBool
-array_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
+array_setAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
+                    uintN *attrsp)
 {
-    jsuint index, length;
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
+                         JSMSG_CANT_SET_ARRAY_ATTRS);
+    return JS_FALSE;
+}
 
-    if (!js_IdIsIndex(id, &index))
+static JSBool
+array_deleteProperty(JSContext *cx, JSObject *obj, jsval id, jsval *rval)
+{
+    uint32 i;
+    
+    if (!ARRAY_IS_DENSE(cx, obj))
+        return js_DeleteProperty(cx, obj, id, rval);
+
+    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) {
+        *rval = JSVAL_FALSE;
         return JS_TRUE;
-    if (!js_GetLengthProperty(cx, obj, &length))
-        return JS_FALSE;
-    if (index >= length) {
-        length = index + 1;
-        return js_SetLengthProperty(cx, obj, length);
     }
+
+    if (js_IdIsIndex(id, &i) && i < ARRAY_DENSELEN(obj) &&
+        obj->dslots[i] != JSVAL_HOLE) {
+        ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) - 1);
+        obj->dslots[i] = JSVAL_HOLE;
+    }
+
+    *rval = JSVAL_TRUE;
     return JS_TRUE;
 }
 
 static JSBool
-array_convert(JSContext *cx, JSObject *obj, JSType type, jsval *vp)
+slowarray_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
+                    jsval *statep, jsid *idp)
+{
+    /* Are we continuing an enumeration that started when we were dense? */
+    if (JSVAL_IS_BOOLEAN(*statep)) {
+        jsid lastIndex = INT_TO_JSID(JSVAL_TO_BOOLEAN(*statep));
+
+        /* Replace our enumeration state with a native one. */
+        if (!js_Enumerate(cx, obj, JSENUMERATE_INIT, statep, idp))
+            return JS_FALSE;
+
+        /* Advance the native enumeration state to the previous index. */
+        do {
+            if (!js_Enumerate(cx, obj, JSENUMERATE_NEXT, statep, idp))
+                return JS_FALSE;
+            if (*statep == JSVAL_NULL)
+                return JS_TRUE;
+        } while (*idp != lastIndex);
+
+        /* Now fall through to our usual js_Enumerate pass-through. */
+    }
+    return js_Enumerate(cx, obj, enum_op, statep, idp);
+}
+
+/*
+ * array_enumerate stores its index state as a pseudo-boolean, so that it can be
+ * distinguished from the tagged private used by js_Enumerate.  To detect and
+ * handle faulting to slowness during an enumeration, slowarray_enumerate must
+ * be able to tell whether it's being called with js_Enumerate's state or
+ * array_enumerate's.  This encoding limits dense arrays to 2^29-1 enumerable
+ * elements, but since that would require a contiguous allocation of 2^31 bytes
+ * for the dslots vector, it is unlikely to be a serious limitation for real
+ * applications.
+ */
+static JSBool
+array_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
+                jsval *statep, jsid *idp)
 {
-    return js_TryValueOf(cx, obj, type, vp);
+    uint32 i, length;
+
+    JS_ASSERT(ARRAY_IS_DENSE(cx, obj));
+
+    if (enum_op == JSENUMERATE_DESTROY)
+        return JS_TRUE;
+
+    if (enum_op == JSENUMERATE_INIT) {
+        *statep = OBJECT_TO_JSVAL(obj);
+        if (idp)
+            *idp = INT_TO_JSID(0);
+        return JS_TRUE;
+    }
+
+    length = ARRAY_DENSELEN(obj);
+    if (*statep == OBJECT_TO_JSVAL(obj)) {
+        if (length == 0) {
+            *statep = JSVAL_NULL;
+            return JS_TRUE;
+        }
+
+        if (obj->dslots[0] != JSVAL_HOLE) {
+            *statep = BOOLEAN_TO_JSVAL(0);
+            *idp = INT_TO_JSID(0);
+            return JS_TRUE;
+        }
+        i = 0;
+    } else {
+        i = JSVAL_TO_BOOLEAN(*statep);
+    }
+
+    do {
+        i++;
+    } while (i < length && obj->dslots[i] == JSVAL_HOLE);
+
+    if (i == length) {
+        *statep = JSVAL_NULL;
+        return JS_TRUE;
+    }
+
+    *idp = INT_TO_JSID(i);
+    *statep = BOOLEAN_TO_JSVAL(i);
+    return JS_TRUE;
+}
+
+static void
+array_finalize(JSContext *cx, JSObject *obj)
+{
+    if (obj->dslots)
+        JS_free(cx, obj->dslots - 1);
+    obj->dslots = NULL;
+}
+
+static void
+array_trace(JSTracer *trc, JSObject *obj)
+{
+    uint32 length;
+    size_t i;
+    jsval v;
+
+    JS_ASSERT(ARRAY_IS_DENSE(cx, obj));
+
+    length = ARRAY_DENSELEN(obj);
+    for (i = 0; i < length; i++) {
+        v = obj->dslots[i];
+        if (JSVAL_IS_TRACEABLE(v)) {
+            JS_SET_TRACING_INDEX(trc, "array_dslots", i);
+            JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
+        }
+    }
+
+    for (i = JSSLOT_PROTO; i <= JSSLOT_PARENT; ++i) {
+        v = STOBJ_GET_SLOT(obj, i);
+        if (JSVAL_IS_TRACEABLE(v)) {
+            JS_SET_TRACING_DETAILS(trc, js_PrintObjectSlotName, obj, i);
+            JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
+        }
+    }
+}
+
+static JSObjectMap *
+array_newObjectMap(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops,
+                   JSClass *clasp, JSObject *obj)
+{
+#ifdef DEBUG
+    extern JSClass js_ArrayClass;
+    extern JSObjectOps js_ArrayObjectOps;
+#endif
+    JSObjectMap *map = JS_malloc(cx, sizeof(*map));
+    if (!map)
+        return NULL;
+
+    map->nrefs = nrefs;
+    JS_ASSERT(ops == &js_ArrayObjectOps);
+    map->ops = ops;
+    JS_ASSERT(clasp == &js_ArrayClass);
+    map->freeslot = JSSLOT_FREE(clasp);
+
+    return map;
+}
+
+void
+array_destroyObjectMap(JSContext *cx, JSObjectMap *map)
+{
+    JS_free(cx, map);
+}
+
+JSObjectOps js_ArrayObjectOps = {
+    array_newObjectMap,   array_destroyObjectMap,
+    array_lookupProperty, array_defineProperty,
+    array_getProperty,    array_setProperty,
+    array_getAttributes,  array_setAttributes,
+    array_deleteProperty, js_DefaultValue,
+    array_enumerate,      js_CheckAccess,
+    NULL,                 array_dropProperty,
+    NULL,                 NULL,
+    NULL,                 js_HasInstance,
+    js_SetProtoOrParent,  js_SetProtoOrParent,
+    array_trace,          NULL,
+    NULL,                 NULL
+};
+
+static JSObjectOps *
+array_getObjectOps(JSContext *cx, JSClass *clasp)
+{
+    return &js_ArrayObjectOps;
 }
 
 JSClass js_ArrayClass = {
     "Array",
+    JSCLASS_HAS_PRIVATE | JSCLASS_HAS_CACHED_PROTO(JSProto_Array) |
+    JSCLASS_HAS_RESERVED_SLOTS(1) | JSCLASS_NEW_ENUMERATE,
+    JS_PropertyStub,    JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
+    JS_EnumerateStub,   JS_ResolveStub,    js_TryValueOf,     array_finalize,
+    array_getObjectOps, NULL,              NULL,              NULL,
+    NULL,               NULL,              NULL,              NULL
+};
+
+JSClass js_SlowArrayClass = {
+    "Array",
     JSCLASS_HAS_PRIVATE | JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
-    array_addProperty, JS_PropertyStub,   JS_PropertyStub,   JS_PropertyStub,
-    JS_EnumerateStub,  JS_ResolveStub,    array_convert,     JS_FinalizeStub,
-    JSCLASS_NO_OPTIONAL_MEMBERS
+    slowarray_addProperty, JS_PropertyStub, JS_PropertyStub,  JS_PropertyStub,
+    JS_EnumerateStub,      JS_ResolveStub,  js_TryValueOf,    JS_FinalizeStub,
+    slowarray_getObjectOps, NULL,           NULL,             NULL,
+    NULL,                  NULL,            NULL,             NULL
 };
 
+/*
+ * Convert an array object from fast-and-dense to slow-and-flexible.
+ */
+static JSBool
+MakeArraySlow(JSContext *cx, JSObject *obj)
+{
+    JSObjectMap *map, *oldmap;
+    uint32 i, length;
+
+    JS_ASSERT(OBJ_GET_CLASS(cx, obj) == &js_ArrayClass);
+
+    /* Create a native scope. */
+    map = js_NewObjectMap(cx, obj->map->nrefs, &js_SlowArrayObjectOps,
+                          &js_SlowArrayClass, obj);
+    if (!map)
+        return JS_FALSE;
+
+    length = ARRAY_DENSELEN(obj);
+    if (length) {
+        map->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
+        obj->dslots[-1] = JS_INITIAL_NSLOTS + length;
+    } else {
+        map->freeslot = STOBJ_NSLOTS(obj);
+    }
+
+    /* Create new properties pointing to existing values in dslots */
+    for (i = 0; i < length; i++) {
+        jsid id;
+        JSScopeProperty *sprop;
+
+        if (!JS_ValueToId(cx, INT_TO_JSVAL(i), &id))
+            goto out_bad;
+
+        if (obj->dslots[i] == JSVAL_HOLE) {
+            obj->dslots[i] = JSVAL_VOID;
+            continue;
+        }
+
+        sprop = js_AddScopeProperty(cx, (JSScope *)map, id, NULL, NULL,
+                                    i + JS_INITIAL_NSLOTS, JSPROP_ENUMERATE,
+                                    0, 0);
+        if (!sprop)
+            goto out_bad;
+    }
+
+    /* Render our formerly-reserved count property GC-safe. */
+    obj->fslots[JSSLOT_ARRAY_COUNT] = JSVAL_VOID;
+
+    /* Make sure we preserve any flags borrowing bits in JSSLOT_CLASS. */
+    obj->fslots[JSSLOT_CLASS] ^= (jsval) &js_ArrayClass;
+    obj->fslots[JSSLOT_CLASS] |= (jsval) &js_SlowArrayClass;
+    
+    /* Swap in our new map. */
+    oldmap = obj->map;
+    obj->map = map;
+    array_destroyObjectMap(cx, oldmap);
+
+    return JS_TRUE;
+    
+out_bad:
+    js_DestroyObjectMap(cx, map);
+    return JS_FALSE;
+}
+
 enum ArrayToStringOp {
     TO_STRING,
     TO_LOCALE_STRING,
     TO_SOURCE
 };
 
 /*
  * When op is TO_STRING or TO_LOCALE_STRING sep indicates a separator to use
@@ -601,20 +1196,26 @@ array_join_sub(JSContext *cx, JSObject *
         } else {
             sepstr = NULL;      /* indicates to use "," as separator */
             seplen = 1;
         }
     }
 
     /* Use rval to locally root each element value as we loop and convert. */
     for (index = 0; index < length; index++) {
-        ok = (JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) &&
-              GetArrayElement(cx, obj, index, &hole, rval));
-        if (!ok)
-            goto done;
+        if (ARRAY_IS_DENSE(cx, obj) && index < ARRAY_DENSELEN(obj)) {
+            *rval = obj->dslots[index];
+            hole = (*rval == JSVAL_HOLE);
+            ok = JS_TRUE;
+        } else {
+            ok = (JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) &&
+                  GetArrayElement(cx, obj, index, &hole, rval));
+            if (!ok)
+                goto done;
+        }
         if (hole ||
             (op != TO_SOURCE &&
              (JSVAL_IS_VOID(*rval) || JSVAL_IS_NULL(*rval)))) {
             str = cx->runtime->emptyString;
         } else {
             if (op == TO_LOCALE_STRING) {
                 JSObject *robj;
 
@@ -720,72 +1321,95 @@ array_join_sub(JSContext *cx, JSObject *
 
 #if JS_HAS_TOSOURCE
 static JSBool
 array_toSource(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
 
     obj = JS_THIS_OBJECT(cx, vp);
-    if (!JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))
+    if (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
+        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {
         return JS_FALSE;
+    }
     return array_join_sub(cx, obj, TO_SOURCE, NULL, vp);
 }
 #endif
 
 static JSBool
 array_toString(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
 
     obj = JS_THIS_OBJECT(cx, vp);
-    if (!JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))
+    if (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
+        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {
         return JS_FALSE;
+    }
     return array_join_sub(cx, obj, TO_STRING, NULL, vp);
 }
 
 static JSBool
 array_toLocaleString(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
 
     obj = JS_THIS_OBJECT(cx, vp);
-    if (!JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))
+    if (OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass &&
+        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {
         return JS_FALSE;
+    }
 
     /*
      *  Passing comma here as the separator. Need a way to get a
      *  locale-specific version.
      */
     return array_join_sub(cx, obj, TO_LOCALE_STRING, NULL, vp);
 }
 
 static JSBool
 InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint end,
                   jsval *vector)
 {
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        if (!EnsureLength(cx, obj, end))
+            return JS_FALSE;
+
+        if (end > ARRAY_LENGTH(obj))
+            ARRAY_SET_LENGTH(obj, end);
+
+        memcpy(obj->dslots + start, vector, sizeof(jsval) * (end - start));
+        return JS_TRUE;
+    }
+
     while (start != end) {
         if (!JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) ||
             !SetArrayElement(cx, obj, start++, *vector++)) {
             return JS_FALSE;
         }
     }
     return JS_TRUE;
 }
 
 static JSBool
 InitArrayObject(JSContext *cx, JSObject *obj, jsuint length, jsval *vector)
 {
-    jsval v;
+    JS_ASSERT(OBJ_IS_ARRAY(cx, obj));
+
+    ARRAY_SET_LENGTH(obj, length);
 
-    JS_ASSERT(OBJ_GET_CLASS(cx, obj) == &js_ArrayClass);
-    if (!IndexToValue(cx, length, &v))
-        return JS_FALSE;
-    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, v);
-    return !vector || InitArrayElements(cx, obj, 0, length, vector);
+    if (vector) {
+        if (!EnsureLength(cx, obj, length))
+            return JS_FALSE;
+        memcpy(obj->dslots, vector, length * sizeof (jsval));
+        ARRAY_SET_COUNT(obj, length);
+    } else {
+        ARRAY_SET_COUNT(obj, 0);
+    }
+    return JS_TRUE;
 }
 
 /*
  * Perl-inspired join, reverse, and sort.
  */
 static JSBool
 array_join(JSContext *cx, uintN argc, jsval *vp)
 {
@@ -1315,17 +1939,17 @@ array_sort(JSContext *cx, uintN argc, js
     *vp = OBJECT_TO_JSVAL(obj);
     return JS_TRUE;
 }
 
 /*
  * Perl-inspired push, pop, shift, unshift, and splice methods.
  */
 static JSBool
-slow_array_push(JSContext *cx, JSObject *obj, uintN argc, jsval *vp)
+array_push_slowly(JSContext *cx, JSObject *obj, uintN argc, jsval *vp)
 {
     jsuint length, newlength;
 
     if (!js_GetLengthProperty(cx, obj, &length))
         return JS_FALSE;
     newlength = length + argc;
     if (!InitArrayElements(cx, obj, length, newlength, vp + 2))
         return JS_FALSE;
@@ -1335,57 +1959,75 @@ slow_array_push(JSContext *cx, JSObject 
         return JS_FALSE;
     return js_SetLengthProperty(cx, obj, newlength);
 }
 
 static JSBool
 array_push(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
-    jsval v;
+    uint32 len;
 
     /* Insist on one argument and obj of the expected class. */
     obj = JS_THIS_OBJECT(cx, vp);
     if (!obj)
         return JS_FALSE;
-    if (argc != 1 || OBJ_GET_CLASS(cx, obj) != &js_ArrayClass)
-        return slow_array_push(cx, obj, argc, vp);
-
-    /* Beware 'length' int to double jsval overflow. */
-    v = STOBJ_GET_SLOT(obj, JSSLOT_ARRAY_LENGTH);
-    if (!(v & JSVAL_INT) || v == INT_TO_JSVAL(JSVAL_INT_MAX))
-        return slow_array_push(cx, obj, argc, vp);
+    if (argc != 1 || !ARRAY_IS_DENSE(cx, obj))
+        return array_push_slowly(cx, obj, argc, vp);
 
-    /*
-     * Ok, we can optimize to define a new property identified by the
-     * current value of 'length'.  We know no such property exists,
-     * because if one did, then js_ArrayClass.addProperty would have
-     * increased the value of 'length' to one greater than this index
-     * (proof by contradiction).
-     */
-    if (!js_DefineNativeProperty(cx, obj, INT_JSVAL_TO_JSID(v), vp[2],
-                                 NULL, NULL, JSPROP_ENUMERATE, 0, 0,
-                                 NULL)) {
+    len = ARRAY_LENGTH(obj);
+    if (INDEX_TOO_SPARSE(obj, len)) {
+        if (!MakeArraySlow(cx, obj))
+            return JS_FALSE;
+        return array_push_slowly(cx, obj, argc, vp);
+    }
+
+    if (!EnsureLength(cx, obj, len + 1))
         return JS_FALSE;
-    }
-    v += 2;
-    JS_ASSERT(STOBJ_GET_SLOT(obj, JSSLOT_ARRAY_LENGTH) == v);
-    *vp = v;
-    return JS_TRUE;
+    ARRAY_SET_LENGTH(obj, len + 1);
+
+    JS_ASSERT(obj->dslots[len] == JSVAL_HOLE);
+    ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) + 1);
+    obj->dslots[len] = vp[2];
+    return IndexToValue(cx, ARRAY_LENGTH(obj), vp);
 }
 
 JSBool
 array_pop(JSContext *cx, uintN argc, jsval *vp)
 {
     JSObject *obj;
     jsuint index;
     JSBool hole;
 
     obj = JS_THIS_OBJECT(cx, vp);
-    if (!obj || !js_GetLengthProperty(cx, obj, &index))
+    if (!obj)
+        return JS_FALSE;
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        *vp = JSVAL_VOID;
+        index = ARRAY_LENGTH(obj);
+        if (index == 0)
+            return JS_TRUE;
+        index--;
+        if (index < ARRAY_DENSELEN(obj)) {
+            *vp = obj->dslots[index];
+            JS_ASSERT(*vp != JSVAL_HOLE);
+            if (index == 0) {
+                JS_free(cx, obj->dslots - 1);
+                obj->dslots = NULL;
+            } else {
+                ARRAY_SET_DENSELEN(obj, index);
+            }
+            ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) - 1);
+        }
+            
+        ARRAY_SET_LENGTH(obj, index);
+        return JS_TRUE;
+    }
+
+    if (!js_GetLengthProperty(cx, obj, &index))
         return JS_FALSE;
     if (index == 0) {
         *vp = JSVAL_VOID;
     } else {
         index--;
 
         /* Get the to-be-deleted property's value into vp. */
         if (!GetArrayElement(cx, obj, index, &hole, vp))
@@ -1624,34 +2266,48 @@ array_concat(JSContext *cx, uintN argc, 
     JSBool hole, ok;
     JSTempValueRooter tvr;
 
     /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
     argv = JS_ARGV(cx, vp) - 1;
     JS_ASSERT(JS_THIS_OBJECT(cx, vp) == JSVAL_TO_OBJECT(argv[0]));
 
     /* Create a new Array object and root it using *vp. */
-    nobj = js_NewArrayObject(cx, 0, NULL);
-    if (!nobj)
-        return JS_FALSE;
-    *vp = OBJECT_TO_JSVAL(nobj);
+    aobj = JS_THIS_OBJECT(cx, vp);
+    if (ARRAY_IS_DENSE(cx, aobj)) {
+        nobj = js_NewArrayObject(cx, ARRAY_DENSELEN(aobj), aobj->dslots);
+        if (!nobj)
+            return JS_FALSE;
+        length = ARRAY_LENGTH(aobj);
+        ARRAY_SET_LENGTH(nobj, length);
+        *vp = OBJECT_TO_JSVAL(nobj);
+        if (argc == 0)
+            return JS_TRUE;
+        argc--;
+        argv++;
+    } else {
+        nobj = js_NewArrayObject(cx, 0, NULL);
+        if (!nobj)
+            return JS_FALSE;
+        *vp = OBJECT_TO_JSVAL(nobj);
+        length = 0;
+    }
 
     /* After this, control must flow through label out: to exit. */
     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
 
     /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
-    length = 0;
     for (i = 0; i <= argc; i++) {
         ok = JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP);
         if (!ok)
             goto out;
         v = argv[i];
         if (JSVAL_IS_OBJECT(v)) {
             aobj = JSVAL_TO_OBJECT(v);
-            if (aobj && OBJ_GET_CLASS(cx, aobj) == &js_ArrayClass) {
+            if (aobj && OBJ_IS_ARRAY(cx, aobj)) {
                 ok = OBJ_GET_PROPERTY(cx, aobj,
                                       ATOM_TO_JSID(cx->runtime->atomState
                                                    .lengthAtom),
                                       &tvr.u.value);
                 if (!ok)
                     goto out;
                 ok = ValueIsLength(cx, tvr.u.value, &alength);
                 if (!ok)
@@ -1699,22 +2355,16 @@ array_slice(JSContext *cx, uintN argc, j
     JSObject *nobj, *obj;
     jsuint length, begin, end, slot;
     jsdouble d;
     JSBool hole, ok;
     JSTempValueRooter tvr;
 
     argv = JS_ARGV(cx, vp);
 
-    /* Create a new Array object and root it using *vp. */
-    nobj = js_NewArrayObject(cx, 0, NULL);
-    if (!nobj)
-        return JS_FALSE;
-    *vp = OBJECT_TO_JSVAL(nobj);
-
     obj = JS_THIS_OBJECT(cx, vp);
     if (!obj || !js_GetLengthProperty(cx, obj, &length))
         return JS_FALSE;
     begin = 0;
     end = length;
 
     if (argc > 0) {
         if (!js_ValueToNumber(cx, argv[0], &d))
@@ -1742,16 +2392,30 @@ array_slice(JSContext *cx, uintN argc, j
             }
             end = (jsuint)d;
         }
     }
 
     if (begin > end)
         begin = end;
 
+    if (ARRAY_IS_DENSE(cx, obj)) {
+        nobj = js_NewArrayObject(cx, end - begin, obj->dslots + begin);
+        if (!nobj)
+            return JS_FALSE;
+        *vp = OBJECT_TO_JSVAL(nobj);
+        return JS_TRUE;
+    }
+
+    /* Create a new Array object and root it using *vp. */
+    nobj = js_NewArrayObject(cx, 0, NULL);
+    if (!nobj)
+        return JS_FALSE;
+    *vp = OBJECT_TO_JSVAL(nobj);
+
     /* After this, control must flow through label out: to exit. */
     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
 
     for (slot = begin; slot < end; slot++) {
         ok = JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP) &&
              GetArrayElement(cx, obj, slot, &hole, &tvr.u.value);
         if (!ok)
             goto out;
@@ -2101,17 +2765,17 @@ static JSFunctionSpec array_methods[] = 
     JS_FN("reverse",            array_reverse,      0,0,JSFUN_GENERIC_NATIVE),
     JS_FN("sort",               array_sort,         0,1,JSFUN_GENERIC_NATIVE),
     JS_FN("push",               array_push,         1,1,JSFUN_GENERIC_NATIVE),
     JS_FN("pop",                array_pop,          0,0,JSFUN_GENERIC_NATIVE),
     JS_FN("shift",              array_shift,        0,0,JSFUN_GENERIC_NATIVE),
     JS_FN("unshift",            array_unshift,      0,1,JSFUN_GENERIC_NATIVE),
     JS_FN("splice",             array_splice,       0,2,JSFUN_GENERIC_NATIVE),
 
-    /* Python-esque sequence methods. */
+    /* Pythonic sequence methods. */
     JS_FN("concat",             array_concat,       0,1,JSFUN_GENERIC_NATIVE),
     JS_FN("slice",              array_slice,        0,2,JSFUN_GENERIC_NATIVE),
 
 #if JS_HAS_ARRAY_EXTRAS
     JS_FN("indexOf",            array_indexOf,      1,1,JSFUN_GENERIC_NATIVE),
     JS_FN("lastIndexOf",        array_lastIndexOf,  1,1,JSFUN_GENERIC_NATIVE),
     JS_FN("forEach",            array_forEach,      1,1,JSFUN_GENERIC_NATIVE),
     JS_FN("map",                array_map,          1,1,JSFUN_GENERIC_NATIVE),
@@ -2156,16 +2820,22 @@ Array(JSContext *cx, JSObject *obj, uint
     return InitArrayObject(cx, obj, length, vector);
 }
 
 JSObject *
 js_InitArrayClass(JSContext *cx, JSObject *obj)
 {
     JSObject *proto;
 
+    /* Initialize the ops structure used by slow arrays */
+    memcpy(&js_SlowArrayObjectOps, &js_ObjectOps, sizeof(JSObjectOps));
+    js_SlowArrayObjectOps.trace = slowarray_trace;
+    js_SlowArrayObjectOps.enumerate = slowarray_enumerate;
+    js_SlowArrayObjectOps.call = NULL;
+
     proto = JS_InitClass(cx, obj, NULL, &js_ArrayClass, Array, 1,
                          array_props, array_methods, NULL, NULL);
 
     /* Initialize the Array prototype object so it gets a length property. */
     if (!proto || !InitArrayObject(cx, proto, 0, NULL))
         return NULL;
     return proto;
 }
@@ -2184,8 +2854,51 @@ js_NewArrayObject(JSContext *cx, jsuint 
     if (!InitArrayObject(cx, obj, length, vector))
         obj = NULL;
     JS_POP_TEMP_ROOT(cx, &tvr);
 
     /* Set/clear newborn root, in case we lost it.  */
     cx->weakRoots.newborn[GCX_OBJECT] = obj;
     return obj;
 }
+
+JSObject *
+js_NewSlowArrayObject(JSContext *cx)
+{
+    JSObject *obj = js_NewObject(cx, &js_SlowArrayClass, NULL, NULL);
+    if (obj)
+        ARRAY_SET_LENGTH(obj, 0);
+    return obj;
+}
+
+#ifdef DEBUG_ARRAYS
+JSBool
+js_ArrayInfo(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
+{
+    uintN i;
+    JSObject *array;
+
+    for (i = 0; i < argc; i++) {
+        char *bytes;
+        
+        bytes = js_DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, argv[i],
+                                           NULL);
+        if (!bytes)
+            return JS_FALSE;
+        if (JSVAL_IS_PRIMITIVE(argv[i]) ||
+            !OBJ_IS_ARRAY(cx, (array = JSVAL_TO_OBJECT(argv[i])))) {
+            fprintf(stderr, "%s: not array\n", bytes);
+            JS_free(cx, bytes);
+            continue;
+        }
+        fprintf(stderr, "%s: %s (len %lu", bytes,
+                ARRAY_IS_DENSE(cx, array) ? "dense" : "sparse",
+                ARRAY_LENGTH(array));
+        if (ARRAY_IS_DENSE(cx, array)) {
+            fprintf(stderr, ", count %lu, denselen %lu",
+                    ARRAY_COUNT(array), ARRAY_DENSELEN(array));
+        }
+        fputs(")\n", stderr);
+        JS_free(cx, bytes);
+    }
+    return JS_TRUE;
+}
+#endif
--- a/js/src/jsarray.h
+++ b/js/src/jsarray.h
@@ -48,25 +48,35 @@
 JS_BEGIN_EXTERN_C
 
 /* Generous sanity-bound on length (in elements) of array initialiser. */
 #define ARRAY_INIT_LIMIT        JS_BIT(24)
 
 extern JSBool
 js_IdIsIndex(jsval id, jsuint *indexp);
 
-extern JSClass js_ArrayClass;
+extern JSClass js_ArrayClass, js_SlowArrayClass;
+
+#define ARRAY_IS_DENSE(cx, obj) (OBJ_GET_CLASS(cx, obj) == &js_ArrayClass)
+#define OBJ_IS_ARRAY(cx, obj)   (ARRAY_IS_DENSE(cx, obj) ||                    \
+                                 OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass)
 
 extern JSObject *
 js_InitArrayClass(JSContext *cx, JSObject *obj);
 
 extern JSObject *
 js_NewArrayObject(JSContext *cx, jsuint length, jsval *vector);
 
-#define JSSLOT_ARRAY_LENGTH     JSSLOT_PRIVATE
+/* Create an array object that starts out already made slow/sparse. */
+extern JSObject *
+js_NewSlowArrayObject(JSContext *cx);
+
+#define JSSLOT_ARRAY_LENGTH            JSSLOT_PRIVATE
+#define JSSLOT_ARRAY_COUNT             (JSSLOT_ARRAY_LENGTH + 1)
+#define JSSLOT_ARRAY_LOOKUP_HOLDER     (JSSLOT_ARRAY_COUNT + 1)
 
 extern JSBool
 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp);
 
 extern JSBool
 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length);
 
 extern JSBool
@@ -94,11 +104,16 @@ typedef JSBool (*JSComparator)(void *arg
  * The sorted result is in vec. vec may be in an inconsistent state if the
  * comparator function cmp returns an error inside a comparison, so remember
  * to check the return value of this function.
  */
 extern JSBool
 js_MergeSort(void *vec, size_t nel, size_t elsize, JSComparator cmp,
              void *arg, void *tmp);
 
+#ifdef DEBUG_ARRAYS
+extern JSBool
+js_ArrayInfo(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval);
+#endif
+
 JS_END_EXTERN_C
 
 #endif /* jsarray_h___ */
--- a/js/src/jsinterp.c
+++ b/js/src/jsinterp.c
@@ -4120,24 +4120,33 @@ interrupt:
           END_VARLEN_CASE
 
           BEGIN_CASE(JSOP_LENGTH)
             lval = FETCH_OPND(-1);
             if (JSVAL_IS_STRING(lval)) {
                 str = JSVAL_TO_STRING(lval);
                 rval = INT_TO_JSVAL(JSSTRING_LENGTH(str));
             } else if (!JSVAL_IS_PRIMITIVE(lval) &&
-                       (obj = JSVAL_TO_OBJECT(lval),
-                        OBJ_GET_CLASS(cx, obj) == &js_ArrayClass)) {
+                       (obj = JSVAL_TO_OBJECT(lval), OBJ_IS_ARRAY(cx, obj))) {
+
+                jsuint length;
+
                 /*
                  * We know that the array is created with only its 'length'
                  * private data in a fixed slot at JSSLOT_ARRAY_LENGTH. See
                  * also JSOP_ARRAYPUSH, far below.
                  */
-                rval = obj->fslots[JSSLOT_ARRAY_LENGTH];
+                length = obj->fslots[JSSLOT_ARRAY_LENGTH];
+                if (length <= JSVAL_INT_MAX) {
+                    rval = INT_TO_JSVAL(length);
+                } else {
+                    ok = js_NewDoubleValue(cx, (jsdouble)length, &rval);
+                    if (!ok)
+                        goto out;
+                }
             } else {
                 i = -1;
                 len = JSOP_LENGTH_LENGTH;
                 goto do_getprop_with_lval;
             }
             STORE_OPND(-1, rval);
           END_CASE(JSOP_LENGTH)
 
@@ -6539,20 +6548,17 @@ interrupt:
             rval = FETCH_OPND(-1);
 
             /*
              * We know that the array is created with only a 'length' private
              * data slot at JSSLOT_ARRAY_LENGTH, and that previous iterations
              * of the comprehension have added the only properties directly in
              * the array object.
              */
-            lval = obj->fslots[JSSLOT_ARRAY_LENGTH];
-            JS_ASSERT(JSVAL_IS_INT(lval));
-            i = JSVAL_TO_INT(lval);
-            SAVE_SP_AND_PC(fp);
+            i = obj->fslots[JSSLOT_ARRAY_LENGTH];
             if (i == ARRAY_INIT_LIMIT) {
                 JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
                                        JSMSG_ARRAY_INIT_TOO_BIG);
                 ok = JS_FALSE;
                 goto out;
             }
             id = INT_TO_JSID(i);
             ok = OBJ_SET_PROPERTY(cx, obj, id, &rval);
--- a/js/src/jsiter.c
+++ b/js/src/jsiter.c
@@ -319,17 +319,17 @@ js_GetNativeIteratorFlags(JSContext *cx,
 {
     if (OBJ_GET_CLASS(cx, iterobj) != &js_IteratorClass)
         return 0;
     return JSVAL_TO_INT(OBJ_GET_SLOT(cx, iterobj, JSSLOT_ITER_FLAGS));
 }
 
 /*
  * Call ToObject(v).__iterator__(keyonly) if ToObject(v).__iterator__ exists.
- * Otherwise construct the defualt iterator.
+ * Otherwise construct the default iterator.
  */
 JS_FRIEND_API(JSBool)
 js_ValueToIterator(JSContext *cx, uintN flags, jsval *vp)
 {
     JSObject *obj;
     JSTempValueRooter tvr;
     JSAtom *atom;
     JSClass *clasp;
--- a/js/src/jsobj.c
+++ b/js/src/jsobj.c
@@ -4122,18 +4122,20 @@ js_Enumerate(JSContext *cx, JSObject *ob
     jsint i, length;
     JSScope *scope;
     JSIdArray *ida;
     JSNativeIteratorState *state;
 
     rt = cx->runtime;
     clasp = OBJ_GET_CLASS(cx, obj);
     enumerate = clasp->enumerate;
-    if (clasp->flags & JSCLASS_NEW_ENUMERATE)
+    if (clasp->flags & JSCLASS_NEW_ENUMERATE) {
+        JS_ASSERT(enumerate != JS_EnumerateStub);
         return ((JSNewEnumerateOp) enumerate)(cx, obj, enum_op, statep, idp);
+    }
 
     switch (enum_op) {
       case JSENUMERATE_INIT:
         if (!enumerate(cx, obj))
             return JS_FALSE;
         length = 0;
 
         /*
@@ -4835,36 +4837,40 @@ js_DumpScopeMeters(JSRuntime *rt)
 
     JS_DumpHistogram(&js_entry_count_bs, logfp);
     JS_BASIC_STATS_INIT(&js_entry_count_bs);
     fflush(logfp);
 }
 #endif
 
 #ifdef DEBUG
-static void
-PrintObjectSlotName(JSTracer *trc, char *buf, size_t bufsize)
+void
+js_PrintObjectSlotName(JSTracer *trc, char *buf, size_t bufsize)
 {
     JSObject *obj;
     uint32 slot;
     JSScope *scope;
     jsval nval;
     JSScopeProperty *sprop;
     JSClass *clasp;
     uint32 key;
     const char *slotname;
 
-    JS_ASSERT(trc->debugPrinter == PrintObjectSlotName);
+    JS_ASSERT(trc->debugPrinter == js_PrintObjectSlotName);
     obj = (JSObject *)trc->debugPrintArg;
     slot = (uint32)trc->debugPrintIndex;
 
-    scope = OBJ_SCOPE(obj);
-    sprop = SCOPE_LAST_PROP(scope);
-    while (sprop && sprop->slot != slot)
-        sprop = sprop->parent;
+    if (OBJ_IS_NATIVE(obj)) {
+        scope = OBJ_SCOPE(obj);
+        sprop = SCOPE_LAST_PROP(scope);
+        while (sprop && sprop->slot != slot)
+            sprop = sprop->parent;
+    } else {
+        sprop = NULL;
+    }
 
     if (!sprop) {
         switch (slot) {
           case JSSLOT_PROTO:
             JS_snprintf(buf, bufsize, "__proto__");
             break;
           case JSSLOT_PARENT:
             JS_snprintf(buf, bufsize, "__parent__");
@@ -4996,17 +5002,17 @@ js_TraceObject(JSTracer *trc, JSObject *
      */
     nslots = (scope->object != obj)
              ? STOBJ_NSLOTS(obj)
              : LOCKED_OBJ_NSLOTS(obj);
 
     for (i = 0; i != nslots; ++i) {
         v = STOBJ_GET_SLOT(obj, i);
         if (JSVAL_IS_TRACEABLE(v)) {
-            JS_SET_TRACING_DETAILS(trc, PrintObjectSlotName, obj, i);
+            JS_SET_TRACING_DETAILS(trc, js_PrintObjectSlotName, obj, i);
             JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
         }
     }
 }
 
 void
 js_Clear(JSContext *cx, JSObject *obj)
 {
--- a/js/src/jsobj.h
+++ b/js/src/jsobj.h
@@ -662,16 +662,19 @@ js_TryMethod(JSContext *cx, JSObject *ob
 
 extern JSBool
 js_XDRObject(JSXDRState *xdr, JSObject **objp);
 
 extern void
 js_TraceObject(JSTracer *trc, JSObject *obj);
 
 extern void
+js_PrintObjectSlotName(JSTracer *trc, char *buf, size_t bufsize);
+
+extern void
 js_Clear(JSContext *cx, JSObject *obj);
 
 extern jsval
 js_GetRequiredSlot(JSContext *cx, JSObject *obj, uint32 slot);
 
 extern JSBool
 js_SetRequiredSlot(JSContext *cx, JSObject *obj, uint32 slot, jsval v);
 
--- a/js/src/jsregexp.c
+++ b/js/src/jsregexp.c
@@ -3432,17 +3432,17 @@ js_ExecuteRegExp(JSContext *cx, JSRegExp
         obj = NULL;
     } else {
         /*
          * The array returned on match has element 0 bound to the matched
          * string, elements 1 through state.parenCount bound to the paren
          * matches, an index property telling the length of the left context,
          * and an input property referring to the input string.
          */
-        obj = js_NewArrayObject(cx, 0, NULL);
+        obj = js_NewSlowArrayObject(cx);
         if (!obj) {
             ok = JS_FALSE;
             goto out;
         }
         *rval = OBJECT_TO_JSVAL(obj);
 
 #define DEFVAL(val, id) {                                                     \
     ok = js_DefineProperty(cx, obj, id, val,                                  \
--- a/js/src/jsscope.c
+++ b/js/src/jsscope.c
@@ -1216,23 +1216,22 @@ js_AddScopeProperty(JSContext *cx, JSSco
         if (!(flags & SPROP_IS_ALIAS)) {
             if (attrs & JSPROP_SHARED) {
                 slot = SPROP_INVALID_SLOT;
             } else {
                 /*
                  * We may have set slot from a nearly-matching sprop, above.
                  * If so, we're overwriting that nearly-matching sprop, so we
                  * can reuse its slot -- we don't need to allocate a new one.
-                 * Callers should therefore pass SPROP_INVALID_SLOT for all
-                 * non-alias, unshared property adds.
+                 * Similarly, we use a specific slot if provided by the caller.
                  */
-                if (slot != SPROP_INVALID_SLOT)
-                    JS_ASSERT(overwriting);
-                else if (!js_AllocSlot(cx, scope->object, &slot))
+                if (slot == SPROP_INVALID_SLOT &&
+                    !js_AllocSlot(cx, scope->object, &slot)) {
                     goto fail_overwrite;
+                }
             }
         }
 
         /*
          * Check for a watchpoint on a deleted property; if one exists, change
          * setter to js_watch_set.
          * XXXbe this could get expensive with lots of watchpoints...
          */
--- a/js/src/jsstr.c
+++ b/js/src/jsstr.c
@@ -808,17 +808,17 @@ str_toUpperCase(JSContext *cx, uintN arg
 
 static JSBool
 str_toLocaleUpperCase(JSContext *cx, uintN argc, jsval *vp)
 {
     JSString *str;
 
     /*
      * Forcefully ignore the first (or any) argument and return toUpperCase(),
-     * ECMA has reserved that argument, presumbaly for defining the locale.
+     * ECMA has reserved that argument, presumably for defining the locale.
      */
     if (cx->localeCallbacks && cx->localeCallbacks->localeToUpperCase) {
         NORMALIZE_THIS(cx, vp, str);
         return cx->localeCallbacks->localeToUpperCase(cx, str, vp);
     }
     return str_toUpperCase(cx, 0, vp);
 }
 
@@ -1265,17 +1265,18 @@ match_glob(JSContext *cx, jsint count, G
             return JS_FALSE;
         *mdata->arrayval = OBJECT_TO_JSVAL(arrayobj);
     }
     matchsub = &cx->regExpStatics.lastMatch;
     matchstr = js_NewStringCopyN(cx, matchsub->chars, matchsub->length);
     if (!matchstr)
         return JS_FALSE;
     v = STRING_TO_JSVAL(matchstr);
-    return js_SetProperty(cx, arrayobj, INT_TO_JSID(count), &v);
+    JS_ASSERT(count <= JSVAL_INT_MAX);
+    return OBJ_SET_PROPERTY(cx, arrayobj, INT_TO_JSID(count), &v);
 }
 
 static JSBool
 str_match(JSContext *cx, uintN argc, jsval *vp)
 {
     JSTempValueRooter tvr;
     MatchData mdata;
     JSBool ok;
@@ -1798,17 +1799,17 @@ str_split(JSContext *cx, uintN argc, jsv
 
     arrayobj = js_ConstructObject(cx, &js_ArrayClass, NULL, NULL, 0, NULL);
     if (!arrayobj)
         return JS_FALSE;
     *vp = OBJECT_TO_JSVAL(arrayobj);
 
     if (argc == 0) {
         v = STRING_TO_JSVAL(str);
-        ok = JS_SetElement(cx, arrayobj, 0, &v);
+        ok = OBJ_SET_PROPERTY(cx, arrayobj, INT_TO_JSID(0), &v);
     } else {
         if (JSVAL_IS_REGEXP(cx, vp[2])) {
             re = (JSRegExp *) JS_GetPrivate(cx, JSVAL_TO_OBJECT(vp[2]));
             sep = &tmp;
 
             /* Set a magic value so we can detect a successful re match. */
             sep->chars = NULL;
             sep->length = 0;