Experimental: port bleeding_edge r1276 (a grab bag of optimizations)...

src/array.js

Index: src/array.js
===================================================================
--- src/array.js	(revision 1313)
+++ src/array.js	(working copy)
@@ -620,7 +620,11 @@
   var custom_compare = IS_FUNCTION(comparefn);
 
   function Compare(x,y) {
+    // Assume the comparefn, if any, is a consistent comparison function.
+    // If it isn't, we are allowed arbitrary behavior by ECMA 15.4.4.11.
+    if (x === y) return 0;
     if (custom_compare) {
+      // Don't call directly to avoid exposing the builtin's global object.
       return comparefn.call(null, x, y);
     }
     if (%_IsSmi(x) && %_IsSmi(y)) {
@@ -635,6 +639,10 @@
   function InsertionSort(a, from, to) {
     for (var i = from + 1; i < to; i++) {
       var element = a[i];
+      // Pre-convert the element to a string for comparison if we know
+      // it will happen on each compare anyway.
+      var key =
+          (custom_compare || %_IsSmi(element)) ? element : ToString(element);
       // place element in a[from..i[
       // binary search
       var min = from;
@@ -642,7 +650,7 @@
       // The search interval is a[min..max[
       while (min < max) {
         var mid = min + ((max - min) >> 1);
-        var order = Compare(a[mid], element);
+        var order = Compare(a[mid], key);
         if (order == 0) {
           min = max = mid;
           break;
@@ -663,43 +671,49 @@
 
   function QuickSort(a, from, to) {
     // Insertion sort is faster for short arrays.
-    if (to - from <= 22) { 
+    if (to - from <= 22) {
       InsertionSort(a, from, to);
       return;
     }
     var pivot_index = $floor($random() * (to - from)) + from;
     var pivot = a[pivot_index];
+    // Pre-convert the element to a string for comparison if we know
+    // it will happen on each compare anyway.
+    var pivot_key =
+      (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot);
     // Issue 95: Keep the pivot element out of the comparisons to avoid
     // infinite recursion if comparefn(pivot, pivot) != 0.
-    a[pivot_index] = a[to - 1];
-    a[to - 1] = pivot;
-    var low_end = from;   // Upper bound of the elements lower than pivot.
-    var high_start = to - 1; // Lower bound of the elements greater than pivot.
-    for (var i = from; i < high_start; ) {
-      var element = a[i];
-      var order = Compare(element, pivot);
+    var low_end = from; // Upper bound of the elements lower than pivot.
+    var high_start = to; // Lower bound of the elements greater than pivot.
+    var eq_start = to - 1; // Lower bound of elements equal to pivot.
+    a[pivot_index] = a[eq_start];
+    a[eq_start] = pivot;
+    // From eq_start to high_start are elements equal to the pivot
+    // (including the pivot).
+    // From low_end to eq_start are elements that have not been compared yet.
+    while (low_end < eq_start) {
+      var element = a[low_end];
+      var order = Compare(element, pivot_key);
       if (order < 0) {
-        a[i] = a[low_end];
-        a[low_end] = element;
         low_end++;
-        i++;
       } else if (order > 0) {
+        eq_start--;
         high_start--;
-        a[i] = a[high_start];
+        a[low_end] = a[eq_start];
+        a[eq_start] = a[high_start];
         a[high_start] = element;
-      } else { // order == 0
-        i++;
+      } else {  // order == 0
+        eq_start--;
+        a[low_end] = a[eq_start];
+        a[eq_start] = element;
       }
     }
-    // Restore the pivot element to its rightful place.
-    a[to - 1] = a[high_start];
-    a[high_start] = pivot;
-    high_start++;
     QuickSort(a, from, low_end);
     QuickSort(a, high_start, to);
   }
 
   var old_length = ToUint32(this.length);
+  if (old_length < 2) return this;
 
   %RemoveArrayHoles(this);
 
@@ -741,10 +755,11 @@
   // loop will not affect the looping.
   var length = this.length;
   var result = [];
+  var result_length = 0;
   for (var i = 0; i < length; i++) {
     var current = this[i];
     if (!IS_UNDEFINED(current) || i in this) {
-      if (f.call(receiver, current, i, this)) result.push(current);
+      if (f.call(receiver, current, i, this)) result[result_length++] = current;
     }
   }
   return result;