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