Bug 1364346 part 3 - Optimize Array.prototype.unshift by taking advantage of shifted elements. r=anba
authorJan de Mooij <jdemooij@mozilla.com>
Tue, 06 Jun 2017 12:16:25 +0200
changeset 410668 84ac08cff36262137054f793700569dd0781541b
parent 410667 2688b23e8e9a09b738450679a172332e4cb532e0
child 410669 ebbe57e667458a96cfde88fd4b9b637f72c7ef6d
push id7391
push usermtabara@mozilla.com
push dateMon, 12 Jun 2017 13:08:53 +0000
treeherdermozilla-beta@2191d7f87e2e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersanba
bugs1364346
milestone55.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 1364346 part 3 - Optimize Array.prototype.unshift by taking advantage of shifted elements. r=anba
js/src/jit-test/tests/basic/shifted-elements7.js
js/src/jsarray.cpp
js/src/vm/NativeObject-inl.h
js/src/vm/NativeObject.cpp
js/src/vm/NativeObject.h
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements7.js
@@ -0,0 +1,47 @@
+function test1() {
+    var a = [];
+    for (var i = 0; i < 100; i++)
+        a.unshift("foo" + i);
+    for (var i = 99; i >= 0; i--) {
+        assertEq(a.shift(), "foo" + i);
+        a.unshift("foo" + (i - 1));
+    }
+    assertEq(a.length, 100);
+}
+test1();
+
+function sum(arr) {
+    var res = 0;
+    for (var i = 0; i < arr.length; i++)
+        res += arr[i];
+    return res;
+}
+function test2() {
+    var a = [];
+    for (var i = 0; i < 200; i++)
+        a.push(i);
+    for (var i = 0; i < 100; i++)
+        a.shift();
+    for (var i = 0; i < 200; i++)
+        a.unshift(i);
+    assertEq(a.length, 300);
+    assertEq(sum(a), 34850);
+}
+test2();
+
+function test3() {
+    var a = [];
+    for (var i = 0; i < 200; i++)
+        a.push(i);
+    var toAdd = [];
+    var step = 1;
+    for (var i = 0; i < 2500; i += step) {
+        for (var j = 0; j < step; j++)
+            toAdd.unshift(i + j);
+        a.unshift(...toAdd);
+        step = Math.max((i / 16)|0, 1);
+    }
+    assertEq(a.length, 41463);
+    assertEq(sum(a), 26657756);
+}
+test3();
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -2499,25 +2499,27 @@ js::array_unshift(JSContext* cx, unsigne
                 break;
             if (ObjectMayHaveExtraIndexedProperties(obj))
                 break;
             if (MaybeInIteration(obj, cx))
                 break;
             NativeObject* nobj = &obj->as<NativeObject>();
             if (nobj->is<ArrayObject>() && !nobj->as<ArrayObject>().lengthIsWritable())
                 break;
-            DenseElementResult result = nobj->ensureDenseElements(cx, uint32_t(length), args.length());
-            if (result != DenseElementResult::Success) {
-                if (result == DenseElementResult::Failure)
-                    return false;
-                MOZ_ASSERT(result == DenseElementResult::Incomplete);
-                break;
+            if (!nobj->tryUnshiftDenseElements(args.length())) {
+                DenseElementResult result = nobj->ensureDenseElements(cx, uint32_t(length), args.length());
+                if (result != DenseElementResult::Success) {
+                    if (result == DenseElementResult::Failure)
+                        return false;
+                    MOZ_ASSERT(result == DenseElementResult::Incomplete);
+                    break;
+                }
+                if (length > 0)
+                    nobj->moveDenseElements(args.length(), 0, uint32_t(length));
             }
-            if (length > 0)
-                nobj->moveDenseElements(args.length(), 0, uint32_t(length));
             for (uint32_t i = 0; i < args.length(); i++)
                 nobj->setDenseElementWithType(cx, i, args[i]);
             optimized = true;
         } while (false);
 
         if (!optimized) {
             if (length > 0) {
                 uint64_t last = length;
--- a/js/src/vm/NativeObject-inl.h
+++ b/js/src/vm/NativeObject-inl.h
@@ -176,31 +176,38 @@ NativeObject::tryShiftDenseElements(uint
         count > ObjectElements::MaxShiftedElements ||
         header->isCopyOnWrite() ||
         header->isFrozen() ||
         header->hasNonwritableArrayLength())
     {
         return false;
     }
 
+    shiftDenseElementsUnchecked(count);
+    return true;
+}
+
+inline void
+NativeObject::shiftDenseElementsUnchecked(uint32_t count)
+{
+    ObjectElements* header = getElementsHeader();
     MOZ_ASSERT(count > 0);
     MOZ_ASSERT(count < header->initializedLength);
 
     if (MOZ_UNLIKELY(header->numShiftedElements() + count > ObjectElements::MaxShiftedElements)) {
         moveShiftedElements();
         header = getElementsHeader();
     }
 
     prepareElementRangeForOverwrite(0, count);
     header->addShiftedElements(count);
 
     elements_ += count;
     ObjectElements* newHeader = getElementsHeader();
     memmove(newHeader, header, sizeof(ObjectElements));
-    return true;
 }
 
 inline void
 NativeObject::moveDenseElements(uint32_t dstStart, uint32_t srcStart, uint32_t count)
 {
     MOZ_ASSERT(dstStart + count <= getDenseCapacity());
     MOZ_ASSERT(srcStart + count <= getDenseInitializedLength());
     MOZ_ASSERT(!denseElementsAreCopyOnWrite());
--- a/js/src/vm/NativeObject.cpp
+++ b/js/src/vm/NativeObject.cpp
@@ -744,16 +744,97 @@ NativeObject::maybeMoveShiftedElements()
     ObjectElements* header = getElementsHeader();
     MOZ_ASSERT(header->numShiftedElements() > 0);
 
     // Move the elements if less than a third of the allocated space is in use.
     if (header->capacity < header->numAllocatedElements() / 3)
         moveShiftedElements();
 }
 
+bool
+NativeObject::tryUnshiftDenseElements(uint32_t count)
+{
+    MOZ_ASSERT(count > 0);
+
+    ObjectElements* header = getElementsHeader();
+    uint32_t numShifted = header->numShiftedElements();
+
+    if (count > numShifted) {
+        // We need more elements than are easily available. Try to make space
+        // for more elements than we need (and shift the remaining ones) so
+        // that unshifting more elements later will be fast.
+
+        // Don't bother reserving elements if the number of elements is small.
+        // Note that there's no technical reason for using this particular
+        // limit.
+        if (header->initializedLength <= 10 ||
+            header->isCopyOnWrite() ||
+            header->isFrozen() ||
+            header->hasNonwritableArrayLength() ||
+            MOZ_UNLIKELY(count > ObjectElements::MaxShiftedElements))
+        {
+            return false;
+        }
+
+        MOZ_ASSERT(header->capacity >= header->initializedLength);
+        uint32_t unusedCapacity = header->capacity - header->initializedLength;
+
+        // Determine toShift, the number of extra elements we want to make
+        // available.
+        uint32_t toShift = count - numShifted;
+        MOZ_ASSERT(toShift <= ObjectElements::MaxShiftedElements,
+                   "count <= MaxShiftedElements so toShift <= MaxShiftedElements");
+
+        // Give up if we need to allocate more elements.
+        if (toShift > unusedCapacity)
+            return false;
+
+        // Move more elements than we need, so that other unshift calls will be
+        // fast. We just have to make sure we don't exceed unusedCapacity.
+        toShift = Min(toShift + unusedCapacity / 2, unusedCapacity);
+
+        // Ensure |numShifted + toShift| does not exceed MaxShiftedElements.
+        if (numShifted + toShift > ObjectElements::MaxShiftedElements)
+            toShift = ObjectElements::MaxShiftedElements - numShifted;
+
+        MOZ_ASSERT(count <= numShifted + toShift);
+        MOZ_ASSERT(numShifted + toShift <= ObjectElements::MaxShiftedElements);
+        MOZ_ASSERT(toShift <= unusedCapacity);
+
+        // Now move/unshift the elements.
+        uint32_t initLen = header->initializedLength;
+        setDenseInitializedLength(initLen + toShift);
+        for (uint32_t i = 0; i < toShift; i++)
+            initDenseElement(initLen + i, UndefinedValue());
+        moveDenseElements(toShift, 0, initLen);
+
+        // Shift the elements we just prepended.
+        shiftDenseElementsUnchecked(toShift);
+
+        // We can now fall-through to the fast path below.
+        header = getElementsHeader();
+        MOZ_ASSERT(header->numShiftedElements() == numShifted + toShift);
+
+        numShifted = header->numShiftedElements();
+        MOZ_ASSERT(count <= numShifted);
+    }
+
+    elements_ -= count;
+    ObjectElements* newHeader = getElementsHeader();
+    memmove(newHeader, header, sizeof(ObjectElements));
+
+    newHeader->unshiftShiftedElements(count);
+
+    // Initialize to |undefined| to ensure pre-barriers don't see garbage.
+    for (uint32_t i = 0; i < count; i++)
+        initDenseElement(i, UndefinedValue());
+
+    return true;
+}
+
 // Given a requested capacity (in elements) and (potentially) the length of an
 // array for which elements are being allocated, compute an actual allocation
 // amount (in elements).  (Allocation amounts include space for an
 // ObjectElements instance, so a return value of |N| implies
 // |N - ObjectElements::VALUES_PER_HEADER| usable elements.)
 //
 // The requested/actual allocation distinction is meant to:
 //
--- a/js/src/vm/NativeObject.h
+++ b/js/src/vm/NativeObject.h
@@ -278,16 +278,26 @@ class ObjectElements
         MOZ_ASSERT(count < initializedLength);
         MOZ_ASSERT(!(flags & (NONWRITABLE_ARRAY_LENGTH | FROZEN | COPY_ON_WRITE)));
         uint32_t numShifted = numShiftedElements() + count;
         MOZ_ASSERT(numShifted <= MaxShiftedElements);
         flags = (numShifted << NumShiftedElementsShift) | (flags & FlagsMask);
         capacity -= count;
         initializedLength -= count;
     }
+    void unshiftShiftedElements(uint32_t count) {
+        MOZ_ASSERT(count > 0);
+        MOZ_ASSERT(!(flags & (NONWRITABLE_ARRAY_LENGTH | FROZEN | COPY_ON_WRITE)));
+        uint32_t numShifted = numShiftedElements();
+        MOZ_ASSERT(count <= numShifted);
+        numShifted -= count;
+        flags = (numShifted << NumShiftedElementsShift) | (flags & FlagsMask);
+        capacity += count;
+        initializedLength += count;
+    }
     void clearShiftedElements() {
         flags &= FlagsMask;
         MOZ_ASSERT(numShiftedElements() == 0);
     }
 
   public:
     constexpr ObjectElements(uint32_t capacity, uint32_t length)
       : flags(0), initializedLength(0), capacity(capacity), length(length)
@@ -950,16 +960,18 @@ class NativeObject : public ShapedObject
      * Trigger the write barrier on a range of slots that will no longer be
      * reachable.
      */
     void prepareSlotRangeForOverwrite(size_t start, size_t end) {
         for (size_t i = start; i < end; i++)
             getSlotAddressUnchecked(i)->HeapSlot::~HeapSlot();
     }
 
+    inline void shiftDenseElementsUnchecked(uint32_t count);
+
   public:
     static bool rollbackProperties(JSContext* cx, HandleNativeObject obj,
                                    uint32_t slotSpan);
 
     inline void setSlotWithType(JSContext* cx, Shape* shape,
                                 const Value& value, bool overwriting = true);
 
     inline const Value& getReservedSlot(uint32_t index) const {
@@ -1069,16 +1081,19 @@ class NativeObject : public ShapedObject
         if (capacity > getDenseCapacity())
             return growElements(cx, capacity);
         return true;
     }
 
     // Try to shift |count| dense elements, see the "Shifted elements" comment.
     inline bool tryShiftDenseElements(uint32_t count);
 
+    // Try to make space for |count| dense elements at the start of the array.
+    bool tryUnshiftDenseElements(uint32_t count);
+
     // Move the elements header and all shifted elements to the start of the
     // allocated elements space, so that numShiftedElements is 0 afterwards.
     void moveShiftedElements();
 
     // If this object has many shifted elements call moveShiftedElements.
     void maybeMoveShiftedElements();
 
     static bool goodElementsAllocationAmount(JSContext* cx, uint32_t reqAllocated,