test/loops/MapMicroBenchmark.java

/*
 * 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/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"
 * that includes elements of multiple types including those with
 * identical hash codes.
 *
 * The program includes a bunch of microbenchmarking safeguards that
 * might underestimate typical performance. For example, by using many
 * different key types and exercising them in warmups it disables most
 * 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 "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;

    // Nanoseconds per run
    static final long NANOS_PER_JOB = 6L * 1000L*1000L*1000L;
    static final long NANOS_PER_WARMUP = 100L*1000L*1000L;

    // 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; // must be > 1
    static final int MAX_ITERS_PER_TEST = 1000000; // avoid runaway

    // sizes are at halfway points for HashMap default resizes
    static final int firstSize = 9;
    static final int sizeStep = 4; // each size 4X last
    static final int nsizes = 9;
    static final int[] sizes = new int[nsizes];

    public static void main(String[] args) throws Throwable {
        if (args.length == 0) {
            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"))
                randomSearches = false;
            else if (args[1].startsWith("r"))
                randomSearches = true;
        }

        System.out.print("Class " + mapClass.getName());
        if (randomSearches)
            System.out.print(" randomized searches");
        else
            System.out.print(" sequential searches");

        System.out.println();

        int n = firstSize;
        for (int i = 0; i < nsizes - 1; ++i) {
            sizes[i] = n;
            n *= sizeStep;
        }
        sizes[nsizes - 1] = n;

        int njobs = 10;
        Job[] jobs = new Job[njobs];

        Object[] os = new Object[n];
        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);

        Object[] rs = new Object[n];
        for (int i = 0; i < n; i++) rs[i] = new RandomInt();
        jobs[8] = new Job("RandomInt ", rs, RandomInt.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(mixed);
        warmup2(jobs);
        warmup1(mixed);
        warmup3(jobs);
        Thread.sleep(500);
        time(jobs);
    }

    static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable {
        for (int k = 0; k < nsizes; ++k) {
            int len = sizes[k];
            for (int i = 0; i < jobs.length; i++) {
                Thread.sleep(50);
                jobs[i].nanos[k] = jobs[i].work(len, minIters, maxIters, timeLimit);
                System.out.print(".");
            }
        }
        System.out.println();
    }

    // First warmup -- run only mixed job to discourage type specialization
    static void warmup1(Job job) throws Throwable {
        for (int k = 0; k < nsizes; ++k)
            job.work(sizes[k], 1, 1, 0);
    }

    // Second, run each once
    static void warmup2(Job[] jobs) throws Throwable {
        System.out.print("warm up");
        runWork(jobs, 1, 1, 0);
        long ck = jobs[0].checkSum;
        for (int i = 1; i < jobs.length - 1; i++) {
            if (jobs[i].checkSum != ck)
                throw new Error("CheckSum");
        }
    }

    // Third: short timed runs
    static void warmup3(Job[] jobs) throws Throwable {
        System.out.print("warm up");
        runWork(jobs, 1, MAX_ITERS_PER_TEST, NANOS_PER_WARMUP);
    }

    static void time(Job[] jobs) throws Throwable {
        System.out.print("running");
        runWork(jobs, MIN_ITERS_PER_TEST, MAX_ITERS_PER_TEST, NANOS_PER_JOB);

        System.out.print("Type/Size:");
        for (int k = 0; k < nsizes; ++k)
            System.out.printf("%7d", sizes[k]);
        System.out.println();

        long[] aves = new long[nsizes];
        int njobs = jobs.length;

        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];
                System.out.printf("%7d", nanos);
                aves[k] += nanos;
            }
            System.out.println();
        }

        System.out.println();
        System.out.print("average   ");
        for (int k = 0; k < nsizes; ++k)
            System.out.printf("%7d", (aves[k] / njobs));
        System.out.println("\n");
    }


    static final class Job {
        final String name;
        final Class elementClass;
        long[] nanos = new long[nsizes];
        final Object[] items;
        Object[] searches;
        volatile long checkSum;
        volatile int lastSum;
        Job(String name, Object[] items, Class elementClass) {
            this.name = name;
            this.items = items;
            this.elementClass = elementClass;
            if (randomSearches) {
                scramble(items);
                this.searches = new Object[items.length];
                System.arraycopy(items, 0, searches, 0, items.length);
                scramble(searches);
            }
            else
                this.searches = items;
        }

        public long work(int len, int minIters, int maxIters, long timeLimit) {
            Map m;
            try {
                m = (Map) mapClass.newInstance();
            } catch (Exception e) {
                throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
            }
            Object[] ins = items;
            Object[] keys = searches;

            if (ins.length < len || keys.length < len)
                throw new Error(name);
            int half = len / 2;
            int quarter = half / 2;
            int sum = lastSum;
            long startTime = System.nanoTime();
            long elapsed;
            int j = 0;
            for (;;) {
                for (int i = 0; i < half; ++i) {
                    Object x = ins[i];
                    if (m.put(x, x) == null)
                        ++sum;
                }
                checkSum += sum ^ (sum << 1); // help avoid loop merging
                sum += len - half;
                for (int i = 0; i < len; ++i) {
                    Object x = keys[i];
                    Object v = m.get(x);
                    if (elementClass.isInstance(v)) // touch v
                        ++sum;
                }
                checkSum += sum ^ (sum << 2);
                for (int i = half; i < len; ++i) {
                    Object x = ins[i];
                    if (m.put(x, x) == null)
                        ++sum;
                }
                checkSum += sum ^ (sum << 3);
                for (Object e : m.keySet()) {
                    if (elementClass.isInstance(e))
                        ++sum;
                }
                checkSum += sum ^ (sum << 4);
                for (Object e : m.values()) {
                    if (elementClass.isInstance(e))
                        ++sum;
                }
                checkSum += sum ^ (sum << 5);
                for (int i = len - 1; i >= 0; --i) {
                    Object x = keys[i];
                    Object v = m.get(x);
                    if (elementClass.isInstance(v))
                        ++sum;
                }
                checkSum += sum ^ (sum << 6);
                for (int i = 0; i < len; ++i) {
                    Object x = ins[i];
                    Object v = m.get(x);
                    if (elementClass.isInstance(v))
                        ++sum;
                }
                checkSum += sum ^ (sum << 7);
                for (int i = 0; i < len; ++i) {
                    Object x = keys[i];
                    Object v = ins[i];
                    if (m.put(x, v) == x)
                        ++sum;
                }
                checkSum += sum ^ (sum << 8);
                for (int i = 0; i < len; ++i) {
                    Object x = keys[i];
                    Object v = ins[i];
                    if (v == m.get(x))
                        ++sum;
                }
                checkSum += sum ^ (sum << 9);
                for (int i = len - 1; i >= 0; --i) {
                    Object x = ins[i];
                    Object v = m.get(x);
                    if (elementClass.isInstance(v))
                        ++sum;
                }
                checkSum += sum ^ (sum << 10);
                for (int i = len - 1; i >= 0; --i) {
                    Object x = keys[i];
                    Object v = ins[i];
                    if (v == m.get(x))
                        ++sum;
                }
                checkSum += sum ^ (sum << 11);
                for (int i = 0; i < quarter; ++i) {
                    Object x = keys[i];
                    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 * 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;
            lastSum = sum;
            return elapsed / ops;
        }

    }


    static final Random rng = new Random(3122688);

    // Shuffle the subarrays for each size. This doesn't fully
    // randomize, but the remaining partial locality is arguably a bit
    // more realistic
    static void scramble(Object[] a) {
        for (int k = 0; k < sizes.length; ++k) {
            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;
                a[i-1] = a[r];
                a[r] = t;
            }
        }
    }

    // plain array shuffle
    static void shuffle(Object[] a, int size) {
        for (int i = size; i > 1; i--) {
            Object t = a[i-1];
            int r = rng.nextInt(i);
            a[i-1] = a[r];
            a[r] = t;
        }
    }

    // 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];
    }

}
Revision:	1.14
Committed:	Wed Mar 5 17:31:06 2014 UTC (10 years, 2 months ago) by jsr166
Branch:	MAIN
Changes since 1.13:	+1 -1 lines
Log Message:	whitespace
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain, as explained at
4	* http://creativecommons.org/publicdomain/zero/1.0/
5	*/
6
7	import java.util.*;
8	import java.io.*;
9	import java.math.*;
10
11	/**
12	* A micro-benchmark with key types and operation mixes roughly
13	* corresponding to some real programs.
14	*
15	* The main results are a table of approximate nanoseconds per
16	* element-operation (averaged across get, put etc) for each type,
17	* across a range of map sizes. It also includes category "Mixed"
18	* that includes elements of multiple types including those with
19	* identical hash codes.
20	*
21	* The program includes a bunch of microbenchmarking safeguards that
22	* might underestimate typical performance. For example, by using many
23	* different key types and exercising them in warmups it disables most
24	* dynamic type specialization. Some test classes, like Float and
25	* BigDecimal are included not because they are commonly used as keys,
26	* but because they can be problematic for some map implementations.
27	*
28	* By default, it creates and inserts in order dense numerical keys
29	* and searches for keys in scrambled order. Use "s" as second arg to
30	* instead insert and search in unscrambled order.
31	*
32	* For String keys, the program tries to use file "testwords.txt", which
33	* is best used with real words. We can't check in this file, but you
34	* can create one from a real dictionary (1 line per word) and then run
35	* linux "shuf" to randomize entries. If no file exists, it uses
36	* String.valueOf(i) for element i.
37	*/
38	public class MapMicroBenchmark {
39	static final String wordFile = "testwords.txt";
40
41	static Class mapClass;
42	static boolean randomSearches = true;
43
44	// Nanoseconds per run
45	static final long NANOS_PER_JOB = 6L * 1000L1000L1000L;
46	static final long NANOS_PER_WARMUP = 100L1000L1000L;
47
48	// map operations per item per iteration -- change if job.work changed
49	static final int OPS_PER_ITER = 11;
50	static final int MIN_ITERS_PER_TEST = 3; // must be > 1
51	static final int MAX_ITERS_PER_TEST = 1000000; // avoid runaway
52
53	// sizes are at halfway points for HashMap default resizes
54	static final int firstSize = 9;
55	static final int sizeStep = 4; // each size 4X last
56	static final int nsizes = 9;
57	static final int[] sizes = new int[nsizes];
58
59	public static void main(String[] args) throws Throwable {
60	if (args.length == 0) {
61	System.out.println("Usage: java MapMicroBenchmark className [r\|s]keys [r\|s]searches");
62	return;
63	}
64
65	mapClass = Class.forName(args[0]);
66
67	if (args.length > 1) {
68	if (args[1].startsWith("s"))
69	randomSearches = false;
70	else if (args[1].startsWith("r"))
71	randomSearches = true;
72	}
73
74	System.out.print("Class " + mapClass.getName());
75	if (randomSearches)
76	System.out.print(" randomized searches");
77	else
78	System.out.print(" sequential searches");
79
80	System.out.println();
81
82	int n = firstSize;
83	for (int i = 0; i < nsizes - 1; ++i) {
84	sizes[i] = n;
85	n *= sizeStep;
86	}
87	sizes[nsizes - 1] = n;
88
89	int njobs = 10;
90	Job[] jobs = new Job[njobs];
91
92	Object[] os = new Object[n];
93	for (int i = 0; i < n; i++) os[i] = new Object();
94	jobs[0] = new Job("Object ", os, Object.class);
95
96	Object[] ss = new Object[n];
97	initStringKeys(ss, n);
98	jobs[1] = new Job("String ", ss, String.class);
99
100	Object[] is = new Object[n];
101	for (int i = 0; i < n; i++) is[i] = Integer.valueOf(i);
102	jobs[2] = new Job("Integer ", is, Integer.class);
103
104	Object[] ls = new Object[n];
105	for (int i = 0; i < n; i++) ls[i] = Long.valueOf((long) i);
106	jobs[3] = new Job("Long ", ls, Long.class);
107
108	Object[] fs = new Object[n];
109	for (int i = 0; i < n; i++) fs[i] = Float.valueOf((float) i);
110	jobs[4] = new Job("Float ", fs, Float.class);
111
112	Object[] ds = new Object[n];
113	for (int i = 0; i < n; i++) ds[i] = Double.valueOf((double) i);
114	jobs[5] = new Job("Double ", ds, Double.class);
115
116	Object[] bs = new Object[n];
117	long b = -n; // include some negatives
118	for (int i = 0; i < n; i++) bs[i] = BigInteger.valueOf(b += 3);
119	jobs[6] = new Job("BigInteger", bs, BigInteger.class);
120
121	Object[] es = new Object[n];
122	long d = Integer.MAX_VALUE; // include crummy codes
123	for (int i = 0; i < n; i++) es[i] = BigDecimal.valueOf(d += 65536);
124	jobs[7] = new Job("BigDecimal", es, BigDecimal.class);
125
126	Object[] rs = new Object[n];
127	for (int i = 0; i < n; i++) rs[i] = new RandomInt();
128	jobs[8] = new Job("RandomInt ", rs, RandomInt.class);
129
130	Object[] ms = new Object[n];
131	for (int i = 0; i < n; i += 2) {
132	int r = rng.nextInt(njobs - 1);
133	ms[i] = jobs[r].items[i];
134	// include some that will have same hash but not .equal
135	if (++r >= njobs - 1) r = 0;
136	ms[i+1] = jobs[r].items[i];
137	}
138	jobs[9] = new Job("Mixed ", ms, Object.class);
139	Job mixed = jobs[9];
140
141	warmup1(mixed);
142	warmup2(jobs);
143	warmup1(mixed);
144	warmup3(jobs);
145	Thread.sleep(500);
146	time(jobs);
147	}
148
149	static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable {
150	for (int k = 0; k < nsizes; ++k) {
151	int len = sizes[k];
152	for (int i = 0; i < jobs.length; i++) {
153	Thread.sleep(50);
154	jobs[i].nanos[k] = jobs[i].work(len, minIters, maxIters, timeLimit);
155	System.out.print(".");
156	}
157	}
158	System.out.println();
159	}
160
161	// First warmup -- run only mixed job to discourage type specialization
162	static void warmup1(Job job) throws Throwable {
163	for (int k = 0; k < nsizes; ++k)
164	job.work(sizes[k], 1, 1, 0);
165	}
166
167	// Second, run each once
168	static void warmup2(Job[] jobs) throws Throwable {
169	System.out.print("warm up");
170	runWork(jobs, 1, 1, 0);
171	long ck = jobs[0].checkSum;
172	for (int i = 1; i < jobs.length - 1; i++) {
173	if (jobs[i].checkSum != ck)
174	throw new Error("CheckSum");
175	}
176	}
177
178	// Third: short timed runs
179	static void warmup3(Job[] jobs) throws Throwable {
180	System.out.print("warm up");
181	runWork(jobs, 1, MAX_ITERS_PER_TEST, NANOS_PER_WARMUP);
182	}
183
184	static void time(Job[] jobs) throws Throwable {
185	System.out.print("running");
186	runWork(jobs, MIN_ITERS_PER_TEST, MAX_ITERS_PER_TEST, NANOS_PER_JOB);
187
188	System.out.print("Type/Size:");
189	for (int k = 0; k < nsizes; ++k)
190	System.out.printf("%7d", sizes[k]);
191	System.out.println();
192
193	long[] aves = new long[nsizes];
194	int njobs = jobs.length;
195
196	for (int i = 0; i < njobs; i++) {
197	System.out.print(jobs[i].name);
198	for (int k = 0; k < nsizes; ++k) {
199	long nanos = jobs[i].nanos[k];
200	System.out.printf("%7d", nanos);
201	aves[k] += nanos;
202	}
203	System.out.println();
204	}
205
206	System.out.println();
207	System.out.print("average ");
208	for (int k = 0; k < nsizes; ++k)
209	System.out.printf("%7d", (aves[k] / njobs));
210	System.out.println("\n");
211	}
212
213
214	static final class Job {
215	final String name;
216	final Class elementClass;
217	long[] nanos = new long[nsizes];
218	final Object[] items;
219	Object[] searches;
220	volatile long checkSum;
221	volatile int lastSum;
222	Job(String name, Object[] items, Class elementClass) {
223	this.name = name;
224	this.items = items;
225	this.elementClass = elementClass;
226	if (randomSearches) {
227	scramble(items);
228	this.searches = new Object[items.length];
229	System.arraycopy(items, 0, searches, 0, items.length);
230	scramble(searches);
231	}
232	else
233	this.searches = items;
234	}
235
236	public long work(int len, int minIters, int maxIters, long timeLimit) {
237	Map m;
238	try {
239	m = (Map) mapClass.newInstance();
240	} catch (Exception e) {
241	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
242	}
243	Object[] ins = items;
244	Object[] keys = searches;
245
246	if (ins.length < len \|\| keys.length < len)
247	throw new Error(name);
248	int half = len / 2;
249	int quarter = half / 2;
250	int sum = lastSum;
251	long startTime = System.nanoTime();
252	long elapsed;
253	int j = 0;
254	for (;;) {
255	for (int i = 0; i < half; ++i) {
256	Object x = ins[i];
257	if (m.put(x, x) == null)
258	++sum;
259	}
260	checkSum += sum ^ (sum << 1); // help avoid loop merging
261	sum += len - half;
262	for (int i = 0; i < len; ++i) {
263	Object x = keys[i];
264	Object v = m.get(x);
265	if (elementClass.isInstance(v)) // touch v
266	++sum;
267	}
268	checkSum += sum ^ (sum << 2);
269	for (int i = half; i < len; ++i) {
270	Object x = ins[i];
271	if (m.put(x, x) == null)
272	++sum;
273	}
274	checkSum += sum ^ (sum << 3);
275	for (Object e : m.keySet()) {
276	if (elementClass.isInstance(e))
277	++sum;
278	}
279	checkSum += sum ^ (sum << 4);
280	for (Object e : m.values()) {
281	if (elementClass.isInstance(e))
282	++sum;
283	}
284	checkSum += sum ^ (sum << 5);
285	for (int i = len - 1; i >= 0; --i) {
286	Object x = keys[i];
287	Object v = m.get(x);
288	if (elementClass.isInstance(v))
289	++sum;
290	}
291	checkSum += sum ^ (sum << 6);
292	for (int i = 0; i < len; ++i) {
293	Object x = ins[i];
294	Object v = m.get(x);
295	if (elementClass.isInstance(v))
296	++sum;
297	}
298	checkSum += sum ^ (sum << 7);
299	for (int i = 0; i < len; ++i) {
300	Object x = keys[i];
301	Object v = ins[i];
302	if (m.put(x, v) == x)
303	++sum;
304	}
305	checkSum += sum ^ (sum << 8);
306	for (int i = 0; i < len; ++i) {
307	Object x = keys[i];
308	Object v = ins[i];
309	if (v == m.get(x))
310	++sum;
311	}
312	checkSum += sum ^ (sum << 9);
313	for (int i = len - 1; i >= 0; --i) {
314	Object x = ins[i];
315	Object v = m.get(x);
316	if (elementClass.isInstance(v))
317	++sum;
318	}
319	checkSum += sum ^ (sum << 10);
320	for (int i = len - 1; i >= 0; --i) {
321	Object x = keys[i];
322	Object v = ins[i];
323	if (v == m.get(x))
324	++sum;
325	}
326	checkSum += sum ^ (sum << 11);
327	for (int i = 0; i < quarter; ++i) {
328	Object x = keys[i];
329	if (m.remove(x) != null)
330	++sum;
331	}
332	for (int i = 0; i < quarter; ++i) {
333	Object x = keys[i];
334	if (m.put(x, x) == null)
335	++sum;
336	}
337	/* // uncomment to avoid calling clear()
338	for (int i = 0; i < len; ++i) {
339	Object x = keys[i];
340	m.remove(x);
341	}
342	*/
343	m.clear();
344	sum += len - (quarter * 2);
345	checkSum += sum ^ (sum << 12);
346
347	if (j == 0 && sum != lastSum + len * OPS_PER_ITER)
348	throw new Error(name);
349
350	elapsed = System.nanoTime() - startTime;
351	++j;
352	if (j >= minIters &&
353	(j >= maxIters \|\| elapsed >= timeLimit))
354	break;
355	// non-warmup - swap some keys for next insert
356	if (minIters != 1 && randomSearches)
357	shuffleSome(ins, len, len >>> 3);
358	}
359	long ops = ((long) j) * len * OPS_PER_ITER;
360	lastSum = sum;
361	return elapsed / ops;
362	}
363
364	}
365
366
367	static final Random rng = new Random(3122688);
368
369	// Shuffle the subarrays for each size. This doesn't fully
370	// randomize, but the remaining partial locality is arguably a bit
371	// more realistic
372	static void scramble(Object[] a) {
373	for (int k = 0; k < sizes.length; ++k) {
374	int origin = (k == 0) ? 0 : sizes[k-1];
375	for (int i = sizes[k]; i > origin + 1; i--) {
376	Object t = a[i-1];
377	int r = rng.nextInt(i - origin) + origin;
378	a[i-1] = a[r];
379	a[r] = t;
380	}
381	}
382	}
383
384	// plain array shuffle
385	static void shuffle(Object[] a, int size) {
386	for (int i = size; i > 1; i--) {
387	Object t = a[i-1];
388	int r = rng.nextInt(i);
389	a[i-1] = a[r];
390	a[r] = t;
391	}
392	}
393
394	// swap nswaps elements
395	static void shuffleSome(Object[] a, int size, int nswaps) {
396	for (int s = 0; s < nswaps; ++s) {
397	int i = rng.nextInt(size);
398	int r = rng.nextInt(size);
399	Object t = a[i];
400	a[i] = a[r];
401	a[r] = t;
402	}
403	}
404
405	// Integer-like class with random hash codes
406	static final class RandomInt {
407	static int seed = 3122688;
408	static int next() { // a non-xorshift, 2^32-period RNG
409	int x = seed;
410	int lo = 16807 * (x & 0xFFFF);
411	int hi = 16807 * (x >>> 16);
412	lo += (hi & 0x7FFF) << 16;
413	if ((lo & 0x80000000) != 0) {
414	lo &= 0x7fffffff;
415	++lo;
416	}
417	lo += hi >>> 15;
418	if (lo == 0 \|\| (lo & 0x80000000) != 0) {
419	lo &= 0x7fffffff;
420	++lo;
421	}
422	seed = lo;
423	return x;
424	}
425	final int value;
426	RandomInt() { value = next(); }
427	public int hashCode() { return value; }
428	public boolean equals(Object x) {
429	return (x instanceof RandomInt) && ((RandomInt)x).value == value;
430	}
431	}
432
433	// Read in String keys from file if possible
434	static void initStringKeys(Object[] keys, int n) throws Exception {
435	FileInputStream fr = null;
436	try {
437	fr = new FileInputStream(wordFile);
438	} catch (IOException ex) {
439	System.out.println("No word file. Using String.valueOf(i)");
440	for (int i = 0; i < n; i++)
441	keys[i] = String.valueOf(i);
442	return;
443	}
444
445	BufferedInputStream in = new BufferedInputStream(fr);
446	int k = 0;
447	outer: while (k < n) {
448	StringBuffer sb = new StringBuffer();
449	for (;;) {
450	int c = in.read();
451	if (c < 0)
452	break outer;
453	char ch = (char) c;
454	if (ch == '\n') {
455	keys[k++] = sb.toString();
456	break;
457	}
458	if (!Character.isWhitespace(ch))
459	sb.append(ch);
460	}
461	}
462	in.close();
463
464	// fill up remaining keys with path-like compounds of previous pairs
465	int j = 0;
466	while (k < n)
467	keys[k++] = (String) keys[j++] + "/" + (String) keys[j];
468	}
469
470	}