Bug 1290554: Use stable sort for TypedArraySort when a user comparator is present. r=anba
authorAndré Bargull <andre.bargull@gmail.com>
Wed, 27 Feb 2019 07:03:32 -0800
changeset 519527 603a46a1e921a1fae58fa168461935a42270c1f0
parent 519526 739c3b30b230fe1df1b3b94ae9b6a7df9467f31a
child 519528 e4565e7ddcb07bb6f4bc59623c821445d8e49069
push id10862
push userffxbld-merge
push dateMon, 11 Mar 2019 13:01:11 +0000
treeherdermozilla-beta@a2e7f5c935da [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersanba
bugs1290554
milestone67.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 1290554: Use stable sort for TypedArraySort when a user comparator is present. r=anba
js/src/builtin/Sorting.js
js/src/builtin/TypedArray.js
js/src/tests/non262/TypedArray/sort_compare_nan.js
js/src/tests/non262/TypedArray/sort_sorted.js
js/src/tests/non262/TypedArray/sort_stable.js
--- a/js/src/builtin/Sorting.js
+++ b/js/src/builtin/Sorting.js
@@ -313,16 +313,107 @@ function MergeSort(array, len, comparefn
                 continue;
             Merge(denseList, start, mid, end, lBuffer, rBuffer, comparefn);
         }
     }
     MoveHoles(array, len, denseList, denseLen);
     return array;
 }
 
