<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Sure.<br><br>> Date: Wed, 12 May 2010 14:12:47 +0400<br>> From: iaroslavski@mail.ru<br>> Subject: Re: New portion of improvements for Dual-Pivot Quicksort<br>> To: dmytro_sheyko@hotmail.com<br>> CC: jjb@google.com; core-libs-dev@openjdk.java.net<br>> <br>> Hello Dmytro,<br>> <br>> Could you please send new version of DPQ<br>> with your changes?<br>> <br>> Thanks,<br>> Vladimir<br>> <br>> Dmytro Sheyko wrote:<br>> > Vladimir,<br>> > <br>> > Your changes are good for me.<br>> > <br>> > Additionally I have some comments/proposals regarding dealing with <br>> > negative zeros.<br>> > <br>> > 1. Scanning for the first zero we can avoid range check (i >= left) if <br>> > 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 <br>> > not needed<br>> > + for (int i = zeroIndex - 1; /*i >= left &&*/ a[i] == 0.0f; <br>> > 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 <br>> > 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 <br>> > 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 < <br>> > 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 <br>> > 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 <br>> > 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. <br>> > "less < e1 && great > e5",<br>> > > and found that more symmetric code "less < e1 && great > e5" is <br>> > 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>