<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Hello,<br><br>More ideas.<br><br>1. We can use<br>Double.doubleToRawLongBits instead of Double.doubleToLongBits and<br>Float.floatToRawIntBits instead of Float.floatToIntBits.<br>No need to handle NaN's because they all are placed to the end of array.<br><br>2. Note that<br>Double.doubleToRawLongBits(+0.0) == 0L and<br>Double.doubleToRawLongBits(-0.0) == Long.MIN_VALUE and<br>Float.floatToRawIntBits(+0.0) == 0 and<br>Float.floatToRawIntBits(-0.0) == Integer.MIN_VALUE.<br><br>Comparing with is zero usually more efficient (or at least not worse) than with other values. Thus such pattern<br><br>    if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak))<br><br>can be replaced with<br><br>    if (ak == 0.0f && Float.floatToIntBits(ak) < 0)<br><br>3. It would be more efficient to count negative zeros after sorting.<br>General sorting algorithm puts both negative and positive zeros together (but maybe not in right order).<br>Therefore we have to process less elements because usually we have less zeros than other numbers.<br><br>Thanks,<br>Dmytro Sheyko<br><br>> From: iaroslavski@mail.ru<br>> To: dmytro_sheyko@hotmail.com; jjb@google.com<br>> CC: core-libs-dev@openjdk.java.net; iaroslavski@mail.ru<br>> Subject: Re[6]: New portion of improvements for Dual-Pivot Quicksort<br>> Date: Fri, 14 May 2010 23:54:06 +0400<br>> <br>> Hello,<br>> <br>> I've updated the class, please, review the changes.<br>> <br>> Vladimir<br>> <br>> Fri, 14 May 2010 01:48:11 +0700 письмо от Dmytro Sheyko <dmytro_sheyko@hotmail.com>:<br>> <br>> > Yes. I prefer F (Find First zero using binary search) over C (Count negatives) and S (Smart Scan for zero).<br>> > <br>> > > From: iaroslavski@mail.ru<br>> > > To: dmytro_sheyko@hotmail.com<br>> > > CC: jjb@google.com; core-libs-dev@openjdk.java.net; iaroslavski@mail.ru<br>> > > Subject: Re[4]: New portion of improvements for Dual-Pivot Quicksort<br>> > > Date: Thu, 13 May 2010 21:34:54 +0400<br>> > > <br>> > > Dmytro,<br>> > > <br>> > > I've tested your suggested variants, and found that case "C"<br>> > > (very interesting approach to find first position of zero<br>> > > by counting negative elements) works slower than original<br>> > > or two other cases.<br>> > > <br>> > > Implementations "F" and "S" are very close to each other<br>> > > and little bit faster than original. I prefer case "F":<br>> > > it is shorter and more clear. Do you agree?<br>> > > <br>> > > I'll prepare updated DualPivotQuicksort file and send it<br>> > > tomorrow.<br>> > > <br>> > > Thank you,<br>> > > Vladimir<br>> > > <br>> > > Wed, 12 May 2010 17:04:52 +0700 письмо от Dmytro Sheyko <dmytro_sheyko@hotmail.com>:<br>> > > <br>> > > > Vladimir,<br>> > > > <br>> > > > Your changes are good for me.<br>> > > > <br>> > > > Additionally I have some comments/proposals regarding dealing with negative zeros.<br>> > > > <br>> > > > 1. Scanning for the first zero we can avoid range check (i >= left) if we have at least one negative value.<br>> > > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010<br>> > > > +++ DualPivotQuicksortS.java Wed May 12 12:10:46 2010<br>> > > > @@ -1705,10 +1705,15 @@<br>> > > > }<br>> > > > <br>> > > > // Find first zero element<br>> > > > - int zeroIndex = findAnyZero(a, left, n);<br>> > > > + int zeroIndex = 0;<br>> > > > <br>> > > > - for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {<br>> > > > - zeroIndex = i;<br>> > > > + if (a[left] < 0.0f) {<br>> > > > + zeroIndex = findAnyZero(a, left, n);<br>> > > > +<br>> > > > + // there is at least one negative value, so range check is not needed<br>> > > > + for (int i = zeroIndex - 1; /*i >= left &&*/ a[i] == 0.0f; i--) {<br>> > > > + zeroIndex = i;<br>> > > > + }<br>> > > > }<br>> > > > <br>> > > > // Turn the right number of positive zeros back into negative zeros<br>> > > > <br>> > > > 2. We can find the position of the first zero by counting negative values during preprocessing phase.<br>> > > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010<br>> > > > +++ DualPivotQuicksortC.java Wed May 12 12:01:24 2010<br>> > > > @@ -1678,7 +1678,7 @@<br>> > > > * Phase 1: Count negative zeros and move NaNs to end of array.<br>> > > > */ <br>> > > > final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);<br>> > > > - int numNegativeZeros = 0;<br>> > > > + int numNegativeZeros = 0, numNegativeValues = 0;<br>> > > > int n = right;<br>> > > > <br>> > > > for (int k = left; k <= n; k++) {<br>> > > > @@ -1689,6 +1689,8 @@<br>> > > > } else if (ak != ak) { // i.e., ak is NaN<br>> > > > a[k--] = a[n];<br>> > > > a[n--] = Float.NaN;<br>> > > > + } else if (ak < 0.0f) {<br>> > > > + numNegativeValues++;<br>> > > > }<br>> > > > }<br>> > > > <br>> > > > @@ -1705,7 +1707,7 @@<br>> > > > }<br>> > > > <br>> > > > // Find first zero element<br>> > > > - int zeroIndex = findAnyZero(a, left, n);<br>> > > > + int zeroIndex = numNegativeValues;<br>> > > > <br>> > > > for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {<br>> > > > zeroIndex = i;<br>> > > > <br>> > > > 3. We can use binary search to find the first zero and thus avoid linear scan.<br>> > > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010<br>> > > > +++ DualPivotQuicksortF.java Wed May 12 12:03:58 2010<br>> > > > @@ -1705,11 +1705,7 @@<br>> > > > }<br>> > > > <br>> > > > // Find first zero element<br>> > > > - int zeroIndex = findAnyZero(a, left, n);<br>> > > > -<br>> > > > - for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {<br>> > > > - zeroIndex = i;<br>> > > > - }<br>> > > > + int zeroIndex = findFirstZero(a, left, n);<br>> > > > <br>> > > > // Turn the right number of positive zeros back into negative zeros<br>> > > > for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {<br>> > > > @@ -1718,7 +1714,7 @@<br>> > > > }<br>> > > > <br>> > > > /**<br>> > > > - * Returns the index of some zero element in the specified range via<br>> > > > + * Returns the index of the first zero element in the specified range via<br>> > > > * binary search. The range is assumed to be sorted, and must contain<br>> > > > * at least one zero.<br>> > > > *<br>> > > > @@ -1726,18 +1722,17 @@<br>> > > > * @param low the index of the first element, inclusive, to be searched<br>> > > > * @param high the index of the last element, inclusive, to be searched<br>> > > > */ <br>> > > > - private static int findAnyZero(float[] a, int low, int high) {<br>> > > > - while (true) {<br>> > > > + private static int findFirstZero(float[] a, int low, int high) {<br>> > > > + while (low < high) {<br>> > > > int middle = (low + high) >>> 1;<br>> > > > float middleValue = a[middle];<br>> > > > <br>> > > > if (middleValue < 0.0f) {<br>> > > > low = middle + 1;<br>> > > > - } else if (middleValue > 0.0f) {<br>> > > > - high = middle - 1;<br>> > > > - } else { // middleValue == 0.0f<br>> > > > - return middle;<br>> > > > + } else { // middleValue >= 0.0f<br>> > > > + high = middle;<br>> > > > }<br>> > > > + return low;<br>> > > > }<br>> > > > }<br>> > > > <br>> > > > Counting negative values appeared more expensive than any other variants. <br>> > > > 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).<br>> > > > And it shows the best result if we have many zeros.<br>> > > > <br>> > > > Regards,<br>> > > > Dmytro Sheyko<br>> > > > <br>> > > > > From: iaroslavski@mail.ru<br>> > > > > To: jjb@google.com; dmytro_sheyko@hotmail.com<br>> > > > > CC: core-libs-dev@openjdk.java.net; iaroslavski@mail.ru<br>> > > > > Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort<br>> > > > > Date: Sun, 9 May 2010 23:51:27 +0400<br>> > > > > <br>> > > > > Josh,<br>> > > > > Dmytro,<br>> > > > > <br>> > > > > I have done more thoroughly testing "great - less > 5 * seventh" vs. "less < e1 && great > e5",<br>> > > > > and found that more symmetric code "less < e1 && great > e5" is little bit faster, ~0.5..0.7%<br>> > > > > on both VMs. Other code has not been changed.<br>> > > > > <br>> > > > > Please, take the latest version in attachment.<br>> > > > > <br>> > > > > Vladimir<br>> > > > > <br>> > > > > Tue, 4 May 2010 21:57:42 -0700 письмо от Joshua Bloch <jjb@google.com>:<br>> > > > > <br>> > > > > > Vladimir,<br>> > > > > > <br>> > > > > > Old:<br>> > > > > > <br>> > > > > >298 if (less < e1 && great > e5) {<br>> > > > > > <br>> > > > > > New:<br>> > > > > > <br>> > > > > >256 if (great - less > 5 * seventh) {<br>> > > > > <br>> > > > > >Regards,<br>> > > > > >Josh<br>                                     <br /><hr />Hotmail: Free, trusted and rich email service. <a href='https://signup.live.com/signup.aspx?id=60969' target='_new'>Get it now.</a></body>
</html>