Bug 477279 - Tune dense array growth. r=brendan.
authorJason Orendorff <jorendorff@mozilla.com>
Mon, 23 Feb 2009 17:31:02 -0600
changeset 25488 42acafcdae02d1aa8eddd308a5e8ffff30e842bc
parent 25487 606a5d4acf46075dd1343a9e6f79e857f401e725
child 25489 393a83c4c7a243e022a02e2428cfc68df6fa6ea5
push id5575
push userrsayre@mozilla.com
push dateWed, 25 Feb 2009 09:05:38 +0000
treeherdermozilla-central@8eba35e62d92 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbrendan
bugs477279
milestone1.9.2a1pre
Bug 477279 - Tune dense array growth. r=brendan.
js/src/jsarray.cpp
js/src/jsarray.h
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -333,24 +333,57 @@ ResizeSlots(JSContext *cx, JSObject *obj
     js_SetDenseArrayCapacity(obj, size);
 
     for (slots = obj->dslots + oldsize; slots < obj->dslots + size; slots++)
         *slots = JSVAL_HOLE;
 
     return JS_TRUE;
 }
 
+/*
+ * When a dense array with CAPACITY_DOUBLING_MAX or fewer slots needs to grow,
+ * double its capacity, to push() N elements in amortized O(N) time.
+ *
+ * Above this limit, grow by 12.5% each time. Speed is still amortized O(N),
+ * with a higher constant factor, and we waste less space.
+ */
+#define CAPACITY_DOUBLING_MAX    (1024 * 1024)
+
+/*
+ * Round up all large allocations to a multiple of this (1MB), so as not to
+ * waste space if malloc gives us 1MB-sized chunks (as jemalloc does).
+ */
+#define CAPACITY_CHUNK  (1024 * 1024 / sizeof(jsval))
+
 static JSBool
