hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation (original) (raw)
Alan Bateman Alan.Bateman at Sun.COM
Thu Oct 29 23:02:19 UTC 2009
- Previous message: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
- Next message: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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 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 arraysdualPivotQuicksort(a, left, right);}
}// Sort center part recursively, excluding known pivot valuessort(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; }
- Previous message: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
- Next message: hg: jdk7/tl/jdk: 6880672: Replace quicksort in java.util.Arrays with dual-pivot implementation
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]