1/* 2 * Copyright (c) 2007, 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 * @summary micro-benchmark correctness mode 27 * @run main RemoveMicroBenchmark iterations=1 size=8 warmup=0 28 */ 29 30import java.lang.ref.WeakReference; 31import java.util.ArrayDeque; 32import java.util.Arrays; 33import java.util.ArrayList; 34import java.util.Collection; 35import java.util.Collections; 36import java.util.Deque; 37import java.util.Enumeration; 38import java.util.Iterator; 39import java.util.LinkedList; 40import java.util.List; 41import java.util.ListIterator; 42import java.util.Map; 43import java.util.PriorityQueue; 44import java.util.Queue; 45import java.util.Spliterator; 46import java.util.Vector; 47import java.util.concurrent.ArrayBlockingQueue; 48import java.util.concurrent.BlockingDeque; 49import java.util.concurrent.BlockingQueue; 50import java.util.concurrent.ConcurrentLinkedDeque; 51import java.util.concurrent.ConcurrentLinkedQueue; 52import java.util.concurrent.CountDownLatch; 53import java.util.concurrent.LinkedBlockingDeque; 54import java.util.concurrent.LinkedBlockingQueue; 55import java.util.concurrent.LinkedTransferQueue; 56import java.util.concurrent.PriorityBlockingQueue; 57import java.util.concurrent.ThreadLocalRandom; 58import java.util.concurrent.TimeUnit; 59import java.util.regex.Pattern; 60import java.util.function.Supplier; 61 62/** 63 * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS] 64 * 65 * To run this in micro-benchmark mode, simply run as a normal java program. 66 * Be patient; this program runs for a very long time. 67 * For faster runs, restrict execution using command line args. 68 * 69 * @author Martin Buchholz 70 */ 71public class RemoveMicroBenchmark { 72 abstract static class Job { 73 private final String name; 74 public Job(String name) { this.name = name; } 75 public String name() { return name; } 76 public abstract void work() throws Throwable; 77 } 78 79 final int iterations; 80 final int size; // number of elements in collections 81 final double warmupSeconds; 82 final long warmupNanos; 83 final Pattern filter; // select subset of Jobs to run 84 final boolean reverse; // reverse order of Jobs 85 final boolean shuffle; // randomize order of Jobs 86 87 RemoveMicroBenchmark(String[] args) { 88 iterations = intArg(args, "iterations", 10_000); 89 size = intArg(args, "size", 1000); 90 warmupSeconds = doubleArg(args, "warmup", 7.0); 91 filter = patternArg(args, "filter"); 92 reverse = booleanArg(args, "reverse"); 93 shuffle = booleanArg(args, "shuffle"); 94 95 warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L)); 96 } 97 98 // --------------- GC finalization infrastructure --------------- 99 100 /** No guarantees, but effective in practice. */ 101 static void forceFullGc() { 102 CountDownLatch finalizeDone = new CountDownLatch(1); 103 WeakReference<?> ref = new WeakReference<Object>(new Object() { 104 protected void finalize() { finalizeDone.countDown(); }}); 105 try { 106 for (int i = 0; i < 10; i++) { 107 System.gc(); 108 if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) { 109 System.runFinalization(); // try to pick up stragglers 110 return; 111 } 112 } 113 } catch (InterruptedException unexpected) { 114 throw new AssertionError("unexpected InterruptedException"); 115 } 116 throw new AssertionError("failed to do a \"full\" gc"); 117 } 118 119 /** 120 * Runs each job for long enough that all the runtime compilers 121 * have had plenty of time to warm up, i.e. get around to 122 * compiling everything worth compiling. 123 * Returns array of average times per job per run. 124 */ 125 long[] time0(List<Job> jobs) throws Throwable { 126 final int size = jobs.size(); 127 long[] nanoss = new long[size]; 128 for (int i = 0; i < size; i++) { 129 if (warmupNanos > 0) forceFullGc(); 130 Job job = jobs.get(i); 131 long totalTime; 132 int runs = 0; 133 long startTime = System.nanoTime(); 134 do { job.work(); runs++; } 135 while ((totalTime = System.nanoTime() - startTime) < warmupNanos); 136 nanoss[i] = totalTime/runs; 137 } 138 return nanoss; 139 } 140 141 void time(List<Job> jobs) throws Throwable { 142 if (warmupNanos > 0) time0(jobs); // Warm up run 143 final int size = jobs.size(); 144 final long[] nanoss = time0(jobs); // Real timing run 145 final long[] milliss = new long[size]; 146 final double[] ratios = new double[size]; 147 148 final String nameHeader = "Method"; 149 final String millisHeader = "Millis"; 150 final String ratioHeader = "Ratio"; 151 152 int nameWidth = nameHeader.length(); 153 int millisWidth = millisHeader.length(); 154 int ratioWidth = ratioHeader.length(); 155 156 for (int i = 0; i < size; i++) { 157 nameWidth = Math.max(nameWidth, jobs.get(i).name().length()); 158 159 milliss[i] = nanoss[i]/(1000L * 1000L); 160 millisWidth = Math.max(millisWidth, 161 String.format("%d", milliss[i]).length()); 162 163 ratios[i] = (double) nanoss[i] / (double) nanoss[0]; 164 ratioWidth = Math.max(ratioWidth, 165 String.format("%.3f", ratios[i]).length()); 166 } 167 168 String format = String.format("%%-%ds %%%dd %%%d.3f%%n", 169 nameWidth, millisWidth, ratioWidth); 170 String headerFormat = String.format("%%-%ds %%%ds %%%ds%%n", 171 nameWidth, millisWidth, ratioWidth); 172 System.out.printf(headerFormat, "Method", "Millis", "Ratio"); 173 174 // Print out absolute and relative times, calibrated against first job 175 for (int i = 0; i < size; i++) 176 System.out.printf(format, jobs.get(i).name(), milliss[i], ratios[i]); 177 } 178 179 private static String keywordValue(String[] args, String keyword) { 180 for (String arg : args) 181 if (arg.startsWith(keyword)) 182 return arg.substring(keyword.length() + 1); 183 return null; 184 } 185 186 private static int intArg(String[] args, String keyword, int defaultValue) { 187 String val = keywordValue(args, keyword); 188 return (val == null) ? defaultValue : Integer.parseInt(val); 189 } 190 191 private static double doubleArg(String[] args, String keyword, double defaultValue) { 192 String val = keywordValue(args, keyword); 193 return (val == null) ? defaultValue : Double.parseDouble(val); 194 } 195 196 private static Pattern patternArg(String[] args, String keyword) { 197 String val = keywordValue(args, keyword); 198 return (val == null) ? null : Pattern.compile(val); 199 } 200 201 private static boolean booleanArg(String[] args, String keyword) { 202 String val = keywordValue(args, keyword); 203 if (val == null || val.equals("false")) return false; 204 if (val.equals("true")) return true; 205 throw new IllegalArgumentException(val); 206 } 207 208 private static List<Job> filter(Pattern filter, List<Job> jobs) { 209 if (filter == null) return jobs; 210 ArrayList<Job> newJobs = new ArrayList<>(); 211 for (Job job : jobs) 212 if (filter.matcher(job.name()).find()) 213 newJobs.add(job); 214 return newJobs; 215 } 216 217 private static void deoptimize(int sum) { 218 if (sum == 42) 219 System.out.println("the answer"); 220 } 221 222 private static <T> List<T> asSubList(List<T> list) { 223 return list.subList(0, list.size()); 224 } 225 226 private static <T> Iterable<T> backwards(final List<T> list) { 227 return new Iterable<T>() { 228 public Iterator<T> iterator() { 229 return new Iterator<T>() { 230 final ListIterator<T> it = list.listIterator(list.size()); 231 public boolean hasNext() { return it.hasPrevious(); } 232 public T next() { return it.previous(); } 233 public void remove() { it.remove(); }};}}; 234 } 235 236 // Checks for correctness *and* prevents loop optimizations 237 class Check { 238 private int sum; 239 public void sum(int sum) { 240 if (this.sum == 0) 241 this.sum = sum; 242 if (this.sum != sum) 243 throw new AssertionError("Sum mismatch"); 244 } 245 } 246 volatile Check check = new Check(); 247 248 public static void main(String[] args) throws Throwable { 249 new RemoveMicroBenchmark(args).run(); 250 } 251 252 void run() throws Throwable { 253// System.out.printf( 254// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n", 255// iterations, size, warmupSeconds, filter); 256 257 final ArrayList<Integer> al = new ArrayList<>(size); 258 259 // Populate collections with random data 260 final ThreadLocalRandom rnd = ThreadLocalRandom.current(); 261 for (int i = 0; i < size; i++) 262 al.add(rnd.nextInt(size)); 263 264 ArrayList<Job> jobs = new ArrayList<>(); 265 266 List.<Collection<Integer>>of( 267 new ArrayList<>(), 268 new LinkedList<>(), 269 new Vector<>(), 270 new ArrayDeque<>(), 271 new PriorityQueue<>(), 272 new ArrayBlockingQueue<>(al.size()), 273 new ConcurrentLinkedQueue<>(), 274 new ConcurrentLinkedDeque<>(), 275 new LinkedBlockingQueue<>(), 276 new LinkedBlockingDeque<>(), 277 new LinkedTransferQueue<>(), 278 new PriorityBlockingQueue<>()) 279 .stream().forEach( 280 x -> { 281 String klazz = x.getClass().getSimpleName(); 282 jobs.addAll(collectionJobs(klazz, () -> x, al)); 283 if (x instanceof Queue) { 284 Queue<Integer> queue = (Queue<Integer>) x; 285 jobs.addAll(queueJobs(klazz, () -> queue, al)); 286 } 287 if (x instanceof Deque) { 288 Deque<Integer> deque = (Deque<Integer>) x; 289 jobs.addAll(dequeJobs(klazz, () -> deque, al)); 290 } 291 if (x instanceof BlockingQueue) { 292 BlockingQueue<Integer> q = (BlockingQueue<Integer>) x; 293 jobs.addAll(blockingQueueJobs(klazz, () -> q, al)); 294 } 295 if (x instanceof BlockingDeque) { 296 BlockingDeque<Integer> q = (BlockingDeque<Integer>) x; 297 jobs.addAll(blockingDequeJobs(klazz, () -> q, al)); 298 } 299 if (x instanceof List) { 300 List<Integer> list = (List<Integer>) x; 301 jobs.addAll( 302 collectionJobs( 303 klazz + " subList", 304 () -> list.subList(0, x.size()), 305 al)); 306 } 307 }); 308 309 if (reverse) Collections.reverse(jobs); 310 if (shuffle) Collections.shuffle(jobs); 311 312 time(filter(filter, jobs)); 313 } 314 315 Collection<Integer> universeRecorder(int[] sum) { 316 return new ArrayList<>() { 317 public boolean contains(Object x) { 318 sum[0] += (Integer) x; 319 return true; 320 }}; 321 } 322 323 Collection<Integer> emptyRecorder(int[] sum) { 324 return new ArrayList<>() { 325 public boolean contains(Object x) { 326 sum[0] += (Integer) x; 327 return false; 328 }}; 329 } 330 331 List<Job> collectionJobs( 332 String description, 333 Supplier<Collection<Integer>> supplier, 334 ArrayList<Integer> al) { 335 return List.of( 336 new Job(description + " removeIf") { 337 public void work() throws Throwable { 338 Collection<Integer> x = supplier.get(); 339 int[] sum = new int[1]; 340 for (int i = 0; i < iterations; i++) { 341 sum[0] = 0; 342 x.addAll(al); 343 x.removeIf(n -> { sum[0] += n; return true; }); 344 check.sum(sum[0]);}}}, 345 new Job(description + " removeIf rnd-two-pass") { 346 public void work() throws Throwable { 347 ThreadLocalRandom rnd = ThreadLocalRandom.current(); 348 Collection<Integer> x = supplier.get(); 349 int[] sum = new int[1]; 350 for (int i = 0; i < iterations; i++) { 351 sum[0] = 0; 352 x.addAll(al); 353 x.removeIf(n -> { 354 boolean b = rnd.nextBoolean(); 355 if (b) sum[0] += n; 356 return b; }); 357 x.removeIf(n -> { sum[0] += n; return true; }); 358 check.sum(sum[0]);}}}, 359 new Job(description + " removeAll") { 360 public void work() throws Throwable { 361 Collection<Integer> x = supplier.get(); 362 int[] sum = new int[1]; 363 Collection<Integer> universe = universeRecorder(sum); 364 for (int i = 0; i < iterations; i++) { 365 sum[0] = 0; 366 x.addAll(al); 367 x.removeAll(universe); 368 check.sum(sum[0]);}}}, 369 new Job(description + " retainAll") { 370 public void work() throws Throwable { 371 Collection<Integer> x = supplier.get(); 372 int[] sum = new int[1]; 373 Collection<Integer> empty = emptyRecorder(sum); 374 for (int i = 0; i < iterations; i++) { 375 sum[0] = 0; 376 x.addAll(al); 377 x.retainAll(empty); 378 check.sum(sum[0]);}}}, 379 new Job(description + " Iterator.remove") { 380 public void work() throws Throwable { 381 Collection<Integer> x = supplier.get(); 382 int[] sum = new int[1]; 383 for (int i = 0; i < iterations; i++) { 384 sum[0] = 0; 385 x.addAll(al); 386 Iterator<Integer> it = x.iterator(); 387 while (it.hasNext()) { 388 sum[0] += it.next(); 389 it.remove(); 390 } 391 check.sum(sum[0]);}}}, 392 new Job(description + " Iterator.remove-rnd-two-pass") { 393 public void work() throws Throwable { 394 ThreadLocalRandom rnd = ThreadLocalRandom.current(); 395 Collection<Integer> x = supplier.get(); 396 int[] sum = new int[1]; 397 for (int i = 0; i < iterations; i++) { 398 sum[0] = 0; 399 x.addAll(al); 400 for (Iterator<Integer> it = x.iterator(); 401 it.hasNext(); ) { 402 Integer e = it.next(); 403 if (rnd.nextBoolean()) { 404 sum[0] += e; 405 it.remove(); 406 } 407 } 408 for (Iterator<Integer> it = x.iterator(); 409 it.hasNext(); ) { 410 sum[0] += it.next(); 411 it.remove(); 412 } 413 check.sum(sum[0]);}}}, 414 new Job(description + " clear") { 415 public void work() throws Throwable { 416 Collection<Integer> x = supplier.get(); 417 int[] sum = new int[1]; 418 for (int i = 0; i < iterations; i++) { 419 sum[0] = 0; 420 x.addAll(al); 421 x.forEach(e -> sum[0] += e); 422 x.clear(); 423 check.sum(sum[0]);}}}); 424 } 425 426 List<Job> queueJobs( 427 String description, 428 Supplier<Queue<Integer>> supplier, 429 ArrayList<Integer> al) { 430 return List.of( 431 new Job(description + " poll()") { 432 public void work() throws Throwable { 433 Queue<Integer> x = supplier.get(); 434 int[] sum = new int[1]; 435 for (int i = 0; i < iterations; i++) { 436 sum[0] = 0; 437 x.addAll(al); 438 for (Integer e; (e = x.poll()) != null; ) 439 sum[0] += e; 440 check.sum(sum[0]);}}}); 441 } 442 443 List<Job> dequeJobs( 444 String description, 445 Supplier<Deque<Integer>> supplier, 446 ArrayList<Integer> al) { 447 return List.of( 448 new Job(description + " descendingIterator().remove") { 449 public void work() throws Throwable { 450 Deque<Integer> x = supplier.get(); 451 int[] sum = new int[1]; 452 for (int i = 0; i < iterations; i++) { 453 sum[0] = 0; 454 x.addAll(al); 455 Iterator<Integer> it = x.descendingIterator(); 456 while (it.hasNext()) { 457 sum[0] += it.next(); 458 it.remove(); 459 } 460 check.sum(sum[0]);}}}, 461 new Job(description + " pollFirst()") { 462 public void work() throws Throwable { 463 Deque<Integer> x = supplier.get(); 464 int[] sum = new int[1]; 465 for (int i = 0; i < iterations; i++) { 466 sum[0] = 0; 467 x.addAll(al); 468 for (Integer e; (e = x.pollFirst()) != null; ) 469 sum[0] += e; 470 check.sum(sum[0]);}}}, 471 new Job(description + " pollLast()") { 472 public void work() throws Throwable { 473 Deque<Integer> x = supplier.get(); 474 int[] sum = new int[1]; 475 for (int i = 0; i < iterations; i++) { 476 sum[0] = 0; 477 x.addAll(al); 478 for (Integer e; (e = x.pollLast()) != null; ) 479 sum[0] += e; 480 check.sum(sum[0]);}}}); 481 } 482 483 List<Job> blockingQueueJobs( 484 String description, 485 Supplier<BlockingQueue<Integer>> supplier, 486 ArrayList<Integer> al) { 487 return List.of( 488 new Job(description + " drainTo(sink)") { 489 public void work() throws Throwable { 490 BlockingQueue<Integer> x = supplier.get(); 491 ArrayList<Integer> sink = new ArrayList<>(); 492 int[] sum = new int[1]; 493 for (int i = 0; i < iterations; i++) { 494 sum[0] = 0; 495 sink.clear(); 496 x.addAll(al); 497 x.drainTo(sink); 498 sink.forEach(e -> sum[0] += e); 499 check.sum(sum[0]);}}}, 500 new Job(description + " drainTo(sink, n)") { 501 public void work() throws Throwable { 502 BlockingQueue<Integer> x = supplier.get(); 503 ArrayList<Integer> sink = new ArrayList<>(); 504 int[] sum = new int[1]; 505 for (int i = 0; i < iterations; i++) { 506 sum[0] = 0; 507 sink.clear(); 508 x.addAll(al); 509 x.drainTo(sink, al.size()); 510 sink.forEach(e -> sum[0] += e); 511 check.sum(sum[0]);}}}); 512 } 513 514 List<Job> blockingDequeJobs( 515 String description, 516 Supplier<BlockingDeque<Integer>> supplier, 517 ArrayList<Integer> al) { 518 return List.of( 519 new Job(description + " timed pollFirst()") { 520 public void work() throws Throwable { 521 BlockingDeque<Integer> x = supplier.get(); 522 int[] sum = new int[1]; 523 for (int i = 0; i < iterations; i++) { 524 sum[0] = 0; 525 x.addAll(al); 526 for (Integer e; (e = x.pollFirst(0L, TimeUnit.DAYS)) != null; ) 527 sum[0] += e; 528 check.sum(sum[0]);}}}, 529 new Job(description + " timed pollLast()") { 530 public void work() throws Throwable { 531 BlockingDeque<Integer> x = supplier.get(); 532 int[] sum = new int[1]; 533 for (int i = 0; i < iterations; i++) { 534 sum[0] = 0; 535 x.addAll(al); 536 for (Integer e; (e = x.pollLast(0L, TimeUnit.DAYS)) != null; ) 537 sum[0] += e; 538 check.sum(sum[0]);}}}); 539 } 540} 541