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 30import static java.util.stream.Collectors.summingInt; 31 32import java.lang.ref.WeakReference; 33import java.util.ArrayDeque; 34import java.util.Arrays; 35import java.util.ArrayList; 36import java.util.Collection; 37import java.util.Collections; 38import java.util.Deque; 39import java.util.Enumeration; 40import java.util.Iterator; 41import java.util.LinkedList; 42import java.util.List; 43import java.util.ListIterator; 44import java.util.Map; 45import java.util.PriorityQueue; 46import java.util.Spliterator; 47import java.util.Vector; 48import java.util.concurrent.ArrayBlockingQueue; 49import java.util.concurrent.ConcurrentLinkedDeque; 50import java.util.concurrent.ConcurrentLinkedQueue; 51import java.util.concurrent.LinkedBlockingDeque; 52import java.util.concurrent.LinkedBlockingQueue; 53import java.util.concurrent.LinkedTransferQueue; 54import java.util.concurrent.PriorityBlockingQueue; 55import java.util.concurrent.ConcurrentSkipListMap; 56import java.util.concurrent.CountDownLatch; 57import java.util.concurrent.ThreadLocalRandom; 58import java.util.concurrent.TimeUnit; 59import java.util.regex.Pattern; 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 */ 72public 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 filter; // 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 filter = 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 List<Job> filter(Pattern filter, List<Job> jobs) { 210 if (filter == null) return jobs; 211 ArrayList<Job> newJobs = new ArrayList<>(); 212 for (Job job : jobs) 213 if (filter.matcher(job.name()).find()) 214 newJobs.add(job); 215 return newJobs; 216 } 217 218 private static void deoptimize(int sum) { 219 if (sum == 42) 220 System.out.println("the answer"); 221 } 222 223 private static <T> List<T> asSubList(List<T> list) { 224 return list.subList(0, list.size()); 225 } 226 227 private static <T> Iterable<T> backwards(final List<T> list) { 228 return new Iterable<T>() { 229 public Iterator<T> iterator() { 230 return new Iterator<T>() { 231 final ListIterator<T> it = list.listIterator(list.size()); 232 public boolean hasNext() { return it.hasPrevious(); } 233 public T next() { return it.previous(); } 234 public void remove() { it.remove(); }};}}; 235 } 236 237 // Checks for correctness *and* prevents loop optimizations 238 class Check { 239 private int sum; 240 public void sum(int sum) { 241 if (this.sum == 0) 242 this.sum = sum; 243 if (this.sum != sum) 244 throw new AssertionError("Sum mismatch"); 245 } 246 } 247 volatile Check check = new Check(); 248 249 public static void main(String[] args) throws Throwable { 250 new IteratorMicroBenchmark(args).run(); 251 } 252 253 void run() throws Throwable { 254// System.out.printf( 255// "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n", 256// iterations, size, warmupSeconds, filter); 257 258 final ArrayList<Integer> al = new ArrayList<>(size); 259 260 // Populate collections with random data 261 final ThreadLocalRandom rnd = ThreadLocalRandom.current(); 262 for (int i = 0; i < size; i++) 263 al.add(rnd.nextInt(size)); 264 265 final ArrayDeque<Integer> ad = new ArrayDeque<>(al); 266 final ArrayBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(al.size()); 267 abq.addAll(al); 268 269 // shuffle circular array elements so they wrap 270 for (int i = 0, n = rnd.nextInt(size); i < n; i++) { 271 ad.addLast(ad.removeFirst()); 272 abq.add(abq.remove()); 273 } 274 275 ArrayList<Job> jobs = new ArrayList<>(Arrays.asList()); 276 277 List.of(al, ad, abq, 278 new LinkedList<>(al), 279 new PriorityQueue<>(al), 280 new Vector<>(al), 281 new ConcurrentLinkedQueue<>(al), 282 new ConcurrentLinkedDeque<>(al), 283 new LinkedBlockingQueue<>(al), 284 new LinkedBlockingDeque<>(al), 285 new LinkedTransferQueue<>(al), 286 new PriorityBlockingQueue<>(al)) 287 .stream() 288 .forEach(x -> { 289 jobs.addAll(collectionJobs(x)); 290 if (x instanceof Deque) 291 jobs.addAll(dequeJobs((Deque<Integer>)x)); 292 }); 293 294 if (reverse) Collections.reverse(jobs); 295 if (shuffle) Collections.shuffle(jobs); 296 297 time(filter(filter, jobs)); 298 } 299 300 List<Job> collectionJobs(Collection<Integer> x) { 301 String klazz = x.getClass().getSimpleName(); 302 return List.of( 303 new Job(klazz + " iterate for loop") { 304 public void work() throws Throwable { 305 for (int i = 0; i < iterations; i++) { 306 int sum = 0; 307 for (Integer n : x) 308 sum += n; 309 check.sum(sum);}}}, 310 new Job(klazz + " iterator().forEachRemaining()") { 311 public void work() throws Throwable { 312 int[] sum = new int[1]; 313 for (int i = 0; i < iterations; i++) { 314 sum[0] = 0; 315 x.iterator().forEachRemaining(n -> sum[0] += n); 316 check.sum(sum[0]);}}}, 317 new Job(klazz + " spliterator().tryAdvance()") { 318 public void work() throws Throwable { 319 int[] sum = new int[1]; 320 for (int i = 0; i < iterations; i++) { 321 sum[0] = 0; 322 Spliterator<Integer> spliterator = x.spliterator(); 323 do {} while (spliterator.tryAdvance(n -> sum[0] += n)); 324 check.sum(sum[0]);}}}, 325 new Job(klazz + " spliterator().forEachRemaining()") { 326 public void work() throws Throwable { 327 int[] sum = new int[1]; 328 for (int i = 0; i < iterations; i++) { 329 sum[0] = 0; 330 x.spliterator().forEachRemaining(n -> sum[0] += n); 331 check.sum(sum[0]);}}}, 332 new Job(klazz + " removeIf") { 333 public void work() throws Throwable { 334 int[] sum = new int[1]; 335 for (int i = 0; i < iterations; i++) { 336 sum[0] = 0; 337 if (x.removeIf(n -> { sum[0] += n; return false; })) 338 throw new AssertionError(); 339 check.sum(sum[0]);}}}, 340 new Job(klazz + " contains") { 341 public void work() throws Throwable { 342 int[] sum = new int[1]; 343 Object y = new Object() { 344 public boolean equals(Object z) { 345 sum[0] += (int) z; return false; }}; 346 for (int i = 0; i < iterations; i++) { 347 sum[0] = 0; 348 if (x.contains(y)) throw new AssertionError(); 349 check.sum(sum[0]);}}}, 350 new Job(klazz + " remove(Object)") { 351 public void work() throws Throwable { 352 int[] sum = new int[1]; 353 Object y = new Object() { 354 public boolean equals(Object z) { 355 sum[0] += (int) z; return false; }}; 356 for (int i = 0; i < iterations; i++) { 357 sum[0] = 0; 358 if (x.remove(y)) throw new AssertionError(); 359 check.sum(sum[0]);}}}, 360 new Job(klazz + " forEach") { 361 public void work() throws Throwable { 362 int[] sum = new int[1]; 363 for (int i = 0; i < iterations; i++) { 364 sum[0] = 0; 365 x.forEach(n -> sum[0] += n); 366 check.sum(sum[0]);}}}, 367 new Job(klazz + " toArray()") { 368 public void work() throws Throwable { 369 int[] sum = new int[1]; 370 for (int i = 0; i < iterations; i++) { 371 sum[0] = 0; 372 for (Object o : x.toArray()) 373 sum[0] += (Integer) o; 374 check.sum(sum[0]);}}}, 375 new Job(klazz + " toArray(a)") { 376 public void work() throws Throwable { 377 Integer[] a = new Integer[x.size()]; 378 int[] sum = new int[1]; 379 for (int i = 0; i < iterations; i++) { 380 sum[0] = 0; 381 x.toArray(a); 382 for (Object o : a) 383 sum[0] += (Integer) o; 384 check.sum(sum[0]);}}}, 385 new Job(klazz + " toArray(empty)") { 386 public void work() throws Throwable { 387 Integer[] empty = new Integer[0]; 388 int[] sum = new int[1]; 389 for (int i = 0; i < iterations; i++) { 390 sum[0] = 0; 391 for (Integer o : x.toArray(empty)) 392 sum[0] += o; 393 check.sum(sum[0]);}}}, 394 new Job(klazz + " stream().collect") { 395 public void work() throws Throwable { 396 for (int i = 0; i < iterations; i++) { 397 check.sum(x.stream() 398 .collect(summingInt(e -> e)));}}}, 399 new Job(klazz + " parallelStream().collect") { 400 public void work() throws Throwable { 401 for (int i = 0; i < iterations; i++) { 402 check.sum(x.parallelStream() 403 .collect(summingInt(e -> e)));}}}); 404 } 405 406 List<Job> dequeJobs(Deque<Integer> x) { 407 String klazz = x.getClass().getSimpleName(); 408 return List.of( 409 new Job(klazz + " descendingIterator() loop") { 410 public void work() throws Throwable { 411 for (int i = 0; i < iterations; i++) { 412 int sum = 0; 413 Iterator<Integer> it = x.descendingIterator(); 414 while (it.hasNext()) 415 sum += it.next(); 416 check.sum(sum);}}}, 417 new Job(klazz + " descendingIterator().forEachRemaining()") { 418 public void work() throws Throwable { 419 int[] sum = new int[1]; 420 for (int i = 0; i < iterations; i++) { 421 sum[0] = 0; 422 x.descendingIterator().forEachRemaining(n -> sum[0] += n); 423 check.sum(sum[0]);}}}); 424 } 425} 426