Bug 1039965 - Avoid slop in JS arrays. r=bhackett,terrence.
authorNicholas Nethercote <nnethercote@mozilla.com>
Thu, 17 Jul 2014 21:14:20 -0700
changeset 195399 dd2018a5f894c967702595dbaed6c4d17503bbc7
parent 195398 95f31fa01c7a0068a96766e63f608880cfd7e0bf
child 195400 d2a81ea71ea757e30b21d826d855e0bfc454b623
push id46582
push usernnethercote@mozilla.com
push dateTue, 22 Jul 2014 05:30:19 +0000
treeherdermozilla-inbound@dd2018a5f894 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett, terrence
bugs1039965
milestone34.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1039965 - Avoid slop in JS arrays. r=bhackett,terrence. This patch changes JS array resizing to always allocate power-of-two sized slot requests. Previously it would mostly make slight-more-than-power-of-two sized requests, which cause lots of slop. Also, shrinkElements() now only does a reallocation if it would result in going down a size class. E.g. if you pop all the elements from a 1000-element array, it would realloc 999, then 998, then 997, all the way down the minimum size. Now it does 512, then 256, down to the minimum size (which is 8). I confirmed with DMD that the element allocations now have zero slop. This reduces peak RSS loading a couple of large PDF files (four times each) with pdf.js by 10s of MiBs.
js/src/jsobj.cpp
js/src/jsobj.h
js/src/vm/ObjectImpl.h
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -6,16 +6,17 @@
 
 /*
  * JS object implementation.
  */
 
 #include "jsobjinlines.h"
 
 #include "mozilla/ArrayUtils.h"
+#include "mozilla/CheckedInt.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/TemplateLib.h"
 
 #include <string.h>
 
 #include "jsapi.h"
 #include "jsarray.h"
@@ -3205,109 +3206,181 @@ ReallocateElements(ThreadSafeContext *cx
                                                                      oldCount, newCount);
     }
 #endif
 
     return static_cast<js::ObjectElements *>(cx->realloc_(oldHeader, oldCount * sizeof(HeapSlot),
                                                           newCount * sizeof(HeapSlot)));
 }
 
+// Round up |count| to one of our standard slot counts.  Up to 1 mebislot (i.e.
+// 1,048,576 slots) the slot count is always a power-of-two:
+//
+//   8, 16, 32, 64, ..., 256 Ki, 512 Ki, 1 Mi
+//
+// Beyond that, we use this formula:
+//
+//   count(n+1) = Math.ceil(count(n) * 1.125)
+//
+// where |count(n)| is the size of the nth bucket measured in MiSlots.
+//
+// These counts lets us add N elements to an array in amortized O(N) time.
+// Having the second class means that for bigger arrays the constant factor is
+// higher, but we waste less space.
+//
+/* static */ uint32_t
+JSObject::goodAllocated(uint32_t n)
+{
+    static const uint32_t Mebi = 1024 * 1024;
+
+    // This table was generated with this JavaScript code and a small amount
+    // subsequent reformatting:
+    //
+    //   for (let n = 1, i = 0; i < 57; i++) {
+    //     print((n * 1024 * 1024) + ', ');
+    //     n = Math.ceil(n * 1.125);
+    //   }
+    //   print('0');
+    //
+    // The final element is a sentinel value.
+    static const uint32_t BigBuckets[] = {
+        1048576, 2097152, 3145728, 4194304, 5242880, 6291456, 7340032, 8388608,
+        9437184, 11534336, 13631488, 15728640, 17825792, 20971520, 24117248,
+        27262976, 31457280, 35651584, 40894464, 46137344, 52428800, 59768832,
+        68157440, 77594624, 88080384, 99614720, 112197632, 126877696,
+        143654912, 162529280, 183500800, 206569472, 232783872, 262144000,
+        295698432, 333447168, 375390208, 422576128, 476053504, 535822336,
+        602931200, 678428672, 763363328, 858783744, 966787072, 1088421888,
+        1224736768, 1377828864, 1550843904, 1744830464, 1962934272, 2208301056,
+        2485125120, 2796552192, 3146776576, 3541041152, 3984588800, 0
+    };
+
+    // This code relies very much on |n| being a uint32_t.
+    if (n < Mebi) {
+        n = RoundUpPow2(n);
+        if (n < JSObject::SLOT_CAPACITY_MIN)
+            n = JSObject::SLOT_CAPACITY_MIN;
+    } else {
+        uint32_t i = 0;
+        while (true) {
+            uint32_t b = BigBuckets[i++];
+            if (b >= n) {
+                // Found the first bucket greater than or equal to |n|.
+                n = b;
+                break;
+            } else if (b == 0) {
+                // Hit the end; return the maximum possible n.
+                n = 0xffffffff;
+                break;
+            }
+        }
+    }
+    return n;
+}
+
 bool
