Early specialize sorting functions depending if there is a custom comparator or not.

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 626 matching lines @@
 
   // Return the deleted elements.
   return deleted_elements;
 }
 
 
 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 InsertionSortWithFunc(a, from, to) {
+    for (var i = from + 1; i < to; i++) {
+      var element = a[i];

[Lasse Reichstein, 2010/04/07 17:43:27]

Come to think of it, using binary search seems overkill, since we are going to
read and write every element after the found position anyway when we place the
element. 
Just do a backwards search-and-copy until finding the correct location. I.e,
something like:

  for (var j = i - 1; j >= from; j--) {
    var tmp = a[j];
    var order = tmp === element ? 0 : comparefn.call(null,tmp,element);
    if (order > 0) {
      a[j + 1] = tmp;
    } else if (order == 0) {
      j--;
      break;
    }
  }
  a[j + 1] = element;

[antonm, 2010/04/07 17:47:27]

Agree.  That's the thing I implemented in C++, but calling JS from C++ is
expensive.  I'll give it a try, but for now it doesn't look like the main reason
for slowness.

+      // 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 = (a[mid] === element) ?
+            0 : comparefn.call(null, a[mid], element);

[Lasse Reichstein, 2010/04/07 17:43:27]

Reading a[mid] twice. Maybe assign to temporary variable.

[antonm, 2010/04/07 17:47:27]

Thanks, will give it a try.

+        if (order == 0) {
+          min = max = mid;

[Lasse Reichstein, 2010/04/07 17:43:27]

No need to assign to max.

[antonm, 2010/04/07 17:47:27]

Will give it a try as well.

+          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 QuickSortWithFunc(a, from, to) {
+    // Insertion sort is faster for short arrays.
+    if (to - from <= 22) {
+      InsertionSortWithFunc(a, from, to);
+      return;
+    }
+    var pivot_index = $floor($random() * (to - from)) + from;
+    var pivot = a[pivot_index];
+    // Issue 95: Keep the pivot element out of the comparisons to avoid
+    // infinite recursion if comparefn(pivot, pivot) != 0.
+    a[pivot_index] = a[from];
+    a[from] = 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.
+    // From low_end to i are elements equal to pivot.
+    // From i to high_start are elements that haven't been compared yet.
+    for (var i = from + 1; i < high_start; ) {
+      var element = a[i];
+      var order = (element === pivot) ?
+          0 : comparefn.call(null, element, pivot);
+      if (order < 0) {
+        a[i] = a[low_end];
+        a[low_end] = element;
+        i++;
+        low_end++;
+      } else if (order > 0) {
+        high_start--;
+        a[i] = a[high_start];
+        a[high_start] = element;
+      } else {  // order == 0
+        i++;
+      }
+    }
+    QuickSortWithFunc(a, from, low_end);
+    QuickSortWithFunc(a, high_start, to);
+  }
 
   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.

[Lasse Reichstein, 2010/04/07 17:43:27]

Comment doesn't make sense any more (not here, at least).

[antonm, 2010/04/07 17:47:27]

Agree.  Will remove.

     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);
+      var key = %_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], key);
         if (order == 0) {
           min = max = mid;
@@ skipping 16 matching lines @@
   function QuickSort(a, from, to) {
     // Insertion sort is faster for short arrays.
     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);
+    var pivot_key = %_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[from];
     a[from] = 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.
     // From low_end to i are elements equal to pivot.
     // From i to high_start are elements that haven't been compared yet.
     for (var i = from + 1; i < high_start; ) {
       var element = a[i];
       var order = Compare(element, pivot_key);
       if (order < 0) {
         a[i] = a[low_end];
         a[low_end] = element;
         i++;
         low_end++;
       } else if (order > 0) {
         high_start--;
         a[i] = a[high_start];
         a[high_start] = element;
       } else {  // order == 0
         i++;
       }
     }
     QuickSort(a, from, low_end);
     QuickSort(a, high_start, to);
   }
 
-  var length;
-
   // Copies elements in the range 0..length from obj's prototype chain
   // to obj itself, if obj has holes. Returns one more than the maximal index
   // of a prototype property.
   function CopyFromPrototype(obj, length) {
     var max = 0;
     for (var proto = obj.__proto__; proto; proto = proto.__proto__) {
       var indices = %GetArrayKeys(proto, length);
       if (indices.length > 0) {
         if (indices[0] == -1) {
           // It's an interval.
@@ skipping 97 matching lines @@
         obj[i] = void 0;
       } else {
         delete obj[i];
       }
     }
 
     // Return the number of defined elements.
     return first_undefined;
   }
 
-  length = TO_UINT32(this.length);
+  var length = TO_UINT32(this.length);
   if (length < 2) return this;
 
   var is_array = IS_ARRAY(this);
   var max_prototype_element;
   if (!is_array) {
     // For compatibility with JSC, we also sort elements inherited from
     // the prototype chain on non-Array objects.
     // We do this by copying them to this object and sorting only
     // local elements. This is not very efficient, but sorting with
     // inherited elements happens very, very rarely, if at all.
     // The specification allows "implementation dependent" behavior
     // if an element on the prototype chain has an element that
     // might interact with sorting.
     max_prototype_element = CopyFromPrototype(this, length);
   }
 
   var num_non_undefined = %RemoveArrayHoles(this, length);
   if (num_non_undefined == -1) {
     // There were indexed accessors in the array.  Move array holes and
     // undefineds to the end using a Javascript function that is safe
     // in the presence of accessors.
     num_non_undefined = SafeRemoveArrayHoles(this);
   }
 
-  QuickSort(this, 0, num_non_undefined);
+  if(IS_FUNCTION(comparefn)) {
+    QuickSortWithFunc(this, 0, num_non_undefined);
+  } else {
+    QuickSort(this, 0, num_non_undefined);
+  }
 
   if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
     // For compatibility with JSC, we shadow any elements in the prototype
     // chain that has become exposed by sort moving a hole to its position.
     ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
   }
 
   return this;
 }
 
@@ skipping 255 matching lines @@
     "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
     "reduce", getFunction("reduce", ArrayReduce, 1),
     "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
   ));
 
   %FinishArrayPrototypeSetup($Array.prototype);
 }
 
 
 SetupArray();