In fact, at first I intentionally skipped the warming-up code, thinking that
use of non-jvm optimized code could give some idea if more fine-tuning
required in the implementation. Then I realized that results also includes
the class loading times :(. So I added code that will just load classes by
sorting an empty array. After change Array.sort was still giving competitive
results at 1000 items. (points to my previous theory about fine-tuning?)
Finally, I decided give the code into hot-spots ingenious hands, dual-pivot
sorted 5000 items in about %35 shorter times.Good job!
2009/9/12 Vladimir Iaroslavski <iaroslav...@mail.ru>
> Hello,
>
> As you mentioned, warm up is needed.
> Add just several lines as here:
> ...
> Random random = new Random();
>
> DualPivotQuicksort.sort(array);
> DualPivotQuicksort.sort(array);
> Arrays.sort(array2);
> Arrays.sort(array2);
>
> for (int i = 0; i < n; i++) {
> int r = random.nextInt(n);
> array[i] = r;
> array2[i] = r;
> }
> ...
> after that I see ratio of time:
>
> 943761 - Arrays
> 534816 - DualPivotQuicksort
>
> do you?
>
> In original your version where you have only one call
> of Quicksorts, a lot of time is spent for loading classes.
>
> And I also note that it is better to run algorithms many times
> (say, 50-100 times) and take average (or minimum) time.
>
> Thank you,
> Vladimir
>
> P.S. Benchmarking in Java is "Dark Art"
>
> -----Original Message-----
> From: Goktug Gokdogan <gokdo...@gmail.com>
> To: Vladimir Iaroslavski <iaroslav...@mail.ru>
> Date: Sat, 12 Sep 2009 15:13:17 +0300
> Subject: 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 <gokdo...@gmail.com>
> 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 <
> iaroslav...@mail.ru
> > > > 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 all 85% organ 0..1
> > >>>>> 0..4
> > >>>>> random ascend descend equal equal pipes random 010101
> > >>>>> random
> > >>>>> Dual-Pivot: 16.83 5.31 5.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 all 85% organ 0..1
> > >>>>> 0..4
> > >>>>> random ascend descend equal equal pipes random 010101
> > >>>>> random
> > >>>>> Dual-Pivot: 23.94 6.68 6.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, 10000, 1000000 } x
> > >>>>> { sawtooth, rand, stagger, plateau, shuffle } x
> > >>>>> { ident, reverse, reverse_front, reverse_back, sort, dither}
> > >>>>>
> > >>>>> where
> > >>>>>
> > >>>>> 100, ... , 1000000 - 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 <j...@google.com>
> > >>>>>
> > >>>>> 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
> > >>>>> Date: Wed, 09 Sep 2009 15:02:25 -0400
> > >>>>> From: Jon Bentley <jbent...@avaya.com>
> > >>>>>
> > >>>>> Vladimir, Josh,
> > >>>>> I *finally* feel like I understand what is going on. Now that
> I
> > >>>>> (think that) I see it, it seems straightforward and obvious.
> > >>>>> Tony Hoare developed Quicksort in the early 1960s. I was very
> > >>>>> proud to make minor contributions to a particularly clean (binary)
> > >>>>> quicksort in the mid 1980s, to a relatively straightforward,
> industrial
> > >>>>> strength Quicksort with McIlroy in the early 1990s, and then to
> > >>>>> algorithms and data structures for strings with Sedgewick in the
> mid
> > >>>>> 1990s.
> > >>>>> I think that Vladimir's contributions to Quicksort go way
> beyond
> > >>>>> anything that I've ever done, and rank up there with Hoare's
> original
> > >>>>> design and Sedgewick's analysis. I feel so privileged to play a
> very,
> > >>>>> very minor role in helping Vladimir with the most excellent work!
> > >>>>>
> > >>>>> -----------------------------------------------
> > >>>>>
> > >>>>> Let me know, if you have any questions/comments.
> > >>>>>
> > >>>>> Thank you,
> > >>>>> Vladimir
>
