# New portion of improvements for Dual-Pivot Quicksort

Dmytro Sheyko dmytro_sheyko at hotmail.com
Wed May 12 11:18:18 UTC 2010

```Sure.

> Date: Wed, 12 May 2010 14:12:47 +0400
> From: iaroslavski at mail.ru
> Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> To: dmytro_sheyko at hotmail.com
> CC: jjb at google.com; core-libs-dev at openjdk.java.net
>
> Hello Dmytro,
>
> Could you please send new version of DPQ
>
> Thanks,
>
> Dmytro Sheyko wrote:
> >
> > Your changes are good for me.
> >
> > negative zeros.
> >
> > 1. Scanning for the first zero we can avoid range check (i >= left) if
> > we have at least one negative value.
> > --- DualPivotQuicksort.java    Tue May 11 09:04:19 2010
> > +++ DualPivotQuicksortS.java    Wed May 12 12:10:46 2010
> > @@ -1705,10 +1705,15 @@
> >          }
> >
> >          // Find first zero element
> > -        int zeroIndex = findAnyZero(a, left, n);
> > +        int zeroIndex = 0;
> >
> > -        for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
> > -            zeroIndex = i;
> > +        if (a[left] < 0.0f) {
> > +            zeroIndex = findAnyZero(a, left, n);
> > +
> > +            // there is at least one negative value, so range check is
> > not needed
> > +            for (int i = zeroIndex - 1; /*i >= left &&*/ a[i] == 0.0f;
> > i--) {
> > +                zeroIndex = i;
> > +            }
> >          }
> >
> >          // Turn the right number of positive zeros back into negative zeros
> >
> > 2. We can find the position of the first zero by counting negative
> > values during preprocessing phase.
> > --- DualPivotQuicksort.java    Tue May 11 09:04:19 2010
> > +++ DualPivotQuicksortC.java    Wed May 12 12:01:24 2010
> > @@ -1678,7 +1678,7 @@
> >           * Phase 1: Count negative zeros and move NaNs to end of array.
> >           */
> >          final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
> > -        int numNegativeZeros = 0;
> > +        int numNegativeZeros = 0, numNegativeValues = 0;
> >          int n = right;
> >
> >          for (int k = left; k <= n; k++) {
> > @@ -1689,6 +1689,8 @@
> >              } else if (ak != ak) { // i.e., ak is NaN
> >                  a[k--] = a[n];
> >                  a[n--] = Float.NaN;
> > +            } else if (ak < 0.0f) {
> > +                numNegativeValues++;
> >              }
> >          }
> >
> > @@ -1705,7 +1707,7 @@
> >          }
> >
> >          // Find first zero element
> > -        int zeroIndex = findAnyZero(a, left, n);
> > +        int zeroIndex = numNegativeValues;
> >
> >          for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
> >              zeroIndex = i;
> >
> > 3. We can use binary search to find the first zero and thus avoid linear
> > scan.
> > --- DualPivotQuicksort.java    Tue May 11 09:04:19 2010
> > +++ DualPivotQuicksortF.java    Wed May 12 12:03:58 2010
> > @@ -1705,11 +1705,7 @@
> >          }
> >
> >          // Find first zero element
> > -        int zeroIndex = findAnyZero(a, left, n);
> > -
> > -        for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
> > -            zeroIndex = i;
> > -        }
> > +        int zeroIndex = findFirstZero(a, left, n);
> >
> >          // Turn the right number of positive zeros back into negative zeros
> >          for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i <
> > m; i++) {
> > @@ -1718,7 +1714,7 @@
> >      }
> >
> >      /**
> > -     * Returns the index of some zero element in the specified range via
> > +     * Returns the index of the first zero element in the specified
> > range via
> >       * binary search. The range is assumed to be sorted, and must contain
> >       * at least one zero.
> >       *
> > @@ -1726,18 +1722,17 @@
> >       * @param low the index of the first element, inclusive, to be searched
> >       * @param high the index of the last element, inclusive, to be searched
> >       */
> > -    private static int findAnyZero(float[] a, int low, int high) {
> > -        while (true) {
> > +    private static int findFirstZero(float[] a, int low, int high) {
> > +        while (low < high) {
> >              int middle = (low + high) >>> 1;
> >              float middleValue = a[middle];
> >
> >              if (middleValue < 0.0f) {
> >                  low = middle + 1;
> > -            } else if (middleValue > 0.0f) {
> > -                high = middle - 1;
> > -            } else { // middleValue == 0.0f
> > -                return middle;
> > +            } else { // middleValue >= 0.0f
> > +                high = middle;
> >              }
> > +            return low;
> >          }
> >      }
> >
> > Counting negative values appeared more expensive than any other variants.
> > The last proposal seems to me as efficient as the current solution is in
> > its worst case - when we have only one negative zero (in the half of array).
> > And it shows the best result if we have many zeros.
> >
> > Regards,
> > Dmytro Sheyko
> >
> >  > From: iaroslavski at mail.ru
> >  > To: jjb at google.com; 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: Sun, 9 May 2010 23:51:27 +0400
> >  >
> >  > Josh,
> >  > Dmytro,
> >  >
> >  > I have done more thoroughly testing "great - less > 5 * seventh" vs.
> > "less < e1 && great > e5",
> >  > and found that more symmetric code "less < e1 && great > e5" is
> > little bit faster, ~0.5..0.7%
> >  > on both VMs. Other code has not been changed.
> >  >
> >  >
> >  >
> >  > Tue, 4 May 2010 21:57:42 -0700 письмо от Joshua Bloch <jjb at google.com>:
> >  >
> >  > >
> >  > > Old:
> >  > >
> >  > >298 if (less < e1 && great > e5) {
> >  > >
> >  > > New:
> >  > >
> >  > >256 if (great - less > 5 * seventh) {
> >  >
> >  > >Regards,
> >  > >Josh

_________________________________________________________________
Hotmail: Free, trusted and rich email service.
https://signup.live.com/signup.aspx?id=60969
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100512/a9a49939/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dpq.zip
Type: application/x-zip-compressed
Size: 20912 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100512/a9a49939/dpq.zip>
```