New portion of improvements for Dual-Pivot Quicksort

[Dmytro Sheyko]

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
 		 	   		  
_________________________________________________________________
Hotmail: Powerful Free email with security by Microsoft.
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/83fba9ad/attachment.html>