Mercurial > hg > release > icedtea8-forest-3.0 > jdk
changeset 10742:e51553af95fc
8073124: Tune test and document TimSort runs length stack size increase
Reviewed-by: dholmes
author | lpriima |
---|---|
date | Mon, 16 Feb 2015 19:16:50 -0500 |
parents | 09ade42f6dca |
children | 7b91e9e3034d |
files | src/share/classes/java/util/ComparableTimSort.java src/share/classes/java/util/TimSort.java test/java/util/Arrays/TimSortStackSize2.java |
diffstat | 3 files changed, 24 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/util/ComparableTimSort.java Thu Feb 12 10:34:35 2015 -0500 +++ b/src/share/classes/java/util/ComparableTimSort.java Mon Feb 16 19:16:50 2015 -0500 @@ -144,6 +144,10 @@ * large) stack lengths for smaller arrays. The "magic numbers" in the * computation below must be changed if MIN_MERGE is decreased. See * the MIN_MERGE declaration above for more information. + * The maximum value of 49 allows for an array up to length + * Integer.MAX_VALUE-4, if array is filled by the worst case stack size + * increasing scenario. More explanations are given in section 4 of: + * http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf */ int stackLen = (len < 120 ? 5 : len < 1542 ? 10 :
--- a/src/share/classes/java/util/TimSort.java Thu Feb 12 10:34:35 2015 -0500 +++ b/src/share/classes/java/util/TimSort.java Mon Feb 16 19:16:50 2015 -0500 @@ -174,6 +174,10 @@ * large) stack lengths for smaller arrays. The "magic numbers" in the * computation below must be changed if MIN_MERGE is decreased. See * the MIN_MERGE declaration above for more information. + * The maximum value of 49 allows for an array up to length + * Integer.MAX_VALUE-4, if array is filled by the worst case stack size + * increasing scenario. More explanations are given in section 4 of: + * http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf */ int stackLen = (len < 120 ? 5 : len < 1542 ? 10 :
--- a/test/java/util/Arrays/TimSortStackSize2.java Thu Feb 12 10:34:35 2015 -0500 +++ b/test/java/util/Arrays/TimSortStackSize2.java Mon Feb 16 19:16:50 2015 -0500 @@ -24,10 +24,10 @@ /* * @test * @bug 8072909 - * @run main/othervm TimSortStackSize2 67108864 + * @run main/othervm -Xmx385m TimSortStackSize2 67108864 * not for regular execution on all platforms: * run main/othervm -Xmx8g TimSortStackSize2 1073741824 - * run main/othervm -Xmx32g TimSortStackSize2 2147483644 + * run main/othervm -Xmx16g TimSortStackSize2 2147483644 * @summary Test TimSort stack size on big arrays */ import java.util.ArrayList; @@ -41,22 +41,30 @@ int lengthOfTest = Integer.parseInt(args[0]); boolean passed = true; try { - Arrays.sort(new TimSortStackSize2(lengthOfTest).createArray(), - new Comparator<Object>() { + Integer [] a = new TimSortStackSize2(lengthOfTest).createArray(); + long begin = System.nanoTime(); + Arrays.sort(a, new Comparator<Object>() { @SuppressWarnings("unchecked") public int compare(Object first, Object second) { return ((Comparable<Object>)first).compareTo(second); } }); - System.out.println("TimSort OK"); + long end = System.nanoTime(); + System.out.println("TimSort: " + (end - begin)); + a = null; } catch (ArrayIndexOutOfBoundsException e){ - System.out.println("TimSort broken"); + System.out.println("TimSort broken:"); e.printStackTrace(); passed = false; } + try { - Arrays.sort(new TimSortStackSize2(lengthOfTest).createArray()); - System.out.println("ComparableTimSort OK"); + Integer [] a = new TimSortStackSize2(lengthOfTest).createArray(); + long begin = System.nanoTime(); + Arrays.sort(a); + long end = System.nanoTime(); + System.out.println("ComparableTimSort: " + (end - begin)); + a = null; } catch (ArrayIndexOutOfBoundsException e){ System.out.println("ComparableTimSort broken:"); e.printStackTrace();