Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101 random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101 random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x) - an ordered copy
dither(x) - add i%5 to x[i]
Here is the result of execution:
Server VM:
http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
Client VM:
http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
Mathematical investigations
---
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
Diff between current and new implementation of Quicksort
Here is the link to the diff for java.util.Arrays class:
http://cr.openjdk.java.net/~alanb/6880672/webrev.00
If you like to look and play with new algorithm,
please, take attached class DualPivotQuicksort.java
Feedback
Also I'd like to share a feedback from Joshua Bloch and
Jon Bentley who spent a lot of time investigating this
algorithm, who gave me many advices and tips how to
make new Quicksort better.
Original Message
Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7
Date: Thu, 10 Sep 2009 07:20:11 -0700
From: Joshua Bloch
Jon also says that Vladimir should make every reasonable improvement to
the basic method before checking in the code. In his words, "It would be
horrible to put the new code into the library, and then have someone
else come along and speed it up by another 20% by using standard
techniques." I believe it's not unlikely that this code may end up
getting ported to many languages and widely deployed in much the manner
of Bentley and McIlroy's fine sort (which is nearing 20 successful years
in the field). Jon will help Vladimir do this.
Original Message
Subject: Dual-Pivot Quicksort: Next Steps
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
I think this is the best place to contact the original authors. The link to Vladimir Yaroslavskiy's original whitepaper describing the algorithm and its proofs was, unfortunately, broken. Using Archive.org's Wayback Machine, I was able to get the last known revision. I reformatted the document in LibreOffice for ease of reading, and fixed some minor grammatical errors. I also implemented the algorithm in an open-source (MIT License) C++ library, which I hope to release in the coming few months. In order to make this algorithm and its proofs more easily accessible, I would like to make the revised whitepaper publicly and freely available from my own web servers, but I wanted to check with the original author(s) first. Furthermore, I wanted to find out if there have been any revisions since the 22 September 2009 version of the whitepaper I acquired. Thank you in advance!
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Wow, is this a reply to a nearly seven-year-old email? [1] I don't know if Vladimir Yaroslavskiy is still on core-libs-dev. I dug through tthe archives and found that he had posted a couple messages somewhat later [2] [3] using different email addresses: Vladimir Iaroslavski Vladimir Iaroslavski You might try to contact him at one of these addresses. Note however that the more recent one is still over five years old. He's also on LinkedIn. His profile says he works for Oracle, but as far as I can see he no longer does. Good luck, s'marks [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-September/002630.html [2] http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-April/004133.html [3] http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-February/005821.html On 2/23/16 6:05 PM, Jason C. McDonald wrote: I think this is the best place to contact the original authors. The link to Vladimir Yaroslavskiy's original whitepaper describing the algorithm and its proofs was, unfortunately, broken. Using Archive.org's Wayback Machine, I was able to get the last known revision. I reformatted the document in LibreOffice for ease of reading, and fixed some minor grammatical errors. I also implemented the algorithm in an open-source (MIT License) C++ library, which I hope to release in the coming few months. In order to make this algorithm and its proofs more easily accessible, I would like to make the revised whitepaper publicly and freely available from my own web servers, but I wanted to check with the original author(s) first. Furthermore, I wanted to find out if there have been any revisions since the 22 September 2009 version of the whitepaper I acquired. Thank you in advance!
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Hi Stuart, I hate replying to an ancient threat, but I figured it was the best method. Thanks for the tips. The original paper was almost as hard to find as he is proving to be. :) All the best, -Jason C. McDonald On 02/26/2016 06:05 PM, Stuart Marks wrote: Wow, is this a reply to a nearly seven-year-old email? [1] I don't know if Vladimir Yaroslavskiy is still on core-libs-dev. I dug through tthe archives and found that he had posted a couple messages somewhat later [2] [3] using different email addresses: Vladimir Iaroslavski Vladimir Iaroslavski You might try to contact him at one of these addresses. Note however that the more recent one is still over five years old. He's also on LinkedIn. His profile says he works for Oracle, but as far as I can see he no longer does. Good luck, s'marks [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-September/002630.html [2] http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-April/004133.html [3] http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-February/005821.html On 2/23/16 6:05 PM, Jason C. McDonald wrote: I think this is the best place to contact the original authors. The link to Vladimir Yaroslavskiy's original whitepaper describing the algorithm and its proofs was, unfortunately, broken. Using Archive.org's Wayback Machine, I was able to get the last known revision. I reformatted the document in LibreOffice for ease of reading, and fixed some minor grammatical errors. I also implemented the algorithm in an open-source (MIT License) C++ library, which I hope to release in the coming few months. In order to make this algorithm and its proofs more easily accessible, I would like to make the revised whitepaper publicly and freely available from my own web servers, but I wanted to check with the original author(s) first. Furthermore, I wanted to find out if there have been any revisions since the 22 September 2009 version of the whitepaper I acquired. Thank you in advance! -- Jason C. McDonald Check out my scribblings! www.indeliblebluepen.com
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
just my two cents :
In the loop tagged "sorting" and "equals element",
a[k] can be stored in a local variable to avoid to recompute it several
time.
The algorithm use two constants: 37 and 13,
I think they should be declared as private static final.
Rémi
Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x) - an ordered copy
dither(x) - add i%5 to x[i]
Here is the result of execution:
Server VM:
http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
Client VM:
http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
Mathematical investigations
---
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
Diff between current and new implementation of Quicksort
Here is the link to the diff for java.util.Arrays class:
http://cr.openjdk.java.net/~alanb/6880672/webrev.00
If you like to look and play with new algorithm,
please, take attached class DualPivotQuicksort.java
Feedback
Also I'd like to share a feedback from Joshua Bloch and
Jon Bentley who spent a lot of time investigating this
algorithm, who gave me many advices and tips how to
make new Quicksort better.
Original Message
Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7
Date: Thu, 10 Sep 2009 07:20:11 -0700
From: Joshua Bloch
Jon also says that Vladimir should make every reasonable improvement to
the basic method before checking in the code. In his words, "It would be
horrible to put the new code into the library, and then have someone
else come along and speed it up by another 20% by using standard
techniques."
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Very interesting stuff.
Does one have tried (theoretically and/or experimental) P1+P2+P3,
P1+P2+P3+P2, ... segmentation ?
Maybe coefficient A has a minimum below 0.8.
-Ulf
Am 11.09.2009 12:35, Vladimir Yaroslavskiy schrieb:
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x) - an ordered copy
dither(x) - add i%5 to x[i]
Here is the result of execution:
Server VM:
http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
Client VM:
http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
Mathematical investigations
---
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
Diff between current and new implementation of Quicksort
Here is the link to the diff for java.util.Arrays class:
http://cr.openjdk.java.net/~alanb/6880672/webrev.00
If you like to look and play with new algorithm,
please, take attached class DualPivotQuicksort.java
Feedback
Also I'd like to share a feedback from Joshua Bloch and
Jon Bentley who spent a lot of time investigating this
algorithm, who gave me many advices and tips how to
make new Quicksort better.
Original Message
Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7
Date: Thu, 10 Sep 2009 07:20:11 -0700
From: Joshua Bloch
Jon also says that Vladimir should make every reasonable improvement to
the basic method before checking in the code. In his words, "It would be
horrible to put the new code into the library, and then have someone
else come along and speed it up by another 20% by using standard
techniques." I believe it's not unlikely that this code may end up
getting ported to many langua
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Hi Ulf,
Sure, I have tried it, see:
Original Message
Subject: Re: Dual-Pivot Quicksort Analysis
Date: Wed, 09 Sep 2009 18:45:46 +0400
From: Vladimir Yaroslavskiy
Organization: Sun Microsystems, Inc.
To: Jon Bentley
CC: Joshua Bloch
Hello,
I've converted the pseudocode into Java and here is the result:
I counted the comps and swaps for array with length n = 2'000'000,
did it 77 times and took the average value:
Classic Quicksort: comps - 52254956
swaps - 26277985
Dual-Pivot Quicksort: comps - 52246553
swaps - 20977937
These values correlate with math proof: the number of comps
the same (2*n*ln(n)) and ratio for swaps is 20977937/26277985
= 0.7983 (theoretical is 0.8/1.0 = 0.8).
I don't have "few words" explanation wh ythe new algorithm is quicker,
just the ratio swaps/comps/partitions is better for Dual-Pivot Quicksort.
If we consider common case when we have (k-1) pivots and divide an
array into k parts, we can ask, if the case k=3 (Dual-Pivot Quicksort)
is the best? May be k=4,5 are better?
It's easy to define recurrence relation for the count of operations
when k=3,4,... but mathematical conclusion will be too complex.
But to find out the answer for this question, I run pseudocode
(in Java, see attached class) for k=4,5 and got:
Quicksort with 3 pivots/4 parts: comps - 54399943
swaps - 24224254
Quicksort with 4 pivots/5 parts: comps - 57241615
swaps - 28659728
So, you can see that "3 pivots/4 parts" is better than
Classic Quicksort for swaps only, "4 pivots/5 parts" is
the looser, and "Dual-Pivot Quicksort" is real winner.
I feel it is expectable result: if we have many pivots
we spent a lot of time on sorting them and dividing into
more parts doesn't save. In case with 2 pivots, we use
only 1 comparison and 1/2 swaps to sort it out.
BTW, the dividing into 3 parts instead of two also shows
better results for MergeSort (but it's not actual for JDK
because TimSort is faster).
Ulf Zibis wrote:
Very interesting stuff.
Does one have tried (theoretically and/or experimental) P1+P2+P3,
P1+P2+P3+P2, ... segmentation ?
Maybe coefficient A has a minimum below 0.8.
-Ulf
Am 11.09.2009 12:35, Vladimir Yaroslavskiy schrieb:
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
saw
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
sure, will do it
Rémi Forax wrote:
just my two cents :
In the loop tagged "sorting" and "equals element",
a[k] can be stored in a local variable to avoid to recompute it several
time.
The algorithm use two constants: 37 and 13,
I think they should be declared as private static final.
Rémi
Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x) - an ordered copy
dither(x) - add i%5 to x[i]
Here is the result of execution:
Server VM:
http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
Client VM:
http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
Mathematical investigations
---
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
Diff between current and new implementation of Quicksort
Here is the link to the diff for java.util.Arrays class:
http://cr.openjdk.java.net/~alanb/6880672/webrev.00
If you like to look and play with new algorithm,
please, take attached class DualPivotQuicksort.java
Feedback
Also I'd like to share a feedback from Joshua Bloch and
Jon Bentley who spent a lot of time investigating this
algorithm, who gave me many advices and tips how to
make new Quicksort better.
Original Message
Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7
Date: Thu, 10 Sep 2009 07:20:11 -0700
From: Joshua Bloch
Jon also says that Vladimir should make every reasonable improvement to
the basic method before checking in the code. In his words, "It would be
horrible to put the new code into the library, and then have someone
else come along and speed it up by anothe
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Am 11.09.2009 15:32, Rémi Forax schrieb:
just my two cents :
In the loop tagged "sorting" and "equals element",
a[k] can be stored in a local variable to avoid to recompute it
several time.
I add 2 cents more:
Doesn't HotSpot see this, and optimize accordingly?
IMO: It's time that javac should do such optimization, as there are less
optimized VM's in the world.
-Ulf
The algorithm use two constants: 37 and 13,
I think they should be declared as private static final.
Rémi
Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08
2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82
3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x) - an ordered copy
dither(x) - add i%5 to x[i]
Here is the result of execution:
Server VM:
http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
Client VM:
http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
Mathematical investigations
---
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
Diff between current and new implementation of Quicksort
Here is the link to the diff for java.util.Arrays class:
http://cr.openjdk.java.net/~alanb/6880672/webrev.00
If you like to look and play with new algorithm,
please, take attached class DualPivotQuicksort.java
Feedback
Also I'd like to share a feedback from Joshua Bloch and
Jon Bentley who spent a lot of time investigating this
algorithm, who gave me many advices and tips how to
make new Quicksort better.
Original Message
Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7
Date: Thu, 10 Sep 2009 07:20:11 -0700
From: Joshua Bloch
Jon also says that Vladimir should make every reasonable im
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Hi,
I've tried to use local variable int ak = a[k] in the loop
and not found saving of time. There are 3 occurrences of a[k]
in each loop, but only two can be changed because third
comes after line: swap(a, k, great--);
As summary: I'm changing only hardcoded constant by
private static final variables.
Thank you,
Vladimir
Ulf Zibis wrote:
Am 11.09.2009 15:32, Rémi Forax schrieb:
just my two cents :
In the loop tagged "sorting" and "equals element",
a[k] can be stored in a local variable to avoid to recompute it
several time.
I add 2 cents more:
Doesn't HotSpot see this, and optimize accordingly?
IMO: It's time that javac should do such optimization, as there are less
optimized VM's in the world.
-Ulf
The algorithm use two constants: 37 and 13,
I think they should be declared as private static final.
Rémi
Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08
2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82
3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x) - an ordered copy
dither(x) - add i%5 to x[i]
Here is the result of execution:
Server VM:
http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
Client VM:
http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
Mathematical investigations
---
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
Diff between current and new implementation of Quicksort
Here is the link to the diff for java.util.Arrays class:
http://cr.openjdk.java.net/~alanb/6880672/webrev.00
If you like to look and play with new algorithm,
please, take attached class DualPivotQuicksort.java
Feedback
Also I'd like to share a feedback from Joshua Bloch and
Jon Be
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Nice.
> int third = len / div;
>
> // "medians"
> int m1 = left + third;
> int m2 = right - third;
>
> if (m1 <= left) {
> m1 = left + 1;
> }
> if (m2 >= right) {
> m2 = right - 1;
> }
I'd suggest this instead:
int third = len / div;
third=third>0?third:1;
// "medians"
int m1 = left + third;
int m2 = right - third;
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
As an observation, why not expand the new algorithm to N-Pivot where N = round(ln(array length)). This should lower the average sort cost even lower.
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Vladimir Yaroslavskiy writes: > I'd like to share with you new Dual-Pivot Quicksort which is > faster than the known implementations (theoretically and > experimental). I'd like to propose to replace the JDK's > Quicksort implementation by new one. This is a great idea; as a mathematician I immediately want to generalize it. Unfortunately, I lack the computing skill to test my generalization in practice. Suppose that instead of 2 pivots we have m (randomly chosen) pivots, where m=sqrt(n+1)-1. Step 1: Sort the m pivots, recursively. Step 2: Build a balanced binary tree from the pivots. Step 3: Sort the remaining n-m elements into (m+1) categories, using the BBT. Step 4: Sort each of the (m+1) categories, recursively. Let S(n) denote the number of steps needed for this algorithm. Calculating roughly: Step 1 requires S(m) steps. Step 2 requires m steps (it is easy since the pivots are already sorted). Step 3 requires (n-m)(log m) comparisons. Step 4 requires, on average, (m+1)S((n-m)/(m+1)) steps. m was chosen so that (n-m)/(m+1)=m, so S(n)=(m+2)S(m)+m+(n-m)(log m) <= (m+2) S(m)+ n log m. Crudely, we replace both m and m+2 by sqrt(n), to get as approximation: S(n) <= 0.5 n log n + n^0.5 [ 0.25 n^0.5 log n + n^0.25 [ 0.125 n^0.25 log n +...]]] = 0.5 n log n [1 + 0.5 + 0.25 + ...] = n log n. This appears to be better than 2 n log n. This argument can be made precise (the only really questionable issue is replacing m+2 by m) by first getting a crude but correct upper bound for 2S(m), which gets absorbed into the -mlogm term. Unfortunately, I'm not up to the detailed comparison vs. swap analysis as done by Mr. Yaroslavskiy, but it seems to me that, if nothing else, having an efficient algorithm to partition the non-pivot elements should provide a savings. Vadim Ponomarenko Dept. of Mathematics and Statistics San Diego State University
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Vadim- It would be very interesting if something along these lines could be made practical. It isn't obvious how to do step (3) in place. Either you end up allocating extra storage to do it, in which case you might as well have used a merge sort, or you end up doing some extra shuffling around of the data, in which case it is probably more expensive than the dual-partition version. Perhaps there is some technique I'm not thinking of. Cheers, Neal On Fri, Sep 11, 2009 at 3:48 PM, Vadim Ponomarenko wrote: > Vladimir Yaroslavskiy writes: > > I'd like to share with you new Dual-Pivot Quicksort which is > > faster than the known implementations (theoretically and > > experimental). I'd like to propose to replace the JDK's > > Quicksort implementation by new one. > > This is a great idea; as a mathematician I immediately want to generalize > it. > Unfortunately, I lack the computing skill to test my generalization in > practice. > > Suppose that instead of 2 pivots we have m (randomly chosen) pivots, where > m=sqrt(n+1)-1. > Step 1: Sort the m pivots, recursively. > Step 2: Build a balanced binary tree from the pivots. > Step 3: Sort the remaining n-m elements into (m+1) categories, using the > BBT. > Step 4: Sort each of the (m+1) categories, recursively. > > Let S(n) denote the number of steps needed for this algorithm. Calculating > roughly: > Step 1 requires S(m) steps. > Step 2 requires m steps (it is easy since the pivots are already sorted). > Step 3 requires (n-m)(log m) comparisons. > Step 4 requires, on average, (m+1)S((n-m)/(m+1)) steps. > > m was chosen so that (n-m)/(m+1)=m, so S(n)=(m+2)S(m)+m+(n-m)(log m) <= > (m+2) > S(m)+ n log m. Crudely, we replace both m and m+2 by sqrt(n), to get as > approximation: > S(n) <= 0.5 n log n + n^0.5 [ 0.25 n^0.5 log n + n^0.25 [ 0.125 n^0.25 log > n > +...]]] = 0.5 n log n [1 + 0.5 + 0.25 + ...] = n log n. This appears to > be > better than 2 n log n. This argument can be made precise (the only really > questionable issue is replacing m+2 by m) by first getting a crude but > correct upper bound for 2S(m), which gets absorbed into the -mlogm term. > > Unfortunately, I'm not up to the detailed comparison vs. swap analysis as > done by Mr. Yaroslavskiy, but it seems to me that, if nothing else, having > an efficient algorithm to partition the non-pivot elements should provide a > savings. > > Vadim Ponomarenko > Dept. of Mathematics and Statistics > San Diego State University > >
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
> Vadim-It would be very interesting if something along these lines could be made practical. It isn't obvious how to do step (3) in place. Either you end up allocating extra storage to do it, in which case you might as well have used a merge sort, or you end up doing some extra shuffling around of the data, in which case it is probably more expensive than the dual-partition version. Perhaps there is some technique I'm not thinking of.Cheers,Neal I didn't think of space requirements, but naively it seems to me that the two-pivot method of categorizing the non-pivot elements in place (which admittedly I don't entirely understand) would work just as well with the m-pivot method.
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
My absolutely non-scientific preliminary tests indicate Arrays.sort performs
better with the same input (5000 items) in nearly all runs (-client).
public static void main(String[] args) {
final int n = 5000;
int[] array = new int[n];
int[] array2 = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
int r = random.nextInt(n);
array[i] = r;
array2[i] = r;
}
long st1 = System.nanoTime();
Arrays.sort(array2);
long st2 = System.nanoTime();
DualPivotQuicksort.sort(array);
long end = System.nanoTime();
System.out.println(st2 - st1);
System.out.println(end - st2);
}
I tried changing which sort runs first, but the results did not change. Over
100.000 items, dual-pivot consistently beats Arrays.sort.
Well, this test is not a good reference though :)
On Fri, Sep 11, 2009 at 5:27 PM, Vladimir Iaroslavski
wrote:
> Hi,
>
> I've tried to use local variable int ak = a[k] in the loop
> and not found saving of time. There are 3 occurrences of a[k]
> in each loop, but only two can be changed because third
> comes after line: swap(a, k, great--);
>
> As summary: I'm changing only hardcoded constant by
> private static final variables.
>
> Thank you,
> Vladimir
>
>
> Ulf Zibis wrote:
>
>> Am 11.09.2009 15:32, Rémi Forax schrieb:
>>
>>> just my two cents :
>>> In the loop tagged "sorting" and "equals element",
>>> a[k] can be stored in a local variable to avoid to recompute it several
>>> time.
>>>
>>
>> I add 2 cents more:
>> Doesn't HotSpot see this, and optimize accordingly?
>> IMO: It's time that javac should do such optimization, as there are less
>> optimized VM's in the world.
>>
>> -Ulf
>>
>>
>>
>>> The algorithm use two constants: 37 and 13,
>>> I think they should be declared as private static final.
>>>
>>> Rémi
>>>
>>>
>>> Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
>>>
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = r
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Sorry :( . Please ignore previous post. Warming-up yield to better results
in dual-pivot's favor.
On Sat, Sep 12, 2009 at 2:43 PM, Goktug Gokdogan wrote:
> My absolutely non-scientific preliminary tests indicate Arrays.sort
> performs better with the same input (5000 items) in nearly all runs
> (-client).
> public static void main(String[] args) {
> final int n = 5000;
> int[] array = new int[n];
> int[] array2 = new int[n];
> Random random = new Random();
> for (int i = 0; i < n; i++) {
> int r = random.nextInt(n);
> array[i] = r;
> array2[i] = r;
> }
>
> long st1 = System.nanoTime();
> Arrays.sort(array2);
> long st2 = System.nanoTime();
> DualPivotQuicksort.sort(array);
> long end = System.nanoTime();
> System.out.println(st2 - st1);
> System.out.println(end - st2);
> }
>
> I tried changing which sort runs first, but the results did not change.
> Over 100.000 items, dual-pivot consistently beats Arrays.sort.
>
> Well, this test is not a good reference though :)
>
> On Fri, Sep 11, 2009 at 5:27 PM, Vladimir Iaroslavski > wrote:
>
>> Hi,
>>
>> I've tried to use local variable int ak = a[k] in the loop
>> and not found saving of time. There are 3 occurrences of a[k]
>> in each loop, but only two can be changed because third
>> comes after line: swap(a, k, great--);
>>
>> As summary: I'm changing only hardcoded constant by
>> private static final variables.
>>
>> Thank you,
>> Vladimir
>>
>>
>> Ulf Zibis wrote:
>>
>>> Am 11.09.2009 15:32, Rémi Forax schrieb:
>>>
just my two cents :
In the loop tagged "sorting" and "equals element",
a[k] can be stored in a local variable to avoid to recompute it several
time.
>>>
>>> I add 2 cents more:
>>> Doesn't HotSpot see this, and optimize accordingly?
>>> IMO: It's time that javac should do such optimization, as there are less
>>> optimized VM's in the world.
>>>
>>> -Ulf
>>>
>>>
>>>
The algorithm use two constants: 37 and 13,
I think they should be declared as private static final.
Rémi
Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
> Hello All,
>
> I'd like to share with you new Dual-Pivot Quicksort which is
> faster than the known implementations (theoretically and
> experimental). I'd like to propose to replace the JDK's
> Quicksort implementation by new one.
>
> Description
> ---
> The classical Quicksort algorithm uses the following scheme:
>
> 1. Pick an element P, called a pivot, from the array.
> 2. Reorder the array so that all elements, which are less than
> the pivot, come before the pivot and all elements greater than
> the pivot come after it (equal values can go either way). After
> this partitioning, the pivot element is in its final position.
> 3. Recursively sort the sub-array of lesser elements and the
> sub-array of greater elements.
>
> The invariant of classical Quicksort is:
>
> [ <= p | >= p ]
>
> There are several modifications of the schema:
>
> [ < p | = p | > p ] or [ = p | < p | > p | = p ]
>
> But all of them use *one* pivot.
>
> The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
>
> 1. Pick an elements P1, P2, called pivots from the array.
> 2. Assume that P1 <= P2, otherwise swap it.
> 3. Reorder the array into three parts: those less than the smaller
> pivot, those larger than the larger pivot, and in between are
> those elements between (or equal to) the two pivots.
> 4. Recursively sort the sub-arrays.
>
> The invariant of the Dual-Pivot Quicksort is:
>
> [ < P1 | P1 <= & <= P2 } > P2 ]
>
> The new Quicksort is faster than current implementation of Quicksort
> in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
>
> The full description of the Dual-Pivot Quicksort you can find
> on my page: http://iaroslavski.narod.ru/quicksort
>
> Performance tests
> -
> Here is result of running on different types of input data:
>
> Client VM all85% organ 0..1
> 0..4
> random ascend descend equal equal pipes random 010101
> random
> Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02
> 2.18
> Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08
> 2.49
>
> Server VM all85% organ 0..1
> 0..4
> random ascend descend equal equal pipes random 010101
> random
> Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96
> 3.41
> Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82
> 3.39
>
> The a lot of other tests have been run under client and server mode.
> The most interesting is BentleyBasher test framework. It runs battery
> of tests for all cases:
>
> { 100, 1000, 1
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
To amplify my previous statement, I think this is a great piece of work! Vladimir is to be commended. I also think that it may well get substantially faster as Vladimir continues to make minor algorithmic modifications. Jon Bentley has made many fine suggestions that Vladimir will try out.There are also some lower-level performance tweaks that may well yield improved performance (e.g., eliminate the div parameter from dualPivotQuicksort, eliminate the division from algorithm). It is, of course, possible that this performance work won't yield significant benefits, but I suspect otherwise. Josh P.S. When all of this is done, the code could use some minor reformatting to match JDK standards, but I wouldn't worry about this until the performance work is done.
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
I reviewed the code. A few simple tricks helped me to speed-up code in my
tests:1. Falling back-to insertion sort at <17 instead of <27 (JDK 6
Arrays.sort falls back <7)
2. (a[great] > pivot2) test is more likely to fail compared to (k < great)
in the while loop, so exchange them (ie. use while (a[great] > pivot2 && k <
great)).
These two changes together improved performance around 4-5 percent in my
laptop.
Hopefully, I will dig algorithm further for other suggestions; if I can
spare more time this week.
Congratulations again for your algorithm!
Goktug
On Fri, Sep 11, 2009 at 5:27 PM, Vladimir Iaroslavski
wrote:
> Hi,
>
> I've tried to use local variable int ak = a[k] in the loop
> and not found saving of time. There are 3 occurrences of a[k]
> in each loop, but only two can be changed because third
> comes after line: swap(a, k, great--);
>
> As summary: I'm changing only hardcoded constant by
> private static final variables.
>
> Thank you,
> Vladimir
>
>
> Ulf Zibis wrote:
>
>> Am 11.09.2009 15:32, Rémi Forax schrieb:
>>
>>> just my two cents :
>>> In the loop tagged "sorting" and "equals element",
>>> a[k] can be stored in a local variable to avoid to recompute it several
>>> time.
>>>
>>
>> I add 2 cents more:
>> Doesn't HotSpot see this, and optimize accordingly?
>> IMO: It's time that javac should do such optimization, as there are less
>> optimized VM's in the world.
>>
>> -Ulf
>>
>>
>>
>>> The algorithm use two constants: 37 and 13,
>>> I think they should be declared as private static final.
>>>
>>> Rémi
>>>
>>>
>>> Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :
>>>
Hello All,
I'd like to share with you new Dual-Pivot Quicksort which is
faster than the known implementations (theoretically and
experimental). I'd like to propose to replace the JDK's
Quicksort implementation by new one.
Description
---
The classical Quicksort algorithm uses the following scheme:
1. Pick an element P, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than
the pivot, come before the pivot and all elements greater than
the pivot come after it (equal values can go either way). After
this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the
sub-array of greater elements.
The invariant of classical Quicksort is:
[ <= p | >= p ]
There are several modifications of the schema:
[ < p | = p | > p ] or [ = p | < p | > p | = p ]
But all of them use *one* pivot.
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
1. Pick an elements P1, P2, called pivots from the array.
2. Assume that P1 <= P2, otherwise swap it.
3. Reorder the array into three parts: those less than the smaller
pivot, those larger than the larger pivot, and in between are
those elements between (or equal to) the two pivots.
4. Recursively sort the sub-arrays.
The invariant of the Dual-Pivot Quicksort is:
[ < P1 | P1 <= & <= P2 } > P2 ]
The new Quicksort is faster than current implementation of Quicksort
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
The full description of the Dual-Pivot Quicksort you can find
on my page: http://iaroslavski.narod.ru/quicksort
Performance tests
-
Here is result of running on different types of input data:
Client VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 16.83 5.315.47 0.35 0.68 10.59 1.06 1.02 2.18
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
Server VM all85% organ 0..1 0..4
random ascend descend equal equal pipes random 010101
random
Dual-Pivot: 23.94 6.686.63 0.43 0.62 17.14 1.42 1.96 3.41
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
The a lot of other tests have been run under client and server mode.
The most interesting is BentleyBasher test framework. It runs battery
of tests for all cases:
{ 100, 1000, 1, 100 } x
{ sawtooth, rand, stagger, plateau, shuffle } x
{ ident, reverse, reverse_front, reverse_back, sort, dither}
where
100, ... , 100 - array length
sawtooth: x[i] =i%m
rand: x[i] = rand() % m
stagger: x[i] = (i*m + i) % n
plateau: x[i] = min(i, m)
shuffle: x[i] = rand()%m? (j+=2): (k+=2)
ident(x) - a copy of x
reverse(x, 0, n) - reversed copy
reverse_front(x, 0, n/2) - front half reversed
reverse_back(x, n/2, n) - back half reversed
sort(x)
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Hello Vladimir, First thing that came to mind - have you thought about extrapolating this approach to more pivots? If 2-pivot algorithm is faster than 1-pivot, then 3-pivot might be even faster, right? Can the number of pivots be chosen as a function of array size (to mitigate overhead)? Thanks, Oleg
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
I suppose if the array is small enough, it is better to use simple Quicksort. And the larger the array, the more sense it makes to use more pivots, because the calculation cost of comparing against many pivots becomes more affordable than iterating for a larger subset. So you think the optimal number of pivots to use could be directly linked to the size of the array you're trying to sort?
Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Date: Tue, 6 Oct 2009 23:11:25 + (UTC) From: quitos Subject: Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort To: core-libs-dev@openjdk.java.net I suppose if the array is small enough, it is better to use simple Quicksort. And the larger the array, the more sense it makes to use more pivots, because the calculation cost of comparing against many pivots becomes more affordable than iterating for a larger subset. So you think the optimal number of pivots to use could be directly linked to the size of the array you're trying to sort? I've tried several cases with different numbers of pivots on different length, and experiments show that 2 pivots from 5 candidates is optimal. Note that if you have many pivots (> 3) the loop of sorting becomes more complex and slower. For small arrays the best choice is Insertion sort which is simpler and faster than any quicksort. Vladimir