-JSObject::growElements(ThreadSafeContext *cx, uint32_t newcap)
+JSObject::growElements(ThreadSafeContext *cx, uint32_t reqCapacity)
 {
     JS_ASSERT(nonProxyIsExtensible());
     JS_ASSERT(canHaveNonEmptyElements());
 
-    /*
-     * When an object with CAPACITY_DOUBLING_MAX or fewer elements needs to
-     * grow, double its capacity, to add 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.
-     */
-    static const size_t CAPACITY_DOUBLING_MAX = 1024 * 1024;
-    static const size_t CAPACITY_CHUNK = CAPACITY_DOUBLING_MAX / sizeof(Value);
-
-    uint32_t oldcap = getDenseCapacity();
-    JS_ASSERT(oldcap <= newcap);
-
-    uint32_t nextsize = (oldcap <= CAPACITY_DOUBLING_MAX)
-                      ? oldcap * 2
-                      : oldcap + (oldcap >> 3);
-
-    uint32_t actualCapacity;
+    uint32_t oldCapacity = getDenseCapacity();
+    JS_ASSERT(oldCapacity < reqCapacity);
+
+    using mozilla::CheckedInt;
+
+    CheckedInt<uint32_t> checkedOldAllocated =
+        CheckedInt<uint32_t>(oldCapacity) + ObjectElements::VALUES_PER_HEADER;
+    CheckedInt<uint32_t> checkedReqAllocated =
+        CheckedInt<uint32_t>(reqCapacity) + ObjectElements::VALUES_PER_HEADER;
+    if (!checkedOldAllocated.isValid() || !checkedReqAllocated.isValid())
+        return false;
+
+    uint32_t reqAllocated = checkedReqAllocated.value();
+    uint32_t oldAllocated = checkedOldAllocated.value();
+
+    uint32_t newAllocated;
     if (is<ArrayObject>() && !as<ArrayObject>().lengthIsWritable()) {
-        JS_ASSERT(newcap <= as<ArrayObject>().length());
+        JS_ASSERT(reqCapacity <= as<ArrayObject>().length());
         // Preserve the |capacity <= length| invariant for arrays with
         // non-writable length.  See also js::ArraySetLength which initially
         // enforces this requirement.
-        actualCapacity = newcap;
+        newAllocated = reqAllocated;
     } else {
-        actualCapacity = Max(newcap, nextsize);
-        if (actualCapacity >= CAPACITY_CHUNK)
-            actualCapacity = JS_ROUNDUP(actualCapacity, CAPACITY_CHUNK);
-        else if (actualCapacity < SLOT_CAPACITY_MIN)
-            actualCapacity = SLOT_CAPACITY_MIN;
-
-        /* Don't let nelements get close to wrapping around uint32_t. */
-        if (actualCapacity >= NELEMENTS_LIMIT || actualCapacity < oldcap || actualCapacity < newcap)
-            return false;
-    }
+        // Check that the oldAllocated is good, i.e. is a value that
+        // goodAllocated() or JSObject::createArray() would produce.
+        JS_ASSERT(oldAllocated == goodAllocated(oldAllocated) ||
+                  (oldAllocated <= MAX_FIXED_SLOTS && (oldAllocated % 2 == 0)));
+        newAllocated = goodAllocated(reqAllocated);
+    }
+
+    uint32_t newCapacity = newAllocated - ObjectElements::VALUES_PER_HEADER;
+    JS_ASSERT(newCapacity > oldCapacity && newCapacity >= reqCapacity);
+
+    // Don't let nelements get close to wrapping around uint32_t.
+    if (newCapacity >= NELEMENTS_LIMIT)
+        return false;
 
     uint32_t initlen = getDenseInitializedLength();
-    uint32_t oldAllocated = oldcap + ObjectElements::VALUES_PER_HEADER;
-    uint32_t newAllocated = actualCapacity + ObjectElements::VALUES_PER_HEADER;
 
     ObjectElements *newheader;
     if (hasDynamicElements()) {
         newheader = ReallocateElements(cx, this, getElementsHeader(), oldAllocated, newAllocated);
         if (!newheader)
-            return false; /* Leave elements as its old size. */
+            return false;   // Leave elements at its old size.
     } else {
         newheader = AllocateElements(cx, this, newAllocated);
         if (!newheader)
-            return false; /* Leave elements as its old size. */
+            return false;   // Leave elements at its old size.
         js_memcpy(newheader, getElementsHeader(),
                   (ObjectElements::VALUES_PER_HEADER + initlen) * sizeof(Value));
     }
 
-    newheader->capacity = actualCapacity;
+    newheader->capacity = newCapacity;
     elements = newheader->elements();
 
-    Debug_SetSlotRangeToCrashOnTouch(elements + initlen, actualCapacity - initlen);
+    Debug_SetSlotRangeToCrashOnTouch(elements + initlen, newCapacity - initlen);
 
     return true;
 }
 
 void
