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
#	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			* 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