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 }