--- jsr166/src/test/loops/MapMicroBenchmark.java 2009/07/22 16:19:51 1.2 +++ jsr166/src/test/loops/MapMicroBenchmark.java 2014/03/05 17:31:06 1.14 @@ -1,16 +1,17 @@ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ import java.util.*; +import java.io.*; import java.math.*; /** * A micro-benchmark with key types and operation mixes roughly * corresponding to some real programs. - * + * * The main results are a table of approximate nanoseconds per * element-operation (averaged across get, put etc) for each type, * across a range of map sizes. It also includes category "Mixed" @@ -23,16 +24,22 @@ import java.math.*; * dynamic type specialization. Some test classes, like Float and * BigDecimal are included not because they are commonly used as keys, * but because they can be problematic for some map implementations. - * + * * By default, it creates and inserts in order dense numerical keys - * and searches for keys in scrambled order. Use "r" as second arg to - * instead use random numerical values, and "s" as third arg to search - * in insertion order. + * and searches for keys in scrambled order. Use "s" as second arg to + * instead insert and search in unscrambled order. + * + * For String keys, the program tries to use file "testwords.txt", which + * is best used with real words. We can't check in this file, but you + * can create one from a real dictionary (1 line per word) and then run + * linux "shuf" to randomize entries. If no file exists, it uses + * String.valueOf(i) for element i. */ public class MapMicroBenchmark { + static final String wordFile = "testwords.txt"; + static Class mapClass; static boolean randomSearches = true; - static boolean randomKeys = false; // Nanoseconds per run static final long NANOS_PER_JOB = 6L * 1000L*1000L*1000L; @@ -40,7 +47,7 @@ public class MapMicroBenchmark { // map operations per item per iteration -- change if job.work changed static final int OPS_PER_ITER = 11; - static final int MIN_ITERS_PER_TEST = 3; + static final int MIN_ITERS_PER_TEST = 3; // must be > 1 static final int MAX_ITERS_PER_TEST = 1000000; // avoid runaway // sizes are at halfway points for HashMap default resizes @@ -54,27 +61,17 @@ public class MapMicroBenchmark { System.out.println("Usage: java MapMicroBenchmark className [r|s]keys [r|s]searches"); return; } - + mapClass = Class.forName(args[0]); if (args.length > 1) { if (args[1].startsWith("s")) - randomKeys = false; - else if (args[1].startsWith("r")) - randomKeys = true; - } - if (args.length > 2) { - if (args[2].startsWith("s")) randomSearches = false; - else if (args[2].startsWith("r")) + else if (args[1].startsWith("r")) randomSearches = true; } System.out.print("Class " + mapClass.getName()); - if (randomKeys) - System.out.print(" random keys"); - else - System.out.print(" sequential keys"); if (randomSearches) System.out.print(" randomized searches"); else @@ -89,97 +86,68 @@ public class MapMicroBenchmark { } sizes[nsizes - 1] = n; - int njobs = 9; + int njobs = 10; + Job[] jobs = new Job[njobs]; Object[] os = new Object[n]; - Object[] ss = new Object[n]; - Object[] is = new Object[n]; - Object[] ls = new Object[n]; - Object[] fs = new Object[n]; - Object[] ds = new Object[n]; - Object[] bs = new Object[n]; - Object[] es = new Object[n]; - Object[] ms = new Object[n]; - - for (int i = 0; i < n; i++) { - os[i] = new Object(); - } - - // To guarantee uniqueness, use xorshift for "random" versions - int rnd = 3122688; - for (int i = 0; i < n; i++) { - rnd = xorshift(rnd); - int j = randomKeys? rnd : i; - ss[i] = String.valueOf(j); - } - - for (int i = 0; i < n; i++) { - rnd = xorshift(rnd); - int j = randomKeys? rnd : i; - is[i] = Integer.valueOf(j); - } - - for (int i = 0; i < n; i++) { - rnd = xorshift(rnd); - int j = randomKeys? rnd : i; - ls[i] = Long.valueOf((long)j); - } - - for (int i = 0; i < n; i++) { - // rnd = xorshift(rnd); - // int j = randomKeys? rnd : i; - fs[i] = Float.valueOf((float)i); // can't use random for float - } - - for (int i = 0; i < n; i++) { - rnd = xorshift(rnd); - int j = randomKeys? rnd : i; - ds[i] = Double.valueOf((double)j); - } - - for (int i = 0; i < n; i++) { - rnd = xorshift(rnd); - int j = randomKeys? rnd : i; - bs[i] = BigInteger.valueOf(j); - } - - for (int i = 0; i < n; i++) { - rnd = xorshift(rnd); - int j = randomKeys? rnd : i; - es[i] = BigDecimal.valueOf(j); - } - - Job[] jobs = new Job[njobs]; + for (int i = 0; i < n; i++) os[i] = new Object(); jobs[0] = new Job("Object ", os, Object.class); + + Object[] ss = new Object[n]; + initStringKeys(ss, n); jobs[1] = new Job("String ", ss, String.class); + + Object[] is = new Object[n]; + for (int i = 0; i < n; i++) is[i] = Integer.valueOf(i); jobs[2] = new Job("Integer ", is, Integer.class); + + Object[] ls = new Object[n]; + for (int i = 0; i < n; i++) ls[i] = Long.valueOf((long) i); jobs[3] = new Job("Long ", ls, Long.class); + + Object[] fs = new Object[n]; + for (int i = 0; i < n; i++) fs[i] = Float.valueOf((float) i); jobs[4] = new Job("Float ", fs, Float.class); + + Object[] ds = new Object[n]; + for (int i = 0; i < n; i++) ds[i] = Double.valueOf((double) i); jobs[5] = new Job("Double ", ds, Double.class); + + Object[] bs = new Object[n]; + long b = -n; // include some negatives + for (int i = 0; i < n; i++) bs[i] = BigInteger.valueOf(b += 3); jobs[6] = new Job("BigInteger", bs, BigInteger.class); + + Object[] es = new Object[n]; + long d = Integer.MAX_VALUE; // include crummy codes + for (int i = 0; i < n; i++) es[i] = BigDecimal.valueOf(d += 65536); jobs[7] = new Job("BigDecimal", es, BigDecimal.class); - for (int i = 0; i < n; i +=2) { - rnd = xorshift(rnd); - int j = (rnd & 7); // change if njobs changes - ms[i] = jobs[j].items[i]; - j = (j + 1) & 7; - ms[i+1] = jobs[j].items[i]; - } + Object[] rs = new Object[n]; + for (int i = 0; i < n; i++) rs[i] = new RandomInt(); + jobs[8] = new Job("RandomInt ", rs, RandomInt.class); - jobs[8] = new Job("Mixed ", ms, Object.class); + Object[] ms = new Object[n]; + for (int i = 0; i < n; i += 2) { + int r = rng.nextInt(njobs - 1); + ms[i] = jobs[r].items[i]; + // include some that will have same hash but not .equal + if (++r >= njobs - 1) r = 0; + ms[i+1] = jobs[r].items[i]; + } + jobs[9] = new Job("Mixed ", ms, Object.class); + Job mixed = jobs[9]; - warmup1(jobs[8]); + warmup1(mixed); warmup2(jobs); - warmup1(jobs[8]); + warmup1(mixed); warmup3(jobs); - warmup1(jobs[8]); Thread.sleep(500); - time(jobs); + time(jobs); } static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable { - for (int k = 0; k < nsizes; ++k) { + for (int k = 0; k < nsizes; ++k) { int len = sizes[k]; for (int i = 0; i < jobs.length; i++) { Thread.sleep(50); @@ -192,7 +160,7 @@ public class MapMicroBenchmark { // First warmup -- run only mixed job to discourage type specialization static void warmup1(Job job) throws Throwable { - for (int k = 0; k < nsizes; ++k) + for (int k = 0; k < nsizes; ++k) job.work(sizes[k], 1, 1, 0); } @@ -225,7 +193,7 @@ public class MapMicroBenchmark { long[] aves = new long[nsizes]; int njobs = jobs.length; - for (int i = 0; i < njobs; i++) { + for (int i = 0; i < njobs; i++) { System.out.print(jobs[i].name); for (int k = 0; k < nsizes; ++k) { long nanos = jobs[i].nanos[k]; @@ -244,7 +212,7 @@ public class MapMicroBenchmark { static final class Job { - final String name; + final String name; final Class elementClass; long[] nanos = new long[nsizes]; final Object[] items; @@ -268,8 +236,8 @@ public class MapMicroBenchmark { public long work(int len, int minIters, int maxIters, long timeLimit) { Map m; try { - m = (Map)mapClass.newInstance(); - } catch(Exception e) { + m = (Map) mapClass.newInstance(); + } catch (Exception e) { throw new RuntimeException("Can't instantiate " + mapClass + ": " + e); } Object[] ins = items; @@ -293,7 +261,7 @@ public class MapMicroBenchmark { sum += len - half; for (int i = 0; i < len; ++i) { Object x = keys[i]; - Object v = m.get(x); + Object v = m.get(x); if (elementClass.isInstance(v)) // touch v ++sum; } @@ -305,12 +273,12 @@ public class MapMicroBenchmark { } checkSum += sum ^ (sum << 3); for (Object e : m.keySet()) { - if (elementClass.isInstance(e)) + if (elementClass.isInstance(e)) ++sum; } checkSum += sum ^ (sum << 4); for (Object e : m.values()) { - if (elementClass.isInstance(e)) + if (elementClass.isInstance(e)) ++sum; } checkSum += sum ^ (sum << 5); @@ -361,32 +329,40 @@ public class MapMicroBenchmark { if (m.remove(x) != null) ++sum; } + for (int i = 0; i < quarter; ++i) { + Object x = keys[i]; + if (m.put(x, x) == null) + ++sum; + } + /* // uncomment to avoid calling clear() + for (int i = 0; i < len; ++i) { + Object x = keys[i]; + m.remove(x); + } + */ m.clear(); - sum += len - quarter; + sum += len - (quarter * 2); checkSum += sum ^ (sum << 12); + if (j == 0 && sum != lastSum + len * OPS_PER_ITER) + throw new Error(name); + elapsed = System.nanoTime() - startTime; ++j; if (j >= minIters && (j >= maxIters || elapsed >= timeLimit)) break; + // non-warmup - swap some keys for next insert + if (minIters != 1 && randomSearches) + shuffleSome(ins, len, len >>> 3); } - long ops = ((long)j) * len * OPS_PER_ITER; - if (sum != lastSum + (int)ops) - throw new Error(name); + long ops = ((long) j) * len * OPS_PER_ITER; lastSum = sum; return elapsed / ops; } } - static final int xorshift(int seed) { - seed ^= seed << 1; - seed ^= seed >>> 3; - seed ^= seed << 10; - return seed; - } - static final Random rng = new Random(3122688); @@ -395,7 +371,7 @@ public class MapMicroBenchmark { // more realistic static void scramble(Object[] a) { for (int k = 0; k < sizes.length; ++k) { - int origin = k == 0? 0 : sizes[k-1]; + int origin = (k == 0) ? 0 : sizes[k-1]; for (int i = sizes[k]; i > origin + 1; i--) { Object t = a[i-1]; int r = rng.nextInt(i - origin) + origin; @@ -403,11 +379,11 @@ public class MapMicroBenchmark { a[r] = t; } } - } + } // plain array shuffle static void shuffle(Object[] a, int size) { - for (int i= size; i>1; i--) { + for (int i = size; i > 1; i--) { Object t = a[i-1]; int r = rng.nextInt(i); a[i-1] = a[r]; @@ -415,7 +391,80 @@ public class MapMicroBenchmark { } } + // swap nswaps elements + static void shuffleSome(Object[] a, int size, int nswaps) { + for (int s = 0; s < nswaps; ++s) { + int i = rng.nextInt(size); + int r = rng.nextInt(size); + Object t = a[i]; + a[i] = a[r]; + a[r] = t; + } + } + // Integer-like class with random hash codes + static final class RandomInt { + static int seed = 3122688; + static int next() { // a non-xorshift, 2^32-period RNG + int x = seed; + int lo = 16807 * (x & 0xFFFF); + int hi = 16807 * (x >>> 16); + lo += (hi & 0x7FFF) << 16; + if ((lo & 0x80000000) != 0) { + lo &= 0x7fffffff; + ++lo; + } + lo += hi >>> 15; + if (lo == 0 || (lo & 0x80000000) != 0) { + lo &= 0x7fffffff; + ++lo; + } + seed = lo; + return x; + } + final int value; + RandomInt() { value = next(); } + public int hashCode() { return value; } + public boolean equals(Object x) { + return (x instanceof RandomInt) && ((RandomInt)x).value == value; + } + } -} + // Read in String keys from file if possible + static void initStringKeys(Object[] keys, int n) throws Exception { + FileInputStream fr = null; + try { + fr = new FileInputStream(wordFile); + } catch (IOException ex) { + System.out.println("No word file. Using String.valueOf(i)"); + for (int i = 0; i < n; i++) + keys[i] = String.valueOf(i); + return; + } + BufferedInputStream in = new BufferedInputStream(fr); + int k = 0; + outer: while (k < n) { + StringBuffer sb = new StringBuffer(); + for (;;) { + int c = in.read(); + if (c < 0) + break outer; + char ch = (char) c; + if (ch == '\n') { + keys[k++] = sb.toString(); + break; + } + if (!Character.isWhitespace(ch)) + sb.append(ch); + } + } + in.close(); + + // fill up remaining keys with path-like compounds of previous pairs + int j = 0; + while (k < n) + keys[k++] = (String) keys[j++] + "/" + (String) keys[j]; + } + +}