Sorry :( . Please ignore previous post. Warming-up yield to better results in dual-pivot's favor.<div><br><br><div class="gmail_quote">On Sat, Sep 12, 2009 at 2:43 PM, Goktug Gokdogan <span dir="ltr"><<a href="mailto:gokdogan@gmail.com">gokdogan@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">My absolutely non-scientific preliminary tests indicate Arrays.sort performs better with the same input (5000 items) in nearly all runs (-client).<div>
<span style="white-space:pre"> </span></div><div>
<span style="white-space:pre"></span><span style="white-space:pre"> </span>public static void main(String[] args) {</div><div><span style="white-space:pre"> </span>final int n = 5000;</div>
<div><span style="white-space:pre"> </span>int[] array = new int[n];</div><div><span style="white-space:pre"> </span>int[] array2 = new int[n];</div><div><span style="white-space:pre"> </span>Random random = new Random();</div>
<div><span style="white-space:pre"> </span>for (int i = 0; i < n; i++) {</div><div><span style="white-space:pre"> </span>int r = random.nextInt(n);</div><div><span style="white-space:pre"> </span>array[i] = r;</div>
<div><span style="white-space:pre"> </span>array2[i] = r;</div><div><span style="white-space:pre"> </span>}</div><div><br></div><div><span style="white-space:pre"> </span>long st1 = System.nanoTime();</div>
<div><span style="white-space:pre"> </span>Arrays.sort(array2);</div><div><span style="white-space:pre"> </span>long st2 = System.nanoTime();</div><div><span style="white-space:pre"> </span>DualPivotQuicksort.sort(array);</div>
<div><span style="white-space:pre"> </span>long end = System.nanoTime();</div><div><span style="white-space:pre"> </span>System.out.println(st2 - st1);</div><div><span style="white-space:pre"> </span>System.out.println(end - st2);</div>
<div><span style="white-space:pre"> </span>} <br><br></div><div>I tried changing which sort runs first, but the results did not change. Over 100.000 items, dual-pivot consistently beats Arrays.sort.</div>
<div><br></div><div>Well, this test is not a good reference though :) </div><div><div></div><div class="h5"><div><br><div class="gmail_quote">On Fri, Sep 11, 2009 at 5:27 PM, Vladimir Iaroslavski <span dir="ltr"><<a href="mailto:iaroslavski@mail.ru" target="_blank">iaroslavski@mail.ru</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
I've tried to use local variable int ak = a[k] in the loop<br>
and not found saving of time. There are 3 occurrences of a[k]<br>
in each loop, but only two can be changed because third<br>
comes after line: swap(a, k, great--);<br>
<br>
As summary: I'm changing only hardcoded constant by<br>
private static final variables.<br>
<br>
Thank you,<br><font color="#888888">
Vladimir</font><div><div></div><div><br>
<br>
Ulf Zibis wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Am 11.09.2009 15:32, Rémi Forax schrieb:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
just my two cents :<br>
In the loop tagged "sorting" and "equals element",<br>
a[k] can be stored in a local variable to avoid to recompute it several time.<br>
</blockquote>
<br>
I add 2 cents more:<br>
Doesn't HotSpot see this, and optimize accordingly?<br>
IMO: It's time that javac should do such optimization, as there are less optimized VM's in the world.<br>
<br>
-Ulf<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
The algorithm use two constants: 37 and 13,<br>
I think they should be declared as private static final.<br>
<br>
Rémi<br>
<br>
<br>
Le 11/09/2009 12:35, Vladimir Yaroslavskiy a écrit :<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hello All,<br>
<br>
I'd like to share with you new Dual-Pivot Quicksort which is<br>
faster than the known implementations (theoretically and<br>
experimental). I'd like to propose to replace the JDK's<br>
Quicksort implementation by new one.<br>
<br>
Description<br>
-----------<br>
The classical Quicksort algorithm uses the following scheme:<br>
<br>
1. Pick an element P, called a pivot, from the array.<br>
2. Reorder the array so that all elements, which are less than<br>
the pivot, come before the pivot and all elements greater than<br>
the pivot come after it (equal values can go either way). After<br>
this partitioning, the pivot element is in its final position.<br>
3. Recursively sort the sub-array of lesser elements and the<br>
sub-array of greater elements.<br>
<br>
The invariant of classical Quicksort is:<br>
<br>
[ <= p | >= p ]<br>
<br>
There are several modifications of the schema:<br>
<br>
[ < p | = p | > p ] or [ = p | < p | > p | = p ]<br>
<br>
But all of them use *one* pivot.<br>
<br>
The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:<br>
<br>
1. Pick an elements P1, P2, called pivots from the array.<br>
2. Assume that P1 <= P2, otherwise swap it.<br>
3. Reorder the array into three parts: those less than the smaller<br>
pivot, those larger than the larger pivot, and in between are<br>
those elements between (or equal to) the two pivots.<br>
4. Recursively sort the sub-arrays.<br>
<br>
The invariant of the Dual-Pivot Quicksort is:<br>
<br>
[ < P1 | P1 <= & <= P2 } > P2 ]<br>
<br>
The new Quicksort is faster than current implementation of Quicksort<br>
in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.<br>
<br>
The full description of the Dual-Pivot Quicksort you can find<br>
on my page: <a href="http://iaroslavski.narod.ru/quicksort" target="_blank">http://iaroslavski.narod.ru/quicksort</a><br>
<br>
Performance tests<br>
-----------------<br>
Here is result of running on different types of input data:<br>
<br>
Client VM all 85% organ 0..1 0..4<br>
random ascend descend equal equal pipes random 010101 random<br>
Dual-Pivot: 16.83 5.31 5.47 0.35 0.68 10.59 1.06 1.02 2.18<br>
Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49<br>
<br>
Server VM all 85% organ 0..1 0..4<br>
random ascend descend equal equal pipes random 010101 random<br>
Dual-Pivot: 23.94 6.68 6.63 0.43 0.62 17.14 1.42 1.96 3.41<br>
Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39<br>
<br>
The a lot of other tests have been run under client and server mode.<br>
The most interesting is BentleyBasher test framework. It runs battery<br>
of tests for all cases:<br>
<br>
{ 100, 1000, 10000, 1000000 } x<br>
{ sawtooth, rand, stagger, plateau, shuffle } x<br>
{ ident, reverse, reverse_front, reverse_back, sort, dither}<br>
<br>
where<br>
<br>
100, ... , 1000000 - array length<br>
<br>
sawtooth: x[i] =i%m<br>
rand: x[i] = rand() % m<br>
stagger: x[i] = (i*m + i) % n<br>
plateau: x[i] = min(i, m)<br>
shuffle: x[i] = rand()%m? (j+=2): (k+=2)<br>
<br>
ident(x) - a copy of x<br>
reverse(x, 0, n) - reversed copy<br>
reverse_front(x, 0, n/2) - front half reversed<br>
reverse_back(x, n/2, n) - back half reversed<br>
sort(x) - an ordered copy<br>
dither(x) - add i%5 to x[i]<br>
<br>
Here is the result of execution:<br>
Server VM: <a href="http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html" target="_blank">http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html</a> <br>
Client VM: <a href="http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html" target="_blank">http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html</a> <br>
<br>
Mathematical investigations<br>
---------------------------<br>
It is proved that for the Dual-Pivot Quicksort the average number of<br>
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),<br>
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)<br>
respectively. Full mathematical proof see in attached proof.txt<br>
and proof_add.txt files. Theoretical results are also confirmed<br>
by experimental counting of the operations.<br>
<br>
Diff between current and new implementation of Quicksort<br>
--------------------------------------------------------<br>
<br>
Here is the link to the diff for java.util.Arrays class:<br>
<a href="http://cr.openjdk.java.net/~alanb/6880672/webrev.00" target="_blank">http://cr.openjdk.java.net/~alanb/6880672/webrev.00</a><br>
<br>
If you like to look and play with new algorithm,<br>
please, take attached class DualPivotQuicksort.java<br>
<br>
Feedback<br>
--------<br>
<br>
Also I'd like to share a feedback from Joshua Bloch and<br>
Jon Bentley who spent a lot of time investigating this<br>
algorithm, who gave me many advices and tips how to<br>
make new Quicksort better.<br>
<br>
-------- Original Message --------<br>
Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7<br>
Date: Thu, 10 Sep 2009 07:20:11 -0700<br>
From: Joshua Bloch <<a href="mailto:jjb@google.com" target="_blank">jjb@google.com</a>><br>
<br>
Jon also says that Vladimir should make every reasonable improvement to<br>
the basic method before checking in the code. In his words, "It would be<br>
horrible to put the new code into the library, and then have someone<br>
else come along and speed it up by another 20% by using standard<br>
techniques." I believe it's not unlikely that this code may end up<br>
getting ported to many languages and widely deployed in much the manner<br>
of Bentley and McIlroy's fine sort (which is nearing 20 successful years<br>
in the field). Jon will help Vladimir do this.<br>
<br>
-------- Original Message --------<br>
Subject: Dual-Pivot Quicksort: Next Steps<br>
Date: Wed, 09 Sep 2009 15:02:25 -0400<br>
From: Jon Bentley <<a href="mailto:jbentley@avaya.com" target="_blank">jbentley@avaya.com</a>><br>
<br>
Vladimir, Josh,<br>
I *finally* feel like I understand what is going on. Now that I<br>
(think that) I see it, it seems straightforward and obvious.<br>
Tony Hoare developed Quicksort in the early 1960s. I was very<br>
proud to make minor contributions to a particularly clean (binary)<br>
quicksort in the mid 1980s, to a relatively straightforward, industrial<br>
strength Quicksort with McIlroy in the early 1990s, and then to<br>
algorithms and data structures for strings with Sedgewick in the mid 1990s.<br>
I think that Vladimir's contributions to Quicksort go way beyond<br>
anything that I've ever done, and rank up there with Hoare's original<br>
design and Sedgewick's analysis. I feel so privileged to play a very,<br>
very minor role in helping Vladimir with the most excellent work!<br>
<br>
-----------------------------------------------<br>
<br>
Let me know, if you have any questions/comments.<br>
<br>
Thank you,<br>
Vladimir<br>
</blockquote></blockquote></blockquote>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>