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: iaroslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@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 <j...@google.com>:
>
> > Vladimir,
> >
> > Old:
> >
> >298 if (less < e1 && great > e5) {
> >
> > New:
> >
> >256 if (great - less > 5 * seventh) {
>
> >Regards,
> >Josh
