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

[Alan Bateman]

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;
                }