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) {
            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.17
Committed:	Thu Jan 15 18:34:19 2015 UTC (9 years, 4 months ago) by jsr166
Branch:	MAIN
Changes since 1.16:	+0 -2 lines
Log Message:	delete extraneous blank lines
#	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	jsr166	1.10	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7	dl	1.3	import java.io.*;
8	dl	1.1	import java.math.*;
9	jsr166	1.16	import java.util.*;
10	dl	1.1
11			/**
12			* A micro-benchmark with key types and operation mixes roughly
13			* corresponding to some real programs.
14	jsr166	1.4	*
15	dl	1.1	* The main results are a table of approximate nanoseconds per
16			* element-operation (averaged across get, put etc) for each type,
17	dl	1.2	* 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	dl	1.1	*
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	jsr166	1.4	*
28	dl	1.1	* By default, it creates and inserts in order dense numerical keys
29	dl	1.3	* 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	jsr166	1.5	* can create one from a real dictionary (1 line per word) and then run
35	dl	1.3	* linux "shuf" to randomize entries. If no file exists, it uses
36			* String.valueOf(i) for element i.
37	dl	1.1	*/
38			public class MapMicroBenchmark {
39	dl	1.3	static final String wordFile = "testwords.txt";
40
41	jsr166	1.15	static Class<?> mapClass;
42	dl	1.1	static boolean randomSearches = true;
43
44	dl	1.2	// Nanoseconds per run
45			static final long NANOS_PER_JOB = 6L * 1000L1000L1000L;
46			static final long NANOS_PER_WARMUP = 100L1000L1000L;
47	dl	1.1
48			// map operations per item per iteration -- change if job.work changed
49			static final int OPS_PER_ITER = 11;
50	dl	1.3	static final int MIN_ITERS_PER_TEST = 3; // must be > 1
51	dl	1.2	static final int MAX_ITERS_PER_TEST = 1000000; // avoid runaway
52	dl	1.1
53			// sizes are at halfway points for HashMap default resizes
54	dl	1.2	static final int firstSize = 9;
55	dl	1.1	static final int sizeStep = 4; // each size 4X last
56	dl	1.2	static final int nsizes = 9;
57	dl	1.1	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	jsr166	1.4
65	dl	1.1	mapClass = Class.forName(args[0]);
66
67			if (args.length > 1) {
68			if (args[1].startsWith("s"))
69	dl	1.3	randomSearches = false;
70	dl	1.1	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	dl	1.3	int njobs = 10;
90			Job[] jobs = new Job[njobs];
91	dl	1.2
92			Object[] os = new Object[n];
93	dl	1.3	for (int i = 0; i < n; i++) os[i] = new Object();
94			jobs[0] = new Job("Object ", os, Object.class);
95
96	dl	1.1	Object[] ss = new Object[n];
97	dl	1.3	initStringKeys(ss, n);
98			jobs[1] = new Job("String ", ss, String.class);
99
100	dl	1.1	Object[] is = new Object[n];
101	dl	1.3	for (int i = 0; i < n; i++) is[i] = Integer.valueOf(i);
102			jobs[2] = new Job("Integer ", is, Integer.class);
103
104	dl	1.1	Object[] ls = new Object[n];
105	jsr166	1.8	for (int i = 0; i < n; i++) ls[i] = Long.valueOf((long) i);
106	dl	1.3	jobs[3] = new Job("Long ", ls, Long.class);
107
108	dl	1.1	Object[] fs = new Object[n];
109	jsr166	1.8	for (int i = 0; i < n; i++) fs[i] = Float.valueOf((float) i);
110	dl	1.3	jobs[4] = new Job("Float ", fs, Float.class);
111
112	dl	1.1	Object[] ds = new Object[n];
113	jsr166	1.8	for (int i = 0; i < n; i++) ds[i] = Double.valueOf((double) i);
114	dl	1.3	jobs[5] = new Job("Double ", ds, Double.class);
115
116	dl	1.1	Object[] bs = new Object[n];
117	dl	1.3	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	dl	1.1	Object[] es = new Object[n];
122	dl	1.3	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	dl	1.2
126	dl	1.3	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	dl	1.1
130	dl	1.3	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	dl	1.2	}
138	dl	1.3	jobs[9] = new Job("Mixed ", ms, Object.class);
139			Job mixed = jobs[9];
140	dl	1.2
141	dl	1.3	warmup1(mixed);
142	dl	1.2	warmup2(jobs);
143	dl	1.3	warmup1(mixed);
144	dl	1.2	warmup3(jobs);
145			Thread.sleep(500);
146	jsr166	1.9	time(jobs);
147	dl	1.1	}
148
149	dl	1.2	static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable {
150	jsr166	1.12	for (int k = 0; k < nsizes; ++k) {
151	dl	1.1	int len = sizes[k];
152			for (int i = 0; i < jobs.length; i++) {
153			Thread.sleep(50);
154	dl	1.2	jobs[i].nanos[k] = jobs[i].work(len, minIters, maxIters, timeLimit);
155	dl	1.1	System.out.print(".");
156			}
157			}
158			System.out.println();
159			}
160
161	dl	1.2	// First warmup -- run only mixed job to discourage type specialization
162			static void warmup1(Job job) throws Throwable {
163	jsr166	1.12	for (int k = 0; k < nsizes; ++k)
164	dl	1.2	job.work(sizes[k], 1, 1, 0);
165			}
166
167			// Second, run each once
168			static void warmup2(Job[] jobs) throws Throwable {
169	dl	1.1	System.out.print("warm up");
170	dl	1.2	runWork(jobs, 1, 1, 0);
171	dl	1.1	long ck = jobs[0].checkSum;
172	dl	1.2	for (int i = 1; i < jobs.length - 1; i++) {
173	dl	1.1	if (jobs[i].checkSum != ck)
174			throw new Error("CheckSum");
175			}
176			}
177
178	dl	1.2	// 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	dl	1.1	static void time(Job[] jobs) throws Throwable {
185			System.out.print("running");
186	dl	1.2	runWork(jobs, MIN_ITERS_PER_TEST, MAX_ITERS_PER_TEST, NANOS_PER_JOB);
187	dl	1.1
188			System.out.print("Type/Size:");
189			for (int k = 0; k < nsizes; ++k)
190	dl	1.2	System.out.printf("%7d", sizes[k]);
191	dl	1.1	System.out.println();
192
193			long[] aves = new long[nsizes];
194			int njobs = jobs.length;
195
196	jsr166	1.9	for (int i = 0; i < njobs; i++) {
197	dl	1.1	System.out.print(jobs[i].name);
198			for (int k = 0; k < nsizes; ++k) {
199			long nanos = jobs[i].nanos[k];
200	dl	1.2	System.out.printf("%7d", nanos);
201	dl	1.1	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	dl	1.2	System.out.printf("%7d", (aves[k] / njobs));
210			System.out.println("\n");
211	dl	1.1	}
212
213			static final class Job {
214	jsr166	1.9	final String name;
215	jsr166	1.15	final Class<?> elementClass;
216	dl	1.1	long[] nanos = new long[nsizes];
217			final Object[] items;
218	dl	1.2	Object[] searches;
219	dl	1.1	volatile long checkSum;
220			volatile int lastSum;
221	jsr166	1.15	Job(String name, Object[] items, Class<?> elementClass) {
222	dl	1.1	this.name = name;
223			this.items = items;
224	dl	1.2	this.elementClass = elementClass;
225	dl	1.1	if (randomSearches) {
226	dl	1.2	scramble(items);
227			this.searches = new Object[items.length];
228			System.arraycopy(items, 0, searches, 0, items.length);
229			scramble(searches);
230	dl	1.1	}
231			else
232	dl	1.2	this.searches = items;
233	dl	1.1	}
234
235	dl	1.2	public long work(int len, int minIters, int maxIters, long timeLimit) {
236			Map m;
237			try {
238	jsr166	1.6	m = (Map) mapClass.newInstance();
239			} catch (Exception e) {
240	dl	1.2	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
241			}
242	dl	1.1	Object[] ins = items;
243	dl	1.2	Object[] keys = searches;
244	dl	1.1
245			if (ins.length < len \|\| keys.length < len)
246			throw new Error(name);
247			int half = len / 2;
248	dl	1.2	int quarter = half / 2;
249	dl	1.1	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	dl	1.2	sum += len - half;
261	dl	1.1	for (int i = 0; i < len; ++i) {
262			Object x = keys[i];
263	jsr166	1.4	Object v = m.get(x);
264	dl	1.2	if (elementClass.isInstance(v)) // touch v
265			++sum;
266	dl	1.1	}
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	jsr166	1.4	if (elementClass.isInstance(e))
276	dl	1.1	++sum;
277			}
278			checkSum += sum ^ (sum << 4);
279			for (Object e : m.values()) {
280	jsr166	1.4	if (elementClass.isInstance(e))
281	dl	1.1	++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	dl	1.2	if (elementClass.isInstance(v))
288	dl	1.1	++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	dl	1.2	if (elementClass.isInstance(v))
295	dl	1.1	++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	dl	1.2	if (v == m.get(x))
309	dl	1.1	++sum;
310			}
311			checkSum += sum ^ (sum << 9);
312			for (int i = len - 1; i >= 0; --i) {
313			Object x = ins[i];
314	dl	1.2	Object v = m.get(x);
315			if (elementClass.isInstance(v))
316	dl	1.1	++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	dl	1.2	if (v == m.get(x))
323	dl	1.1	++sum;
324			}
325			checkSum += sum ^ (sum << 11);
326	dl	1.2	for (int i = 0; i < quarter; ++i) {
327			Object x = keys[i];
328			if (m.remove(x) != null)
329			++sum;
330	dl	1.1	}
331	dl	1.3	for (int i = 0; i < quarter; ++i) {
332			Object x = keys[i];
333			if (m.put(x, x) == null)
334			++sum;
335			}
336	dl	1.11	/* // 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	dl	1.2	m.clear();
343	dl	1.3	sum += len - (quarter * 2);
344	dl	1.1	checkSum += sum ^ (sum << 12);
345
346	dl	1.3	if (j == 0 && sum != lastSum + len * OPS_PER_ITER)
347			throw new Error(name);
348	jsr166	1.4
349	dl	1.1	elapsed = System.nanoTime() - startTime;
350			++j;
351	dl	1.2	if (j >= minIters &&
352			(j >= maxIters \|\| elapsed >= timeLimit))
353	dl	1.1	break;
354	dl	1.3	// non-warmup - swap some keys for next insert
355	jsr166	1.4	if (minIters != 1 && randomSearches)
356	dl	1.3	shuffleSome(ins, len, len >>> 3);
357	dl	1.1	}
358	jsr166	1.8	long ops = ((long) j) * len * OPS_PER_ITER;
359	dl	1.1	lastSum = sum;
360			return elapsed / ops;
361			}
362
363			}
364
365	dl	1.2	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	jsr166	1.6	int origin = (k == 0) ? 0 : sizes[k-1];
373	dl	1.2	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	jsr166	1.4	}
381	dl	1.1
382	dl	1.2	// plain array shuffle
383	dl	1.1	static void shuffle(Object[] a, int size) {
384	jsr166	1.13	for (int i = size; i > 1; i--) {
385	dl	1.1	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	dl	1.3	// 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	dl	1.2
431	dl	1.3	// Read in String keys from file if possible
432	jsr166	1.4	static void initStringKeys(Object[] keys, int n) throws Exception {
433	dl	1.3	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	jsr166	1.14	outer: while (k < n) {
446	dl	1.3	StringBuffer sb = new StringBuffer();
447			for (;;) {
448			int c = in.read();
449	jsr166	1.4	if (c < 0)
450	dl	1.3	break outer;
451	jsr166	1.8	char ch = (char) c;
452	dl	1.3	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	jsr166	1.7	keys[k++] = (String) keys[j++] + "/" + (String) keys[j];
466	dl	1.3	}
467	dl	1.2
468	dl	1.1	}