Revision: 11873
Author: erikcorry
Date: Wed Jun 20 00:52:47 2012
Log: Quicksort: Choose pivot with recursive sort of pivot candidates
on large arrays to avoid patholgical cases.
Review URL: http://codereview.chromium.org/10532193
http://code.google.com/p/v8/source/detail?r=11873
Added:
/branches/bleeding_edge/test/mjsunit/regress/regress-2185-2.js
Modified:
/branches/bleeding_edge/src/array.js
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/regress/regress-2185-2.js Wed Jun
20 00:52:47 2012
@@ -0,0 +1,145 @@
+// Copyright 2012 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
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// These tests used to time out before this was fixed.
+
+var LEN = 1e5;
+
+function short() {
+ var sum = 0;
+ for (var i = 0; i < 10000; i++) {
+ var a = [1, 4, 34, 23, 6, 123, 3, 2, 11, 515, 4, 33, 22, 2, 2, 1, 0,
123,
+ 23, 42, 43, 1002, 44, 43, 101, 23, 55, 11, 101, 102, 45, 11,
404,
+ 31415, 34, 53, 453, 45, 34, 5, 2, 35, 5, 345, 36, 45, 345, 3,
45,
+ 3, 5, 5, 2, 2342344, 2234, 23, 2718, 1500, 2, 19, 22, 43, 41,
0,
+ -1, 33, 45, 78];
+ a.sort(function(a, b) { return a - b; });
+ sum += a[0];
+ }
+ return sum;
+}
+
+function short_bench(name, array) {
+ var start = new Date();
+ short();
+ var end = new Date();
+ var ms = end - start;
+ print("Short " + Math.floor(ms) + "ms");
+}
+
+function sawseq(a, tooth) {
+ var count = 0;
+ while (true) {
+ for (var i = 0; i < tooth; i++) {
+ a.push(i);
+ if (++count >= LEN) return a;
+ }
+ }
+}
+
+function sawseq2(a, tooth) {
+ var count = 0;
+ while (true) {
+ for (var i = 0; i < tooth; i++) {
+ a.push(i);
+ if (++count >= LEN) return a;
+ }
+ for (var i = 0; i < tooth; i++) {
+ a.push(tooth - i);
+ if (++count >= LEN) return a;
+ }
+ }
+}
+
+function sawseq3(a, tooth) {
+ var count = 0;
+ while (true) {
+ for (var i = 0; i < tooth; i++) {
+ a.push(tooth - i);
+ if (++count >= LEN) return a;
+ }
+ }
+}
+
+function up(a) {
+ for (var i = 0; i < LEN; i++) {
+ a.push(i);
+ }
+ return a;
+}
+
+function down(a) {
+ for (var i = 0; i < LEN; i++) {
+ a.push(LEN - i);
+ }
+ return a;
+}
+
+function ran(a) {
+ for (var i = 0; i < LEN; i++) {
+ a.push(Math.floor(Math.random() * LEN));
+ }
+ return a;
+}
+
+var random = ran([]);
+var asc = up([]);
+var desc = down([]);
+var asc_desc = down(up([]));
+var desc_asc = up(down([]));
+var asc_asc = up(up([]));
+var desc_desc = down(down([]));
+var saw1 = sawseq([], 1000);
+var saw2 = sawseq([], 500);
+var saw3 = sawseq([], 200);
+var saw4 = sawseq2([], 200);
+var saw5 = sawseq3([], 200);
+
+function bench(name, array) {
+ var start = new Date();
+ array.sort(function(a, b) { return a - b; });
+ var end = new Date();
+ for (var i = 0; i < array.length - 1; i++) {
+ if (array[i] > array[i + 1]) throw name + " " + i;
+ }
+ var ms = end - start;
+ print(name + " " + Math.floor(ms) + "ms");
+}
+
+short_bench();
+bench("random", random);
+bench("up", asc);
+bench("down", desc);
+bench("saw 1000", saw1);
+bench("saw 500", saw2);
+bench("saw 200", saw3);
+bench("saw 200 symmetric", saw4);
+bench("saw 200 down", saw4);
+bench("up, down", asc_desc);
+bench("up, up", asc_asc);
+bench("down, down", desc_desc);
+bench("down, up", desc_asc);
=======================================
--- /branches/bleeding_edge/src/array.js Mon Jun 18 02:23:05 2012
+++ /branches/bleeding_edge/src/array.js Wed Jun 20 00:52:47 2012
@@ -777,18 +777,36 @@
}
};
+ var GetThirdIndex = function(a, from, to) {
+ var t_array = [];
+ // Use both 'from' and 'to' to determine the pivot candidates.
+ var increment = 200 + ((to - from) & 15);
+ for (var i = from + 1; i < to - 1; i += increment) {
+ t_array.push([i, a[i]]);
+ }
+ t_array.sort(function(a, b) {
+ return %_CallFunction(receiver, a[1], b[1], comparefn) } );
+ var third_index = t_array[t_array.length >> 1][0];
+ return third_index;
+ }
+
var QuickSort = function QuickSort(a, from, to) {
+ var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
+ if (to - from > 1000) {
+ third_index = GetThirdIndex(a, from, to);
+ } else {
+ third_index = from + ((to - from) >> 1);
+ }
// 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 v2 = a[third_index];
var c01 = %_CallFunction(receiver, v0, v1, comparefn);
if (c01 > 0) {
// v1 < v0, so swap them.
@@ -819,7 +837,7 @@
var pivot = v1;
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[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
