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