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 }