Bug 1364346 part 2 - Rename unshiftElements to moveShiftedElements, tweak heuristics. r=anba
authorJan de Mooij <jdemooij@mozilla.com>
Mon, 05 Jun 2017 11:27:25 +0200
changeset 412794 efd4e852aca2966b88dd625ae31d7970bd4152b0
parent 412793 43383407d7c14ca3f1ee006e2b57ec5fe3ff0d3e
child 412795 0b104ac29e71e240d6f31dbb128dd500ecdfdede
push id1490
push usermtabara@mozilla.com
push dateMon, 31 Jul 2017 14:08:16 +0000
treeherdermozilla-release@70e32e6bf15e [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 2 - Rename unshiftElements to moveShiftedElements, tweak heuristics. r=anba
js/src/vm/ArrayObject.h
js/src/vm/NativeObject-inl.h
js/src/vm/NativeObject.cpp
js/src/vm/NativeObject.h
--- a/js/src/vm/ArrayObject.h
+++ b/js/src/vm/ArrayObject.h
@@ -28,17 +28,17 @@ class ArrayObject : public NativeObject
     }
 
     uint32_t length() const {
         return getElementsHeader()->length;
     }
 
     void setNonWritableLength(JSContext* cx) {
         if (getElementsHeader()->numShiftedElements() > 0)
-            unshiftElements();
+            moveShiftedElements();
 
         // 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.
         ObjectElements* header = getElementsHeader();
--- a/js/src/vm/NativeObject-inl.h
+++ b/js/src/vm/NativeObject-inl.h
@@ -180,17 +180,17 @@ NativeObject::tryShiftDenseElements(uint
     {
         return false;
     }
 
     MOZ_ASSERT(count > 0);
     MOZ_ASSERT(count < header->initializedLength);
 
     if (MOZ_UNLIKELY(header->numShiftedElements() + count > ObjectElements::MaxShiftedElements)) {
-        unshiftElements();
+        moveShiftedElements();
         header = getElementsHeader();
     }
 
     prepareElementRangeForOverwrite(0, count);
     header->addShiftedElements(count);
 
     elements_ += count;
     ObjectElements* newHeader = getElementsHeader();
--- a/js/src/vm/NativeObject.cpp
+++ b/js/src/vm/NativeObject.cpp
@@ -110,17 +110,17 @@ ObjectElements::FreezeElements(JSContext
 {
     if (!obj->maybeCopyElementsForWrite(cx))
         return false;
 
     if (obj->hasEmptyElements())
         return true;
 
     if (obj->getElementsHeader()->numShiftedElements() > 0)
-        obj->unshiftElements();
+        obj->moveShiftedElements();
 
     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;
@@ -702,56 +702,56 @@ NativeObject::maybeDensifySparseElements
      */
     if (!NativeObject::clearFlag(cx, obj, BaseShape::INDEXED))
         return DenseElementResult::Failure;
 
     return DenseElementResult::Success;
 }
 
 void
-NativeObject::unshiftElements()
+NativeObject::moveShiftedElements()
 {
     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.
+    // the shifted 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()
+NativeObject::maybeMoveShiftedElements()
 {
     ObjectElements* header = getElementsHeader();
     MOZ_ASSERT(header->numShiftedElements() > 0);
 
-    // Unshift if less than a third of the allocated space is in use.
+    // Move the elements if less than a third of the allocated space is in use.
     if (header->capacity < header->numAllocatedElements() / 3)
-        unshiftElements();
+        moveShiftedElements();
 }
 
 // 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.)
 //
@@ -842,32 +842,41 @@ 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.
+    // If there are shifted elements, consider moving them first. If we don't
+    // move them here, the code below will include the shifted elements in the
+    // resize.
     uint32_t numShifted = getElementsHeader()->numShiftedElements();
     if (numShifted > 0) {
-        maybeUnshiftElements();
+        // If the number of elements is small, it's cheaper to just move them as
+        // it may avoid a malloc/realloc. Note that there's no technical reason
+        // for using this particular value, but it works well in real-world use
+        // cases.
+        static const size_t MaxElementsToMoveEagerly = 20;
+
+        if (getElementsHeader()->initializedLength <= MaxElementsToMoveEagerly)
+            moveShiftedElements();
+        else
+            maybeMoveShiftedElements();
         if (getDenseCapacity() >= reqCapacity)
             return true;
         numShifted = getElementsHeader()->numShiftedElements();
 
-        // Ensure |reqCapacity + numShifted| below won't overflow by forcing an
-        // unshift in that case.
+        // If |reqCapacity + numShifted| overflows, we just move all shifted
+        // elements to avoid the problem.
         CheckedInt<uint32_t> checkedReqCapacity(reqCapacity);
         checkedReqCapacity += numShifted;
         if (MOZ_UNLIKELY(!checkedReqCapacity.isValid())) {
-            unshiftElements();
+            moveShiftedElements();
             numShifted = 0;
         }
     }
 
     uint32_t oldCapacity = getDenseCapacity();
     MOZ_ASSERT(oldCapacity < reqCapacity);
 
     uint32_t newAllocated = 0;
@@ -927,20 +936,20 @@ NativeObject::shrinkElements(JSContext* 
 {
     MOZ_ASSERT(canHaveNonEmptyElements());
     if (denseElementsAreCopyOnWrite())
         MOZ_CRASH();
 
     if (!hasDynamicElements())
         return;
 
-    // If we have shifted elements, consider unshifting them.
+    // If we have shifted elements, consider moving them.
     uint32_t numShifted = getElementsHeader()->numShiftedElements();
     if (numShifted > 0) {
-        maybeUnshiftElements();
+        maybeMoveShiftedElements();
         numShifted = getElementsHeader()->numShiftedElements();
     }
 
     uint32_t oldCapacity = getDenseCapacity();
     MOZ_ASSERT(reqCapacity < oldCapacity);
 
     uint32_t newAllocated = 0;
     MOZ_ALWAYS_TRUE(goodElementsAllocationAmount(cx, reqCapacity + numShifted, 0, &newAllocated));
--- a/js/src/vm/NativeObject.h
+++ b/js/src/vm/NativeObject.h
@@ -165,17 +165,17 @@ ArraySetLength(JSContext* cx, Handle<Arr
  *    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
+ * Shifted elements can be moved 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: uint16_t {
@@ -200,17 +200,17 @@ class ObjectElements
         // 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.
+    // Allow shifting 2047 elements before actually moving the elements.
     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:
@@ -1069,21 +1069,22 @@ 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);
 
-    // Unshift all shifted elements so that numShiftedElements is 0.
-    void unshiftElements();
+    // 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, unshift them.
-    void maybeUnshiftElements();
+    // If this object has many shifted elements call moveShiftedElements.
+    void maybeMoveShiftedElements();
 
     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();