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.io.*;
import java.math.*;
import java.util.*;

/**
 * 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) {
            final Map m;
            try {
                m = (Map) mapClass.getConstructor().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.18
Committed:	Sun Oct 23 03:03:23 2016 UTC (7 years, 6 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.17:	+2 -2 lines
Log Message:	fix deprecation warnings for Class#newInstance
#	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.io.*;
8	import java.math.*;
9	import java.util.*;
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	static final class Job {
214	final String name;
215	final Class<?> elementClass;
216	long[] nanos = new long[nsizes];
217	final Object[] items;
218	Object[] searches;
219	volatile long checkSum;
220	volatile int lastSum;
221	Job(String name, Object[] items, Class<?> elementClass) {
222	this.name = name;
223	this.items = items;
224	this.elementClass = elementClass;
225	if (randomSearches) {
226	scramble(items);
227	this.searches = new Object[items.length];
228	System.arraycopy(items, 0, searches, 0, items.length);
229	scramble(searches);
230	}
231	else
232	this.searches = items;
233	}
234
235	public long work(int len, int minIters, int maxIters, long timeLimit) {
236	final Map m;
237	try {
238	m = (Map) mapClass.getConstructor().newInstance();
239	} catch (Exception e) {
240	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
241	}
242	Object[] ins = items;
243	Object[] keys = searches;
244
245	if (ins.length < len \|\| keys.length < len)
246	throw new Error(name);
247	int half = len / 2;
248	int quarter = half / 2;
249	int sum = lastSum;
250	long startTime = System.nanoTime();
251	long elapsed;
252	int j = 0;
253	for (;;) {
254	for (int i = 0; i < half; ++i) {
255	Object x = ins[i];
256	if (m.put(x, x) == null)
257	++sum;
258	}
259	checkSum += sum ^ (sum << 1); // help avoid loop merging
260	sum += len - half;
261	for (int i = 0; i < len; ++i) {
262	Object x = keys[i];
263	Object v = m.get(x);
264	if (elementClass.isInstance(v)) // touch v
265	++sum;
266	}
267	checkSum += sum ^ (sum << 2);
268	for (int i = half; i < len; ++i) {
269	Object x = ins[i];
270	if (m.put(x, x) == null)
271	++sum;
272	}
273	checkSum += sum ^ (sum << 3);
274	for (Object e : m.keySet()) {
275	if (elementClass.isInstance(e))
276	++sum;
277	}
278	checkSum += sum ^ (sum << 4);
279	for (Object e : m.values()) {
280	if (elementClass.isInstance(e))
281	++sum;
282	}
283	checkSum += sum ^ (sum << 5);
284	for (int i = len - 1; i >= 0; --i) {
285	Object x = keys[i];
286	Object v = m.get(x);
287	if (elementClass.isInstance(v))
288	++sum;
289	}
290	checkSum += sum ^ (sum << 6);
291	for (int i = 0; i < len; ++i) {
292	Object x = ins[i];
293	Object v = m.get(x);
294	if (elementClass.isInstance(v))
295	++sum;
296	}
297	checkSum += sum ^ (sum << 7);
298	for (int i = 0; i < len; ++i) {
299	Object x = keys[i];
300	Object v = ins[i];
301	if (m.put(x, v) == x)
302	++sum;
303	}
304	checkSum += sum ^ (sum << 8);
305	for (int i = 0; i < len; ++i) {
306	Object x = keys[i];
307	Object v = ins[i];
308	if (v == m.get(x))
309	++sum;
310	}
311	checkSum += sum ^ (sum << 9);
312	for (int i = len - 1; i >= 0; --i) {
313	Object x = ins[i];
314	Object v = m.get(x);
315	if (elementClass.isInstance(v))
316	++sum;
317	}
318	checkSum += sum ^ (sum << 10);
319	for (int i = len - 1; i >= 0; --i) {
320	Object x = keys[i];
321	Object v = ins[i];
322	if (v == m.get(x))
323	++sum;
324	}
325	checkSum += sum ^ (sum << 11);
326	for (int i = 0; i < quarter; ++i) {
327	Object x = keys[i];
328	if (m.remove(x) != null)
329	++sum;
330	}
331	for (int i = 0; i < quarter; ++i) {
332	Object x = keys[i];
333	if (m.put(x, x) == null)
334	++sum;
335	}
336	/* // uncomment to avoid calling clear()
337	for (int i = 0; i < len; ++i) {
338	Object x = keys[i];
339	m.remove(x);
340	}
341	*/
342	m.clear();
343	sum += len - (quarter * 2);
344	checkSum += sum ^ (sum << 12);
345
346	if (j == 0 && sum != lastSum + len * OPS_PER_ITER)
347	throw new Error(name);
348
349	elapsed = System.nanoTime() - startTime;
350	++j;
351	if (j >= minIters &&
352	(j >= maxIters \|\| elapsed >= timeLimit))
353	break;
354	// non-warmup - swap some keys for next insert
355	if (minIters != 1 && randomSearches)
356	shuffleSome(ins, len, len >>> 3);
357	}
358	long ops = ((long) j) * len * OPS_PER_ITER;
359	lastSum = sum;
360	return elapsed / ops;
361	}
362
363	}
364
365	static final Random rng = new Random(3122688);
366
367	// Shuffle the subarrays for each size. This doesn't fully
368	// randomize, but the remaining partial locality is arguably a bit
369	// more realistic
370	static void scramble(Object[] a) {
371	for (int k = 0; k < sizes.length; ++k) {
372	int origin = (k == 0) ? 0 : sizes[k-1];
373	for (int i = sizes[k]; i > origin + 1; i--) {
374	Object t = a[i-1];
375	int r = rng.nextInt(i - origin) + origin;
376	a[i-1] = a[r];
377	a[r] = t;
378	}
379	}
380	}
381
382	// plain array shuffle
383	static void shuffle(Object[] a, int size) {
384	for (int i = size; i > 1; i--) {
385	Object t = a[i-1];
386	int r = rng.nextInt(i);
387	a[i-1] = a[r];
388	a[r] = t;
389	}
390	}
391
392	// swap nswaps elements
393	static void shuffleSome(Object[] a, int size, int nswaps) {
394	for (int s = 0; s < nswaps; ++s) {
395	int i = rng.nextInt(size);
396	int r = rng.nextInt(size);
397	Object t = a[i];
398	a[i] = a[r];
399	a[r] = t;
400	}
401	}
402
403	// Integer-like class with random hash codes
404	static final class RandomInt {
405	static int seed = 3122688;
406	static int next() { // a non-xorshift, 2^32-period RNG
407	int x = seed;
408	int lo = 16807 * (x & 0xFFFF);
409	int hi = 16807 * (x >>> 16);
410	lo += (hi & 0x7FFF) << 16;
411	if ((lo & 0x80000000) != 0) {
412	lo &= 0x7fffffff;
413	++lo;
414	}
415	lo += hi >>> 15;
416	if (lo == 0 \|\| (lo & 0x80000000) != 0) {
417	lo &= 0x7fffffff;
418	++lo;
419	}
420	seed = lo;
421	return x;
422	}
423	final int value;
424	RandomInt() { value = next(); }
425	public int hashCode() { return value; }
426	public boolean equals(Object x) {
427	return (x instanceof RandomInt) && ((RandomInt)x).value == value;
428	}
429	}
430
431	// Read in String keys from file if possible
432	static void initStringKeys(Object[] keys, int n) throws Exception {
433	FileInputStream fr = null;
434	try {
435	fr = new FileInputStream(wordFile);
436	} catch (IOException ex) {
437	System.out.println("No word file. Using String.valueOf(i)");
438	for (int i = 0; i < n; i++)
439	keys[i] = String.valueOf(i);
440	return;
441	}
442
443	BufferedInputStream in = new BufferedInputStream(fr);
444	int k = 0;
445	outer: while (k < n) {
446	StringBuffer sb = new StringBuffer();
447	for (;;) {
448	int c = in.read();
449	if (c < 0)
450	break outer;
451	char ch = (char) c;
452	if (ch == '\n') {
453	keys[k++] = sb.toString();
454	break;
455	}
456	if (!Character.isWhitespace(ch))
457	sb.append(ch);
458	}
459	}
460	in.close();
461
462	// fill up remaining keys with path-like compounds of previous pairs
463	int j = 0;
464	while (k < n)
465	keys[k++] = (String) keys[j++] + "/" + (String) keys[j];
466	}
467
468	}