I made 2 changes to sort implementation, used random pivot only if
size of the segment is bigger than 1000, also used a simpler
insertion sort, This two additions improves performance of sort %30-40
on smaller arrays (element count < 500) and %5-10 on larger arrays. I
tried with shuffled, nearly sorted, sorted, all-same, sawtooth type
arrays with various sizes.
Index: src/array.js
===================================================================
--- src/array.js (revision 402)
+++ src/array.js (working copy)
@@ -667,46 +667,25 @@
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];
- // 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], element);
- if (order == 0) {
- min = max = mid;
- break;
- }
- if (order < 0) {
- min = mid + 1;
- } else {
- max = mid;
- }
- }
- // place element at position min==max.
- for (var j = min; j < i; j++) {
- var tmp = a[j];
- a[j] = element;
- element = tmp;
- }
- a[i] = element;
- }
}
function QuickSort(a, from, to) {
// Insertion sort is faster for short arrays.
- if (to - from <= 22) {
- InsertionSort(a, from, to);
+ var len = to - from;
+ if (len <= 22) {
+ for (var i = from; i < to; i++) {
+ for (var j = i; j > from && Compare(a[j-1], a[j]) > 0; j--) {
+ var tmp = a[j];
+ a[j] = a[j-1];
+ a[j-1] = tmp;
+ }
+ }
return;
}
- var pivot_index = $floor($random() * (to - from)) + from;
+ var pivot_index = from + (len >> 1);
+ if (len > 1000) {
+ pivot_index = $floor($random() * len) + 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.
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
