Quicksort: Choose pivot with recursive sort of pivot candidates on large arrays to avoid patholgi...

src/array.js

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 759 matching lines @@
         if (order > 0) {
           a[j + 1] = tmp;
         } else {
           break;
         }
       }
       a[j + 1] = element;
     }
   };
 
+  var GetThirdIndex = function(a, from, to) {
+    var t_array = [];

[danno, 2012/06/19 14:52:17]

How about creating an InternalArray of the appropriate size here? That obviates
the need for the push() stub call later (you can just assign to the element)

[Erik Corry, 2012/06/19 18:36:29]

OK I tried that and it ended badly.  I have to be 100% sure I get the length
right and there are multiple chances to make off by 1 errors.  Leaving as it is
unless you feel very strongly about this.

[danno, 2012/06/19 19:55:55]

Nah, it's fine. I'd rather have the readable code and know it's right.

On 2012/06/19 18:36:29, Erik Corry wrote:

+    // Use both 'from' and 'to' to determine the pivot candidates.
+    var increment = 200 + ((to - from) & 15);
+    for (var i = from + 1; i < to - 1; i += increment) {
+      t_array.push([i, a[i]]);
+    }
+    t_array.sort(function(a, b) {
+        return %_CallFunction(receiver, a[1], b[1], comparefn) } );
+    var third_index = t_array[t_array.length >> 1][0];
+    return third_index;
+  }
+
   var QuickSort = function QuickSort(a, from, to) {
+    var third_index = 0;
     while (true) {
       // Insertion sort is faster for short arrays.
       if (to - from <= 10) {
         InsertionSort(a, from, to);
         return;
       }
+      if (to - from > 1000) {
+        third_index = GetThirdIndex(a, from, to);

[danno, 2012/06/19 14:52:17]

It still seems to be the case that you can carefully construct an array that
triggers the worst case. Is that something we need to avoid?

[Erik Corry, 2012/06/19 18:36:29]

I think we don't as long as it can't happen accidentally.  There is no longer a
stack overflow risk.

+      } else {
+        third_index = from + ((to - from) >> 1);
+      }
       // Find a pivot as the median of first, last and middle element.
       var v0 = a[from];
       var v1 = a[to - 1];
-      var middle_index = from + ((to - from) >> 1);
-      var v2 = a[middle_index];
+      var v2 = a[third_index];
       var c01 = %_CallFunction(receiver, v0, v1, comparefn);
       if (c01 > 0) {
         // v1 < v0, so swap them.
         var tmp = v0;
         v0 = v1;
         v1 = tmp;
       } // v0 <= v1.
       var c02 = %_CallFunction(receiver, v0, v2, comparefn);
       if (c02 >= 0) {
         // v2 <= v0 <= v1.
@@ skipping 10 matching lines @@
           v1 = v2;
           v2 = tmp;
         }
       }
       // v0 <= v1 <= v2
       a[from] = v0;
       a[to - 1] = v2;
       var pivot = v1;
       var low_end = from + 1;   // Upper bound of elements lower than pivot.
       var high_start = to - 1;  // Lower bound of elements greater than pivot.
-      a[middle_index] = a[low_end];
+      a[third_index] = a[low_end];
       a[low_end] = pivot;
 
       // From low_end to i are elements equal to pivot.
       // From i to high_start are elements that haven't been compared yet.
       partition: for (var i = low_end + 1; i < high_start; i++) {
         var element = a[i];
         var order = %_CallFunction(receiver, element, pivot, comparefn);
         if (order < 0) {
           a[i] = a[low_end];
           a[low_end] = element;
@@ skipping 698 matching lines @@
   // exposed to user code.
   // Adding only the functions that are actually used.
   SetUpLockedPrototype(InternalArray, $Array(), $Array(
     "join", getFunction("join", ArrayJoin),
     "pop", getFunction("pop", ArrayPop),
     "push", getFunction("push", ArrayPush)
   ));
 }
 
 SetUpArray();