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 return concatStreams(
364 collectionJobs(x),
365
366 (isMutable(x))
367 ? mutableCollectionJobs(x)
368 : Stream.empty(),
369
370 (x instanceof Deque)
371 ? dequeJobs((Deque<Integer>)x)
372 : Stream.empty(),
373
374 (x instanceof List)
375 ? listJobs((List<Integer>)x)
376 : Stream.empty(),
377
378 (x instanceof List && isMutable(x))
379 ? mutableListJobs((List<Integer>)x)
380 : Stream.empty());
381 }
382
383 Object sneakyAdder(int[] sneakySum) {
384 return new Object() {
385 public int hashCode() { throw new AssertionError(); }
386 public boolean equals(Object z) {
387 sneakySum[0] += (int) z; return false; }};
388 }
389
390 Stream<Job> collectionJobs(Collection<Integer> x) {
391 final String klazz = goodClassName(x);
392 return Stream.of(
393 new Job(klazz + " iterate for loop") {
394 public void work() throws Throwable {
395 for (int i = 0; i < iterations; i++) {
396 int sum = 0;
397 for (Integer n : x)
398 sum += n;
399 check.sum(sum);}}},
400 new Job(klazz + " iterator().forEachRemaining()") {
401 public void work() throws Throwable {
402 int[] sum = new int[1];
403 for (int i = 0; i < iterations; i++) {
404 sum[0] = 0;
405 x.iterator().forEachRemaining(n -> sum[0] += n);
406 check.sum(sum[0]);}}},
407 new Job(klazz + " spliterator().tryAdvance()") {
408 public void work() throws Throwable {
409 int[] sum = new int[1];
410 for (int i = 0; i < iterations; i++) {
411 sum[0] = 0;
412 Spliterator<Integer> spliterator = x.spliterator();
413 do {} while (spliterator.tryAdvance(n -> sum[0] += n));
414 check.sum(sum[0]);}}},
415 new Job(klazz + " spliterator().forEachRemaining()") {
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 x.spliterator().forEachRemaining(n -> sum[0] += n);
421 check.sum(sum[0]);}}},
422 new Job(klazz + " contains") {
423 public void work() throws Throwable {
424 int[] sum = new int[1];
425 Object sneakyAdder = sneakyAdder(sum);
426 for (int i = 0; i < iterations; i++) {
427 sum[0] = 0;
428 if (x.contains(sneakyAdder)) throw new AssertionError();
429 check.sum(sum[0]);}}},
430 new Job(klazz + " containsAll") {
431 public void work() throws Throwable {
432 int[] sum = new int[1];
433 Collection<Object> sneakyAdderCollection =
434 Collections.singleton(sneakyAdder(sum));
435 for (int i = 0; i < iterations; i++) {
436 sum[0] = 0;
437 if (x.containsAll(sneakyAdderCollection))
438 throw new AssertionError();
439 check.sum(sum[0]);}}},
440 new Job(klazz + " forEach") {
441 public void work() throws Throwable {
442 int[] sum = new int[1];
443 for (int i = 0; i < iterations; i++) {
444 sum[0] = 0;
445 x.forEach(n -> sum[0] += n);
446 check.sum(sum[0]);}}},
447 new Job(klazz + " toArray()") {
448 public void work() throws Throwable {
449 int[] sum = new int[1];
450 for (int i = 0; i < iterations; i++) {
451 sum[0] = 0;
452 for (Object o : x.toArray())
453 sum[0] += (Integer) o;
454 check.sum(sum[0]);}}},
455 new Job(klazz + " toArray(a)") {
456 public void work() throws Throwable {
457 Integer[] a = new Integer[x.size()];
458 int[] sum = new int[1];
459 for (int i = 0; i < iterations; i++) {
460 sum[0] = 0;
461 x.toArray(a);
462 for (Object o : a)
463 sum[0] += (Integer) o;
464 check.sum(sum[0]);}}},
465 new Job(klazz + " toArray(empty)") {
466 public void work() throws Throwable {
467 Integer[] empty = new Integer[0];
468 int[] sum = new int[1];
469 for (int i = 0; i < iterations; i++) {
470 sum[0] = 0;
471 for (Integer o : x.toArray(empty))
472 sum[0] += o;
473 check.sum(sum[0]);}}},
474 new Job(klazz + " stream().forEach") {
475 public void work() throws Throwable {
476 int[] sum = new int[1];
477 for (int i = 0; i < iterations; i++) {
478 sum[0] = 0;
479 x.stream().forEach(n -> sum[0] += n);
480 check.sum(sum[0]);}}},
481 new Job(klazz + " stream().mapToInt") {
482 public void work() throws Throwable {
483 for (int i = 0; i < iterations; i++) {
484 check.sum(x.stream().mapToInt(e -> e).sum());}}},
485 new Job(klazz + " stream().collect") {
486 public void work() throws Throwable {
487 for (int i = 0; i < iterations; i++) {
488 check.sum(x.stream()
489 .collect(summingInt(e -> e)));}}},
490 new Job(klazz + " stream()::iterator") {
491 public void work() throws Throwable {
492 int[] sum = new int[1];
493 for (int i = 0; i < iterations; i++) {
494 sum[0] = 0;
495 for (Integer o : (Iterable<Integer>) x.stream()::iterator)
496 sum[0] += o;
497 check.sum(sum[0]);}}},
498 new Job(klazz + " parallelStream().forEach") {
499 public void work() throws Throwable {
500 for (int i = 0; i < iterations; i++) {
501 LongAdder sum = new LongAdder();
502 x.parallelStream().forEach(n -> sum.add(n));
503 check.sum((int) sum.sum());}}},
504 new Job(klazz + " parallelStream().mapToInt") {
505 public void work() throws Throwable {
506 for (int i = 0; i < iterations; i++) {
507 check.sum(x.parallelStream().mapToInt(e -> e).sum());}}},
508 new Job(klazz + " parallelStream().collect") {
509 public void work() throws Throwable {
510 for (int i = 0; i < iterations; i++) {
511 check.sum(x.parallelStream()
512 .collect(summingInt(e -> e)));}}},
513 new Job(klazz + " parallelStream()::iterator") {
514 public void work() throws Throwable {
515 int[] sum = new int[1];
516 for (int i = 0; i < iterations; i++) {
517 sum[0] = 0;
518 for (Integer o : (Iterable<Integer>) x.parallelStream()::iterator)
519 sum[0] += o;
520 check.sum(sum[0]);}}});
521 }
522
523 Stream<Job> mutableCollectionJobs(Collection<Integer> x) {
524 final String klazz = goodClassName(x);
525 return Stream.of(
526 new Job(klazz + " removeIf") {
527 public void work() throws Throwable {
528 int[] sum = new int[1];
529 for (int i = 0; i < iterations; i++) {
530 sum[0] = 0;
531 if (x.removeIf(n -> { sum[0] += n; return false; }))
532 throw new AssertionError();
533 check.sum(sum[0]);}}},
534 new Job(klazz + " remove(Object)") {
535 public void work() throws Throwable {
536 int[] sum = new int[1];
537 Object sneakyAdder = sneakyAdder(sum);
538 for (int i = 0; i < iterations; i++) {
539 sum[0] = 0;
540 if (x.remove(sneakyAdder)) throw new AssertionError();
541 check.sum(sum[0]);}}});
542 }
543
544 Stream<Job> dequeJobs(Deque<Integer> x) {
545 final String klazz = goodClassName(x);
546 return Stream.of(
547 new Job(klazz + " descendingIterator() loop") {
548 public void work() throws Throwable {
549 for (int i = 0; i < iterations; i++) {
550 int sum = 0;
551 Iterator<Integer> it = x.descendingIterator();
552 while (it.hasNext())
553 sum += it.next();
554 check.sum(sum);}}},
555 new Job(klazz + " descendingIterator().forEachRemaining()") {
556 public void work() throws Throwable {
557 int[] sum = new int[1];
558 for (int i = 0; i < iterations; i++) {
559 sum[0] = 0;
560 x.descendingIterator().forEachRemaining(n -> sum[0] += n);
561 check.sum(sum[0]);}}});
562 }
563
564 Stream<Job> listJobs(List<Integer> x) {
565 final String klazz = goodClassName(x);
566 return Stream.of(
567 new Job(klazz + " listIterator forward loop") {
568 public void work() throws Throwable {
569 for (int i = 0; i < iterations; i++) {
570 int sum = 0;
571 ListIterator<Integer> it = x.listIterator();
572 while (it.hasNext())
573 sum += it.next();
574 check.sum(sum);}}},
575 new Job(klazz + " listIterator backward loop") {
576 public void work() throws Throwable {
577 for (int i = 0; i < iterations; i++) {
578 int sum = 0;
579 ListIterator<Integer> it = x.listIterator(x.size());
580 while (it.hasPrevious())
581 sum += it.previous();
582 check.sum(sum);}}},
583 new Job(klazz + " indexOf") {
584 public void work() throws Throwable {
585 int[] sum = new int[1];
586 Object sneakyAdder = sneakyAdder(sum);
587 for (int i = 0; i < iterations; i++) {
588 sum[0] = 0;
589 if (x.indexOf(sneakyAdder) != -1)
590 throw new AssertionError();
591 check.sum(sum[0]);}}},
592 new Job(klazz + " lastIndexOf") {
593 public void work() throws Throwable {
594 int[] sum = new int[1];
595 Object sneakyAdder = sneakyAdder(sum);
596 for (int i = 0; i < iterations; i++) {
597 sum[0] = 0;
598 if (x.lastIndexOf(sneakyAdder) != -1)
599 throw new AssertionError();
600 check.sum(sum[0]);}}},
601 new Job(klazz + " equals") {
602 public void work() throws Throwable {
603 ArrayList<Integer> copy = new ArrayList<>(x);
604 for (int i = 0; i < iterations; i++) {
605 if (!x.equals(copy))
606 throw new AssertionError();}}},
607 new Job(klazz + " hashCode") {
608 public void work() throws Throwable {
609 int hashCode = Arrays.hashCode(x.toArray());
610 for (int i = 0; i < iterations; i++) {
611 if (x.hashCode() != hashCode)
612 throw new AssertionError();}}});
613 }
614
615 Stream<Job> mutableListJobs(List<Integer> x) {
616 final String klazz = goodClassName(x);
617 return Stream.of(
618 new Job(klazz + " replaceAll") {
619 public void work() throws Throwable {
620 int[] sum = new int[1];
621 UnaryOperator<Integer> sneakyAdder =
622 x -> { sum[0] += x; return x; };
623 for (int i = 0; i < iterations; i++) {
624 sum[0] = 0;
625 x.replaceAll(sneakyAdder);
626 check.sum(sum[0]);}}});
627 }
628 }