<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Hi Vladimir,<br><br>I tried to figure out why the testcase failed on my modification. It appeared that number of negative zeros were changed during general sort.<br>As I can see you already fixed this issue. Well, my modification was based on assumption that we can speed up eliminating explicit array range checks.<br>However, such assumption is wrong because Hotspot anyway emits range checks at its discretion and therefore processZeros generally does not work as fast as I expected.<br>So complications I made are not worth doing.<br><br>As for the latest code you posted. Doesn't it make sense to skip leading negative zeros before farther processing? In this case we avoid unnecessary assigning +0.0 and then -0.0 to the same location a[k] (i.e. where k == p).<br><br> <br> /*<br> * Skip the last negative value (if any) or all leading negative zeros<br> */<br> while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {<br> left++;<br> }<br><br> for (int k = left + 1, p = left; k <= right; k++) {<br> double ak = a[k];<br> if (ak != 0.0d) {<br> return;<br> }<br> if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d<br> a[k] = 0.0d;<br> a[p++] = -0.0d;<br> }<br> }<br><br>Thank you,<br>Dmytro Sheyko<br><br><br>> Date: Wed, 19 May 2010 14:41:32 +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: core-libs-dev@openjdk.java.net<br>> <br>> resend the class with correct constructor<br>> <br>> Vladimir Iaroslavski wrote:<br>> > Dmytro,<br>> > <br>> > Thank you for comments, I updated double method, did little bit<br>> > javadoc changes and replaced in char/short/byte methods<br>> > "fromIndex -> left", "toIndex-1 -> right", the code became<br>> > consistent with main sort method and more compact. Also I use<br>> > more usual "i--" and "i++" in for loops (instead of "--i", "++i.<br>> > <br>> > To accent the difference between float/double and other types,<br>> > I put comment where it is important:<br>> > <br>> > /*<br>> > * In spite of a[great] == pivot1, the assignment<br>> > * a[less++] = pivot1 may be incorrect, if a[great]<br>> > * and pivot1 are floating-point zeros of different<br>> > * signs, therefore in float/double methods we have<br>> > * to use more accurate assignment a[k] = a[great].<br>> > */<br>> > a[less++] = pivot1;<br>> > <br>> > and for double/float:<br>> > <br>> > /*<br>> > .....<br>> > */<br>> > a[k] = a[great];<br>> > <br>> > See updated version in attachment.<br>> > <br>> > Thank you,<br>> > Vladimir<br>> > <br>> > Dmytro Sheyko wrote:<br>> >> Vladimir,<br>> >><br>> >> I can see that you changed sortNegZeroAndNaN(float[]...) but probably <br>> >> forgot to change sortNegZeroAndNaN(double[]...).<br>> >><br>> >> You really puzzled me with failed testcase and note that sorting <br>> >> algorithm (without special attention to zeros) generally may change <br>> >> number of negative zeros.<br>> >> I will provide my comments later.<br>> >><br>> >> As for counting sort, I think we should use single format style over <br>> >> the file (unless we have valuable reason not to do this). I mean to <br>> >> choose<br>> >> 1)<br>> >> if (toIndex - fromIndex > <br>> >> COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {<br>> >> countingSort(a, fromIndex, toIndex);<br>> >> return;<br>> >> }<br>> >> sort(a, fromIndex, toIndex - 1, true);<br>> >> 2)<br>> >> if (toIndex - fromIndex > <br>> >> COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {<br>> >> countingSort(a, fromIndex, toIndex);<br>> >> } else {<br>> >> sort(a, fromIndex, toIndex - 1, true);<br>> >> }<br>> >> I prefer the second one.<br>> >><br>> >> Thanks a lot,<br>> >> Dmytro Sheyko<br>> >><br>> >> > Date: Tue, 18 May 2010 18:57:50 +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: core-libs-dev@openjdk.java.net<br>> >> ><br>> >> > Hello,<br>> >> ><br>> >> > I've run your modification for counting sort, it real faster.<br>> >> > I attached new version with your changes (I did little bit<br>> >> > format it) and included my case with float/double.<br>> >> ><br>> >> > Note that you modification doesn't pass test from Sorting class,<br>> >> > which I sent earlier. It fails on float/double test:<br>> >> ><br>> >> > Test #3: random = 666, len = 34, a = 0, g = 6, z = 9, n = 10, p = 9<br>> >> ><br>> >> > I suggest shorter method (which is based on your idea to skip counting<br>> >> > negative zeros on Phase 1.): I found find first zero index (or it will<br>> >> > be index of first positive element if no zeros at all, or last <br>> >> negative,<br>> >> > if no positive and zero elements) and then swap negative zero to the<br>> >> > beginning of the sub-range.<br>> >> ><br>> >> > int hi = right;<br>> >> ><br>> >> > while (left < hi) {<br>> >> > int middle = (left + hi) >>> 1;<br>> >> > float middleValue = a[middle];<br>> >> ><br>> >> > if (middleValue < 0.0f) {<br>> >> > left = middle + 1;<br>> >> > } else {<br>> >> > hi = middle;<br>> >> > }<br>> >> > }<br>> >> ><br>> >> > for (int k = left, p = left; k <= right; k++) {<br>> >> > float ak = a[k];<br>> >> > if (ak != 0.0f) {<br>> >> > return;<br>> >> > }<br>> >> > if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f<br>> >> > a[k] = +0.0f;<br>> >> > a[p++] = -0.0f;<br>> >> > }<br>> >> > }<br>> >> ><br>> >> > Important note: in partitioning loop there are several places<br>> >> > (marked by // !) where potential bug with -0.0 could be<br>> >> > (when pivot and a[great] are zeros with different signs):<br>> >> ><br>> >> > if (a[great] == pivot1) {<br>> >> > a[k] = a[less];<br>> >> > - a[less++] = pivot1; // !<br>> >> > + a[less++] = a[great];<br>> >> > } else { // pivot1 < a[great] < pivot2<br>> >> > a[k] = a[great];<br>> >> > }<br>> >> > - a[great--] = pivot2; // !<br>> >> > + a[great--] = ak;<br>> >> > } else if (ak == pivot1) { // Move a[k] to left part<br>> >> > a[k] = a[less];<br>> >> > - a[less++] = pivot1; // !<br>> >> > + a[less++] = ak;<br>> >> > }<br>> >> ><br>> >> > and the same in "Pivots are equal" branch.<br>> >> ><br>> >> > I did changes "pivot1/2 -> ak" in methods for all types<br>> >> > and "pivot1 -> a[great]" in float/double sections only.<br>> >> ><br>> >> > Please, review format changes for counting sort and new version<br>> >> > of Phase 3 for float/double.<br>> >> ><br>> >> > Thank you,<br>> >> > Vladimir<br>> >> ><br>> >> > Dmytro Sheyko wrote:<br>> >> > > Hi,<br>> >> > ><br>> >> > > About counting sort again.<br>> >> > ><br>> >> > > 1. This condition "i < count.length && k <= right" is excessive. <br>> >> Any one<br>> >> > > conjunct is enough. "k <= right" seems better.<br>> >> > > 2. No need to calculate "short value = (short) (i + <br>> >> Short.MIN_VALUE)"<br>> >> > > when "count[i]" is zero.<br>> >> > > 3. For signed primitives (byte and short) we would better loop <br>> >> backward.<br>> >> > > Thanks to "k >= fromIndex" condition we will quit looping earlier<br>> >> > > assuming that typically we work with positive numbers.<br>> >> > > For unsigned primitives (char) we would better loop forward because<br>> >> > > typically we work with characters about zero (ASCII).<br>> >> > ><br>> >> > > - for (int i = 0, k = left; i < count.length && k <= right; i++) {<br>> >> > > - short value = (short) (i + Short.MIN_VALUE);<br>> >> > > - for (int s = count[i]; s > 0; s--) {<br>> >> > > - a[k++] = value;<br>> >> > > - }<br>> >> > > - }<br>> >> > ><br>> >> > > + for (int i = NUM_SHORT_VALUES - 1, k = toIndex - 1; k >=<br>> >> > > fromIndex; --i) {<br>> >> > > + while (count[i] == 0) --i;<br>> >> > > + short value = (short) (i + Short.MIN_VALUE);<br>> >> > > + int s = count[i];<br>> >> > > + do { a[k--] = value; } while (--s > 0);<br>> >> > > + }<br>> >> > ><br>> >> > > Thanks,<br>> >> > > Dmytro Sheyko<br>> >> > ><br>> >> > > > From: iaroslavski@mail.ru<br>> >> > > > To: 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 <br>> >> Quicksort<br>> >> > > > Date: Tue, 18 May 2010 01:11:19 +0400<br>> >> > > ><br>> >> > > > Sounds good!<br>> >> > > > Will consider too...<br>> >> > > ><br>> >> > > > Mon, 17 May 2010 22:24:11 +0700 письмо от Dmytro Sheyko<br>> >> > > <dmytro_sheyko@hotmail.com>:<br>> >> > > ><br>> >> > > > > Hi,<br>> >> > > > ><br>> >> > > > > Regarding counting sort. We can check whether we should <br>> >> switch to<br>> >> > > counting sort only once in the beginning.<br>> >> > > > ><br>> >> > > > > > Date: Mon, 17 May 2010 17:30:37 +0400<br>> >> > > > > > From: iaroslavski@mail.ru<br>> >> > > > > > Subject: Re: New portion of improvements for Dual-Pivot <br>> >> Quicksort<br>> >> > > > > > To: dmytro_sheyko@hotmail.com<br>> >> > > > > > CC: core-libs-dev@openjdk.java.net<br>> >> > > > > ><br>> >> > > > > > Hello,<br>> >> > > > > ><br>> >> > > > > > Thank you for review, I'll check and run tests again with you<br>> >> > > changes.<br>> >> > > > > ><br>> >> > > > > > Thank you,<br>> >> > > > > > Vladimir<br>> >> > > > > ><br>> >> > > > > > Dmytro Sheyko wrote:<br>> >> > > > > > > Hello,<br>> >> > > > > > ><br>> >> > > > > > > More ideas.<br>> >> > > > > > ><br>> >> > > > > > > 1. We can use<br>> >> > > > > > > Double.doubleToRawLongBits instead of <br>> >> Double.doubleToLongBits and<br>> >> > > > > > > Float.floatToRawIntBits instead of Float.floatToIntBits.<br>> >> > > > > > > No need to handle NaN's because they all are placed to <br>> >> the end<br>> >> > > 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 <br>> >> least not<br>> >> > > worse)<br>> >> > > > > > > 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<br>> >> > > sorting.<br>> >> > > > > > > General sorting algorithm puts both negative and positive <br>> >> zeros<br>> >> > > together<br>> >> > > > > > > (but maybe not in right order).<br>> >> > > > > > > Therefore we have to process less elements because <br>> >> usually we<br>> >> > > have less<br>> >> > > > > > > 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<br>> >> > > 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<br>> >> > > > > > > <dmytro_sheyko@hotmail..com>:<br>> >> > > > > > > ><br>> >> > > > > > > > > Yes. I prefer F (Find First zero using binary search) <br>> >> over<br>> >> > > C (Count<br>> >> > > > > > > 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;<br>> >> > > > > > > iaroslavski@mail.ru<br>> >> > > > > > > > > > Subject: Re[4]: New portion of improvements for<br>> >> > > 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 <br>> >> case "C"<br>> >> > > > > > > > > > (very interesting approach to find first position <br>> >> of zero<br>> >> > > > > > > > > > by counting negative elements) works slower than <br>> >> original<br>> >> > > > > > > > > > or two other cases.<br>> >> > > > > > > > > ><br>> >> > > > > > > > > > Implementations "F" and "S" are very close to each <br>> >> other<br>> >> > > > > > > > > > and little bit faster than original. I prefer case <br>> >> "F":<br>> >> > > > > > > > > > it is shorter and more clear. Do you agree?<br>> >> > > > > > > > > ><br>> >> > > > > > > > > > I'll prepare updated DualPivotQuicksort file and <br>> >> send it<br>> >> > > > > > > > > > tomorrow.<br>> >> > > > > > > > > ><br>> >> > > > > > > > > > Thank you,<br>> >> > > > > > > > > > Vladimir<br>> >> > > > > > > > > ><br>> >> > > > > > > > > > Wed, 12 May 2010 17:04:52 +0700 письмо от Dmytro <br>> >> Sheyko<br>> >> > > > > > > <dmytro_sheyko@hotmail.com>:<br>> >> > > > > > > > > ><br>> >> > > > > > > > > > > Vladimir,<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > Your changes are good for me.<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > Additionally I have some comments/proposals <br>> >> regarding<br>> >> > > dealing<br>> >> > > > > > > with negative zeros.<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > 1. Scanning for the first zero we can avoid range <br>> >> check<br>> >> > > (i >=<br>> >> > > > > > > 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 <br>> >> 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] ==<br>> >> > > 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<br>> >> > > check is<br>> >> > > > > > > not needed<br>> >> > > > > > > > > > > + for (int i = zeroIndex - 1; /*i >= left &&*/ <br>> >> a[i] ==<br>> >> > > 0.0f; i--) {<br>> >> > > > > > > > > > > + zeroIndex = i;<br>> >> > > > > > > > > > > + }<br>> >> > > > > > > > > > > }<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > // Turn the right number of positive zeros back into<br>> >> > > negative zeros<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > 2. We can find the position of the first zero by <br>> >> counting<br>> >> > > > > > > negative values during preprocessing phase.<br>> >> > > > > > > > > > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010<br>> >> > > > > > > > > > > +++ DualPivotQuicksortC.java Wed May 12 12:01:24 <br>> >> 2010<br>> >> > > > > > > > > > > @@ -1678,7 +1678,7 @@<br>> >> > > > > > > > > > > * Phase 1: Count negative zeros and move NaNs to <br>> >> end of<br>> >> > > array.<br>> >> > > > > > > > > > > */<br>> >> > > > > > > > > > > final int NEGATIVE_ZERO = <br>> >> 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] == <br>> >> 0.0f;<br>> >> > > i--) {<br>> >> > > > > > > > > > > zeroIndex = i;<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > 3. We can use binary search to find the first <br>> >> zero and<br>> >> > > thus<br>> >> > > > > > > avoid linear scan.<br>> >> > > > > > > > > > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010<br>> >> > > > > > > > > > > +++ DualPivotQuicksortF.java Wed May 12 12:03:58 <br>> >> 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] ==<br>> >> > > 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<br>> >> > > negative zeros<br>> >> > > > > > > > > > > for (int i = zeroIndex, m = zeroIndex +<br>> >> > > numNegativeZeros; i <<br>> >> > > > > > > m; i++) {<br>> >> > > > > > > > > > > @@ -1718,7 +1714,7 @@<br>> >> > > > > > > > > > > }<br>> >> > > > > > > > > > ><br>> >> > > > > > > > > > > /**<br>> >> > > > > > > > > > > - * Returns the index of some zero element in the<br>> >> > > specified<br>> >> > > > > > > range via<br>> >> > > > > > > > > > > + * Returns the index of the first zero element <br>> >> in the<br>> >> > > > > > > specified range via<br>> >> > > > > > > > > > > * binary search. The range is assumed to be <br>> >> sorted, and<br>> >> > > must<br>> >> > > > > > > contain<br>> >> > > > > > > > > > > * at least one zero.<br>> >> > > > > > > > > > > *<br>> >> > > > > > > > > > > @@ -1726,18 +1722,17 @@<br>> >> > > > > > > > > > > * @param low the index of the first element, <br>> >> inclusive,<br>> >> > > to be<br>> >> > > > > > > searched<br>> >> > > > > > > > > > > * @param high the index of the last element, <br>> >> inclusive,<br>> >> > > to be<br>> >> > > > > > > searched<br>> >> > > > > > > > > > > */<br>> >> > > > > > > > > > > - private static int findAnyZero(float[] a, int low,<br>> >> > > int high) {<br>> >> > > > > > > > > > > - while (true) {<br>> >> > > > > > > > > > > + private static int findFirstZero(float[] a, int <br>> >> low,<br>> >> > > 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 <br>> >> than<br>> >> > > any other<br>> >> > > > > > > variants.<br>> >> > > > > > > > > > > The last proposal seems to me as efficient as the <br>> >> current<br>> >> > > > > > > solution is in its worst case - when we have only one <br>> >> negative<br>> >> > > zero (in<br>> >> > > > > > > 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; <br>> >> iaroslavski@mail.ru<br>> >> > > > > > > > > > > > Subject: Re[2]: New portion of improvements for<br>> >> > > Dual-Pivot<br>> >> > > > > > > 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 - <br>> >> less > 5 *<br>> >> > > > > > > seventh" vs. "less < e1 && great > e5",<br>> >> > > > > > > > > > > > and found that more symmetric code "less < e1 &&<br>> >> > > great > e5"<br>> >> > > > > > > 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 <br>> >> Bloch<br>> >> > > > > > > <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>