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

src/array.js

 // Copyright 2006-2008 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 602 matching lines @@
 }
 
 
 function ArraySort(comparefn) {
   // In-place QuickSort algorithm.
   // For short (length <= 22) arrays, insertion sort is used for efficiency.
 
   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)) {
       return %SmiLexicographicCompare(x, y);
     }
     x = ToString(x);
     y = ToString(y);
     if (x == y) return 0;
     else return x < y ? -1 : 1;
   };
 
   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;
       var max = i;
       // 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;
         }
         if (order < 0) {
           min = mid + 1;
         } else {
           max = mid;
         }
       }
       // place element at position min==max.
       for (var j = i; j > min; j--) {
         a[j] = a[j - 1];
       }
       a[min] = element;
     }
   }
 
   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);
 
   var length = ToUint32(this.length);
 
   // Move undefined elements to the end of the array.
   for (var i = 0; i < length; ) {
     if (IS_UNDEFINED(this[i])) {
       length--;
       this[i] = this[length];
@@ skipping 21 matching lines @@
 // preserving the semantics, since the calls to the receiver function can add
 // or delete elements from the array.
 function ArrayFilter(f, receiver) {
   if (!IS_FUNCTION(f)) {
     throw MakeTypeError('called_non_callable', [ f ]);
   }
   // Pull out the length so that modifications to the length in the
   // 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;
 }
 
 
 function ArrayForEach(f, receiver) {
   if (!IS_FUNCTION(f)) {
     throw MakeTypeError('called_non_callable', [ f ]);
   }
@@ skipping 159 matching lines @@
     ArrayEvery: 1,
     ArrayMap: 1,
     ArrayIndexOf: 1,
     ArrayLastIndexOf: 1,
     ArrayPush: 1
   });
 }
 
 
 SetupArray();