-JSObject::shrinkElements(ThreadSafeContext *cx, uint32_t newcap)
+JSObject::shrinkElements(ThreadSafeContext *cx, uint32_t reqCapacity)
 {
     JS_ASSERT(cx->isThreadLocal(this));
     JS_ASSERT(canHaveNonEmptyElements());
 
-    uint32_t oldcap = getDenseCapacity();
-    JS_ASSERT(newcap <= oldcap);
-
-    // Don't shrink elements below the minimum capacity.
-    if (oldcap <= SLOT_CAPACITY_MIN || !hasDynamicElements())
+    if (!hasDynamicElements())
         return;
 
-    newcap = Max(newcap, SLOT_CAPACITY_MIN);
-
-    uint32_t oldAllocated = oldcap + ObjectElements::VALUES_PER_HEADER;
-    uint32_t newAllocated = newcap + ObjectElements::VALUES_PER_HEADER;
+    uint32_t oldCapacity = getDenseCapacity();
+    JS_ASSERT(reqCapacity < oldCapacity);
+
+    uint32_t oldAllocated = oldCapacity + ObjectElements::VALUES_PER_HEADER;
+    uint32_t reqAllocated = reqCapacity + ObjectElements::VALUES_PER_HEADER;
+
+    // Check that the oldAllocated is good, i.e. is a value that
+    // goodAllocated() would produce.
+    JS_ASSERT(oldAllocated == goodAllocated(oldAllocated));
+
+    uint32_t newAllocated = goodAllocated(reqAllocated);
+    if (newAllocated == oldAllocated)
+        return;  // Leave elements at its old size.
+
+    MOZ_ASSERT(newAllocated > ObjectElements::VALUES_PER_HEADER);
+    uint32_t newCapacity = newAllocated - ObjectElements::VALUES_PER_HEADER;
 
     ObjectElements *newheader = ReallocateElements(cx, this, getElementsHeader(),
                                                    oldAllocated, newAllocated);
     if (!newheader) {
         cx->recoverFromOutOfMemory();
         return;  // Leave elements at its old size.
     }
 
-    newheader->capacity = newcap;
+    newheader->capacity = newCapacity;
     elements = newheader->elements();
 }
 
 bool
 js::SetClassAndProto(JSContext *cx, HandleObject obj,
                      const Class *clasp, Handle<js::TaggedProto> proto,
                      bool *succeeded)
 {
--- a/js/src/jsobj.h
+++ b/js/src/jsobj.h
@@ -597,16 +597,17 @@ class JSObject : public js::ObjectImpl
 
     /* Accessors for elements. */
     bool ensureElements(js::ThreadSafeContext *cx, uint32_t capacity) {
         if (capacity > getDenseCapacity())
             return growElements(cx, capacity);
         return true;
     }
 
+    static uint32_t goodAllocated(uint32_t count);
     bool growElements(js::ThreadSafeContext *cx, uint32_t newcap);
     void shrinkElements(js::ThreadSafeContext *cx, uint32_t cap);
     void setDynamicElements(js::ObjectElements *header) {
         JS_ASSERT(!hasDynamicElements());
         elements = header->elements();
         JS_ASSERT(hasDynamicElements());
     }
 
--- a/js/src/vm/ObjectImpl.h
+++ b/js/src/vm/ObjectImpl.h
@@ -201,21 +201,16 @@ class ObjectElements
     uint32_t initializedLength;
 
     /* Number of allocated slots. */
     uint32_t capacity;
 
     /* 'length' property of array objects, unused for other objects. */
     uint32_t length;
 
-    void staticAsserts() {
-        static_assert(sizeof(ObjectElements) == VALUES_PER_HEADER * sizeof(Value),
-                      "Elements size and values-per-Elements mismatch");
-    }
-
     bool shouldConvertDoubleElements() const {
         return flags & CONVERT_DOUBLE_ELEMENTS;
     }
     void setShouldConvertDoubleElements() {
         flags |= CONVERT_DOUBLE_ELEMENTS;
     }
     void clearShouldConvertDoubleElements() {
         flags &= ~CONVERT_DOUBLE_ELEMENTS;
@@ -249,19 +244,24 @@ class ObjectElements
         return int(offsetof(ObjectElements, capacity)) - int(sizeof(ObjectElements));
     }
     static int offsetOfLength() {
         return int(offsetof(ObjectElements, length)) - int(sizeof(ObjectElements));
     }
 
     static bool ConvertElementsToDoubles(JSContext *cx, uintptr_t elements);
 
+    // This is enough slots to store an object of this class. See the static
+    // assertion below.
     static const size_t VALUES_PER_HEADER = 2;
 };
 
+static_assert(ObjectElements::VALUES_PER_HEADER * sizeof(HeapSlot) == sizeof(ObjectElements),
+              "ObjectElements doesn't fit in the given number of slots");
+
 /* Shared singleton for objects with no elements. */
 extern HeapSlot *const emptyObjectElements;
 
 struct Class;
 class GCMarker;
 struct ObjectOps;
 class Shape;