1 /*
2 * Copyright (c) 2015, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 8072909
27 * @summary Test TimSort stack size on big arrays
28 * @key intermittent
29 * @library /lib/testlibrary /test/lib
30 * @modules java.management
31 * java.base/jdk.internal
32 * @build jdk.testlibrary.*
33 * @build TimSortStackSize2
34 * @run driver ClassFileInstaller sun.hotspot.WhiteBox
35 * sun.hotspot.WhiteBox$WhiteBoxPermission
36 * @run main/othervm -Xbootclasspath/a:. -XX:+UnlockDiagnosticVMOptions
37 * -XX:+WhiteBoxAPI TimSortStackSize2
38 */
39 import java.util.ArrayList;
40 import java.util.Arrays;
41 import java.util.List;
42 import java.util.function.Consumer;
43
44 import jdk.testlibrary.OutputAnalyzer;
45 import jdk.testlibrary.ProcessTools;
46 import jdk.testlibrary.Utils;
47 import sun.hotspot.WhiteBox;
48
49 public class TimSortStackSize2 {
50
51 public static void main(String[] args) {
52 if ( args == null || args.length == 0 ){
53 startMeWithArgs();
54 } else {
55 doTestOfTwoTimSorts(Integer.parseInt(args[0]));
56 }
57 }
58
59 private static void startMeWithArgs(){
60 /*
61 * big tests not for regular execution on all platforms:
62 * run main/othervm -Xmx8g TimSortStackSize2 1073741824
63 * run main/othervm -Xmx16g TimSortStackSize2 2147483644
64 */
65 try {
66 Boolean compressedOops = WhiteBox.getWhiteBox()
67 .getBooleanVMFlag("UseCompressedOops");
68 long memory = (compressedOops == null || compressedOops) ? 385 : 770;
69 final String xmsValue = "-Xms" + memory + "m";
70 final String xmxValue = "-Xmx" + 2 * memory + "m";
71
72 System.out.printf("compressedOops: %s; Test will be started with \"%s %s\"%n",
73 compressedOops, xmsValue, xmxValue);
74 OutputAnalyzer output = ProcessTools.executeTestJava(xmsValue,
75 xmxValue,
76 "TimSortStackSize2",
77 "67108864");
78 System.out.println(output.getOutput());
79 output.shouldHaveExitValue(0);
80 } catch (Exception e) {
81 e.printStackTrace();
82 throw new RuntimeException(e);
83 }
84 }
85
86 private static void doTestOfTwoTimSorts(final int lengthOfTest){
87 boolean passed = doTest("TimSort", lengthOfTest,
88 (Integer [] a) -> Arrays.sort(a));
89 passed = doTest("ComparableTimSort", lengthOfTest, (Integer [] a) ->
90 Arrays.sort(a, (Object first, Object second) -> {
91 return ((Comparable<Object>)first).compareTo(second);
92 }))
93 && passed;
94 if ( !passed ){
95 throw new RuntimeException();
96 }
97 }
98
99 private static boolean doTest(final String msg, final int lengthOfTest,
100 final Consumer<Integer[]> c){
101 Integer [] a = null;
102 try {
103 a = new TimSortStackSize2(lengthOfTest).createArray();
104 long begin = System.nanoTime();
105 c.accept(a);
106 long end = System.nanoTime();
107 System.out.println(msg + " OK. Time: " + (end - begin) + "ns");
108 } catch (ArrayIndexOutOfBoundsException e){
109 System.out.println(msg + " broken:");
110 e.printStackTrace();
111 return false;
112 } finally {
113 a = null;
114 }
115 return true;
116 }
117
118 private static final int MIN_MERGE = 32;
119 private final int minRun;
120 private final int length;
121 private final List<Long> runs = new ArrayList<Long>();
122
123 public TimSortStackSize2(final int len) {
124 this.length = len;
125 minRun = minRunLength(len);
126 fillRunsJDKWorstCase();
127 }
128
129 private static int minRunLength(int n) {
130 assert n >= 0;
131 int r = 0; // Becomes 1 if any 1 bits are shifted off
132 while (n >= MIN_MERGE) {
133 r |= (n & 1);
134 n >>= 1;
135 }
136 return n + r;
137 }
138
139 /**
140 * Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br>
141 * 1. X = x_1 + ... + x_n <br>
142 * 2. x_j >= minRun for all j <br>
143 * 3. x_1 + ... + x_{j-2} < x_j < x_1 + ... + x_{j-1} for all j <br>
144 * These conditions guarantee that TimSort merges all x_j's one by one
145 * (resulting in X) using only merges on the second-to-last element.
146 * @param X The sum of the sequence that should be added to runs.
147 */
148 private void generateJDKWrongElem(long X) {
149 for(long newTotal; X >= 2 * minRun + 1; X = newTotal) {
150 //Default strategy
151 newTotal = X / 2 + 1;
152 //Specialized strategies
153 if(3 * minRun + 3 <= X && X <= 4*minRun+1) {
154 // add x_1=MIN+1, x_2=MIN, x_3=X-newTotal to runs
155 newTotal = 2 * minRun + 1;
156 } else if (5 * minRun + 5 <= X && X <= 6 * minRun + 5) {
157 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal to runs
158 newTotal = 3 * minRun + 3;
159 } else if (8 * minRun + 9 <= X && X <= 10 * minRun + 9) {
160 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal to runs
161 newTotal = 5 * minRun + 5;
162 } else if (13 * minRun + 15 <= X && X <= 16 * minRun + 17) {
163 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=3MIN+4, x_6=X-newTotal to runs
164 newTotal = 8 * minRun + 9;
165 }
166 runs.add(0, X - newTotal);
167 }
168 runs.add(0, X);
169 }
170
171 /**
172 * Fills <code>runs</code> with a sequence of run lengths of the form<br>
173 * Y_n x_{n,1} x_{n,2} ... x_{n,l_n} <br>
174 * Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br>
175 * ... <br>
176 * Y_1 x_{1,1} x_{1,2} ... x_{1,l_1}<br>
177 * The Y_i's are chosen to satisfy the invariant throughout execution,
178 * but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>)
179 * into an X_i that violates the invariant.
180 * X is the sum of all run lengths that will be added to <code>runs</code>.
181 */
182 private void fillRunsJDKWorstCase() {
183 long runningTotal = 0;
184 long Y = minRun + 4;
185 long X = minRun;
186
187 while (runningTotal + Y + X <= length) {
188 runningTotal += X + Y;
189 generateJDKWrongElem(X);
190 runs.add(0, Y);
191
192 // X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1}
193 X = Y + runs.get(1) + 1;
194
195 // Y_{i+1} = X_{i+1} + Y_i + 1
196 Y += X + 1;
197 }
198
199 if (runningTotal + X <= length) {
200 runningTotal += X;
201 generateJDKWrongElem(X);
202 }
203
204 runs.add(length - runningTotal);
205 }
206
207 private Integer [] createArray() {
208 Integer [] a = new Integer[length];
209 Arrays.fill(a, 0);
210 int endRun = -1;
211 for (long len : runs) {
212 a[endRun += len] = 1;
213 }
214 a[length - 1] = 0;
215 return a;
216 }
217
218 }