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

[Jonathan Gibbons]

Alan,

Can I suggest you do a full build of JDK on JPRT with 
SKIP_BUILD_CYCLE=false to test this fix?

-- Jon


Joshua Bloch wrote:
> 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 
> <mailto: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
>             <mailto: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/d6ca5a5e/attachment.html>