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