Bug 1348772 - Optimize Array.prototype.shift to have O(1) perf instead of O(n). r=jonco
authorJan de Mooij <jdemooij@mozilla.com>
Thu, 11 May 2017 17:12:39 +0200
changeset 576331 ecfa2c50a8d8f126b2bf5856c3aebdc7cec3ecc1
parent 576330 fbdfd57233be82bd1d81c75030c84b612b734d89
child 576335 2d5adb9d53a2bc85eb9da1ff27752bf577e94ccc
push id58318
push userdmitchell@mozilla.com
push dateThu, 11 May 2017 16:12:32 +0000
reviewersjonco
bugs1348772
milestone55.0a1
Bug 1348772 - Optimize Array.prototype.shift to have O(1) perf instead of O(n). r=jonco JS code often uses arrays as queues, with a loop to shift() all items, and this resulted in quadratic behavior for us. That kind of code is much faster now.
js/src/gc/Barrier.cpp
js/src/gc/Marking.cpp
js/src/gc/Nursery.cpp
js/src/gc/Nursery.h
js/src/jit-test/tests/basic/shifted-elements1.js
js/src/jit-test/tests/basic/shifted-elements2.js
js/src/jit-test/tests/basic/shifted-elements3.js
js/src/jit-test/tests/basic/shifted-elements4.js
js/src/jit-test/tests/basic/shifted-elements5.js
js/src/jit-test/tests/basic/shifted-elements6.js
js/src/jit/CodeGenerator.cpp
js/src/jit/VMFunctions.cpp
js/src/jsarray.cpp
js/src/jsgc.cpp
js/src/jsobj.cpp
js/src/jsobjinlines.h
js/src/vm/NativeObject-inl.h
js/src/vm/NativeObject.cpp
js/src/vm/NativeObject.h
--- a/js/src/gc/Barrier.cpp
+++ b/js/src/gc/Barrier.cpp
@@ -42,29 +42,36 @@ IsMarkedBlack(JSObject* obj)
         return true;
 
     return false;
 }
 
 bool
 HeapSlot::preconditionForSet(NativeObject* owner, Kind kind, uint32_t slot) const
 {
-    return kind == Slot
-         ? &owner->getSlotRef(slot) == this
-         : &owner->getDenseElement(slot) == (const Value*)this;
+    if (kind == Slot)
+        return &owner->getSlotRef(slot) == this;
+
+    uint32_t numShifted = owner->getElementsHeader()->numShiftedElements();
+    MOZ_ASSERT(slot >= numShifted);
+    return &owner->getDenseElement(slot - numShifted) == (const Value*)this;
 }
 
 void
 HeapSlot::assertPreconditionForWriteBarrierPost(NativeObject* obj, Kind kind, uint32_t slot,
                                                 const Value& target) const
 {
-    if (kind == Slot)
+    if (kind == Slot) {
         MOZ_ASSERT(obj->getSlotAddressUnchecked(slot)->get() == target);
-    else
-        MOZ_ASSERT(static_cast<HeapSlot*>(obj->getDenseElements() + slot)->get() == target);
+    } else {
+        uint32_t numShifted = obj->getElementsHeader()->numShiftedElements();
+        MOZ_ASSERT(slot >= numShifted);
+        MOZ_ASSERT(static_cast<HeapSlot*>(obj->getDenseElements() + (slot - numShifted))->get() ==
+                   target);
+    }
 
     CheckEdgeIsNotBlackToGray(obj, target);
 }
 
 bool
 CurrentThreadIsIonCompiling()
 {
     return TlsContext.get()->ionCompiling;
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -1818,17 +1818,20 @@ GCMarker::saveValueRanges()
             NativeObject* obj = &array.ptr.asValueArrayObject()->as<NativeObject>();
             MOZ_ASSERT(obj->isNative());
 
             uintptr_t index;
             HeapSlot::Kind kind;
             HeapSlot* vp = obj->getDenseElementsAllowCopyOnWrite();
             if (array.end == vp + obj->getDenseInitializedLength()) {
                 MOZ_ASSERT(array.start >= vp);
-                index = array.start - vp;
+                // Add the number of shifted elements here (and subtract in
+                // restoreValueArray) to ensure shift() calls on the array
+                // are handled correctly.
+                index = obj->unshiftedIndex(array.start - vp);
                 kind = HeapSlot::Element;
             } else {
                 HeapSlot* vp = obj->fixedSlots();
                 unsigned nfixed = obj->numFixedSlots();
                 if (array.start == array.end) {
                     index = obj->slotSpan();
                 } else if (array.start >= vp && array.start < vp + nfixed) {
                     MOZ_ASSERT(array.end == vp + Min(nfixed, obj->slotSpan()));
@@ -1860,16 +1863,21 @@ GCMarker::restoreValueArray(const MarkSt
     NativeObject* obj = &objArg->as<NativeObject>();
 
     uintptr_t start = array.index;
     if (array.kind == HeapSlot::Element) {
         if (!obj->is<ArrayObject>())
             return false;
 
         uint32_t initlen = obj->getDenseInitializedLength();
+
+        // Account for shifted elements.
+        uint32_t numShifted = obj->getElementsHeader()->numShiftedElements();
+        start = (numShifted < start) ? start - numShifted : 0;
+
         HeapSlot* vp = obj->getDenseElementsAllowCopyOnWrite();
         if (start < initlen) {
             *vpp = vp + start;
             *endp = vp + initlen;
         } else {
             /* The object shrunk, in which case no scanning is needed. */
             *vpp = *endp = vp;
         }
@@ -2684,18 +2692,21 @@ js::gc::StoreBuffer::SlotsEdge::trace(Te
     if (!obj->isNative())
         return;
 
     if (IsInsideNursery(obj))
         return;
 
     if (kind() == ElementKind) {
         int32_t initLen = obj->getDenseInitializedLength();
-        int32_t clampedStart = Min(start_, initLen);
-        int32_t clampedEnd = Min(start_ + count_, initLen);
+        int32_t numShifted = obj->getElementsHeader()->numShiftedElements();
+        int32_t clampedStart = Min(Max(0, start_ - numShifted), initLen);
+        int32_t clampedEnd = Min(Max(0, start_ + count_ - numShifted), initLen);
+        MOZ_ASSERT(clampedStart >= 0);
+        MOZ_ASSERT(clampedStart <= clampedEnd);
         mover.traceSlots(static_cast<HeapSlot*>(obj->getDenseElements() + clampedStart)
                             ->unsafeUnbarrieredForTracing(), clampedEnd - clampedStart);
     } else {
         int32_t start = Min(uint32_t(start_), obj->slotSpan());
         int32_t end = Min(uint32_t(start_) + count_, obj->slotSpan());
         MOZ_ASSERT(end >= start);
         mover.traceObjectSlots(obj, start, end - start);
     }
@@ -3009,52 +3020,58 @@ js::TenuringTracer::moveSlotsToTenured(N
 }
 
 size_t
 js::TenuringTracer::moveElementsToTenured(NativeObject* dst, NativeObject* src, AllocKind dstKind)
 {
     if (src->hasEmptyElements() || src->denseElementsAreCopyOnWrite())
         return 0;
 
-    Zone* zone = src->zone();
-    ObjectElements* srcHeader = src->getElementsHeader();
-    ObjectElements* dstHeader;
+    void* srcAllocatedHeader = src->getUnshiftedElementsHeader();
 
     /* TODO Bug 874151: Prefer to put element data inline if we have space. */
-    if (!nursery().isInside(srcHeader)) {
+    if (!nursery().isInside(srcAllocatedHeader)) {
         MOZ_ASSERT(src->elements_ == dst->elements_);
-        nursery().removeMallocedBuffer(srcHeader);
+        nursery().removeMallocedBuffer(srcAllocatedHeader);
         return 0;
     }
 
-    size_t nslots = ObjectElements::VALUES_PER_HEADER + srcHeader->capacity;
+    ObjectElements* srcHeader = src->getElementsHeader();
+
+    // Shifted elements are copied too.
+    uint32_t numShifted = srcHeader->numShiftedElements();
+    size_t nslots = srcHeader->numAllocatedElements();
 
     /* Unlike other objects, Arrays can have fixed elements. */
     if (src->is<ArrayObject>() && nslots <= GetGCKindSlots(dstKind)) {
         dst->as<ArrayObject>().setFixedElements();
-        dstHeader = dst->as<ArrayObject>().getElementsHeader();
-        js_memcpy(dstHeader, srcHeader, nslots * sizeof(HeapSlot));
-        nursery().setElementsForwardingPointer(srcHeader, dstHeader, nslots);
+        js_memcpy(dst->getElementsHeader(), srcAllocatedHeader, nslots * sizeof(HeapSlot));
+        dst->elements_ += numShifted;
+        nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
+                                               srcHeader->capacity);
         return nslots * sizeof(HeapSlot);
     }
 
     MOZ_ASSERT(nslots >= 2);
 
+    Zone* zone = src->zone();
+    ObjectElements* dstHeader;
     {
         AutoEnterOOMUnsafeRegion oomUnsafe;
         dstHeader = reinterpret_cast<ObjectElements*>(zone->pod_malloc<HeapSlot>(nslots));
         if (!dstHeader) {
             oomUnsafe.crash(sizeof(HeapSlot) * nslots,
                             "Failed to allocate elements while tenuring.");
         }
     }
 
-    js_memcpy(dstHeader, srcHeader, nslots * sizeof(HeapSlot));
-    nursery().setElementsForwardingPointer(srcHeader, dstHeader, nslots);
-    dst->elements_ = dstHeader->elements();
+    js_memcpy(dstHeader, srcAllocatedHeader, nslots * sizeof(HeapSlot));
+    dst->elements_ = dstHeader->elements() + numShifted;
+    nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
+                                           srcHeader->capacity);
     return nslots * sizeof(HeapSlot);
 }
 
 
 /*** IsMarked / IsAboutToBeFinalized **************************************************************/
 
 template <typename T>
 static inline void
--- a/js/src/gc/Nursery.cpp
+++ b/js/src/gc/Nursery.cpp
@@ -435,21 +435,21 @@ Nursery::setSlotsForwardingPointer(HeapS
     // Slot arrays always have enough space for a forwarding pointer, since the
     // number of slots is never zero.
     MOZ_ASSERT(nslots > 0);
     setForwardingPointer(oldSlots, newSlots, /* direct = */ true);
 }
 
 void
 Nursery::setElementsForwardingPointer(ObjectElements* oldHeader, ObjectElements* newHeader,
-                                      uint32_t nelems)
+                                      uint32_t capacity)
 {
     // Only use a direct forwarding pointer if there is enough space for one.
     setForwardingPointer(oldHeader->elements(), newHeader->elements(),
-                         nelems > ObjectElements::VALUES_PER_HEADER);
+                         capacity > 0);
 }
 
 #ifdef DEBUG
 static bool IsWriteableAddress(void* ptr)
 {
     volatile uint64_t* vPtr = reinterpret_cast<volatile uint64_t*>(ptr);
     *vPtr = *vPtr;
     return true;
--- a/js/src/gc/Nursery.h
+++ b/js/src/gc/Nursery.h
@@ -454,17 +454,17 @@ class Nursery
      */
     void collectToFixedPoint(TenuringTracer& trc, gc::TenureCountCache& tenureCounts);
 
     /* Handle relocation of slots/elements pointers stored in Ion frames. */
     void setForwardingPointer(void* oldData, void* newData, bool direct);
 
     void setSlotsForwardingPointer(HeapSlot* oldSlots, HeapSlot* newSlots, uint32_t nslots);
     void setElementsForwardingPointer(ObjectElements* oldHeader, ObjectElements* newHeader,
-                                      uint32_t nelems);
+                                      uint32_t capacity);
 
     /* Free malloced pointers owned by freed things in the nursery. */
     void freeMallocedBuffers();
 
     /*
      * Frees all non-live nursery-allocated things at the end of a minor
      * collection.
      */
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements1.js
@@ -0,0 +1,14 @@
+function f() {
+    var arr = [];
+    var iters = 1500;
+    for (var i = 0; i < iters; i++) {
+        arr.push(i);
+        if (i % 2 === 0)
+            assertEq(arr.shift(), i / 2);
+    }
+    assertEq(arr.length, iters / 2);
+    for (var i = iters / 2; i < iters; i++)
+        assertEq(arr.shift(), i);
+    assertEq(arr.length, 0);
+}
+f();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements2.js
@@ -0,0 +1,22 @@
+// Always use the per-element barrier.
+gczeal(12);
+
+function f() {
+    var arr = [];
+    for (var i = 0; i < 1000; i++)
+        arr.push(i);
+    gc(); // Ensure arr is tenured.
+
+    // Now store a nursery object somewhere in the array, shift elements,
+    // trigger a GC, and check the post barrier kept the object alive.
+    for (var i = 0; i < 20; i++)
+        arr.shift();
+    for (var i = 0; i < 40; i++)
+        arr[900] = {x: i};
+    for (var i = 0; i < 10; i++)
+        arr.shift();
+    gc();
+
+    assertEq(arr[890].x, 39);
+}
+f();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements3.js
@@ -0,0 +1,23 @@
+// Always use the per-element barrier.
+gczeal(12);
+
+function f() {
+    var arr = [];
+    for (var i = 0; i < 1000; i++)
+        arr.push(i);
+    gc(); // Ensure arr is tenured.
+
+    for (var i = 0; i < 10; i++)
+        arr.shift();
+
+    // Add a nursery object, shift all elements, and trigger a GC to ensure
+    // the post barrier doesn't misbehave.
+    for (var j = 0; j < 40; j++)
+        arr[500] = {x: j};
+    while (arr.length > 0)
+        arr.shift();
+
+    gc();
+    return arr;
+}
+f();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements4.js
@@ -0,0 +1,11 @@
+function f() {
+    var arr = [];
+    for (var i = 0; i < 2; i++) {
+	for (var j = 0; j < 90000; j++)
+	    arr.push(j);
+	for (var j = 0; j < 90000; j++)
+	    assertEq(arr.shift(), j);
+	assertEq(arr.length, 0);
+    }
+}
+f();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements5.js
@@ -0,0 +1,39 @@
+function testFreeze() {
+    var arr = [];
+    for (var i = 0; i < 20; i++)
+        arr.push(i);
+    for (var i = 0; i < 10; i++)
+        arr.shift();
+    Object.freeze(arr);
+    assertEq(arr.length, 10);
+    arr[0] = -1;
+    assertEq(arr[0], 10);
+}
+testFreeze();
+testFreeze();
+
+function testCopyOnWrite() {
+    var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
+    for (var i = 0; i < 5; i++)
+        assertEq(arr.shift(), i + 1);
+    assertEq(arr.toString(), "6,7,8,9");
+}
+testCopyOnWrite();
+testCopyOnWrite();
+
+function testNonWritableLength() {
+    var arr = [];
+    for (var i = 0; i < 20; i++)
+        arr.push(i);
+    Object.defineProperty(arr, "length", {writable: false, value: arr.length});
+    var ex;
+    try {
+        arr.shift();
+    } catch(e) {
+        ex = e;
+    }
+    assertEq(ex instanceof TypeError, true);
+    assertEq(arr.length, 20);
+}
+testNonWritableLength();
+testNonWritableLength();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/shifted-elements6.js
@@ -0,0 +1,17 @@
+// Test incremental GC slices and shifted elements.
+function f() {
+    var arr = [];
+    for (var i = 0; i < 1000; i++)
+        arr.push({x: i});
+    var arr2 = [];
+    for (var i = 0; i < 1000; i++) {
+        gcslice(900);
+        var o = arr.shift();
+        assertEq(o.x, i);
+        arr2.push(o);
+    }
+    gc();
+    for (var i = 0; i < 1000; i++)
+        assertEq(arr2[i].x, i);
+}
+f();
--- a/js/src/jit/CodeGenerator.cpp
+++ b/js/src/jit/CodeGenerator.cpp
@@ -8949,40 +8949,46 @@ CodeGenerator::emitArrayPopShift(LInstru
     if (mir->unboxedType() == JSVAL_TYPE_MAGIC) {
         // Handle the failure case when the array length is non-writable in the
         // OOL path.  (Unlike in the adding-an-element cases, we can't rely on the
         // capacity <= length invariant for such arrays to avoid an explicit
         // check.)
         Address elementFlags(elementsTemp, ObjectElements::offsetOfFlags());
         Imm32 bit(ObjectElements::NONWRITABLE_ARRAY_LENGTH);
         masm.branchTest32(Assembler::NonZero, elementFlags, bit, ool->entry());
-
+    }
+
+    if (mir->mode() == MArrayPopShift::Shift) {
+        // Don't save the elementsTemp register.
+        LiveRegisterSet temps;
+        temps.add(elementsTemp);
+
+        saveVolatile(temps);
+        masm.setupUnalignedABICall(elementsTemp);
+        masm.passABIArg(obj);
+        masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, js::ArrayShiftMoveElements));
+        restoreVolatile(temps);
+
+        if (mir->unboxedType() == JSVAL_TYPE_MAGIC) {
+            // Reload elementsTemp as ArrayShiftMoveElements may have moved it.
+            masm.loadPtr(Address(obj, NativeObject::offsetOfElements()), elementsTemp);
+        }
+    }
+
+    if (mir->unboxedType() == JSVAL_TYPE_MAGIC) {
         // Now adjust length and initializedLength.
         masm.store32(lengthTemp, Address(elementsTemp, ObjectElements::offsetOfLength()));
         masm.store32(lengthTemp, Address(elementsTemp, ObjectElements::offsetOfInitializedLength()));
     } else {
         // Unboxed arrays always have writable lengths. Adjust length and
         // initializedLength.
         masm.store32(lengthTemp, Address(obj, UnboxedArrayObject::offsetOfLength()));
         masm.add32(Imm32(-1), Address(obj, UnboxedArrayObject::offsetOfCapacityIndexAndInitializedLength()));
     }
 
-    if (mir->mode() == MArrayPopShift::Shift) {
-        // Don't save the temp registers.
-        LiveRegisterSet temps;
-        temps.add(elementsTemp);
-        temps.add(lengthTemp);
-
-        saveVolatile(temps);
-        masm.setupUnalignedABICall(lengthTemp);
-        masm.passABIArg(obj);
-        masm.callWithABI(JS_FUNC_TO_DATA_PTR(void*, js::ArrayShiftMoveElements));
-        restoreVolatile(temps);
-    }
-
     masm.bind(&done);
     masm.bind(ool->rejoin());
 }
 
 void
 CodeGenerator::visitArrayPopShiftV(LArrayPopShiftV* lir)
 {
     Register obj = ToRegister(lir->object());
--- a/js/src/jit/VMFunctions.cpp
+++ b/js/src/jit/VMFunctions.cpp
@@ -700,17 +700,19 @@ PostWriteElementBarrier(JSRuntime* rt, J
         return;
 
     if (nobj->getDenseInitializedLength() > MAX_WHOLE_CELL_BUFFER_SIZE
 #ifdef JS_GC_ZEAL
          || rt->hasZealMode(gc::ZealMode::ElementsBarrier)
 #endif
         )
     {
-        rt->gc.storeBuffer().putSlot(nobj, HeapSlot::Element, index, 1);
+        rt->gc.storeBuffer().putSlot(nobj, HeapSlot::Element,
+                                     nobj->unshiftedIndex(index),
+                                     1);
         return;
     }
 
     rt->gc.storeBuffer().putWholeCell(obj);
 }
 
 template void
 PostWriteElementBarrier<IndexInBounds::Yes>(JSRuntime* rt, JSObject* obj, int32_t index);
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -786,16 +786,21 @@ js::ArraySetLength(JSContext* cx, Handle
 
     // Trim the initialized length, if needed, to preserve the <= length
     // invariant.  (Capacity was already reduced during element deletion, if
     // necessary.)
     ObjectElements* header = arr->getElementsHeader();
     header->initializedLength = Min(header->initializedLength, newLen);
 
     if (attrs & JSPROP_READONLY) {
+        if (header->numShiftedElements() > 0) {
+            arr->unshiftElements();
+            header = arr->getElementsHeader();
+        }
+
         header->setNonwritableArrayLength();
 
         // When an array's length becomes non-writable, writes to indexes
         // greater than or equal to the length don't change the array.  We
         // handle this with a check for non-writable length in most places.
         // But in JIT code every check counts -- so we piggyback the check on
         // the already-required range check for |index < capacity| by making
         // capacity of arrays with non-writable length never exceed the length.
@@ -2224,28 +2229,26 @@ js::array_pop(JSContext* cx, unsigned ar
 }
 
 template <JSValueType Type>
 static inline DenseElementResult
 ShiftMoveBoxedOrUnboxedDenseElements(JSObject* obj)
 {
     MOZ_ASSERT(HasBoxedOrUnboxedDenseElements<Type>(obj));
 
-    /*
-     * At this point the length and initialized length have already been
-     * decremented and the result fetched, so just shift the array elements
-     * themselves.
-     */
     size_t initlen = GetBoxedOrUnboxedInitializedLength<Type>(obj);
+    MOZ_ASSERT(initlen > 0);
+
     if (Type == JSVAL_TYPE_MAGIC) {
-        obj->as<NativeObject>().moveDenseElementsNoPreBarrier(0, 1, initlen);
+        if (!obj->as<NativeObject>().tryShiftDenseElements(1))
+            obj->as<NativeObject>().moveDenseElementsNoPreBarrier(0, 1, initlen - 1);
     } else {
         uint8_t* data = obj->as<UnboxedArrayObject>().elements();
         size_t elementSize = UnboxedTypeSize(Type);
-        memmove(data, data + elementSize, initlen * elementSize);
+        memmove(data, data + elementSize, (initlen - 1) * elementSize);
     }
 
     return DenseElementResult::Success;
 }
 
 DefineBoxedOrUnboxedFunctor1(ShiftMoveBoxedOrUnboxedDenseElements, JSObject*);
 
 void
@@ -2270,16 +2273,21 @@ ArrayShiftDenseKernel(JSContext* cx, Han
     size_t initlen = GetBoxedOrUnboxedInitializedLength<Type>(obj);
     if (initlen == 0)
         return DenseElementResult::Incomplete;
 
     rval.set(GetBoxedOrUnboxedDenseElement<Type>(obj, 0));
     if (rval.isMagic(JS_ELEMENTS_HOLE))
         rval.setUndefined();
 
+    if (Type == JSVAL_TYPE_MAGIC) {
+        if (obj->as<NativeObject>().tryShiftDenseElements(1))
+            return DenseElementResult::Success;
+    }
+
     DenseElementResult result = MoveBoxedOrUnboxedDenseElements<Type>(cx, obj, 0, 1, initlen - 1);
     if (result != DenseElementResult::Success)
         return result;
 
     SetBoxedOrUnboxedInitializedLength<Type>(cx, obj, initlen - 1);
     return DenseElementResult::Success;
 }
 
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -1966,18 +1966,20 @@ RelocateCell(Zone* zone, TenuredCell* sr
         JSObject* srcObj = static_cast<JSObject*>(static_cast<Cell*>(src));
         JSObject* dstObj = static_cast<JSObject*>(static_cast<Cell*>(dst));
 
         if (srcObj->isNative()) {
             NativeObject* srcNative = &srcObj->as<NativeObject>();
             NativeObject* dstNative = &dstObj->as<NativeObject>();
 
             // Fixup the pointer to inline object elements if necessary.
-            if (srcNative->hasFixedElements())
-                dstNative->setFixedElements();
+            if (srcNative->hasFixedElements()) {
+                uint32_t numShifted = srcNative->getElementsHeader()->numShiftedElements();
+                dstNative->setFixedElements(numShifted);
+            }
 
             // For copy-on-write objects that own their elements, fix up the
             // owner pointer to point to the relocated object.
             if (srcNative->denseElementsAreCopyOnWrite()) {
                 GCPtrNativeObject& owner = dstNative->getElementsHeader()->ownerObject();
                 if (owner == srcNative)
                     owner = dstNative;
             }
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -537,16 +537,18 @@ js::SetIntegrityLevel(JSContext* cx, Han
         //
         // ArraySetLength also implements the capacity <= length invariant for
         // arrays with non-writable length.  We don't need to do anything special
         // for that, because capacity was zeroed out by preventExtensions.  (See
         // the assertion about getDenseCapacity above.)
         if (level == IntegrityLevel::Frozen && obj->is<ArrayObject>()) {
             if (!obj->as<ArrayObject>().maybeCopyElementsForWrite(cx))
                 return false;
+            if (nobj->getElementsHeader()->numShiftedElements() > 0)
+                nobj->unshiftElements();
             obj->as<ArrayObject>().getElementsHeader()->setNonwritableArrayLength();
         }
     } else {
         RootedId id(cx);
         Rooted<PropertyDescriptor> desc(cx);
 
         const unsigned AllowConfigure = JSPROP_IGNORE_ENUMERATE | JSPROP_IGNORE_READONLY |
                                         JSPROP_IGNORE_VALUE;
@@ -3876,18 +3878,20 @@ JSObject::allocKindForTenure(const js::N
 void
 JSObject::addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf, JS::ClassInfo* info)
 {
     if (is<NativeObject>() && as<NativeObject>().hasDynamicSlots())
         info->objectsMallocHeapSlots += mallocSizeOf(as<NativeObject>().slots_);
 
     if (is<NativeObject>() && as<NativeObject>().hasDynamicElements()) {
         js::ObjectElements* elements = as<NativeObject>().getElementsHeader();
-        if (!elements->isCopyOnWrite() || elements->ownerObject() == this)
-            info->objectsMallocHeapElementsNormal += mallocSizeOf(elements);
+        if (!elements->isCopyOnWrite() || elements->ownerObject() == this) {
+            void* allocatedElements = as<NativeObject>().getUnshiftedElementsHeader();
+            info->objectsMallocHeapElementsNormal += mallocSizeOf(allocatedElements);
+        }
     }
 
     // Other things may be measured in the future if DMD indicates it is worthwhile.
     if (is<JSFunction>() ||
         is<PlainObject>() ||
         is<ArrayObject>() ||
         is<CallObject>() ||
         is<RegExpObject>() ||
@@ -3942,17 +3946,17 @@ JSObject::sizeOfIncludingThisInNursery()
         const NativeObject& native = as<NativeObject>();
 
         size += native.numFixedSlots() * sizeof(Value);
         size += native.numDynamicSlots() * sizeof(Value);
 
         if (native.hasDynamicElements()) {
             js::ObjectElements& elements = *native.getElementsHeader();
             if (!elements.isCopyOnWrite() || elements.ownerObject() == this)
-                size += elements.capacity * sizeof(HeapSlot);
+                size += (elements.capacity + elements.numShiftedElements()) * sizeof(HeapSlot);
         }
 
         if (is<ArgumentsObject>())
             size += as<ArgumentsObject>().sizeOfData();
     }
 
     return size;
 }
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -94,20 +94,21 @@ JSObject::finalize(js::FreeOp* fop)
 
     if (nobj->hasDynamicElements()) {
         js::ObjectElements* elements = nobj->getElementsHeader();
         if (elements->isCopyOnWrite()) {
             if (elements->ownerObject() == this) {
                 // Don't free the elements until object finalization finishes,
                 // so that other objects can access these elements while they
                 // are themselves finalized.
+                MOZ_ASSERT(elements->numShiftedElements() == 0);
                 fop->freeLater(elements);
             }
         } else {
-            fop->free_(elements);
+            fop->free_(nobj->getUnshiftedElementsHeader());
         }
     }
 
     nobj->sweepDictionaryListPointer();
 }
 
 MOZ_ALWAYS_INLINE void
 js::NativeObject::sweepDictionaryListPointer()
--- a/js/src/vm/NativeObject-inl.h
+++ b/js/src/vm/NativeObject-inl.h
@@ -119,35 +119,40 @@ NativeObject::markDenseElementsNotPacked
 
 inline void
 NativeObject::elementsRangeWriteBarrierPost(uint32_t start, uint32_t count)
 {
     for (size_t i = 0; i < count; i++) {
         const Value& v = elements_[start + i];
         if (v.isObject() && IsInsideNursery(&v.toObject())) {
             zone()->group()->storeBuffer().putSlot(this, HeapSlot::Element,
-                                                   start + i, count - i);
+                                                   unshiftedIndex(start + i),
+                                                   count - i);
             return;
         }
     }
 }
 
 inline void
 NativeObject::copyDenseElements(uint32_t dstStart, const Value* src, uint32_t count)
 {
     MOZ_ASSERT(dstStart + count <= getDenseCapacity());
     MOZ_ASSERT(!denseElementsAreCopyOnWrite());
     MOZ_ASSERT(!denseElementsAreFrozen());
 #ifdef DEBUG
     for (uint32_t i = 0; i < count; ++i)
         checkStoredValue(src[i]);
 #endif
     if (JS::shadow::Zone::asShadowZone(zone())->needsIncrementalBarrier()) {
-        for (uint32_t i = 0; i < count; ++i)
-            elements_[dstStart + i].set(this, HeapSlot::Element, dstStart + i, src[i]);
+        uint32_t numShifted = getElementsHeader()->numShiftedElements();
+        for (uint32_t i = 0; i < count; ++i) {
+            elements_[dstStart + i].set(this, HeapSlot::Element,
+                                        dstStart + i + numShifted,
+                                        src[i]);
+        }
     } else {
         memcpy(&elements_[dstStart], src, count * sizeof(HeapSlot));
         elementsRangeWriteBarrierPost(dstStart, count);
     }
 }
 
 inline void
 NativeObject::initDenseElements(uint32_t dstStart, const Value* src, uint32_t count)
@@ -158,16 +163,46 @@ NativeObject::initDenseElements(uint32_t
 #ifdef DEBUG
     for (uint32_t i = 0; i < count; ++i)
         checkStoredValue(src[i]);
 #endif
     memcpy(&elements_[dstStart], src, count * sizeof(HeapSlot));
     elementsRangeWriteBarrierPost(dstStart, count);
 }
 
+inline bool
+NativeObject::tryShiftDenseElements(uint32_t count)
+{
+    ObjectElements* header = getElementsHeader();
+    if (header->isCopyOnWrite() ||
+        header->isFrozen() ||
+        header->hasNonwritableArrayLength() ||
+        header->initializedLength == count)
+    {
+        return false;
+    }
+
+    MOZ_ASSERT(count > 0);
+    MOZ_ASSERT(count < header->initializedLength);
+    MOZ_ASSERT(count <= ObjectElements::MaxShiftedElements);
+
+    if (MOZ_UNLIKELY(header->numShiftedElements() + count > ObjectElements::MaxShiftedElements)) {
+        unshiftElements();
+        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());
     MOZ_ASSERT(!denseElementsAreFrozen());
 
@@ -179,26 +214,27 @@ NativeObject::moveDenseElements(uint32_t
      * 2. JS code moves slots 1..2 into slots 0..1, so it contains [B, C, C].
      * 3. Incremental GC finishes by marking slots 1 and 2 (i.e., C).
      *
      * Since normal marking never happens on B, it is very important that the
      * write barrier is invoked here on B, despite the fact that it exists in
      * the array before and after the move.
      */
     if (JS::shadow::Zone::asShadowZone(zone())->needsIncrementalBarrier()) {
+        uint32_t numShifted = getElementsHeader()->numShiftedElements();
         if (dstStart < srcStart) {
             HeapSlot* dst = elements_ + dstStart;
             HeapSlot* src = elements_ + srcStart;
             for (uint32_t i = 0; i < count; i++, dst++, src++)
-                dst->set(this, HeapSlot::Element, dst - elements_, *src);
+                dst->set(this, HeapSlot::Element, dst - elements_ + numShifted, *src);
         } else {
             HeapSlot* dst = elements_ + dstStart + count - 1;
             HeapSlot* src = elements_ + srcStart + count - 1;
             for (uint32_t i = 0; i < count; i++, dst--, src--)
-                dst->set(this, HeapSlot::Element, dst - elements_, *src);
+                dst->set(this, HeapSlot::Element, dst - elements_ + numShifted, *src);
         }
     } else {
         memmove(elements_ + dstStart, elements_ + srcStart, count * sizeof(HeapSlot));
         elementsRangeWriteBarrierPost(dstStart, count);
     }
 }
 
 inline void
@@ -226,22 +262,23 @@ NativeObject::ensureDenseInitializedLeng
      * Ensure that the array's contents have been initialized up to index, and
      * mark the elements through 'index + extra' as initialized in preparation
      * for a write.
      */
     MOZ_ASSERT(index + extra <= getDenseCapacity());
     uint32_t& initlen = getElementsHeader()->initializedLength;
 
     if (initlen < index + extra) {
+        uint32_t numShifted = getElementsHeader()->numShiftedElements();
         size_t offset = initlen;
         for (HeapSlot* sp = elements_ + initlen;
              sp != elements_ + (index + extra);
              sp++, offset++)
         {
-            sp->init(this, HeapSlot::Element, offset, MagicValue(JS_ELEMENTS_HOLE));
+            sp->init(this, HeapSlot::Element, offset + numShifted, MagicValue(JS_ELEMENTS_HOLE));
         }
         initlen = index + extra;
     }
 }
 
 inline void
 NativeObject::ensureDenseInitializedLength(JSContext* cx, uint32_t index, uint32_t extra)
 {
--- a/js/src/vm/NativeObject.cpp
+++ b/js/src/vm/NativeObject.cpp
@@ -3,16 +3,17 @@
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "vm/NativeObject-inl.h"
 
 #include "mozilla/ArrayUtils.h"
 #include "mozilla/Casting.h"
+#include "mozilla/CheckedInt.h"
 
 #include "jswatchpoint.h"
 
 #include "gc/Marking.h"
 #include "js/Value.h"
 #include "vm/Debugger.h"
 #include "vm/TypedArrayObject.h"
 
@@ -23,16 +24,17 @@
 #include "vm/EnvironmentObject-inl.h"
 #include "vm/Shape-inl.h"
 
 using namespace js;
 
 using JS::AutoCheckCannotGC;
 using JS::GenericNaN;
 using mozilla::ArrayLength;
+using mozilla::CheckedInt;
 using mozilla::DebugOnly;
 using mozilla::PodCopy;
 using mozilla::RoundUpPow2;
 
 static const ObjectElements emptyElementsHeader(0, 0);
 
 /* Objects with no elements share one empty set of elements. */
 HeapSlot* const js::emptyObjectElements =
@@ -107,16 +109,19 @@ ObjectElements::MakeElementsCopyOnWrite(
 ObjectElements::FreezeElements(JSContext* cx, HandleNativeObject obj)
 {
     if (!obj->maybeCopyElementsForWrite(cx))
         return false;
 
     if (obj->hasEmptyElements())
         return true;
 
+    if (obj->getElementsHeader()->numShiftedElements() > 0)
+        obj->unshiftElements();
+
     ObjectElements* header = obj->getElementsHeader();
 
     // Note: this method doesn't update type information to indicate that the
     // elements might be frozen. Handling this is left to the caller.
     header->freeze();
 
     return true;
 }
@@ -324,17 +329,17 @@ NativeObject::setLastPropertyMakeNonNati
 {
     MOZ_ASSERT(!inDictionaryMode());
     MOZ_ASSERT(!shape->getObjectClass()->isNative());
     MOZ_ASSERT(shape->zone() == zone());
     MOZ_ASSERT(shape->slotSpan() == 0);
     MOZ_ASSERT(shape->numFixedSlots() == 0);
 
     if (hasDynamicElements())
-        js_free(getElementsHeader());
+        js_free(getUnshiftedElementsHeader());
     if (hasDynamicSlots()) {
         js_free(slots_);
         slots_ = nullptr;
     }
 
     shape_ = shape;
 }
 
@@ -696,16 +701,59 @@ NativeObject::maybeDensifySparseElements
      * to grow the object.
      */
     if (!NativeObject::clearFlag(cx, obj, BaseShape::INDEXED))
         return DenseElementResult::Failure;
 
     return DenseElementResult::Success;
 }
 
+void
+NativeObject::unshiftElements()
+{
+    ObjectElements* header = getElementsHeader();
+    uint32_t numShifted = header->numShiftedElements();
+    MOZ_ASSERT(numShifted > 0);
+
+    uint32_t initLength = header->initializedLength;
+
+    ObjectElements* newHeader = static_cast<ObjectElements*>(getUnshiftedElementsHeader());
+    memmove(newHeader, header, sizeof(ObjectElements));
+
+    newHeader->clearShiftedElements();
+    newHeader->capacity += numShifted;
+    elements_ = newHeader->elements();
+
+    // To move the elements, temporarily update initializedLength to include
+    // both shifted and unshifted elements.
+    newHeader->initializedLength += numShifted;
+
+    // Move the elements. Initialize to |undefined| to ensure pre-barriers
+    // don't see garbage.
+    for (size_t i = 0; i < numShifted; i++)
+        initDenseElement(i, UndefinedValue());
+    moveDenseElements(0, numShifted, initLength);
+
+    // Restore the initialized length. We use setDenseInitializedLength to
+    // make sure prepareElementRangeForOverwrite is called on the shifted
+    // elements.
+    setDenseInitializedLength(initLength);
+}
+
+void
+NativeObject::maybeUnshiftElements()
+{
+    ObjectElements* header = getElementsHeader();
+    MOZ_ASSERT(header->numShiftedElements() > 0);
+
+    // Unshift if less than a third of the allocated space is in use.
+    if (header->capacity < header->numAllocatedElements() / 3)
+        unshiftElements();
+}
+
 // 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:
 //
@@ -794,101 +842,134 @@ bool
 NativeObject::growElements(JSContext* cx, uint32_t reqCapacity)
 {
     MOZ_ASSERT(nonProxyIsExtensible());
     MOZ_ASSERT(canHaveNonEmptyElements());
     MOZ_ASSERT(!denseElementsAreFrozen());
     if (denseElementsAreCopyOnWrite())
         MOZ_CRASH();
 
+    // If there are shifted elements, consider unshifting them first. If we
+    // don't unshift here, the code below will include the shifted elements in
+    // the resize.
+    uint32_t numShifted = getElementsHeader()->numShiftedElements();
+    if (numShifted > 0) {
+        maybeUnshiftElements();
+        if (getDenseCapacity() >= reqCapacity)
+            return true;
+        numShifted = getElementsHeader()->numShiftedElements();
+
+        // Ensure |reqCapacity + numShifted| below won't overflow by forcing an
+        // unshift in that case.
+        CheckedInt<uint32_t> checkedReqCapacity(reqCapacity);
+        checkedReqCapacity += numShifted;
+        if (MOZ_UNLIKELY(!checkedReqCapacity.isValid())) {
+            unshiftElements();
+            numShifted = 0;
+        }
+    }
+
     uint32_t oldCapacity = getDenseCapacity();
     MOZ_ASSERT(oldCapacity < reqCapacity);
 
     uint32_t newAllocated = 0;
     if (is<ArrayObject>() && !as<ArrayObject>().lengthIsWritable()) {
         MOZ_ASSERT(reqCapacity <= as<ArrayObject>().length());
         MOZ_ASSERT(reqCapacity <= MAX_DENSE_ELEMENTS_COUNT);
         // Preserve the |capacity <= length| invariant for arrays with
         // non-writable length.  See also js::ArraySetLength which initially
         // enforces this requirement.
-        newAllocated = reqCapacity + ObjectElements::VALUES_PER_HEADER;
+        newAllocated = reqCapacity + numShifted + ObjectElements::VALUES_PER_HEADER;
     } else {
-        if (!goodElementsAllocationAmount(cx, reqCapacity, getElementsHeader()->length, &newAllocated))
+        if (!goodElementsAllocationAmount(cx, reqCapacity + numShifted,
+                                          getElementsHeader()->length,
+                                          &newAllocated))
+        {
             return false;
+        }
     }
 
-    uint32_t newCapacity = newAllocated - ObjectElements::VALUES_PER_HEADER;
+    uint32_t newCapacity = newAllocated - ObjectElements::VALUES_PER_HEADER - numShifted;
     MOZ_ASSERT(newCapacity > oldCapacity && newCapacity >= reqCapacity);
 
     // If newCapacity exceeds MAX_DENSE_ELEMENTS_COUNT, the array should become
     // sparse.
     MOZ_ASSERT(newCapacity <= MAX_DENSE_ELEMENTS_COUNT);
 
     uint32_t initlen = getDenseInitializedLength();
 
-    HeapSlot* oldHeaderSlots = reinterpret_cast<HeapSlot*>(getElementsHeader());
+    HeapSlot* oldHeaderSlots = reinterpret_cast<HeapSlot*>(getUnshiftedElementsHeader());
     HeapSlot* newHeaderSlots;
     if (hasDynamicElements()) {
         MOZ_ASSERT(oldCapacity <= MAX_DENSE_ELEMENTS_COUNT);
-        uint32_t oldAllocated = oldCapacity + ObjectElements::VALUES_PER_HEADER;
+        uint32_t oldAllocated = oldCapacity + ObjectElements::VALUES_PER_HEADER + numShifted;
 
         newHeaderSlots = ReallocateObjectBuffer<HeapSlot>(cx, this, oldHeaderSlots, oldAllocated, newAllocated);
         if (!newHeaderSlots)
             return false;   // Leave elements at its old size.
     } else {
         newHeaderSlots = AllocateObjectBuffer<HeapSlot>(cx, this, newAllocated);
         if (!newHeaderSlots)
             return false;   // Leave elements at its old size.
-        PodCopy(newHeaderSlots, oldHeaderSlots, ObjectElements::VALUES_PER_HEADER + initlen);
+        PodCopy(newHeaderSlots, oldHeaderSlots,
+                ObjectElements::VALUES_PER_HEADER + initlen + numShifted);
     }
 
     ObjectElements* newheader = reinterpret_cast<ObjectElements*>(newHeaderSlots);
-    newheader->capacity = newCapacity;
-    elements_ = newheader->elements();
+    elements_ = newheader->elements() + numShifted;
+    getElementsHeader()->capacity = newCapacity;
 
     Debug_SetSlotRangeToCrashOnTouch(elements_ + initlen, newCapacity - initlen);
 
     return true;
 }
 
 void
 NativeObject::shrinkElements(JSContext* cx, uint32_t reqCapacity)
 {
-    uint32_t oldCapacity = getDenseCapacity();
-    MOZ_ASSERT(reqCapacity < oldCapacity);
-
     MOZ_ASSERT(canHaveNonEmptyElements());
     if (denseElementsAreCopyOnWrite())
         MOZ_CRASH();
 
     if (!hasDynamicElements())
         return;
 
+    // If we have shifted elements, consider unshifting them.
+    uint32_t numShifted = getElementsHeader()->numShiftedElements();
+    if (numShifted > 0) {
+        maybeUnshiftElements();
+        numShifted = getElementsHeader()->numShiftedElements();
+    }
+
+    uint32_t oldCapacity = getDenseCapacity();
+    MOZ_ASSERT(reqCapacity < oldCapacity);
+
     uint32_t newAllocated = 0;
-    MOZ_ALWAYS_TRUE(goodElementsAllocationAmount(cx, reqCapacity, 0, &newAllocated));
+    MOZ_ALWAYS_TRUE(goodElementsAllocationAmount(cx, reqCapacity + numShifted, 0, &newAllocated));
     MOZ_ASSERT(oldCapacity <= MAX_DENSE_ELEMENTS_COUNT);
-    uint32_t oldAllocated = oldCapacity + ObjectElements::VALUES_PER_HEADER;
+
+    uint32_t oldAllocated = oldCapacity + ObjectElements::VALUES_PER_HEADER + numShifted;
     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;
+    uint32_t newCapacity = newAllocated - ObjectElements::VALUES_PER_HEADER - numShifted;
     MOZ_ASSERT(newCapacity <= MAX_DENSE_ELEMENTS_COUNT);
 
-    HeapSlot* oldHeaderSlots = reinterpret_cast<HeapSlot*>(getElementsHeader());
+    HeapSlot* oldHeaderSlots = reinterpret_cast<HeapSlot*>(getUnshiftedElementsHeader());
     HeapSlot* newHeaderSlots = ReallocateObjectBuffer<HeapSlot>(cx, this, oldHeaderSlots,
                                                                 oldAllocated, newAllocated);
     if (!newHeaderSlots) {
         cx->recoverFromOutOfMemory();
         return;  // Leave elements at its old size.
     }
 
     ObjectElements* newheader = reinterpret_cast<ObjectElements*>(newHeaderSlots);
-    newheader->capacity = newCapacity;
-    elements_ = newheader->elements();
+    elements_ = newheader->elements() + numShifted;
+    getElementsHeader()->capacity = newCapacity;
 }
 
 /* static */ bool
 NativeObject::CopyElementsForWrite(JSContext* cx, NativeObject* obj)
 {
     MOZ_ASSERT(obj->denseElementsAreCopyOnWrite());
     MOZ_ASSERT(!obj->denseElementsAreFrozen());
 
--- a/js/src/vm/NativeObject.h
+++ b/js/src/vm/NativeObject.h
@@ -152,21 +152,38 @@ ArraySetLength(JSContext* cx, Handle<Arr
  * a hole value. However, in such cases we want to keep the initialized length
  * as small as possible: if the object is known to have no hole values below
  * its initialized length, then it is "packed" and can be accessed much faster
  * by JIT code.
  *
  * Elements do not track property creation order, so enumerating the elements
  * of an object does not necessarily visit indexes in the order they were
  * created.
+ *
+ * Shifted elements
+ * ----------------
+ * It's pretty common to use an array as a queue, like this:
+ *
+ *    while (arr.length > 0)
+ *        foo(arr.shift());
+ *
+ * To ensure we don't get quadratic behavior on this, elements can be 'shifted'
+ * in memory. tryShiftDenseElements does this by incrementing elements_ to point
+ * to the next element and moving the ObjectElements header in memory (so it's
+ * stored where the shifted Value used to be).
+ *
+ * Shifted elements can be unshifted when we grow the array, when the array is
+ * frozen (for simplicity, shifted elements are not supported on objects that
+ * are frozen, have copy-on-write elements, or on arrays with non-writable
+ * length).
  */
 class ObjectElements
 {
   public:
-    enum Flags: uint32_t {
+    enum Flags: uint16_t {
         // Integers written to these elements must be converted to doubles.
         CONVERT_DOUBLE_ELEMENTS     = 0x1,
 
         // Present only if these elements correspond to an array with
         // non-writable length; never present for non-arrays.
         NONWRITABLE_ARRAY_LENGTH    = 0x2,
 
         // These elements are shared with another object and must be copied
@@ -182,29 +199,40 @@ class ObjectElements
         // memory.  This is a static property of the TypedArray, set when it
         // is created and never changed.
         SHARED_MEMORY               = 0x8,
 
         // These elements are set to integrity level "frozen".
         FROZEN                      = 0x10,
     };
 
+    // The flags word stores both the flags and the number of shifted elements.
+    // Allow shifting 2047 elements before unshifting.
+    static const size_t NumShiftedElementsBits = 11;
+    static const size_t MaxShiftedElements = (1 << NumShiftedElementsBits) - 1;
+    static const size_t NumShiftedElementsShift = 32 - NumShiftedElementsBits;
+    static const size_t FlagsMask = (1 << NumShiftedElementsShift) - 1;
+    static_assert(MaxShiftedElements == 2047,
+                  "MaxShiftedElements should match the comment");
+
   private:
     friend class ::JSObject;
     friend class ArrayObject;
     friend class NativeObject;
     friend class TenuringTracer;
 
     friend bool js::SetIntegrityLevel(JSContext* cx, HandleObject obj, IntegrityLevel level);
 
     friend bool
     ArraySetLength(JSContext* cx, Handle<ArrayObject*> obj, HandleId id,
                    unsigned attrs, HandleValue value, ObjectOpResult& result);
 
-    /* See Flags enum above. */
+    // The NumShiftedElementsBits high bits of this are used to store the
+    // number of shifted elements, the other bits are available for the flags.
+    // See Flags enum above.
     uint32_t flags;
 
     /*
      * Number of initialized elements. This is <= the capacity, and for arrays
      * is <= the length. Memory for elements above the initialized length is
      * uninitialized, but values between the initialized length and the proper
      * length are conceptually holes.
      */
@@ -237,16 +265,31 @@ class ObjectElements
     bool isCopyOnWrite() const {
         return flags & COPY_ON_WRITE;
     }
     void clearCopyOnWrite() {
         MOZ_ASSERT(isCopyOnWrite());
         flags &= ~COPY_ON_WRITE;
     }
 
+    void addShiftedElements(uint32_t count) {
+        MOZ_ASSERT(count < capacity);
+        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 clearShiftedElements() {
+        flags &= FlagsMask;
+        MOZ_ASSERT(numShiftedElements() == 0);
+    }
+
   public:
     constexpr ObjectElements(uint32_t capacity, uint32_t length)
       : flags(0), initializedLength(0), capacity(capacity), length(length)
     {}
 
     enum class SharedMemory {
         IsShared
     };
@@ -256,17 +299,17 @@ class ObjectElements
     {}
 
     HeapSlot* elements() {
         return reinterpret_cast<HeapSlot*>(uintptr_t(this) + sizeof(ObjectElements));
     }
     const HeapSlot* elements() const {
         return reinterpret_cast<const HeapSlot*>(uintptr_t(this) + sizeof(ObjectElements));
     }
-    static ObjectElements * fromElements(HeapSlot* elems) {
+    static ObjectElements* fromElements(HeapSlot* elems) {
         return reinterpret_cast<ObjectElements*>(uintptr_t(elems) - sizeof(ObjectElements));
     }
 
     bool isSharedMemory() const {
         return flags & SHARED_MEMORY;
     }
 
     GCPtrNativeObject& ownerObject() const {
@@ -306,16 +349,27 @@ class ObjectElements
     }
 
     uint8_t elementAttributes() const {
         if (isFrozen())
             return JSPROP_ENUMERATE | JSPROP_PERMANENT | JSPROP_READONLY;
         return JSPROP_ENUMERATE;
     }
 
+    uint32_t numShiftedElements() const {
+        uint32_t numShifted = flags >> NumShiftedElementsShift;
+        MOZ_ASSERT_IF(numShifted > 0,
+                      !(flags & (NONWRITABLE_ARRAY_LENGTH | FROZEN | COPY_ON_WRITE)));
+        return numShifted;
+    }
+
+    uint32_t numAllocatedElements() const {
+        return VALUES_PER_HEADER + capacity + numShiftedElements();
+    }
+
     // 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");
 
@@ -980,29 +1034,54 @@ class NativeObject : public ShapedObject
 
     static void elementsSizeMustNotOverflow() {
         static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT <= INT32_MAX / sizeof(JS::Value),
                       "every caller of this method require that an element "
                       "count multiplied by sizeof(Value) can't overflow "
                       "uint32_t (and sometimes int32_t ,too)");
     }
 
-    ObjectElements * getElementsHeader() const {
+    ObjectElements* getElementsHeader() const {
         return ObjectElements::fromElements(elements_);
     }
 
+    // Returns a pointer to the first element, including shifted elements.
+    inline HeapSlot* unshiftedElements() const {
+        return elements_ - getElementsHeader()->numShiftedElements();
+    }
+
+    // Like getElementsHeader, but returns a pointer to the unshifted header.
+    // This is mainly useful for free()ing dynamic elements: the pointer
+    // returned here is the one we got from malloc.
+    void* getUnshiftedElementsHeader() const {
+        return ObjectElements::fromElements(unshiftedElements());
+    }
+
+    uint32_t unshiftedIndex(uint32_t index) const {
+        return index + getElementsHeader()->numShiftedElements();
+    }
+
     /* Accessors for elements. */
     bool ensureElements(JSContext* cx, uint32_t capacity) {
         MOZ_ASSERT(!denseElementsAreCopyOnWrite());
         MOZ_ASSERT(!denseElementsAreFrozen());
         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);
+
+    // Unshift all shifted elements so that numShiftedElements is 0.
+    void unshiftElements();
+
+    // If this object has many shifted elements, unshift them.
+    void maybeUnshiftElements();
+
     static bool goodElementsAllocationAmount(JSContext* cx, uint32_t reqAllocated,
                                              uint32_t length, uint32_t* goodAmount);
     bool growElements(JSContext* cx, uint32_t newcap);
     void shrinkElements(JSContext* cx, uint32_t cap);
     void setDynamicElements(ObjectElements* header) {
         MOZ_ASSERT(!hasDynamicElements());
         elements_ = header->elements();
         MOZ_ASSERT(hasDynamicElements());
@@ -1034,17 +1113,17 @@ class NativeObject : public ShapedObject
 
     // Use this function with care.  This is done to allow sparsifying frozen
     // objects, but should only be called in a few places, and should be
     // audited carefully!
     void setDenseElementUnchecked(uint32_t index, const Value& val) {
         MOZ_ASSERT(index < getDenseInitializedLength());
         MOZ_ASSERT(!denseElementsAreCopyOnWrite());
         checkStoredValue(val);
-        elements_[index].set(this, HeapSlot::Element, index, val);
+        elements_[index].set(this, HeapSlot::Element, unshiftedIndex(index), val);
     }
 
   public:
     void setDenseInitializedLength(uint32_t length) {
         MOZ_ASSERT(!denseElementsAreFrozen());
         setDenseInitializedLengthUnchecked(length);
     }
 
@@ -1056,17 +1135,17 @@ class NativeObject : public ShapedObject
         setDenseElementUnchecked(index, val);
     }
 
     void initDenseElement(uint32_t index, const Value& val) {
         MOZ_ASSERT(index < getDenseInitializedLength());
         MOZ_ASSERT(!denseElementsAreCopyOnWrite());
         MOZ_ASSERT(!denseElementsAreFrozen());
         checkStoredValue(val);
-        elements_[index].init(this, HeapSlot::Element, index, val);
+        elements_[index].init(this, HeapSlot::Element, unshiftedIndex(index), val);
     }
 
     void setDenseElementMaybeConvertDouble(uint32_t index, const Value& val) {
         if (val.isInt32() && shouldConvertDoubleElements())
             setDenseElement(index, DoubleValue(val.toInt32()));
         else
             setDenseElement(index, val);
     }
@@ -1151,34 +1230,34 @@ class NativeObject : public ShapedObject
                       "slots will hold the ObjectElements header");
         return &fixedSlots()[2];
     }
 
 #ifdef DEBUG
     bool canHaveNonEmptyElements();
 #endif
 
-    void setFixedElements() {
+    void setFixedElements(uint32_t numShifted = 0) {
         MOZ_ASSERT(canHaveNonEmptyElements());
-        elements_ = fixedElements();
+        elements_ = fixedElements() + numShifted;
     }
 
     inline bool hasDynamicElements() const {
         /*
          * Note: for objects with zero fixed slots this could potentially give
          * a spurious 'true' result, if the end of this object is exactly
          * aligned with the end of its arena and dynamic slots are allocated
          * immediately afterwards. Such cases cannot occur for dense arrays
          * (which have at least two fixed slots) and can only result in a leak.
          */
-        return !hasEmptyElements() && elements_ != fixedElements();
+        return !hasEmptyElements() && !hasFixedElements();
     }
 
     inline bool hasFixedElements() const {
-        return elements_ == fixedElements();
+        return unshiftedElements() == fixedElements();
     }
 
     inline bool hasEmptyElements() const {
         return elements_ == emptyObjectElements || elements_ == emptyObjectElementsShared;
     }
 
     /*
      * Get a pointer to the unused data in the object's allocation immediately