Re[4]: New portion of improvements for Dual-Pivot Quicksort

[Vladimir Iaroslavski]

I tried with separate method sortPivotCandidates(...), no changes in behaviour,
but at the same time I don't see that the method makes sources much cleaner,
inline comments are enough. I attach the latest version of DPQ.

Fri, 4 Jun 2010 14:21:58 +0700 письмо от Dmytro Sheyko <dmytro_sheyko at hotmail.com>:

> Seems good,
> 
> One note. Since we gave up to sort pivot candidates in local variables, maybe we can move this out to separate procedure (in order to make sources cleaner a bit), e.g.
> 
> private static void sortPivotCandidates(double[] a, int ae1, int ae2, int ae3, int ae4, int ae5)
> 
> Hope the compiler is able to inline it without extra cost.
> 
> Thanks,
> Dmytro Sheyko
> 
> > From: iaroslavski at mail.ru
> > To: dmytro_sheyko at hotmail.com
> > CC: core-libs-dev at openjdk.java.net; iaroslavski at mail.ru
> > Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort
> > Date: Fri, 4 Jun 2010 01:17:57 +0400
> > 
> > Hello,
> > 
> > I tried your case (which is selection sort) and it works as expected: not worse
> > than "network" or "bubble" sorting. But nevertheless, the best choice is to use
> > insertion sort, I wrote more elegant implementation, see:
> > 
> > ///int ae1 = a[e1], ae3 = a[e3], ae5 = a[e5], ae2 = a[e2], ae4 = a[e4];
> > 
> > // Sort these elements using insertion sort
> > if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
> > 
> > if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
> > if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
> > }
> > if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
> > if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
> > if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
> > }
> > }
> > if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
> > if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
> > if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
> > if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
> > }
> > }
> > }
> > 
> > ///a[e1] = ae1; a[e3] = ae3; a[e5] = ae5; a[e2] = ae2; a[e4] = ae4;
> > 
> > Note that this implementation doesn't use local variables ae1, .. , ae5
> > at all, and without variables it works faster. This code is not too long,
> > extra 4 lines only. And if on client VM it works as other "network"
> > implementations, but on server VM it wins 1.2%.
> > 
> > In compare with first implementation of Dual-Pivot Quicksort, which
> > is used now in JDK 7, suggested version wins ~15% and 6% for client
> > and server modes.
> > 
> > Updated version of the class I will send tomorrow.
> > 
> > Dmytro,
> > could you please look at suggested insertion sort for 5 elements?
> > 
> > Do you have any comments/improvements? One place to be improved
> > is last two ifs "if (a[e4] < ..." and "if (a[e5] < ..." where
> > element is compared with all sorted elements, whereas we can save
> > comparisons by binary fork. But implementation becomes too complex
> > and long.
> > 
> > As it can be expected, the best sorting for small arrays is insertion,
> > then selection and then only bubble sort, even for 5 elements.
> > 
> > Best regards,
> > Vladimir
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DualPivotQuicksort.java
Type: application/octet-stream
Size: 111287 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100605/4d4b0804/DualPivotQuicksort.java>