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