Use JavaScript's Array.sort.

dart/lib/compiler/implementation/lib/interceptors.dart

Index: dart/lib/compiler/implementation/lib/interceptors.dart
diff --git a/dart/lib/compiler/implementation/lib/interceptors.dart b/dart/lib/compiler/implementation/lib/interceptors.dart
index 680af43e4408e4c86110e683b17e77d774d02123..240b0dd3b39dc8da5b65e1e657663fb21266e929 100644
--- a/dart/lib/compiler/implementation/lib/interceptors.dart
+++ b/dart/lib/compiler/implementation/lib/interceptors.dart
@@ -364,13 +364,69 @@ every(receiver, f) {
 sort$0(receiver) {
   if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort());

[floitsch, 2012/10/18 12:27:22]

After this if I would call sort$1(receiver, Comparable.compare).
It will reevaluate the isJsArray test, but make things much simpler.

[Lasse Reichstein Nielsen, 2012/10/18 13:04:00]

The trick is that this is simpler because we know the compare function - it will
not work on nulls. So instead of copying the array contents if it contains a
null, we just make it throw immediately.

[floitsch, 2012/10/18 13:46:51]

Since the shortcut only applies when it is going to throw, I wouldn't make the
special case.
If we really want to abort early I would rather special case in sort$1 (testing
if compare === Compare.compareTo).

   checkMutable(receiver, 'sort');
-  DualPivotQuicksort.sort(receiver, Comparable.compare);
+
+  int length = JS('int', '#.length', receiver);
+  if (length == 0 || length == 1) return;

[Lasse Reichstein Nielsen, 2012/10/18 13:04:00]

<= 1 should be fine, a JS Array's length can't be negative.

+  for (int i = 0; i < length; i++) {
+    // JavaScript's Array.prototype.sort has wierd semantics for null.
+    // It won't call compare and automatically pushes null/undefined
+    // to the end.
+    if (JS('var', '#[#]', receiver, i) == null) {
+      var other = JS('var', '#[#]', receiver, 0);
+      if (i == 0) {
+        other = JS('var', '#[#]', receiver, 1);
+      }
+      // Provoke a null error by comparing null to another element in
+      // the array.
+      Comparable.compare(null, other);
+    }
+  }
+
+  JS('void', '#.sort(#)', receiver, DART_CLOSURE_TO_JS(Comparable.compare));
 }
 
 sort$1(receiver, compare) {
   if (!isJsArray(receiver)) return UNINTERCEPTED(receiver.sort(compare));
   checkMutable(receiver, 'sort');
-  DualPivotQuicksort.sort(receiver, compare);
+  int length = JS('int', '#.length', receiver);

[floitsch, 2012/10/18 12:27:22]

Just tell dart2js that receiver is a JavaScript-array, instead of having all
these JS here.

[ahe, 2012/11/23 08:43:42]

How do I do that?

[sra1, 2012/11/23 10:57:33]

This code is dominated by isJsArray(receiver).
Why is that not sufficient?

[floitsch, 2012/11/23 13:00:51]

It should be, and now with the new interceptor approach this should work even
better.

+  if (length == 0 || length == 1) return;
+  bool hasNull = false;
+  var array = receiver;
+  for (int i = 0; i < length; i++) {

[floitsch, 2012/10/18 12:27:22]

Given that you already run through the array, you could also see if every
element is a number (but not NaN, Infinity, -Infinity). If the compare function
=== Compare.compareTo (the common case) we could probably be even faster by
avoiding the expensive compareTo function and creating a three phase sorting:
- count the -0s and replace them with 0s.
- sort using function(x, y) { return x - y; }
- search for the first 0 and replace the first ones with as many -0s as there
were in the beginning.

[sra1, 2012/11/23 10:57:33]

This assumes compareTo returns num, not int.  I'm not convinced that is a wise
choice.

You would need to weed out values within 2x of the max magnitude since otherwise
the subtraction could overflow and return Infinity.

+    // JavaScript's Array.prototype.sort has wierd semantics for null.

[floitsch, 2012/10/18 12:27:22]

weird

+    // It won't call compare and automatically pushes null/undefined
+    // to the end.
+    if (JS('var', '#[#]', array, i) == null) {
+      if (!hasNull) {
+        array = JS('var', '#.slice(0)', array);

[floitsch, 2012/10/18 12:27:22]

Why do we need a copy? To avoid the try/finally?

[Lasse Reichstein Nielsen, 2012/10/19 07:03:21]

Because any NullSentinel in the original array would be visible during the call
to the compare function.

+      }
+      JS('var', '#[#] = #', array, i, const NullSentinel());
+      hasNull = true;
+    }
+  }
+  var jsCompare;
+  if (hasNull) {

[floitsch, 2012/10/18 12:27:22]

I would special case for the Compare.compare:
if (compare === Compare.compare && hasNull) jsCompare = ...;
In that case you don't even need to bind.

+    jsCompare = DART_CLOSURE_TO_JS(compareHelperNull);
+  } else {
+    jsCompare = DART_CLOSURE_TO_JS(compareHelper);
+  }
+  // [DART_CLOSURE_TO_JS] only accepts static or top-level functions.
+  // So we use [compareHelper] and JavaScript's
+  // Function.prototype.bind to create a new closure we can safely
+  // pass to JavaScript.
+  jsCompare = JS('var', '#.bind(#, #)', jsCompare, null, compare);

[Lasse Reichstein Nielsen, 2012/10/18 11:54:50]

Is 'bind' fast now? That would be great :)

Try replacing it with this and see which is faster:
JS("var",
   "(function(compare, jsCompare) { return function(a,b) { return
jsCompare(compare, a, b); }; })(#,#)",
    compare, jsCompare);

+
+  JS('void', '#.sort(#)', receiver, jsCompare);
+
+  if (hasNull) {
+    for (int i = 0; i < length; i++) {
+      var element = JS('var', '#[#]', array, i);
+      if (const NullSentinel() == element) {
+        element = null;
+      }
+      JS('var', '#[#] = #', receiver, i, element);
+    }
+  }
 }
 
 isNegative(receiver) {