J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright (c) 2007 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 21 | * have any questions. |
| 22 | */ |
| 23 | |
| 24 | /* |
| 25 | * This is not a regression test, but a micro-benchmark. |
| 26 | * Be patient; this runs for half an hour! |
| 27 | * |
| 28 | * I have run this as follows: |
| 29 | * |
| 30 | * for f in -client -server; do mergeBench dolphin . jr -dsa -da $f IteratorMicroBenchmark.java; done |
| 31 | * |
| 32 | * |
| 33 | * @author Martin Buchholz |
| 34 | */ |
| 35 | |
| 36 | import java.util.*; |
| 37 | import java.util.concurrent.*; |
| 38 | import java.util.regex.Pattern; |
| 39 | |
| 40 | public class IteratorMicroBenchmark { |
| 41 | abstract static class Job { |
| 42 | private final String name; |
| 43 | public Job(String name) { this.name = name; } |
| 44 | public String name() { return name; } |
| 45 | public abstract void work() throws Throwable; |
| 46 | } |
| 47 | |
| 48 | private static void collectAllGarbage() { |
| 49 | final java.util.concurrent.CountDownLatch drained |
| 50 | = new java.util.concurrent.CountDownLatch(1); |
| 51 | try { |
| 52 | System.gc(); // enqueue finalizable objects |
| 53 | new Object() { protected void finalize() { |
| 54 | drained.countDown(); }}; |
| 55 | System.gc(); // enqueue detector |
| 56 | drained.await(); // wait for finalizer queue to drain |
| 57 | System.gc(); // cleanup finalized objects |
| 58 | } catch (InterruptedException e) { throw new Error(e); } |
| 59 | } |
| 60 | |
| 61 | /** |
| 62 | * Runs each job for long enough that all the runtime compilers |
| 63 | * have had plenty of time to warm up, i.e. get around to |
| 64 | * compiling everything worth compiling. |
| 65 | * Returns array of average times per job per run. |
| 66 | */ |
| 67 | private static long[] time0(Job ... jobs) throws Throwable { |
| 68 | final long warmupNanos = 10L * 1000L * 1000L * 1000L; |
| 69 | long[] nanoss = new long[jobs.length]; |
| 70 | for (int i = 0; i < jobs.length; i++) { |
| 71 | collectAllGarbage(); |
| 72 | long t0 = System.nanoTime(); |
| 73 | long t; |
| 74 | int j = 0; |
| 75 | do { jobs[i].work(); j++; } |
| 76 | while ((t = System.nanoTime() - t0) < warmupNanos); |
| 77 | nanoss[i] = t/j; |
| 78 | } |
| 79 | return nanoss; |
| 80 | } |
| 81 | |
| 82 | private static void time(Job ... jobs) throws Throwable { |
| 83 | |
| 84 | long[] warmup = time0(jobs); // Warm up run |
| 85 | long[] nanoss = time0(jobs); // Real timing run |
| 86 | long[] milliss = new long[jobs.length]; |
| 87 | double[] ratios = new double[jobs.length]; |
| 88 | |
| 89 | final String nameHeader = "Method"; |
| 90 | final String millisHeader = "Millis"; |
| 91 | final String ratioHeader = "Ratio"; |
| 92 | |
| 93 | int nameWidth = nameHeader.length(); |
| 94 | int millisWidth = millisHeader.length(); |
| 95 | int ratioWidth = ratioHeader.length(); |
| 96 | |
| 97 | for (int i = 0; i < jobs.length; i++) { |
| 98 | nameWidth = Math.max(nameWidth, jobs[i].name().length()); |
| 99 | |
| 100 | milliss[i] = nanoss[i]/(1000L * 1000L); |
| 101 | millisWidth = Math.max(millisWidth, |
| 102 | String.format("%d", milliss[i]).length()); |
| 103 | |
| 104 | ratios[i] = (double) nanoss[i] / (double) nanoss[0]; |
| 105 | ratioWidth = Math.max(ratioWidth, |
| 106 | String.format("%.3f", ratios[i]).length()); |
| 107 | } |
| 108 | |
| 109 | String format = String.format("%%-%ds %%%dd %%%d.3f%%n", |
| 110 | nameWidth, millisWidth, ratioWidth); |
| 111 | String headerFormat = String.format("%%-%ds %%%ds %%%ds%%n", |
| 112 | nameWidth, millisWidth, ratioWidth); |
| 113 | System.out.printf(headerFormat, "Method", "Millis", "Ratio"); |
| 114 | |
| 115 | // Print out absolute and relative times, calibrated against first job |
| 116 | for (int i = 0; i < jobs.length; i++) |
| 117 | System.out.printf(format, jobs[i].name(), milliss[i], ratios[i]); |
| 118 | } |
| 119 | |
| 120 | private static String keywordValue(String[] args, String keyword) { |
| 121 | for (String arg : args) |
| 122 | if (arg.startsWith(keyword)) |
| 123 | return arg.substring(keyword.length() + 1); |
| 124 | return null; |
| 125 | } |
| 126 | |
| 127 | private static int intArg(String[] args, String keyword, int defaultValue) { |
| 128 | String val = keywordValue(args, keyword); |
| 129 | return val == null ? defaultValue : Integer.parseInt(val); |
| 130 | } |
| 131 | |
| 132 | private static Pattern patternArg(String[] args, String keyword) { |
| 133 | String val = keywordValue(args, keyword); |
| 134 | return val == null ? null : Pattern.compile(val); |
| 135 | } |
| 136 | |
| 137 | private static Job[] filter(Pattern filter, Job[] jobs) { |
| 138 | if (filter == null) return jobs; |
| 139 | Job[] newJobs = new Job[jobs.length]; |
| 140 | int n = 0; |
| 141 | for (Job job : jobs) |
| 142 | if (filter.matcher(job.name()).find()) |
| 143 | newJobs[n++] = job; |
| 144 | // Arrays.copyOf not available in JDK 5 |
| 145 | Job[] ret = new Job[n]; |
| 146 | System.arraycopy(newJobs, 0, ret, 0, n); |
| 147 | return ret; |
| 148 | } |
| 149 | |
| 150 | private static void deoptimize(int sum) { |
| 151 | if (sum == 42) |
| 152 | System.out.println("the answer"); |
| 153 | } |
| 154 | |
| 155 | private static <T> List<T> asSubList(List<T> list) { |
| 156 | return list.subList(0, list.size()); |
| 157 | } |
| 158 | |
| 159 | private static <T> Iterable<T> backwards(final List<T> list) { |
| 160 | return new Iterable<T>() { |
| 161 | public Iterator<T> iterator() { |
| 162 | return new Iterator<T>() { |
| 163 | final ListIterator<T> it = list.listIterator(list.size()); |
| 164 | public boolean hasNext() { return it.hasPrevious(); } |
| 165 | public T next() { return it.previous(); } |
| 166 | public void remove() { it.remove(); }};}}; |
| 167 | } |
| 168 | |
| 169 | /** |
| 170 | * Usage: [iterations=N] [size=N] [filter=REGEXP] |
| 171 | */ |
| 172 | public static void main(String[] args) throws Throwable { |
| 173 | final int iterations = intArg(args, "iterations", 100000); |
| 174 | final int size = intArg(args, "size", 1000); |
| 175 | final Pattern filter = patternArg(args, "filter"); |
| 176 | |
| 177 | final ConcurrentSkipListMap<Integer,Integer> m |
| 178 | = new ConcurrentSkipListMap<Integer,Integer>(); |
| 179 | final Vector<Integer> v = new Vector<Integer>(size); |
| 180 | final ArrayList<Integer> al = new ArrayList<Integer>(size); |
| 181 | |
| 182 | // Populate collections with random data |
| 183 | final Random rnd = new Random(); |
| 184 | for (int i = 0; i < size; i++) { |
| 185 | m.put(rnd.nextInt(size), rnd.nextInt(size)); |
| 186 | v.add(rnd.nextInt(size)); |
| 187 | } |
| 188 | al.addAll(v); |
| 189 | |
| 190 | // Also test "short" collections |
| 191 | final int shortSize = 5; |
| 192 | final Vector<Integer> sv = new Vector<Integer>(v.subList(0, shortSize)); |
| 193 | final ArrayList<Integer> sal = new ArrayList<Integer>(sv); |
| 194 | |
| 195 | // Checks for correctness *and* prevents loop optimizations |
| 196 | class Check { |
| 197 | private int sum; |
| 198 | public void sum(int sum) { |
| 199 | if (this.sum == 0) |
| 200 | this.sum = sum; |
| 201 | if (this.sum != sum) |
| 202 | throw new AssertionError("Sum mismatch"); |
| 203 | } |
| 204 | } |
| 205 | final Check check = new Check(); |
| 206 | final Check shortCheck = new Check(); |
| 207 | |
| 208 | Job[] jobs = { |
| 209 | // new Job("Vector iterate desugared") { |
| 210 | // public void work() throws Throwable { |
| 211 | // for (int i = 0; i < iterations; i++) { |
| 212 | // int sum = 0; |
| 213 | // for (Iterator<Integer> it = v.iterator(); it.hasNext();) |
| 214 | // sum += it.next(); |
| 215 | // check.sum(sum);}}}, |
| 216 | new Job("array loop") { |
| 217 | public void work() throws Throwable { |
| 218 | Integer[] a = al.toArray(new Integer[0]); |
| 219 | for (int i = 0; i < iterations; i++) { |
| 220 | int sum = 0; |
| 221 | int size = a.length; |
| 222 | for (int j = 0; j < size; ++j) |
| 223 | sum += a[j]; |
| 224 | check.sum(sum);}}}, |
| 225 | new Job("Vector get loop") { |
| 226 | public void work() throws Throwable { |
| 227 | for (int i = 0; i < iterations; i++) { |
| 228 | int sum = 0; |
| 229 | int size = v.size(); |
| 230 | for (int j = 0; j < size; ++j) |
| 231 | sum += v.get(j); |
| 232 | check.sum(sum);}}}, |
| 233 | new Job("Vector iterate for loop") { |
| 234 | public void work() throws Throwable { |
| 235 | for (int i = 0; i < iterations; i++) { |
| 236 | int sum = 0; |
| 237 | for (Integer n : v) |
| 238 | sum += n; |
| 239 | check.sum(sum);}}}, |
| 240 | new Job("Vector descending listIterator loop") { |
| 241 | public void work() throws Throwable { |
| 242 | for (int i = 0; i < iterations; i++) { |
| 243 | int sum = 0; |
| 244 | ListIterator<Integer> it = v.listIterator(al.size()); |
| 245 | while (it.hasPrevious()) |
| 246 | sum += it.previous(); |
| 247 | check.sum(sum);}}}, |
| 248 | new Job("Vector Enumeration loop") { |
| 249 | public void work() throws Throwable { |
| 250 | for (int i = 0; i < iterations; i++) { |
| 251 | int sum = 0; |
| 252 | Enumeration<Integer> it = v.elements(); |
| 253 | while (it.hasMoreElements()) |
| 254 | sum += it.nextElement(); |
| 255 | check.sum(sum);}}}, |
| 256 | new Job("Vector subList iterate for loop") { |
| 257 | public void work() throws Throwable { |
| 258 | for (int i = 0; i < iterations; i++) { |
| 259 | int sum = 0; |
| 260 | for (Integer n : asSubList(v)) |
| 261 | sum += n; |
| 262 | check.sum(sum);}}}, |
| 263 | new Job("Vector subList subList subList iterate for loop") { |
| 264 | public void work() throws Throwable { |
| 265 | for (int i = 0; i < iterations; i++) { |
| 266 | int sum = 0; |
| 267 | for (Integer n : asSubList(asSubList(asSubList(v)))) |
| 268 | sum += n; |
| 269 | check.sum(sum);}}}, |
| 270 | new Job("Vector backwards wrapper ListIterator for loop") { |
| 271 | public void work() throws Throwable { |
| 272 | for (int i = 0; i < iterations; i++) { |
| 273 | int sum = 0; |
| 274 | for (Integer n : backwards(v)) |
| 275 | sum += n; |
| 276 | check.sum(sum);}}}, |
| 277 | new Job("Vector backwards wrapper subList ListIterator for loop") { |
| 278 | public void work() throws Throwable { |
| 279 | for (int i = 0; i < iterations; i++) { |
| 280 | int sum = 0; |
| 281 | for (Integer n : backwards(asSubList(v))) |
| 282 | sum += n; |
| 283 | check.sum(sum);}}}, |
| 284 | // new Job("Vector iterate for loop invokeinterface") { |
| 285 | // public void work() throws Throwable { |
| 286 | // final List<Integer> l = v; |
| 287 | // for (int i = 0; i < iterations; i++) { |
| 288 | // int sum = 0; |
| 289 | // for (Integer n : l) |
| 290 | // sum += n; |
| 291 | // check.sum(sum);}}}, |
| 292 | // new Job("Vector subList iterate for loop invokeinterface") { |
| 293 | // public void work() throws Throwable { |
| 294 | // final List<Integer> l = v; |
| 295 | // for (int i = 0; i < iterations; i++) { |
| 296 | // int sum = 0; |
| 297 | // for (Integer n : asSubList(l)) |
| 298 | // sum += n; |
| 299 | // check.sum(sum);}}}, |
| 300 | new Job("Short Vector get loop") { |
| 301 | public void work() throws Throwable { |
| 302 | for (int i = 0; i < (iterations * size / shortSize); i++) { |
| 303 | int sum = 0; |
| 304 | int size = sv.size(); |
| 305 | for (int j = 0; j < size; ++j) |
| 306 | sum += sv.get(j); |
| 307 | shortCheck.sum(sum);}}}, |
| 308 | new Job("Short Vector iterate for loop") { |
| 309 | public void work() throws Throwable { |
| 310 | for (int i = 0; i < (iterations * size / shortSize); i++) { |
| 311 | int sum = 0; |
| 312 | for (Integer n : sv) |
| 313 | sum += n; |
| 314 | shortCheck.sum(sum);}}}, |
| 315 | new Job("Short Vector sublist iterate for loop") { |
| 316 | public void work() throws Throwable { |
| 317 | for (int i = 0; i < (iterations * size / shortSize); i++) { |
| 318 | int sum = 0; |
| 319 | for (Integer n : asSubList(sv)) |
| 320 | sum += n; |
| 321 | shortCheck.sum(sum);}}}, |
| 322 | new Job("ArrayList get loop") { |
| 323 | public void work() throws Throwable { |
| 324 | for (int i = 0; i < iterations; i++) { |
| 325 | int sum = 0; |
| 326 | int size = al.size(); |
| 327 | for (int j = 0; j < size; ++j) |
| 328 | sum += al.get(j); |
| 329 | check.sum(sum);}}}, |
| 330 | new Job("ArrayList iterate for loop") { |
| 331 | public void work() throws Throwable { |
| 332 | for (int i = 0; i < iterations; i++) { |
| 333 | int sum = 0; |
| 334 | for (Integer n : al) |
| 335 | sum += n; |
| 336 | check.sum(sum);}}}, |
| 337 | new Job("ArrayList descending listIterator loop") { |
| 338 | public void work() throws Throwable { |
| 339 | for (int i = 0; i < iterations; i++) { |
| 340 | int sum = 0; |
| 341 | ListIterator<Integer> it = al.listIterator(al.size()); |
| 342 | while (it.hasPrevious()) |
| 343 | sum += it.previous(); |
| 344 | check.sum(sum);}}}, |
| 345 | new Job("ArrayList listIterator loop") { |
| 346 | public void work() throws Throwable { |
| 347 | for (int i = 0; i < iterations; i++) { |
| 348 | int sum = 0; |
| 349 | ListIterator<Integer> it = al.listIterator(); |
| 350 | while (it.hasNext()) |
| 351 | sum += it.next(); |
| 352 | check.sum(sum);}}}, |
| 353 | new Job("ArrayList subList get loop") { |
| 354 | public void work() throws Throwable { |
| 355 | List<Integer> sl = asSubList(al); |
| 356 | for (int i = 0; i < iterations; i++) { |
| 357 | int sum = 0; |
| 358 | int size = sl.size(); |
| 359 | for (int j = 0; j < size; ++j) |
| 360 | sum += sl.get(j); |
| 361 | check.sum(sum);}}}, |
| 362 | new Job("ArrayList subList iterate for loop") { |
| 363 | public void work() throws Throwable { |
| 364 | for (int i = 0; i < iterations; i++) { |
| 365 | int sum = 0; |
| 366 | for (Integer n : asSubList(al)) |
| 367 | sum += n; |
| 368 | check.sum(sum);}}}, |
| 369 | new Job("ArrayList subList subList subList iterate for loop") { |
| 370 | public void work() throws Throwable { |
| 371 | for (int i = 0; i < iterations; i++) { |
| 372 | int sum = 0; |
| 373 | for (Integer n : asSubList(asSubList(asSubList(al)))) |
| 374 | sum += n; |
| 375 | check.sum(sum);}}}, |
| 376 | new Job("ArrayList backwards wrapper ListIterator for loop") { |
| 377 | public void work() throws Throwable { |
| 378 | for (int i = 0; i < iterations; i++) { |
| 379 | int sum = 0; |
| 380 | for (Integer n : backwards(al)) |
| 381 | sum += n; |
| 382 | check.sum(sum);}}}, |
| 383 | new Job("ArrayList backwards wrapper subList ListIterator for loop") { |
| 384 | public void work() throws Throwable { |
| 385 | for (int i = 0; i < iterations; i++) { |
| 386 | int sum = 0; |
| 387 | for (Integer n : backwards(asSubList(al))) |
| 388 | sum += n; |
| 389 | check.sum(sum);}}}, |
| 390 | // new Job("ArrayList iterate desugared") { |
| 391 | // public void work() throws Throwable { |
| 392 | // for (int i = 0; i < iterations; i++) { |
| 393 | // int sum = 0; |
| 394 | // for (Iterator<Integer> it = al.iterator(); it.hasNext();) |
| 395 | // sum += it.next(); |
| 396 | // check.sum(sum);}}}, |
| 397 | new Job("Short ArrayList get loop") { |
| 398 | public void work() throws Throwable { |
| 399 | for (int i = 0; i < (iterations * size / shortSize); i++) { |
| 400 | int sum = 0; |
| 401 | int size = sal.size(); |
| 402 | for (int j = 0; j < size; ++j) |
| 403 | sum += sal.get(j); |
| 404 | shortCheck.sum(sum);}}}, |
| 405 | new Job("Short ArrayList iterate for loop") { |
| 406 | public void work() throws Throwable { |
| 407 | for (int i = 0; i < (iterations * size / shortSize); i++) { |
| 408 | int sum = 0; |
| 409 | for (Integer n : sal) |
| 410 | sum += n; |
| 411 | shortCheck.sum(sum);}}}, |
| 412 | new Job("Short ArrayList sublist iterate for loop") { |
| 413 | public void work() throws Throwable { |
| 414 | for (int i = 0; i < (iterations * size / shortSize); i++) { |
| 415 | int sum = 0; |
| 416 | for (Integer n : asSubList(sal)) |
| 417 | sum += n; |
| 418 | shortCheck.sum(sum);}}}, |
| 419 | new Job("Vector ArrayList alternating iteration") { |
| 420 | public void work() throws Throwable { |
| 421 | for (int i = 0; i < iterations; i++) { |
| 422 | int sum = 0; |
| 423 | Iterator<Integer> it1 = v.iterator(); |
| 424 | Iterator<Integer> it2 = al.iterator(); |
| 425 | while (it1.hasNext()) |
| 426 | sum += it1.next() + it2.next(); |
| 427 | check.sum(sum/2);}}}, |
| 428 | new Job("Vector ArrayList alternating invokeVirtual iteration") { |
| 429 | public void work() throws Throwable { |
| 430 | for (int i = 0; i < iterations; i++) { |
| 431 | int sum = 0; |
| 432 | List<Iterator<Integer>> its |
| 433 | = new ArrayList<Iterator<Integer>>(2); |
| 434 | its.add(v.iterator()); |
| 435 | its.add(al.iterator()); |
| 436 | for (int k = 0; its.get(k).hasNext(); k = (k == 0) ? 1 : 0) |
| 437 | sum += its.get(k).next(); |
| 438 | check.sum(sum/2);}}}, |
| 439 | new Job("ConcurrentSkipListMap entrySet iterate") { |
| 440 | public void work() throws Throwable { |
| 441 | for (int i = 0; i < iterations; i++) { |
| 442 | int sum = 0; |
| 443 | for (Map.Entry<Integer,Integer> e : m.entrySet()) |
| 444 | sum += e.getKey(); |
| 445 | deoptimize(sum);}}} |
| 446 | }; |
| 447 | |
| 448 | time(filter(filter, jobs)); |
| 449 | } |
| 450 | } |