1 /*
2 * Copyright (c) 2015, 2016, 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 import java.text.*;
25 import java.util.Random;
26
27 class TreeNode {
28 public TreeNode left, right;
29 public int val; // will always be the height of the tree
30 }
31
32
33 /* Args:
34 live-data-size: in megabytes (approximate, will be rounded down).
35 work: units of mutator non-allocation work per byte allocated,
36 (in unspecified units. This will affect the promotion rate
37 printed at the end of the run: more mutator work per step implies
38 fewer steps per second implies fewer bytes promoted per second.)
39 short/long ratio: ratio of short-lived bytes allocated to long-lived
40 bytes allocated.
41 pointer mutation rate: number of pointer mutations per step.
42 steps: number of steps to do.
43 */
44
45 public class TestGCOld {
46
47 // Command-line parameters.
48
49 private static int size, workUnits, promoteRate, ptrMutRate, steps;
50
51 // Constants.
52
53 private static final int MEG = 1000000;
54 private static final int INSIGNIFICANT = 999; // this many bytes don't matter
55 private static final int BYTES_PER_WORD = 4;
56 private static final int BYTES_PER_NODE = 20; // bytes per TreeNode
57 private static final int WORDS_DEAD = 100; // size of young garbage object
58
59 private final static int treeHeight = 14;
60 private final static long treeSize = heightToBytes(treeHeight);
61
62 private static final String msg1
63 = "Usage: java TestGCOld <size> <work> <ratio> <mutation> <steps>";
64 private static final String msg2
65 = " where <size> is the live storage in megabytes";
66 private static final String msg3
67 = " <work> is the mutator work per step (arbitrary units)";
68 private static final String msg4
69 = " <ratio> is the ratio of short-lived to long-lived allocation";
70 private static final String msg5
71 = " <mutation> is the mutations per step";
72 private static final String msg6
73 = " <steps> is the number of steps";
74
75 // Counters (and global variables that discourage optimization)
76
77 private static long youngBytes = 0; // total young bytes allocated
78 private static long nodes = 0; // total tree nodes allocated
79 private static long actuallyMut = 0; // pointer mutations in old trees
80 private static long mutatorSum = 0; // checksum to discourage optimization
81 public static int[] aexport; // exported array to discourage opt
82
83 // Global variables.
84
85 private static TreeNode[] trees;
86 private static int where = 0; // roving index into trees
87 private static Random rnd = new Random();
88
89 // Returns the height of the given tree.
90
91 private static int height (TreeNode t) {
92 if (t == null) {
93 return 0;
94 }
95 else {
96 return 1 + Math.max (height (t.left), height (t.right));
97 }
98 }
99
100 // Returns the length of the shortest path in the given tree.
101
102 private static int shortestPath (TreeNode t) {
103 if (t == null) {
104 return 0;
105 }
106 else {
107 return 1 + Math.min (shortestPath (t.left), shortestPath (t.right));
108 }
109 }
110
111 // Returns the number of nodes in a balanced tree of the given height.
112
113 private static long heightToNodes (int h) {
114 if (h == 0) {
115 return 0;
116 }
117 else {
118 long n = 1;
119 while (h > 1) {
120 n = n + n;
121 h = h - 1;
122 }
123 return n + n - 1;
124 }
125 }
126
127 // Returns the number of bytes in a balanced tree of the given height.
128
129 private static long heightToBytes (int h) {
130 return BYTES_PER_NODE * heightToNodes (h);
131 }
132
133 // Returns the height of the largest balanced tree
134 // that has no more than the given number of nodes.
135
136 private static int nodesToHeight (long nodes) {
137 int h = 1;
138 long n = 1;
139 while (n + n - 1 <= nodes) {
140 n = n + n;
141 h = h + 1;
142 }
143 return h - 1;
144 }
145
146 // Returns the height of the largest balanced tree
147 // that occupies no more than the given number of bytes.
148
149 private static int bytesToHeight (long bytes) {
150 return nodesToHeight (bytes / BYTES_PER_NODE);
151 }
152
153 // Returns a newly allocated balanced binary tree of height h.
154
155 private static TreeNode makeTree(int h) {
156 if (h == 0) return null;
157 else {
158 TreeNode res = new TreeNode();
159 nodes++;
160 res.left = makeTree(h-1);
161 res.right = makeTree(h-1);
162 res.val = h;
163 return res;
164 }
165 }
166
167 // Allocates approximately size megabytes of trees and stores
168 // them into a global array.
169
170 private static void init() {
171 int ntrees = (int) ((size * MEG) / treeSize);
172 trees = new TreeNode[ntrees];
173
174 System.err.println("Allocating " + ntrees + " trees.");
175 System.err.println(" (" + (ntrees * treeSize) + " bytes)");
176 for (int i = 0; i < ntrees; i++) {
177 trees[i] = makeTree(treeHeight);
178 // doYoungGenAlloc(promoteRate*ntrees*treeSize, WORDS_DEAD);
179 }
180 System.err.println(" (" + nodes + " nodes)");
181
182 /* Allow any in-progress GC to catch up... */
183 // try { Thread.sleep(20000); } catch (InterruptedException x) {}
184 }
185
186 // Confirms that all trees are balanced and have the correct height.
187
188 private static void checkTrees() {
189 int ntrees = trees.length;
190 for (int i = 0; i < ntrees; i++) {
191 TreeNode t = trees[i];
192 int h1 = height(t);
193 int h2 = shortestPath(t);
194 if ((h1 != treeHeight) || (h2 != treeHeight)) {
195 System.err.println("*****BUG: " + h1 + " " + h2);
196 }
197 }
198 }
199
200 // Called only by replaceTree (below) and by itself.
201
202 private static void replaceTreeWork(TreeNode full, TreeNode partial, boolean dir) {
203 boolean canGoLeft = full.left != null && full.left.val > partial.val;
204 boolean canGoRight = full.right != null && full.right.val > partial.val;
205 if (canGoLeft && canGoRight) {
206 if (dir)
207 replaceTreeWork(full.left, partial, !dir);
208 else
209 replaceTreeWork(full.right, partial, !dir);
210 } else if (!canGoLeft && !canGoRight) {
211 if (dir)
212 full.left = partial;
213 else
214 full.right = partial;
215 } else if (!canGoLeft) {
216 full.left = partial;
217 } else {
218 full.right = partial;
219 }
220 }
221
222 // Given a balanced tree full and a smaller balanced tree partial,
223 // replaces an appropriate subtree of full by partial, taking care
224 // to preserve the shape of the full tree.
225
226 private static void replaceTree(TreeNode full, TreeNode partial) {
227 boolean dir = (partial.val % 2) == 0;
228 actuallyMut++;
229 replaceTreeWork(full, partial, dir);
230 }
231
232 // Allocates approximately n bytes of long-lived storage,
233 // replacing oldest existing long-lived storage.
234
235 private static void oldGenAlloc(long n) {
236 int full = (int) (n / treeSize);
237 long partial = n % treeSize;
238 // System.out.println("In oldGenAlloc, doing " + full + " full trees "
239 // + "and one partial tree of size " + partial);
240 for (int i = 0; i < full; i++) {
241 trees[where++] = makeTree(treeHeight);
242 if (where == trees.length) where = 0;
243 }
244 while (partial > INSIGNIFICANT) {
245 int h = bytesToHeight(partial);
246 TreeNode newTree = makeTree(h);
247 replaceTree(trees[where++], newTree);
248 if (where == trees.length) where = 0;
249 partial = partial - heightToBytes(h);
250 }
251 }
252
253 // Interchanges two randomly selected subtrees (of same size and depth).
254
255 private static void oldGenSwapSubtrees() {
256 // Randomly pick:
257 // * two tree indices
258 // * A depth
259 // * A path to that depth.
260 int index1 = rnd.nextInt(trees.length);
261 int index2 = rnd.nextInt(trees.length);
262 int depth = rnd.nextInt(treeHeight);
263 int path = rnd.nextInt();
264 TreeNode tn1 = trees[index1];
265 TreeNode tn2 = trees[index2];
266 for (int i = 0; i < depth; i++) {
267 if ((path & 1) == 0) {
268 tn1 = tn1.left;
269 tn2 = tn2.left;
270 } else {
271 tn1 = tn1.right;
272 tn2 = tn2.right;
273 }
274 path >>= 1;
275 }
276 TreeNode tmp;
277 if ((path & 1) == 0) {
278 tmp = tn1.left;
279 tn1.left = tn2.left;
280 tn2.left = tmp;
281 } else {
282 tmp = tn1.right;
283 tn1.right = tn2.right;
284 tn2.right = tmp;
285 }
286 actuallyMut += 2;
287 }
288
289 // Update "n" old-generation pointers.
290
291 private static void oldGenMut(long n) {
292 for (int i = 0; i < n/2; i++) {
293 oldGenSwapSubtrees();
294 }
295 }
296
297 // Does the amount of mutator work appropriate for n bytes of young-gen
298 // garbage allocation.
299
300 private static void doMutWork(long n) {
301 int sum = 0;
302 long limit = workUnits*n/10;
303 for (long k = 0; k < limit; k++) sum++;
304 // We don't want dead code elimination to eliminate the loop above.
305 mutatorSum = mutatorSum + sum;
306 }
307
308 // Allocate n bytes of young-gen garbage, in units of "nwords"
309 // words.
310
311 private static void doYoungGenAlloc(long n, int nwords) {
312 final int nbytes = nwords*BYTES_PER_WORD;
313 int allocated = 0;
314 while (allocated < n) {
315 aexport = new int[nwords];
316 /* System.err.println("Step"); */
317 allocated += nbytes;
318 }
319 youngBytes = youngBytes + allocated;
320 }
321
322 // Allocate "n" bytes of young-gen data; and do the
323 // corresponding amount of old-gen allocation and pointer
324 // mutation.
325
326 // oldGenAlloc may perform some mutations, so this code
327 // takes those mutations into account.
328
329 private static void doStep(long n) {
330 long mutations = actuallyMut;
331
332 doYoungGenAlloc(n, WORDS_DEAD);
333 doMutWork(n);
334 oldGenAlloc(n / promoteRate);
335 oldGenMut(Math.max(0L, (mutations + ptrMutRate) - actuallyMut));
336 }
337
338 public static void main(String[] args) {
339 if (args.length != 5) {
340 System.err.println(msg1);
341 System.err.println(msg2);
342 System.err.println(msg3);
343 System.err.println(msg4);
344 System.err.println(msg5);
345 System.err.println(msg6);
346 return;
347 }
348
349 size = Integer.parseInt(args[0]);
350 workUnits = Integer.parseInt(args[1]);
351 promoteRate = Integer.parseInt(args[2]);
352 ptrMutRate = Integer.parseInt(args[3]);
353 steps = Integer.parseInt(args[4]);
354
355 System.out.println(size + " megabytes of live storage");
356 System.out.println(workUnits + " work units per step");
357 System.out.println("promotion ratio is 1:" + promoteRate);
358 System.out.println("pointer mutation rate is " + ptrMutRate);
359 System.out.println(steps + " steps");
360
361 init();
362 // checkTrees();
363 youngBytes = 0;
364 nodes = 0;
365
366 System.err.println("Initialization complete...");
367
368 long start = System.currentTimeMillis();
369
370 for (int step = 0; step < steps; step++) {
371 doStep(MEG);
372 }
373
374 long end = System.currentTimeMillis();
375 float secs = ((float)(end-start))/1000.0F;
376
377 // checkTrees();
378
379 NumberFormat nf = NumberFormat.getInstance();
380 nf.setMaximumFractionDigits(1);
381 System.out.println("\nTook " + nf.format(secs) + " sec in steady state.");
382 nf.setMaximumFractionDigits(2);
383 System.out.println("Allocated " + steps + " Mb of young gen garbage"
384 + " (= " + nf.format(((float)steps)/secs) +
385 " Mb/sec)");
386 System.out.println(" (actually allocated " +
387 nf.format(((float) youngBytes)/MEG) + " megabytes)");
388 float promoted = ((float)steps) / (float)promoteRate;
389 System.out.println("Promoted " + promoted +
390 " Mb (= " + nf.format(promoted/secs) + " Mb/sec)");
391 System.out.println(" (actually promoted " +
392 nf.format(((float) (nodes * BYTES_PER_NODE))/MEG) +
393 " megabytes)");
394 if (ptrMutRate != 0) {
395 System.out.println("Mutated " + actuallyMut +
396 " pointers (= " +
397 nf.format(actuallyMut/secs) + " ptrs/sec)");
398
399 }
400 // This output serves mainly to discourage optimization.
401 System.out.println("Checksum = " + (mutatorSum + aexport.length));
402
403 }
404 }