hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation

[Joshua Bloch]

My review of this patch: looks good to me.

      Josh

On Thu, Oct 29, 2009 at 4:02 PM, Alan Bateman <Alan.Bateman at sun.com> wrote:

> Jonathan Gibbons wrote:
>
>> :
>> Alan,
>>
>> My hudson falls over with a stack overflow at DualPivotQuicksort.java:477
>> when doing a full build (SKIP_BOOT_CYCLE=false)
>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>>    at
>>> java.util.DualPivotQuicksort.dualPivotQuicksort(DualPivotQuicksort.java:477)
>>>
>>> gnumake[4]: ***
>>> [/x/hudson/jobs/jdk7.tl.langtools-jdk/workspace/tl/build/solaris-sparc/classes/sun/text/resources/CharacterBreakIteratorData]
>>> Error 1
>>> gnumake[4]: Leaving directory
>>> `/x/hudson/jobs/jdk7.tl.langtools-jdk/workspace/tl/jdk/make/java/text'
>>> gnumake[3]: *** [all] Error 1
>>> gnumake[3]: Leaving directory
>>> `/x/hudson/jobs/jdk7.tl.langtools-jdk/workspace/tl/jdk/make/java'
>>> gnumake[2]: *** [all] Error 1
>>> gnumake[2]: Leaving directory
>>> `/x/hudson/jobs/jdk7.tl.langtools-jdk/workspace/tl/jdk/make'
>>> gnumake[1]: *** [jdk-build] Error 2
>>> gnumake[1]: Leaving directory
>>> `/x/hudson/jobs/jdk7.tl.langtools-jdk/workspace/tl'
>>> gnumake: *** [build_product_image] Error 2
>>> Sending e-mails to: jonathan.gibbons at sun.com
>>> finished: FAILURE
>>>
>>>
>> Full log for Sun folk at:
>>
>> http://javac.sfbay:8080/hudson/job/jdk7.tl.langtools-jdk/80/console
>>
>> -- Jon
>>
> Sorry about that - Vladimir also found this today and I've just created
> 6896573 to track it. The fix is attached so we'll get that in before TL
> integrates. The lesson here is that we should have included new tests with
> this (Vladimir has been developing tests to integrate - we just need to dial
> them down so that they run in a reasonable time).
>
> -Alan.
>
>
> diff -r b05abb410c52 src/share/classes/java/util/DualPivotQuicksort.java
> --- a/src/share/classes/java/util/DualPivotQuicksort.java       Thu Oct 29
> 11:18:37 2009 +0000
> +++ b/src/share/classes/java/util/DualPivotQuicksort.java       Thu Oct 29
> 22:49:11 2009 +0000
> @@ -36,7 +36,7 @@ package java.util;
>  * @author Jon Bentley
>  * @author Josh Bloch
>  *
> - * @version 2009.10.22 m765.827.v4
> + * @version 2009.10.29 m765.827.v5
>  */
> final class DualPivotQuicksort {
>
> @@ -473,9 +473,10 @@ final class DualPivotQuicksort {
>                    a[great--] = pivot2;
>                }
>            }
> -        } else { // Use Dual-Pivot Quicksort on large arrays
> -            dualPivotQuicksort(a, left, right);
> -        }
> +        }
> +
> +        // Sort center part recursively, excluding known pivot values
> +        sort(a, less, great);
>    }
>
>    /** The number of distinct short values */
> @@ -507,7 +508,7 @@ final class DualPivotQuicksort {
>            for (int i = left; i <= right; i++) {
>                count[a[i] - Short.MIN_VALUE]++;
>            }
> -            for (int i = 0, k = left; i < count.length && k < right; i++)
> {
> +            for (int i = 0, k = left; i < count.length && k <= right; i++)
> {
>                short value = (short) (i + Short.MIN_VALUE);
>
>                for (int s = count[i]; s > 0; s--) {
> @@ -723,13 +724,13 @@ final class DualPivotQuicksort {
>                a[j + 1] = ak;
>            }
>        } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
> -            // Use counting sort on large arrays
> +            // Use counting sort on huge arrays
>            int[] count = new int[NUM_BYTE_VALUES];
>
>            for (int i = left; i <= right; i++) {
>                count[a[i] - Byte.MIN_VALUE]++;
>            }
> -            for (int i = 0, k = left; i < count.length && k < right; i++)
> {
> +            for (int i = 0, k = left; i < count.length && k <= right; i++)
> {
>                byte value = (byte) (i + Byte.MIN_VALUE);
>
>                for (int s = count[i]; s > 0; s--) {
> @@ -951,7 +952,7 @@ final class DualPivotQuicksort {
>            for (int i = left; i <= right; i++) {
>                count[a[i]]++;
>            }
> -            for (int i = 0, k = left; i < count.length && k < right; i++)
> {
> +            for (int i = 0, k = left; i < count.length && k <= right; i++)
> {
>                for (int s = count[i]; s > 0; s--) {
>                    a[k++] = (char) i;
>               }
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20091029/ddec8499/attachment.html>