Revision: 6087
Author: [email protected]
Date: Mon Dec 20 06:57:51 2010
Log: Tweak quicksort loop to reduce number of compares slightly.
Review URL: http://codereview.chromium.org/6039002
http://code.google.com/p/v8/source/detail?r=6087
Modified:
/branches/bleeding_edge/src/array.js
/branches/bleeding_edge/test/mjsunit/array-sort.js
=======================================
--- /branches/bleeding_edge/src/array.js Fri Dec 17 02:06:11 2010
+++ /branches/bleeding_edge/src/array.js Mon Dec 20 06:57:51 2010
@@ -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 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 @@
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 @@
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);
=======================================
--- /branches/bleeding_edge/test/mjsunit/array-sort.js Tue Dec 7 03:01:02
2010
+++ /branches/bleeding_edge/test/mjsunit/array-sort.js Mon Dec 20 06:57:51
2010
@@ -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 @@
}
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);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