-EnsureCapacity(JSContext *cx, JSObject *obj, uint32 len)
+EnsureCapacity(JSContext *cx, JSObject *obj, uint32 capacity)
 {
-    uint32 oldlen = js_DenseArrayCapacity(obj);
-
-    if (len > oldlen) {
-        return ResizeSlots(cx, obj, oldlen,
-                           len + ARRAY_GROWBY - (len % ARRAY_GROWBY));
+    uint32 oldsize = js_DenseArrayCapacity(obj);
+
+    if (capacity > oldsize) {
+        /*
+         * If this overflows uint32, capacity is very large. nextsize will end
+         * up being less than capacity, the code below will thus disregard it,
+         * and ResizeSlots will fail.
+         *
+         * The way we use dslots[-1] forces a few +1s and -1s here. For
+         * example, (oldsize * 2 + 1) produces the sequence 7, 15, 31, 63, ...
+         * which makes the total allocation size (with dslots[-1]) a power
+         * of two.
+         */
+        uint32 nextsize = (oldsize <= CAPACITY_DOUBLING_MAX)
+                          ? oldsize * 2 + 1
+                          : oldsize + (oldsize >> 3);
+
+        capacity = JS_MAX(capacity, nextsize);
+        if (capacity >= CAPACITY_CHUNK)
+            capacity = JS_ROUNDUP(capacity + 1, CAPACITY_CHUNK) - 1;  /* -1 for dslots[-1] */
+        else if (capacity < ARRAY_CAPACITY_MIN)
+            capacity = ARRAY_CAPACITY_MIN;
+        return ResizeSlots(cx, obj, oldsize, capacity);
     }
     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
@@ -2142,17 +2175,17 @@ js_ArrayCompPush(JSContext *cx, JSObject
 
     if (length == js_DenseArrayCapacity(obj)) {
         if (length >= ARRAY_INIT_LIMIT) {
             JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
                                    JSMSG_ARRAY_INIT_TOO_BIG);
             return JS_FALSE;
         }
 
-        if (!ResizeSlots(cx, obj, length, length + ARRAY_GROWBY))
+        if (!EnsureCapacity(cx, obj, length + 1))
             return JS_FALSE;
     }
     obj->fslots[JSSLOT_ARRAY_LENGTH] = length + 1;
     obj->fslots[JSSLOT_ARRAY_COUNT]++;
     obj->dslots[length] = v;
     return JS_TRUE;
 }
 
@@ -2489,22 +2522,22 @@ array_concat(JSContext *cx, uintN argc, 
     /* 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. */
     aobj = JS_THIS_OBJECT(cx, vp);
     if (OBJ_IS_DENSE_ARRAY(cx, aobj)) {
         /*
-         * Clone aobj but pass the minimum of its length and capacity, to handle
-         * a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In such a
-         * case we'll pass 8 (not 3) due to the ARRAY_GROWBY over-allocation
-         * policy, which will cause nobj to be over-allocated to 16. But in the
-         * normal case where length is <= capacity, nobj and aobj will have the
-         * same capacity.
+         * Clone aobj but pass the minimum of its length and capacity, to
+         * handle a = [1,2,3]; a.length = 10000 "dense" cases efficiently. In
+         * such a case we'll pass 8 (not 3) due to ARRAY_CAPACITY_MIN, which
+         * will cause nobj to be over-allocated to 16. But in the normal case
+         * where length is <= capacity, nobj and aobj will have the same
+         * capacity.
          */
         length = aobj->fslots[JSSLOT_ARRAY_LENGTH];
         jsuint capacity = js_DenseArrayCapacity(aobj);
         nobj = js_NewArrayObject(cx, JS_MIN(length, capacity), aobj->dslots,
                                  aobj->fslots[JSSLOT_ARRAY_COUNT] !=
                                  (jsval) length);
         if (!nobj)
             return JS_FALSE;
@@ -3120,26 +3153,26 @@ js_FastNewArrayWithLength(JSContext* cx,
         obj->fslots[JSSLOT_ARRAY_LENGTH] = i;
     return obj;
 }
 
 JSObject* FASTCALL
 js_NewUninitializedArray(JSContext* cx, JSObject* proto, uint32 len)
 {
     JSObject *obj = js_FastNewArrayWithLength(cx, proto, len);
-    if (!obj || !ResizeSlots(cx, obj, 0, JS_MAX(len, ARRAY_GROWBY)))
+    if (!obj || !ResizeSlots(cx, obj, 0, JS_MAX(len, ARRAY_CAPACITY_MIN)))
         return NULL;
     return obj;
 }
 
 #define ARRAY_CTOR_GUTS(exact_len, newslots_code)                             \
     JS_ASSERT(JS_ON_TRACE(cx));                                               \
     JSObject* obj = js_FastNewArray(cx, proto);                               \
     if (obj) {                                                                \
-        const uint32 len = ARRAY_GROWBY;                                      \
+        const uint32 len = ARRAY_CAPACITY_MIN;                                \
         jsval* newslots = (jsval*) JS_malloc(cx, sizeof (jsval) * (len + 1)); \
         if (newslots) {                                                       \
             obj->dslots = newslots + 1;                                       \
             js_SetDenseArrayCapacity(obj, len);                               \
             {newslots_code}                                                   \
             while (++newslots < obj->dslots + len)                            \
                 *newslots = JSVAL_HOLE;                                       \
             obj->fslots[JSSLOT_ARRAY_LENGTH] = (exact_len);                   \
--- a/js/src/jsarray.h
+++ b/js/src/jsarray.h
@@ -43,16 +43,18 @@
  * JS Array interface.
  */
 #include "jsprvtd.h"
 #include "jspubtd.h"
 #include "jsobj.h"
 
 JS_BEGIN_EXTERN_C
 
+#define ARRAY_CAPACITY_MIN      7
+
 /* 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, js_SlowArrayClass;
 
@@ -89,18 +91,16 @@ js_DenseArrayCapacity(JSObject *obj)
 static JS_INLINE void
 js_SetDenseArrayCapacity(JSObject *obj, uint32 capacity)
 {
     JS_ASSERT(OBJ_IS_DENSE_ARRAY(BOGUS_CX, obj));
     JS_ASSERT(obj->dslots);
     obj->dslots[-1] = (jsval) capacity;
 }
 
-#define ARRAY_GROWBY 8
-
 extern JSBool
 js_GetLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp);
 
 extern JSBool
 js_SetLengthProperty(JSContext *cx, JSObject *obj, jsuint length);
 
 extern JSBool
 js_HasLengthProperty(JSContext *cx, JSObject *obj, jsuint *lengthp);