New portion of improvements for Dual-Pivot Quicksort

[Vladimir Iaroslavski]

Hello Dmytro,

Could you please send new version of DPQ
with your changes?

Thanks,
Vladimir

Dmytro Sheyko wrote:
> Vladimir,
> 
> Your changes are good for me.
> 
> Additionally I have some comments/proposals regarding dealing with 
> 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.
>  >
>  > Please, take the latest version in attachment.
>  >
>  > Vladimir
>  >
>  > Tue, 4 May 2010 21:57:42 -0700 письмо от Joshua Bloch <jjb at google.com>:
>  >
>  > > Vladimir,
>  > >
>  > > Old:
>  > >
>  > >298 if (less < e1 && great > e5) {
>  > >
>  > > New:
>  > >
>  > >256 if (great - less > 5 * seventh) {
>  >
>  > >Regards,
>  > >Josh