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
#	User	Rev	Content
1	dl	1.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	dl	1.2	* 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	dl	1.1	*
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	dl	1.2	// Nanoseconds per run
38			static final long NANOS_PER_JOB = 6L * 1000L1000L1000L;
39			static final long NANOS_PER_WARMUP = 100L1000L1000L;
40	dl	1.1
41			// map operations per item per iteration -- change if job.work changed
42			static final int OPS_PER_ITER = 11;
43	dl	1.2	static final int MIN_ITERS_PER_TEST = 3;
44			static final int MAX_ITERS_PER_TEST = 1000000; // avoid runaway
45	dl	1.1
46			// sizes are at halfway points for HashMap default resizes
47	dl	1.2	static final int firstSize = 9;
48	dl	1.1	static final int sizeStep = 4; // each size 4X last
49	dl	1.2	static final int nsizes = 9;
50	dl	1.1	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	dl	1.2	int njobs = 9;
93
94			Object[] os = new Object[n];
95	dl	1.1	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	dl	1.2	Object[] ms = new Object[n];
103
104			for (int i = 0; i < n; i++) {
105			os[i] = new Object();
106			}
107	dl	1.1
108			// To guarantee uniqueness, use xorshift for "random" versions
109	dl	1.2	int rnd = 3122688;
110	dl	1.1	for (int i = 0; i < n; i++) {
111	dl	1.2	rnd = xorshift(rnd);
112			int j = randomKeys? rnd : i;
113	dl	1.1	ss[i] = String.valueOf(j);
114	dl	1.2	}
115
116			for (int i = 0; i < n; i++) {
117			rnd = xorshift(rnd);
118			int j = randomKeys? rnd : i;
119	dl	1.1	is[i] = Integer.valueOf(j);
120	dl	1.2	}
121
122			for (int i = 0; i < n; i++) {
123			rnd = xorshift(rnd);
124			int j = randomKeys? rnd : i;
125	dl	1.1	ls[i] = Long.valueOf((long)j);
126	dl	1.2	}
127
128			for (int i = 0; i < n; i++) {
129			// rnd = xorshift(rnd);
130			// int j = randomKeys? rnd : i;
131	dl	1.1	fs[i] = Float.valueOf((float)i); // can't use random for float
132	dl	1.2	}
133
134			for (int i = 0; i < n; i++) {
135			rnd = xorshift(rnd);
136			int j = randomKeys? rnd : i;
137	dl	1.1	ds[i] = Double.valueOf((double)j);
138	dl	1.2	}
139
140			for (int i = 0; i < n; i++) {
141			rnd = xorshift(rnd);
142			int j = randomKeys? rnd : i;
143	dl	1.1	bs[i] = BigInteger.valueOf(j);
144	dl	1.2	}
145
146			for (int i = 0; i < n; i++) {
147			rnd = xorshift(rnd);
148			int j = randomKeys? rnd : i;
149	dl	1.1	es[i] = BigDecimal.valueOf(j);
150			}
151
152	dl	1.2	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	dl	1.1	time(jobs);
179			}
180
181	dl	1.2	static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable {
182	dl	1.1	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	dl	1.2	jobs[i].nanos[k] = jobs[i].work(len, minIters, maxIters, timeLimit);
187	dl	1.1	System.out.print(".");
188			}
189			}
190			System.out.println();
191			}
192
193	dl	1.2	// 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	dl	1.1	System.out.print("warm up");
202	dl	1.2	runWork(jobs, 1, 1, 0);
203	dl	1.1	long ck = jobs[0].checkSum;
204	dl	1.2	for (int i = 1; i < jobs.length - 1; i++) {
205	dl	1.1	if (jobs[i].checkSum != ck)
206			throw new Error("CheckSum");
207			}
208			}
209
210	dl	1.2	// 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	dl	1.1	static void time(Job[] jobs) throws Throwable {
217			System.out.print("running");
218	dl	1.2	runWork(jobs, MIN_ITERS_PER_TEST, MAX_ITERS_PER_TEST, NANOS_PER_JOB);
219	dl	1.1
220			System.out.print("Type/Size:");
221			for (int k = 0; k < nsizes; ++k)
222	dl	1.2	System.out.printf("%7d", sizes[k]);
223	dl	1.1	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	dl	1.2	System.out.printf("%7d", nanos);
233	dl	1.1	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	dl	1.2	System.out.printf("%7d", (aves[k] / njobs));
242			System.out.println("\n");
243	dl	1.1	}
244
245
246			static final class Job {
247			final String name;
248	dl	1.2	final Class elementClass;
249	dl	1.1	long[] nanos = new long[nsizes];
250			final Object[] items;
251	dl	1.2	Object[] searches;
252	dl	1.1	volatile long checkSum;
253			volatile int lastSum;
254	dl	1.2	Job(String name, Object[] items, Class elementClass) {
255	dl	1.1	this.name = name;
256			this.items = items;
257	dl	1.2	this.elementClass = elementClass;
258	dl	1.1	if (randomSearches) {
259	dl	1.2	scramble(items);
260			this.searches = new Object[items.length];
261			System.arraycopy(items, 0, searches, 0, items.length);
262			scramble(searches);
263	dl	1.1	}
264			else
265	dl	1.2	this.searches = items;
266	dl	1.1	}
267
268	dl	1.2	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	dl	1.1	Object[] ins = items;
276	dl	1.2	Object[] keys = searches;
277	dl	1.1
278			if (ins.length < len \|\| keys.length < len)
279			throw new Error(name);
280			int half = len / 2;
281	dl	1.2	int quarter = half / 2;
282	dl	1.1	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	dl	1.2	sum += len - half;
294	dl	1.1	for (int i = 0; i < len; ++i) {
295			Object x = keys[i];
296			Object v = m.get(x);
297	dl	1.2	if (elementClass.isInstance(v)) // touch v
298			++sum;
299	dl	1.1	}
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	dl	1.2	if (elementClass.isInstance(e))
309	dl	1.1	++sum;
310			}
311			checkSum += sum ^ (sum << 4);
312			for (Object e : m.values()) {
313	dl	1.2	if (elementClass.isInstance(e))
314	dl	1.1	++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	dl	1.2	if (elementClass.isInstance(v))
321	dl	1.1	++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	dl	1.2	if (elementClass.isInstance(v))
328	dl	1.1	++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	dl	1.2	if (v == m.get(x))
342	dl	1.1	++sum;
343			}
344			checkSum += sum ^ (sum << 9);
345			for (int i = len - 1; i >= 0; --i) {
346			Object x = ins[i];
347	dl	1.2	Object v = m.get(x);
348			if (elementClass.isInstance(v))
349	dl	1.1	++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	dl	1.2	if (v == m.get(x))
356	dl	1.1	++sum;
357			}
358			checkSum += sum ^ (sum << 11);
359	dl	1.2	for (int i = 0; i < quarter; ++i) {
360			Object x = keys[i];
361			if (m.remove(x) != null)
362			++sum;
363	dl	1.1	}
364	dl	1.2	m.clear();
365			sum += len - quarter;
366	dl	1.1	checkSum += sum ^ (sum << 12);
367
368			elapsed = System.nanoTime() - startTime;
369			++j;
370	dl	1.2	if (j >= minIters &&
371			(j >= maxIters \|\| elapsed >= timeLimit))
372	dl	1.1	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	dl	1.2	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	dl	1.1
408	dl	1.2	// plain array shuffle
409	dl	1.1	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	dl	1.2
419
420	dl	1.1	}
421