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

/**
 * A micro-benchmark with key types and operation mixes roughly
 * corresponding to some real programs.
 *
 * The main results are a table of approximate nanoseconds per
 * element-operation (averaged across get, put etc) for each type,
 * across a range of map sizes. It also includes category "Mixed"
 * that includes elements of multiple types including those with
 * identical hash codes.
 *
 * The program includes a bunch of microbenchmarking safeguards that
 * might underestimate typical performance. For example, by using many
 * different key types and exercising them in warmups it disables most
 * dynamic type specialization.  Some test classes, like Float and
 * BigDecimal are included not because they are commonly used as keys,
 * but because they can be problematic for some map implementations.
 *
 * By default, it creates and inserts in order dense numerical keys
 * and searches for keys in scrambled order. Use "s" as second arg to
 * instead insert and search in unscrambled order.
 *
 * For String keys, the program tries to use file "testwords.txt", which
 * is best used with real words.  We can't check in this file, but you
 * can create one from a real dictonary (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;
                }
                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.4
Committed:	Thu Oct 29 23:09:07 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.3:	+11 -12 lines
Log Message:	whitespace
#	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	dl	1.3	import java.io.*;
9	dl	1.1	import java.math.*;
10
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			* can create one from a real dictonary (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	dl	1.1	*/
38			public class MapMicroBenchmark {
39	dl	1.3	static final String wordFile = "testwords.txt";
40
41	dl	1.1	static Class mapClass;
42			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	dl	1.3	for (int i = 0; i < n; i++) ls[i] = Long.valueOf((long)i);
106			jobs[3] = new Job("Long ", ls, Long.class);
107
108	dl	1.1	Object[] fs = new Object[n];
109	dl	1.3	for (int i = 0; i < n; i++) fs[i] = Float.valueOf((float)i);
110			jobs[4] = new Job("Float ", fs, Float.class);
111
112	dl	1.1	Object[] ds = new Object[n];
113	dl	1.3	for (int i = 0; i < n; i++) ds[i] = Double.valueOf((double)i);
114			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	dl	1.1	time(jobs);
147			}
148
149	dl	1.2	static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable {
150	dl	1.1	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	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			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	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			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	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
214			static final class Job {
215			final String name;
216	dl	1.2	final Class elementClass;
217	dl	1.1	long[] nanos = new long[nsizes];
218			final Object[] items;
219	dl	1.2	Object[] searches;
220	dl	1.1	volatile long checkSum;
221			volatile int lastSum;
222	dl	1.2	Job(String name, Object[] items, Class elementClass) {
223	dl	1.1	this.name = name;
224			this.items = items;
225	dl	1.2	this.elementClass = elementClass;
226	dl	1.1	if (randomSearches) {
227	dl	1.2	scramble(items);
228			this.searches = new Object[items.length];
229			System.arraycopy(items, 0, searches, 0, items.length);
230			scramble(searches);
231	dl	1.1	}
232			else
233	dl	1.2	this.searches = items;
234	dl	1.1	}
235
236	dl	1.2	public long work(int len, int minIters, int maxIters, long timeLimit) {
237			Map m;
238			try {
239			m = (Map)mapClass.newInstance();
240			} catch(Exception e) {
241			throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
242			}
243	dl	1.1	Object[] ins = items;
244	dl	1.2	Object[] keys = searches;
245	dl	1.1
246			if (ins.length < len \|\| keys.length < len)
247			throw new Error(name);
248			int half = len / 2;
249	dl	1.2	int quarter = half / 2;
250	dl	1.1	int sum = lastSum;
251			long startTime = System.nanoTime();
252			long elapsed;
253			int j = 0;
254			for (;;) {
255			for (int i = 0; i < half; ++i) {
256			Object x = ins[i];
257			if (m.put(x, x) == null)
258			++sum;
259			}
260			checkSum += sum ^ (sum << 1); // help avoid loop merging
261	dl	1.2	sum += len - half;
262	dl	1.1	for (int i = 0; i < len; ++i) {
263			Object x = keys[i];
264	jsr166	1.4	Object v = m.get(x);
265	dl	1.2	if (elementClass.isInstance(v)) // touch v
266			++sum;
267	dl	1.1	}
268			checkSum += sum ^ (sum << 2);
269			for (int i = half; i < len; ++i) {
270			Object x = ins[i];
271			if (m.put(x, x) == null)
272			++sum;
273			}
274			checkSum += sum ^ (sum << 3);
275			for (Object e : m.keySet()) {
276	jsr166	1.4	if (elementClass.isInstance(e))
277	dl	1.1	++sum;
278			}
279			checkSum += sum ^ (sum << 4);
280			for (Object e : m.values()) {
281	jsr166	1.4	if (elementClass.isInstance(e))
282	dl	1.1	++sum;
283			}
284			checkSum += sum ^ (sum << 5);
285			for (int i = len - 1; i >= 0; --i) {
286			Object x = keys[i];
287			Object v = m.get(x);
288	dl	1.2	if (elementClass.isInstance(v))
289	dl	1.1	++sum;
290			}
291			checkSum += sum ^ (sum << 6);
292			for (int i = 0; i < len; ++i) {
293			Object x = ins[i];
294			Object v = m.get(x);
295	dl	1.2	if (elementClass.isInstance(v))
296	dl	1.1	++sum;
297			}
298			checkSum += sum ^ (sum << 7);
299			for (int i = 0; i < len; ++i) {
300			Object x = keys[i];
301			Object v = ins[i];
302			if (m.put(x, v) == x)
303			++sum;
304			}
305			checkSum += sum ^ (sum << 8);
306			for (int i = 0; i < len; ++i) {
307			Object x = keys[i];
308			Object v = ins[i];
309	dl	1.2	if (v == m.get(x))
310	dl	1.1	++sum;
311			}
312			checkSum += sum ^ (sum << 9);
313			for (int i = len - 1; i >= 0; --i) {
314			Object x = ins[i];
315	dl	1.2	Object v = m.get(x);
316			if (elementClass.isInstance(v))
317	dl	1.1	++sum;
318			}
319			checkSum += sum ^ (sum << 10);
320			for (int i = len - 1; i >= 0; --i) {
321			Object x = keys[i];
322			Object v = ins[i];
323	dl	1.2	if (v == m.get(x))
324	dl	1.1	++sum;
325			}
326			checkSum += sum ^ (sum << 11);
327	dl	1.2	for (int i = 0; i < quarter; ++i) {
328			Object x = keys[i];
329			if (m.remove(x) != null)
330			++sum;
331	dl	1.1	}
332	dl	1.3	for (int i = 0; i < quarter; ++i) {
333			Object x = keys[i];
334			if (m.put(x, x) == null)
335			++sum;
336			}
337	dl	1.2	m.clear();
338	dl	1.3	sum += len - (quarter * 2);
339	dl	1.1	checkSum += sum ^ (sum << 12);
340
341	dl	1.3	if (j == 0 && sum != lastSum + len * OPS_PER_ITER)
342			throw new Error(name);
343	jsr166	1.4
344	dl	1.1	elapsed = System.nanoTime() - startTime;
345			++j;
346	dl	1.2	if (j >= minIters &&
347			(j >= maxIters \|\| elapsed >= timeLimit))
348	dl	1.1	break;
349	dl	1.3	// non-warmup - swap some keys for next insert
350	jsr166	1.4	if (minIters != 1 && randomSearches)
351	dl	1.3	shuffleSome(ins, len, len >>> 3);
352	dl	1.1	}
353			long ops = ((long)j) * len * OPS_PER_ITER;
354			lastSum = sum;
355			return elapsed / ops;
356			}
357
358			}
359
360
361	dl	1.2	static final Random rng = new Random(3122688);
362
363			// Shuffle the subarrays for each size. This doesn't fully
364			// randomize, but the remaining partial locality is arguably a bit
365			// more realistic
366			static void scramble(Object[] a) {
367			for (int k = 0; k < sizes.length; ++k) {
368			int origin = k == 0? 0 : sizes[k-1];
369			for (int i = sizes[k]; i > origin + 1; i--) {
370			Object t = a[i-1];
371			int r = rng.nextInt(i - origin) + origin;
372			a[i-1] = a[r];
373			a[r] = t;
374			}
375			}
376	jsr166	1.4	}
377	dl	1.1
378	dl	1.2	// plain array shuffle
379	dl	1.1	static void shuffle(Object[] a, int size) {
380			for (int i= size; i>1; i--) {
381			Object t = a[i-1];
382			int r = rng.nextInt(i);
383			a[i-1] = a[r];
384			a[r] = t;
385			}
386			}
387
388	dl	1.3	// swap nswaps elements
389			static void shuffleSome(Object[] a, int size, int nswaps) {
390			for (int s = 0; s < nswaps; ++s) {
391			int i = rng.nextInt(size);
392			int r = rng.nextInt(size);
393			Object t = a[i];
394			a[i] = a[r];
395			a[r] = t;
396			}
397			}
398
399			// Integer-like class with random hash codes
400			static final class RandomInt {
401			static int seed = 3122688;
402			static int next() { // a non-xorshift, 2^32-period RNG
403			int x = seed;
404			int lo = 16807 * (x & 0xFFFF);
405			int hi = 16807 * (x >>> 16);
406			lo += (hi & 0x7FFF) << 16;
407			if ((lo & 0x80000000) != 0) {
408			lo &= 0x7fffffff;
409			++lo;
410			}
411			lo += hi >>> 15;
412			if (lo == 0 \|\| (lo & 0x80000000) != 0) {
413			lo &= 0x7fffffff;
414			++lo;
415			}
416			seed = lo;
417			return x;
418			}
419			final int value;
420			RandomInt() { value = next(); }
421			public int hashCode() { return value; }
422			public boolean equals(Object x) {
423			return (x instanceof RandomInt) && ((RandomInt)x).value == value;
424			}
425			}
426	dl	1.2
427	dl	1.3	// Read in String keys from file if possible
428	jsr166	1.4	static void initStringKeys(Object[] keys, int n) throws Exception {
429	dl	1.3	FileInputStream fr = null;
430			try {
431			fr = new FileInputStream(wordFile);
432			} catch (IOException ex) {
433			System.out.println("No word file. Using String.valueOf(i)");
434			for (int i = 0; i < n; i++)
435			keys[i] = String.valueOf(i);
436			return;
437			}
438
439			BufferedInputStream in = new BufferedInputStream(fr);
440			int k = 0;
441			outer:while (k < n) {
442			StringBuffer sb = new StringBuffer();
443			for (;;) {
444			int c = in.read();
445	jsr166	1.4	if (c < 0)
446	dl	1.3	break outer;
447			char ch = (char)c;
448			if (ch == '\n') {
449			keys[k++] = sb.toString();
450			break;
451			}
452			if (!Character.isWhitespace(ch))
453			sb.append(ch);
454			}
455			}
456			in.close();
457
458			// fill up remaining keys with path-like compounds of previous pairs
459			int j = 0;
460			while (k < n)
461			keys[k++] = (String)keys[j++] + "/" + (String)keys[j];
462			}
463	dl	1.2
464	dl	1.1	}