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.
 *
 * 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;

    static final long NANOS_PER_JOB = 8L * 1000L*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 = 2;
    static final int MAX_ITERS_PER_TEST = 1000000;

    // sizes are at halfway points for HashMap default resizes
    static final int firstSize = 36;
    static final int sizeStep = 4; // each size 4X last
    static final int nsizes = 8;
    static final int[] sizes = new int[nsizes];

    static final class Missing {} // class for guaranteed non-matches
    static final Object MISSING = new Missing();

    static Map newMap() {
        try {
            return (Map)mapClass.newInstance();
        } catch(Exception e) {
            throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
        }
    }

    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;

        Object[] ss = new Object[n];
        Object[] os = 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];

        // To guarantee uniqueness, use xorshift for "random" versions
        int j = randomKeys? 1234567 : 0;
        for (int i = 0; i < n; i++) {
            ss[i] = String.valueOf(j);
            os[i] = new Object();
            is[i] = Integer.valueOf(j);
            ls[i] = Long.valueOf((long)j);
            fs[i] = Float.valueOf((float)i); // can't use random for float
            ds[i] = Double.valueOf((double)j);
            bs[i] = BigInteger.valueOf(j);
            es[i] = BigDecimal.valueOf(j);
            j = randomKeys? xorshift(j) : j + 1;
        }

        List<Job> list = new ArrayList<Job>();
        list.add(new Job("BigDecimal", es));
        list.add(new Job("BigInteger", bs));
        list.add(new Job("String    ", ss));
        list.add(new Job("Double    ", ds));
        list.add(new Job("Float     ", fs));
        list.add(new Job("Long      ", ls));
        list.add(new Job("Integer   ", is));
        list.add(new Job("Object    ", os));

        Job[] jobs = list.toArray(new Job[0]);
        warmup(jobs);
        warmup(jobs);
        time(jobs);
    }

    static void runWork(Job[] jobs, int maxIters) throws Throwable {
        for (int k = 0; k <  nsizes; ++k) {
            int len = sizes[k];
            for (int i = 0; i < jobs.length; i++) {
                jobs[i].setup(len);
                Thread.sleep(50);
                jobs[i].nanos[k] = jobs[i].work(len, maxIters);
                System.out.print(".");
            }
        }
        System.out.println();
    }

    static void warmup(Job[] jobs) throws Throwable {
        System.out.print("warm up");
        runWork(jobs, MIN_ITERS_PER_TEST);
        long ck = jobs[0].checkSum;
        for (int i = 1; i < jobs.length; i++) {
            if (jobs[i].checkSum != ck)
                throw new Error("CheckSum");
        }
    }

    static void time(Job[] jobs) throws Throwable {
        System.out.print("running");
        runWork(jobs, MAX_ITERS_PER_TEST);

        System.out.print("Type/Size:");
        for (int k = 0; k < nsizes; ++k)
            System.out.printf("%8d", 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("%8d", nanos);
                aves[k] += nanos;
            }
            System.out.println();
        }

        System.out.println();
        System.out.print("average   ");
        for (int k = 0; k < nsizes; ++k)
            System.out.printf("%8d", (aves[k] / njobs));
        System.out.println();
    }


    static final class Job {
        final String name;
        long[] nanos = new long[nsizes];
        final Object[] items;
        final Object[] dups;
        Object[] reordered;
        volatile long checkSum;
        volatile int lastSum;
        Job(String name, Object[] items) {
            this.name = name;
            this.items = items;
            if (randomSearches)
                this.dups = new Object[items.length];
            else
                this.dups = items;
        }

        public void setup(int len) {
            if (randomSearches) {
                System.arraycopy(items, 0, dups, 0, len);
                shuffle(dups, len);
                reordered = dups;
            }
            else
                reordered = items;
        }

        public long work(int len, int maxIters) {
            Object[] ins = items;
            Object[] keys = reordered;

            if (ins.length < len || keys.length < len)
                throw new Error(name);
            int half = len / 2;
            Class eclass = ins[0].getClass();
            int sum = lastSum;
            long startTime = System.nanoTime();
            long elapsed;
            Map m = newMap();
            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
                for (int i = 0; i < len; ++i) {
                    Object x = keys[i];
                    Object v = m.get(x); 
                    if (v != null && v.getClass() == eclass) // touch v
                        sum += 2;
                }
                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 (e.getClass() == eclass)
                        ++sum;
                }
                checkSum += sum ^ (sum << 4);
                for (Object e : m.values()) {
                    if (e.getClass() == eclass)
                        ++sum;
                }
                checkSum += sum ^ (sum << 5);
                for (int i = len - 1; i >= 0; --i) {
                    Object x = keys[i];
                    Object v = m.get(x);
                    if (v != null && v.getClass() == eclass)
                        ++sum;
                }
                checkSum += sum ^ (sum << 6);
                for (int i = 0; i < len; ++i) {
                    Object x = ins[i];
                    Object v = m.get(x);
                    if (v != null && v.getClass() == eclass)
                        ++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.equals(m.get(x)))
                        ++sum;
                }
                checkSum += sum ^ (sum << 9);
                for (int i = len - 1; i >= 0; --i) {
                    Object x = ins[i];
                    if (m.get(x) != MISSING)
                        ++sum;
                }
                checkSum += sum ^ (sum << 10);
                for (int i = len - 1; i >= 0; --i) {
                    Object x = keys[i];
                    Object v = ins[i];
                    if (v.equals(m.get(x)))
                        ++sum;
                }
                checkSum += sum ^ (sum << 11);
                if ((j & 1) == 1) { // lower remove rate
                    for (int i = 0; i < len; ++i) {
                        Object x = keys[i];
                        if (m.remove(x) != null)
                            ++sum;
                    }
                }
                else {
                    m.clear();
                    sum += len;
                }
                checkSum += sum ^ (sum << 12);

                elapsed = System.nanoTime() - startTime;
                ++j;
                if (j >= MIN_ITERS_PER_TEST &&
                    (j >= maxIters || elapsed >= NANOS_PER_JOB))
                    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(3152688);

    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.1
