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

Jonathan Gibbons Jonathan.Gibbons at Sun.COM
Fri Oct 30 00:21:30 UTC 2009

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 (SKIPBOOTCYCLE=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: *** [buildproductimage] 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🔞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.MINVALUE]++;_ _}_ _- 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.MINVALUE);_ _for (int s = count[i]; s > 0; s--) { @@ -723,13 +724,13 @@ final class DualPivotQuicksort { a[j + 1] = ak; } } else if (right - left + 1 > COUNTINGSORTTHRESHOLDFORBYTE) { - // Use counting sort on large arrays + // Use counting sort on huge arrays int[] count = new int[NUMBYTEVALUES]; for (int i = left; i <= right; i++) {_ _count[a[i] - Byte.MINVALUE]++;_ _}_ _- 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.MINVALUE);_ _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>

More information about the core-libs-dev mailing list