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/licenses/publicdomain
 */

import java.util.*;
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 "r" as second arg to
 * instead use random numerical values, and "s" as third arg to search
 * in insertion order.
 */
public class MapMicroBenchmark {
    static Class mapClass;
    static boolean randomSearches = true;
    static boolean randomKeys = false;

    // 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;
    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"))
                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"))
                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
            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 = 9;

        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];
        jobs[0] = new Job("Object    ", os, Object.class);
        jobs[1] = new Job("String    ", ss, String.class);
        jobs[2] = new Job("Integer   ", is, Integer.class);
        jobs[3] = new Job("Long      ", ls, Long.class);
        jobs[4] = new Job("Float     ", fs, Float.class);
        jobs[5] = new Job("Double    ", ds, Double.class);
        jobs[6] = new Job("BigInteger", bs, BigInteger.class);
        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];
        }

        jobs[8] = new Job("Mixed     ", ms, Object.class);

        warmup1(jobs[8]);
        warmup2(jobs);
        warmup1(jobs[8]);
        warmup3(jobs);
        warmup1(jobs[8]);
        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;
                }
                m.clear();
                sum += len - quarter;
                checkSum += sum ^ (sum << 12);

                elapsed = System.nanoTime() - startTime;
                ++j;
                if (j >= minIters &&
                    (j >= maxIters || elapsed >= timeLimit))
                    break;
            }
            long ops = ((long)j) * len * OPS_PER_ITER;
            if (sum != lastSum + (int)ops)
                throw new Error(name);
            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);

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


}

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