Bug 1259007 - Update for Merge to use only one buffer; r=mrrrgn
☠☠ backed out by ac482faf3373 ☠ ☠
author4esn0k <vic99999@yandex.ru>
Thu, 24 Mar 2016 17:39:13 -0700
changeset 290469 8e8e5cdc1ff48176c1ddec999aec28f07e9d1c3d
parent 290468 542fffb3ce3d941e223a33753539c7c83b32d8f5
child 290470 e40580ed0fe6fab50f1d8d23747c2cf423d93016
push id19656
push usergwagner@mozilla.com
push dateMon, 04 Apr 2016 13:43:23 +0000
treeherderb2g-inbound@e99061fde28a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmrrrgn
bugs1259007
milestone48.0a1
Bug 1259007 - Update for Merge to use only one buffer; r=mrrrgn
js/src/builtin/Sorting.js
--- a/js/src/builtin/Sorting.js
+++ b/js/src/builtin/Sorting.js
@@ -169,53 +169,42 @@ function InsertionSort(array, from, to, 
 
 function SwapArrayElements(array, i, j) {
     var swap = array[i];
     array[i] = array[j];
     array[j] = swap;
 }
 
 // A helper function for MergeSort.
-function Merge(list, start, mid, end, lBuffer, rBuffer, comparefn) {
+function Merge(source, start, mid, end, destination, comparefn) {
     var i, j, k;
 
-    var sizeLeft = mid - start + 1;
-    var sizeRight =  end - mid;
-
-    // Copy our virtual lists into separate buffers.
-    for (i = 0; i < sizeLeft; i++)
-        lBuffer[i] = list[start + i];
-
-    for (j = 0; j < sizeRight; j++)
-        rBuffer[j] = list[mid + 1 + j];
-
-
-    i = 0;
-    j = 0;
+    i = start;
+    j = mid;
     k = start;
-    while (i < sizeLeft && j < sizeRight) {
-        if (comparefn(lBuffer[i], rBuffer[j]) <= 0) {
-            list[k] = lBuffer[i];
+    while (i < mid && j < end) {
+        if (comparefn(source[j], source[i]) < 0) {
+            destination[k] = source[j];
+            j++;
+        } else {
+            destination[k] = source[i];
             i++;
-        } else {
-            list[k] = rBuffer[j];
-            j++;
         }
         k++;
     }
 
     // Empty out any remaining elements in the buffer.
-    while (i < sizeLeft) {
-        list[k] =lBuffer[i];
+    while (i < mid) {
+        destination[k] = source[i];
         i++;
         k++;
     }
 
-    while (j < sizeRight) {
-        list[k] =rBuffer[j];
+    while (j < end) {
+        destination[k] = source[j];
         j++;
         k++;
     }
 }
 
 // Helper function for overwriting a sparse array with a
 // dense array, filling remaining slots with holes.
 function MoveHoles(sparse, sparseLen, dense, denseLen) {
@@ -243,36 +232,37 @@ function MergeSort(array, len, comparefn
     // Insertion sort for small arrays, where "small" is defined by performance
     // testing.
     if (len < 24) {
         InsertionSort(denseList, 0, denseLen - 1, comparefn);
         MoveHoles(array, len, denseList, denseLen);
         return array;
     }
 
+    var source = denseList;
     // We do all of our allocating up front
-    var lBuffer = new List();
-    var rBuffer = new List();
+    var destination = new List();
 
     var mid, end, endOne, endTwo;
     for (var windowSize = 1; windowSize < denseLen; windowSize = 2 * windowSize) {
-        for (var start = 0; start < denseLen - 1; start += 2 * windowSize) {
+        for (var start = 0; start < denseLen; start += 2 * windowSize) {
             assert(windowSize < denseLen, "The window size is larger than the array denseLength!");
             // The midpoint between the two subarrays.
-            mid = start + windowSize - 1;
+            mid = start + windowSize;
+            mid = mid < denseLen ? mid : denseLen;
             // To keep from going over the edge.
-            end = start + 2 * windowSize - 1;
-            end = end < denseLen - 1 ? end : denseLen - 1;
-            // Skip lopsided runs to avoid doing useless work
-            if (mid > end)
-                continue;
-            Merge(denseList, start, mid, end, lBuffer, rBuffer, comparefn);
+            end = start + 2 * windowSize;
+            end = end < denseLen ? end : denseLen;
+            Merge(source, start, mid, end, destination, comparefn);
         }
+        var tmp = source;
+        source = destination;
+        destination = tmp;
     }
-    MoveHoles(array, len, denseList, denseLen);
+    MoveHoles(array, len, source, denseLen);
     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) {