New portion of improvements for Dual-Pivot Quicksort
Vladimir Iaroslavski
iaroslavski at mail.ru
Wed Jun 9 12:28:43 UTC 2010
Hi,
I just compared two cases:
if (ak != ak) { // a[k] is NaN
a[k] = a[right];
a[right--] = ak;
}
and
if (Float.isNaN(ak)) {
a[k] = a[right];
a[right--] = ak;
}
The results are:
random
ak != ak: 18846
isNaN(ak): 18860
ascendant
ak != ak: 3767
isNaN(ak): 3928
descendant
ak != ak: 4185
isNaN(ak): 4264
I think we can leave ak != ak with comment that ak is NaN.
I also checked that processing NaNs at the end is not worse,
therefore, let we have this code:
while (left <= right && Float.isNaN(a[right])) {
right--;
}
for (int k = right - 1; k >= left; k--) {
float ak = a[k];
if (ak != ak) { // a[k] is NaN
a[k] = a[right];
a[right--] = ak;
}
}
and the same for double, see updated version in attachment.
Thanks,
Vladimir
Dmytro Sheyko wrote:
> Hi,
>
> From performance point of view, it does not matter whether we use
> Float.isNaN(ak) or (ak != ak). Hotspot generates the same native code.
>
> As for not skipping trailing nans, can you explain why it could be faster?
>
> Thank you,
> Dmytro Sheyko
>
> > Date: Tue, 8 Jun 2010 18:09:42 +0400
> > From: iaroslavski at mail.ru
> > Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> > To: dmytro_sheyko at hotmail.com
> > CC: core-libs-dev at openjdk.java.net
> >
> > Hello,
> >
> > Good catch! I agree with k!=p condition, but have doubt about using
> > Float.isNaN(ak) instead of ak != ak in for loop. Float.isNaN does exactly
> > the same comparison and at the same time it is called for all elements
> > of the array.
> >
> > I checked now and see that it is better to eliminate while loop,
> > and the best case is:
> >
> > for (int k = right; k >= left; k--) {
> > float ak = a[k];
> > if (ak != ak) { // a[k] is NaN
> > a[k] = a[right];
> > a[right--] = ak;
> > }
> > }
> >
> > If we have a lot of NaNs, it will be proceeded on linear time
> > and only small amount of elements will be sorted. If there are
> > no NaNs [at the end] - more probably use case - this code works
> > faster. I run simple test and it shows that case without while loop
> > is little bit faster, ~0.5%.
> >
> > Please, see attached version.
> >
> > Thank you,
> > Vladimir
> >
> > Dmytro Sheyko wrote:
> > > Hi,
> > >
> > > Coming back to NaN processing.
> > > It appeared that current code unnecessarily stirs up NaNs in the
> end of
> > > array even when they are just on their places.
> > > So I propose to replace these code
> > > /*
> > > * Phase 1: Move NaNs to the end of the array.
> > > */
> > > for (int k = left; k <= right; k++) {
> > > float ak = a[k];
> > > if (ak != ak) { // a[k] is NaN
> > > a[k--] = a[right];
> > > a[right--] = ak;
> > > }
> > > }
> > > with following
> > > /*
> > > * Phase 1: Move NaNs to the end of the array.
> > > */
> > > while (left <= right && Float.isNaN(a[right])) {
> > > right--;
> > > }
> > > for (int k = right - 1; k >= left; k--) {
> > > float ak = a[k];
> > > if (Float.isNaN(ak)) {
> > > a[k] = a[right];
> > > a[right] = ak;
> > > right--;
> > > }
> > > }
> > >
> > > Also I would like to note that while we are processing negative zeros,
> > > condition (k != p) is unnecessary.
> > >
> > > for (int k = left + 1, p = left; k <= right; k++) {
> > > float ak = a[k];
> > > if (ak != 0.0f) {
> > > return;
> > > }
> > > if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
> > > if (k != p) { // !!! always true
> > > a[k] = +0.0f;
> > > a[p] = -0.0f;
> > > }
> > > p++;
> > > }
> > > }
> > >
> > > Here k is strictly greater than p initially and then grows faster
> than p.
> > >
> > >
> > > > 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[4]: New portion of improvements for Dual-Pivot Quicksort
> > > > Date: Sat, 5 Jun 2010 23:40:31 +0400
> > > >
> > > > 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 --------------
An embedded and charset-unspecified text was scrubbed...
Name: DualPivotQuicksort.java
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100609/95f539f1/DualPivotQuicksort.java>
More information about the core-libs-dev
mailing list