hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
|
View:
New views
6 Messages
—
Rating Filter:
Alert me
|
 |
hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
by Alan Bateman
::
Rate this Message:
Changeset: b05abb410c52
Author: alanb Date: 2009-10-29 11:18 +0000 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/b05abb410c52 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation Reviewed-by: jjb Contributed-by: vladimir.yaroslavskiy@..., joshua.bloch@..., jbentley@... ! make/java/java/FILES_java.gmk ! src/share/classes/java/util/Arrays.java + src/share/classes/java/util/DualPivotQuicksort.java |
|
|
Re: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
by jonathan.gibbons
::
Rate this Message:
Alan.Bateman@... wrote:
> Changeset: b05abb410c52 > Author: alanb > Date: 2009-10-29 11:18 +0000 > URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/b05abb410c52 > > 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation > Reviewed-by: jjb > Contributed-by: vladimir.yaroslavskiy@..., joshua.bloch@..., jbentley@... > > ! make/java/java/FILES_java.gmk > ! src/share/classes/java/util/Arrays.java > + src/share/classes/java/util/DualPivotQuicksort.java > > 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@... > finished: FAILURE > http://javac.sfbay:8080/hudson/job/jdk7.tl.langtools-jdk/80/console -- Jon |
|
|
Re: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
by Alan Bateman
::
Rate this Message:
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@... >> finished: FAILURE >> > Full log for Sun folk at: > > http://javac.sfbay:8080/hudson/job/jdk7.tl.langtools-jdk/80/console > > -- Jon 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; } |
|
|
Re: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
by Joshua Bloch-3
::
Rate this Message:
My review of this patch: looks good to me.
Josh
On Thu, Oct 29, 2009 at 4:02 PM, Alan Bateman <Alan.Bateman@...> wrote:
|
|
|
Re: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
by jonathan.gibbons
::
Rate this Message:
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. |
|
|
Re: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
by Alan Bateman
::
Rate this Message:
Jonathan Gibbons wrote:
> Alan, > > Can I suggest you do a full build of JDK on JPRT with > SKIP_BUILD_CYCLE=false to test this fix? > > -- Jon I've done that and all is well. I should say that the original changes did go through JPRT to check the build and ensure the java/util tests ran on all platforms but SKIP_BUILD_CYCLE wasn't set. I think I read on one of the mailing lists that Kelly is thinking of changing SKIP_BUILD_CYCLE to false, in which case we might catch more issues like this earlier. -Alan. |
| Free embeddable forum powered by Nabble | Forum Help |