Committed:	Wed Jul 1 11:24:49 2009 UTC (14 years, 10 months ago) by dl
Branch:	MAIN
Log Message:	Initial checkin
#	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.
17	*
18	* The program includes a bunch of microbenchmarking safeguards that
19	* might underestimate typical performance. For example, by using many
20	* different key types and exercising them in warmups it disables most
21	* dynamic type specialization. Some test classes, like Float and
22	* BigDecimal are included not because they are commonly used as keys,
23	* but because they can be problematic for some map implementations.
24	*
25	* By default, it creates and inserts in order dense numerical keys
26	* and searches for keys in scrambled order. Use "r" as second arg to
27	* instead use random numerical values, and "s" as third arg to search
28	* in insertion order.
29	*/
30	public class MapMicroBenchmark {
31	static Class mapClass;
32	static boolean randomSearches = true;
33	static boolean randomKeys = false;
34
35	static final long NANOS_PER_JOB = 8L * 1000L1000L1000L;
36
37	// map operations per item per iteration -- change if job.work changed
38	static final int OPS_PER_ITER = 11;
39	static final int MIN_ITERS_PER_TEST = 2;
40	static final int MAX_ITERS_PER_TEST = 1000000;
41
42	// sizes are at halfway points for HashMap default resizes
43	static final int firstSize = 36;
44	static final int sizeStep = 4; // each size 4X last
45	static final int nsizes = 8;
46	static final int[] sizes = new int[nsizes];
47
48	static final class Missing {} // class for guaranteed non-matches
49	static final Object MISSING = new Missing();
50
51	static Map newMap() {
52	try {
53	return (Map)mapClass.newInstance();
54	} catch(Exception e) {
55	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
56	}
57	}
58
59	public static void main(String[] args) throws Throwable {
60	if (args.length == 0) {
61	System.out.println("Usage: java MapMicroBenchmark className [r\|s]keys [r\|s]searches");
62	return;
63	}
64
65	mapClass = Class.forName(args[0]);
66
67	if (args.length > 1) {
68	if (args[1].startsWith("s"))
69	randomKeys = false;
70	else if (args[1].startsWith("r"))
71	randomKeys = true;
72	}
73	if (args.length > 2) {
74	if (args[2].startsWith("s"))
75	randomSearches = false;
76	else if (args[2].startsWith("r"))
77	randomSearches = true;
78	}
79
80	System.out.print("Class " + mapClass.getName());
81	if (randomKeys)
82	System.out.print(" random keys");
83	else
84	System.out.print(" sequential keys");
85	if (randomSearches)
86	System.out.print(" randomized searches");
87	else
88	System.out.print(" sequential searches");
89
90	System.out.println();
91
92	int n = firstSize;
93	for (int i = 0; i < nsizes - 1; ++i) {
94	sizes[i] = n;
95	n *= sizeStep;
96	}
97	sizes[nsizes - 1] = n;
98
99	Object[] ss = new Object[n];
100	Object[] os = new Object[n];
101	Object[] is = new Object[n];
102	Object[] ls = new Object[n];
103	Object[] fs = new Object[n];
104	Object[] ds = new Object[n];
105	Object[] bs = new Object[n];
106	Object[] es = new Object[n];
107
108	// To guarantee uniqueness, use xorshift for "random" versions
109	int j = randomKeys? 1234567 : 0;
110	for (int i = 0; i < n; i++) {
111	ss[i] = String.valueOf(j);
112	os[i] = new Object();
113	is[i] = Integer.valueOf(j);
114	ls[i] = Long.valueOf((long)j);
115	fs[i] = Float.valueOf((float)i); // can't use random for float
116	ds[i] = Double.valueOf((double)j);
117	bs[i] = BigInteger.valueOf(j);
118	es[i] = BigDecimal.valueOf(j);
119	j = randomKeys? xorshift(j) : j + 1;
120	}
121
122	List<Job> list = new ArrayList<Job>();
123	list.add(new Job("BigDecimal", es));
124	list.add(new Job("BigInteger", bs));
125	list.add(new Job("String ", ss));
126	list.add(new Job("Double ", ds));
127	list.add(new Job("Float ", fs));
128	list.add(new Job("Long ", ls));
129	list.add(new Job("Integer ", is));
130	list.add(new Job("Object ", os));
131
132	Job[] jobs = list.toArray(new Job[0]);
133	warmup(jobs);
134	warmup(jobs);
135	time(jobs);
136	}
137
138	static void runWork(Job[] jobs, int maxIters) throws Throwable {
139	for (int k = 0; k < nsizes; ++k) {
140	int len = sizes[k];
141	for (int i = 0; i < jobs.length; i++) {
142	jobs[i].setup(len);
143	Thread.sleep(50);
144	jobs[i].nanos[k] = jobs[i].work(len, maxIters);
145	System.out.print(".");
146	}
147	}
148	System.out.println();
149	}
150
151	static void warmup(Job[] jobs) throws Throwable {
152	System.out.print("warm up");
153	runWork(jobs, MIN_ITERS_PER_TEST);
154	long ck = jobs[0].checkSum;
155	for (int i = 1; i < jobs.length; i++) {
156	if (jobs[i].checkSum != ck)
157	throw new Error("CheckSum");
158	}
159	}
160
161	static void time(Job[] jobs) throws Throwable {
162	System.out.print("running");
163	runWork(jobs, MAX_ITERS_PER_TEST);
164
165	System.out.print("Type/Size:");
166	for (int k = 0; k < nsizes; ++k)
167	System.out.printf("%8d", sizes[k]);
168	System.out.println();
169
170	long[] aves = new long[nsizes];
171	int njobs = jobs.length;
172
173	for (int i = 0; i < njobs; i++) {
174	System.out.print(jobs[i].name);
175	for (int k = 0; k < nsizes; ++k) {
176	long nanos = jobs[i].nanos[k];
177	System.out.printf("%8d", nanos);
178	aves[k] += nanos;
179	}
180	System.out.println();
181	}
182
183	System.out.println();
184	System.out.print("average ");
185	for (int k = 0; k < nsizes; ++k)
186	System.out.printf("%8d", (aves[k] / njobs));
187	System.out.println();
188	}
189
190
191	static final class Job {
192	final String name;
193	long[] nanos = new long[nsizes];
194	final Object[] items;
195	final Object[] dups;
196	Object[] reordered;
197	volatile long checkSum;
198	volatile int lastSum;
199	Job(String name, Object[] items) {
200	this.name = name;
201	this.items = items;
202	if (randomSearches)
203	this.dups = new Object[items.length];
204	else
205	this.dups = items;
206	}
207
208	public void setup(int len) {
209	if (randomSearches) {
210	System.arraycopy(items, 0, dups, 0, len);
211	shuffle(dups, len);
212	reordered = dups;
213	}
214	else
215	reordered = items;
216	}
217
218	public long work(int len, int maxIters) {
219	Object[] ins = items;
220	Object[] keys = reordered;
221
222	if (ins.length < len \|\| keys.length < len)
223	throw new Error(name);
224	int half = len / 2;
225	Class eclass = ins[0].getClass();
226	int sum = lastSum;
227	long startTime = System.nanoTime();
228	long elapsed;
229	Map m = newMap();
230	int j = 0;
231	for (;;) {
232	for (int i = 0; i < half; ++i) {
233	Object x = ins[i];
234	if (m.put(x, x) == null)
235	++sum;
236	}
237	checkSum += sum ^ (sum << 1); // help avoid loop merging
238	for (int i = 0; i < len; ++i) {
239	Object x = keys[i];
240	Object v = m.get(x);
241	if (v != null && v.getClass() == eclass) // touch v
242	sum += 2;
243	}
244	checkSum += sum ^ (sum << 2);
245	for (int i = half; i < len; ++i) {
246	Object x = ins[i];
247	if (m.put(x, x) == null)
248	++sum;
249	}
250	checkSum += sum ^ (sum << 3);
251	for (Object e : m.keySet()) {
252	if (e.getClass() == eclass)
253	++sum;
254	}
255	checkSum += sum ^ (sum << 4);
256	for (Object e : m.values()) {
257	if (e.getClass() == eclass)
258	++sum;
259	}
260	checkSum += sum ^ (sum << 5);
261	for (int i = len - 1; i >= 0; --i) {
262	Object x = keys[i];
263	Object v = m.get(x);
264	if (v != null && v.getClass() == eclass)
265	++sum;
266	}
267	checkSum += sum ^ (sum << 6);
268	for (int i = 0; i < len; ++i) {
269	Object x = ins[i];
270	Object v = m.get(x);
271	if (v != null && v.getClass() == eclass)
272	++sum;
273	}
274	checkSum += sum ^ (sum << 7);
275	for (int i = 0; i < len; ++i) {
276	Object x = keys[i];
277	Object v = ins[i];
278	if (m.put(x, v) == x)
279	++sum;
280	}
281	checkSum += sum ^ (sum << 8);
282	for (int i = 0; i < len; ++i) {
283	Object x = keys[i];
284	Object v = ins[i];
285	if (v.equals(m.get(x)))
286	++sum;
287	}
288	checkSum += sum ^ (sum << 9);
289	for (int i = len - 1; i >= 0; --i) {
290	Object x = ins[i];
291	if (m.get(x) != MISSING)
292	++sum;
293	}
294	checkSum += sum ^ (sum << 10);
295	for (int i = len - 1; i >= 0; --i) {
296	Object x = keys[i];
297	Object v = ins[i];
298	if (v.equals(m.get(x)))
299	++sum;
300	}
301	checkSum += sum ^ (sum << 11);
302	if ((j & 1) == 1) { // lower remove rate
303	for (int i = 0; i < len; ++i) {
304	Object x = keys[i];
305	if (m.remove(x) != null)
306	++sum;
307	}
308	}
309	else {
310	m.clear();
311	sum += len;
312	}
313	checkSum += sum ^ (sum << 12);
314
315	elapsed = System.nanoTime() - startTime;
316	++j;
317	if (j >= MIN_ITERS_PER_TEST &&
318	(j >= maxIters \|\| elapsed >= NANOS_PER_JOB))
319	break;
320	}
321	long ops = ((long)j) * len * OPS_PER_ITER;
322	if (sum != lastSum + (int)ops)
323	throw new Error(name);
324	lastSum = sum;
325	return elapsed / ops;
326	}
327
328	}
329
330	static final int xorshift(int seed) {
331	seed ^= seed << 1;
332	seed ^= seed >>> 3;
333	seed ^= seed << 10;
334	return seed;
335	}
336
337
338	static final Random rng = new Random(3152688);
339
340	static void shuffle(Object[] a, int size) {
341	for (int i= size; i>1; i--) {
342	Object t = a[i-1];
343	int r = rng.nextInt(i);
344	a[i-1] = a[r];
345	a[r] = t;
346	}
347	}
348
349	}
350