Hi Mehmet
Thank you for your input. We have evaluated different strategies for
improving the speed of ArraySort including your suggestions.
Using the middle element for as the pivot for short arrays work well in
certain special cases as you have noted, but it doesn't have a noticeable
impact on random arrays. We have decided to postpone using techniques that
deal with these kinds of special cases until we know more about whether they
make a difference in practice.
The simpler insertion sort works well for small integers where the Compare
function is fast, but for strings it actually slows down sort because of the
higher number of calls to compare (note that the existing InsertionSort is
optimal in number of comparisons). Since JavaScript array sort is really
designed for strings, we have decided to keep InsertionSort as it is.
Thanks again for your ideas.
Regards,
Ole
On Wed, Oct 1, 2008 at 7:40 PM, Mehmet D. Akin <[EMAIL PROTECTED]> wrote:
>
> 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.
> >
>
--
--
Ole I Hougaard
Google Aarhus, Denmark
+45 8745 9215
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
