From 5741575327d4f44201ee33e957d8c278b765bc52 Mon Sep 17 00:00:00 2001
From: "lrn@chromium.org"
 <lrn@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Mon, 20 Dec 2010 14:57:51 +0000
Subject: [PATCH] Tweak quicksort loop to reduce number of compares slightly.

Review URL: http://codereview.chromium.org/6039002

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@6087 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/array.js               | 31 ++++++++++++++++++-------------
 test/mjsunit/array-sort.js | 17 ++++++++++++++++-
 2 files changed, 34 insertions(+), 14 deletions(-)

diff --git a/src/array.js b/src/array.js
index 467d4eb..0f1e969 100644
--- a/src/array.js
+++ b/src/array.js
@@ -1,4 +1,4 @@
-// Copyright 2006-2008 the V8 project authors. All rights reserved.
+// Copyright 2010 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:
@@ -677,24 +677,23 @@ function ArraySort(comparefn) {
 
   function QuickSort(a, from, to) {
     // Insertion sort is faster for short arrays.
-    if (to - from <= 13) {
+    if (to - from <= 10) {
       InsertionSort(a, from, to);
       return;
     }
-
     // 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 c01 = comparefn(v0, v1);
+    var c01 = %_CallFunction(global_receiver, v0, v1, comparefn);
     if (c01 > 0) {
       // v1 < v0, so swap them.
       var tmp = v0;
       v0 = v1;
       v1 = tmp;
     } // v0 <= v1.
-    var c02 = comparefn(v0, v2);
+    var c02 = %_CallFunction(global_receiver, v0, v2, comparefn);
     if (c02 >= 0) {
       // v2 <= v0 <= v1.
       var tmp = v0;
@@ -703,7 +702,7 @@ function ArraySort(comparefn) {
       v1 = tmp;
     } else {
       // v0 <= v1 && v0 < v2
-      var c12 = comparefn(v1, v2);
+      var c12 = %_CallFunction(global_receiver, v1, v2, comparefn);
       if (c12 > 0) {
         // v0 <= v2 < v1
         var tmp = v1;
@@ -715,25 +714,31 @@ function ArraySort(comparefn) {
     a[from] = v0;
     a[to - 1] = v2;
     var pivot = v1;
-    var low_end = from + 1;   // Upper bound of the elements lower than pivot.
-    var high_start = to - 1;  // Lower bound of the elements greater than pivot.
+    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[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.
-    for (var i = low_end + 1; i < high_start; ) {
+    partition: for (var i = low_end + 1; i < high_start; i++) {
       var element = a[i];
       var order = %_CallFunction(global_receiver, element, pivot, comparefn);
       if (order < 0) {
         %_SwapElements(a, i, low_end);
-        i++;
         low_end++;
       } else if (order > 0) {
-        high_start--;
+        do {
+          high_start--;
+          if (high_start == i) break partition;
+          var top_elem = a[high_start];
+          order = %_CallFunction(global_receiver, top_elem, pivot, comparefn);
+        } while (order > 0);
         %_SwapElements(a, i, high_start);
-      } else {  // order == 0
-        i++;
+        if (order < 0) {
+          %_SwapElements(a, i, low_end);
+          low_end++;
+        }
       }
     }
     QuickSort(a, from, low_end);
diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js
index a082abc..7060c5f 100644
--- a/test/mjsunit/array-sort.js
+++ b/test/mjsunit/array-sort.js
@@ -1,4 +1,4 @@
-// Copyright 2008 the V8 project authors. All rights reserved.
+// Copyright 2010 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:
@@ -360,3 +360,18 @@ function TestSpecialCasesInheritedElementSort() {
 }
 
 TestSpecialCasesInheritedElementSort();
+
+// Test that sort calls compare function with global object as receiver,
+// and with only elements of the array as arguments.
+function o(v) { 
+  return {__proto__: o.prototype, val: v};
+}
+var arr = [o(1), o(2), o(4), o(8), o(16), o(32), o(64), o(128), o(256), o(-0)];
+var global = this;
+function cmpTest(a, b) {
+  assertEquals(global, this);
+  assertTrue(a instanceof o);
+  assertTrue(b instanceof o);
+  return a.val - b.val;
+}
+arr.sort(cmpTest);
\ No newline at end of file
-- 
2.7.4