+// A helper function for MergeSortTypedArray.
+//
+// Merge comparefn-sorted slices list[start..<=mid] and list[mid+1..<=end],
+// storing the merged sequence in out[start..<=end].
+function MergeTypedArray(list, out, start, mid, end, comparefn) {
+    // Skip lopsided runs to avoid doing useless work.
+    // Skip calling the comparator if the sub-list is already sorted.
+    if (mid >= end || comparefn(list[mid], list[mid + 1]) <= 0) {
+        for (var i = start; i <= end; i++) {
+            out[i] = list[i];
+        }
+        return;
+    }
+
+    var i = start;
+    var j = mid + 1;
+    var k = start;
+    while (i <= mid && j <= end) {
+        var lvalue = list[i];
+        var rvalue = list[j];
+        if (comparefn(lvalue, rvalue) <= 0) {
+            out[k++] = lvalue;
+            i++;
+        } else {
+            out[k++] = rvalue;
+            j++;
+        }
+    }
+
+    // Empty out any remaining elements.
+    while (i <= mid) {
+        out[k++] = list[i++];
+    }
+    while (j <= end) {
+        out[k++] = list[j++];
+    }
+}
+
+// Iterative, bottom up, mergesort. Optimized version for TypedArrays.
+function MergeSortTypedArray(array, len, comparefn) {
+    assert(IsPossiblyWrappedTypedArray(array),
+           "MergeSortTypedArray works only with typed arrays.");
+
+    // Insertion sort for small arrays, where "small" is defined by performance
+    // testing.
+    if (len < 8) {
+        InsertionSort(array, 0, len - 1, comparefn);
+        return array;
+    }
+
+    // Use the same TypedArray kind for the buffer.
+    var C = _ConstructorForTypedArray(array);
+
+    // We do all of our allocating up front.
+    var lBuffer = array;
+    var rBuffer = new C(len);
+
+    // Use insertion sort for the initial ranges.
+    var windowSize = 4;
+    for (var start = 0; start < len - 1; start += windowSize) {
+        var end = std_Math_min(start + windowSize - 1, len - 1);
+        InsertionSort(lBuffer, start, end, comparefn);
+    }
+
+    for (; windowSize < len; windowSize = 2 * windowSize) {
+        for (var start = 0; start < len; start += 2 * windowSize) {
+            // The midpoint between the two subarrays.
+            var mid = start + windowSize - 1;
+
+            // To keep from going over the edge.
+            var end = std_Math_min(start + 2 * windowSize - 1, len - 1);
+
+            MergeTypedArray(lBuffer, rBuffer, start, mid, end, comparefn);
+        }
+
+        // Swap both lists.
+        var swap = lBuffer;
+        lBuffer = rBuffer;
+        rBuffer = swap;
+    }
+
+    // Move the sorted elements into the array.
+    if (lBuffer !== array) {
+        for (var i = 0; i < len; i++) {
+            array[i] = lBuffer[i];
+        }
+    }
+
+    return array;
+}
+
 // Rearranges the elements in array[from:to + 1] and returns an index j such that:
 // - from < j < to
 // - each element in array[from:j] is less than or equal to array[j]
 // - each element in array[j + 1:to + 1] greater than or equal to array[j].
 function Partition(array, from, to, comparefn) {
     assert(to - from >= 3, "Partition will not work with less than three elements");
 
     var medianIndex = from + ((to - from) >> 1);
@@ -380,17 +471,16 @@ function QuickSort(array, len, comparefn
             end   = stack[--top];
             start = stack[--top];
         } else {
             pivotIndex = Partition(array, start, end, comparefn);
 
             // Calculate the left and right sub-array lengths and save
             // stack space by directly modifying start/end so that
             // we sort the longest of the two during the next iteration.
-            // This reduces the maximum stack size to log2(len).
             leftLen = (pivotIndex - 1) - start;
             rightLen = end - (pivotIndex + 1);
 
             if (rightLen > leftLen) {
                 stack[top++] = start;
                 stack[top++] = pivotIndex - 1;
                 start = pivotIndex + 1;
             } else {
--- a/js/src/builtin/TypedArray.js
+++ b/js/src/builtin/TypedArray.js
@@ -1183,17 +1183,17 @@ function TypedArrayCompareInt(x, y) {
         return diff;
 
     // Steps 3-5, 8-9 (Not applicable when sorting integer values).
 
     // Step 10.
     return 0;
 }
 
-// ES2018 draft rev 3bbc87cd1b9d3bf64c3e68ca2fe9c5a3f2c304c0
+// ES2019 draft rev 8a16cb8d18660a1106faae693f0f39b9f1a30748
 // 22.2.3.26 %TypedArray%.prototype.sort ( comparefn )
 function TypedArraySort(comparefn) {
     // This function is not generic.
 
     // Step 1.
     if (comparefn !== undefined) {
         if (!IsCallable(comparefn))
             ThrowTypeError(JSMSG_NOT_FUNCTION, DecompileArg(0, comparefn));
@@ -1278,23 +1278,25 @@ function TypedArraySort(comparefn) {
         // It's faster for us to check the typed array's length than to check
         // for detached buffers.
         if (length === 0) {
             assert(PossiblyWrappedTypedArrayHasDetachedBuffer(obj),
                    "Length can only change from non-zero to zero when the buffer was detached");
             ThrowTypeError(JSMSG_TYPED_ARRAY_DETACHED);
         }
 
-        // Step c. is redundant, see:
-        // https://bugzilla.mozilla.org/show_bug.cgi?id=1121937#c36
+        // Step c.
+        if (v !== v)
+            return 0;
+
         // Step d.
         return v;
     };
 
-    return QuickSort(obj, len, wrappedCompareFn);
+    return MergeSortTypedArray(obj, len, wrappedCompareFn);
 }
 
 // ES2017 draft rev f8a9be8ea4bd97237d176907a1e3080dce20c68f
 //   22.2.3.28 %TypedArray%.prototype.toLocaleString ([ reserved1 [ , reserved2 ] ])
 // ES2017 Intl draft rev 78bbe7d1095f5ff3760ac4017ed366026e4cb276
 //   13.4.1 Array.prototype.toLocaleString ([ locales [ , options ]])
 function TypedArrayToLocaleString(locales = undefined, options = undefined) {
     // ValidateTypedArray, then step 1.
new file mode 100644
--- /dev/null
+++ b/js/src/tests/non262/TypedArray/sort_compare_nan.js
@@ -0,0 +1,12 @@
+// Returning zero from the sort comparator...
+let ta = new Int32Array([0, 1]).sort(() => 0);
+assertEq(ta[0], 0);
+assertEq(ta[1], 1);
+
+// ... should give the same result as returning NaN.
+let tb = new Int32Array([0, 1]).sort(() => NaN);
+assertEq(tb[0], 0);
+assertEq(tb[1], 1);
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
new file mode 100644
--- /dev/null
+++ b/js/src/tests/non262/TypedArray/sort_sorted.js
@@ -0,0 +1,30 @@
+function SortedAscending(length) {
+    var array = new Int32Array(length);
+    for (var i = 0; i < length; ++i)
+        array[i] = i + 1;
+
+    array.sort((x, y) => x - y);
+
+    for (var i = 0; i < length; ++i)
+        assertEq(i + 1, array[i], `Mismatch at index=${i}, length=${length}`);
+}
+
+for (var i = 0; i < 256; ++i)
+    SortedAscending(i);
+
+function SortedDescending(length) {
+    var array = new Int32Array(length);
+    for (var i = 0; i < length; ++i)
+        array[i] = length - i;
+
+    array.sort((x, y) => x - y);
+
+    for (var i = 0; i < length; ++i)
+        assertEq(i + 1, array[i], `Mismatch at index=${i}, length=${length}`);
+}
+
+for (var i = 0; i < 256; ++i)
+    SortedDescending(i);
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);
new file mode 100644
--- /dev/null
+++ b/js/src/tests/non262/TypedArray/sort_stable.js
@@ -0,0 +1,23 @@
+// Test with different lengths to cover the case when InsertionSort is resp.
+// is not called.
+for (let i = 2; i <= 10; ++i) {
+    let length = 2 ** i;
+    let ta = new Int8Array(length);
+
+    ta[0] = 2;
+    ta[1] = 1;
+    ta[2] = 0;
+
+    for (let i = 3; i < length; ++i) {
+        ta[i] = 4;
+    }
+
+    ta.sort((a, b) => (a/4|0) - (b/4|0));
+
+    assertEq(ta[0], 2);
+    assertEq(ta[1], 1);
+    assertEq(ta[2], 0);
+}
+
+if (typeof reportCompare === "function")
+    reportCompare(true, true);