ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/loops/MapMicroBenchmark.java

Comparing jsr166/src/test/loops/MapMicroBenchmark.java (file contents):
Revision 1.1 by dl, Wed Jul 1 11:24:49 2009 UTC vs.
Revision 1.2 by dl, Wed Jul 22 16:19:51 2009 UTC

#	Line 13 | Line 13 | import java.math.*;
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.
16	>	* across a range of map sizes. It also includes category "Mixed"
17	>	* that includes elements of multiple types including those with
18	>	* identical hash codes.
19		*
20		* The program includes a bunch of microbenchmarking safeguards that
21		* might underestimate typical performance. For example, by using many
#	Line 32 | Line 34 | public class MapMicroBenchmark {
34		static boolean randomSearches = true;
35		static boolean randomKeys = false;
36
37	<	static final long NANOS_PER_JOB = 8L * 1000L*1000L*1000L;
37	>	// Nanoseconds per run
38	>	static final long NANOS_PER_JOB = 6L * 1000L*1000L*1000L;
39	>	static final long NANOS_PER_WARMUP = 100L*1000L*1000L;
40
41		// map operations per item per iteration -- change if job.work changed
42		static final int OPS_PER_ITER = 11;
43	<	static final int MIN_ITERS_PER_TEST = 2;
44	<	static final int MAX_ITERS_PER_TEST = 1000000;
43	>	static final int MIN_ITERS_PER_TEST = 3;
44	>	static final int MAX_ITERS_PER_TEST = 1000000; // avoid runaway
45
46		// sizes are at halfway points for HashMap default resizes
47	<	static final int firstSize = 36;
47	>	static final int firstSize = 9;
48		static final int sizeStep = 4; // each size 4X last
49	<	static final int nsizes = 8;
49	>	static final int nsizes = 9;
50		static final int[] sizes = new int[nsizes];
51
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	–
52		public static void main(String[] args) throws Throwable {
53		if (args.length == 0) {
54		System.out.println("Usage: java MapMicroBenchmark className [r|s]keys [r|s]searches");
#	Line 96 | Line 89 | public class MapMicroBenchmark {
89		}
90		sizes[nsizes - 1] = n;
91
92	<	Object[] ss = new Object[n];
92	>	int njobs = 9;
93	>
94		Object[] os = new Object[n];
95	+	Object[] ss = new Object[n];
96		Object[] is = new Object[n];
97		Object[] ls = new Object[n];
98		Object[] fs = new Object[n];
99		Object[] ds = new Object[n];
100		Object[] bs = new Object[n];
101		Object[] es = new Object[n];
102	+	Object[] ms = new Object[n];
103	+
104	+	for (int i = 0; i < n; i++) {
105	+	os[i] = new Object();
106	+	}
107
108		// To guarantee uniqueness, use xorshift for "random" versions
109	<	int j = randomKeys? 1234567 : 0;
109	>	int rnd = 3122688;
110		for (int i = 0; i < n; i++) {
111	+	rnd = xorshift(rnd);
112	+	int j = randomKeys? rnd : i;
113		ss[i] = String.valueOf(j);
114	<	os[i] = new Object();
114	>	}
115	>
116	>	for (int i = 0; i < n; i++) {
117	>	rnd = xorshift(rnd);
118	>	int j = randomKeys? rnd : i;
119		is[i] = Integer.valueOf(j);
120	+	}
121	+
122	+	for (int i = 0; i < n; i++) {
123	+	rnd = xorshift(rnd);
124	+	int j = randomKeys? rnd : i;
125		ls[i] = Long.valueOf((long)j);
126	+	}
127	+
128	+	for (int i = 0; i < n; i++) {
129	+	//            rnd = xorshift(rnd);
130	+	//            int j = randomKeys? rnd : i;
131		fs[i] = Float.valueOf((float)i); // can't use random for float
132	+	}
133	+
134	+	for (int i = 0; i < n; i++) {
135	+	rnd = xorshift(rnd);
136	+	int j = randomKeys? rnd : i;
137		ds[i] = Double.valueOf((double)j);
138	+	}
139	+
140	+	for (int i = 0; i < n; i++) {
141	+	rnd = xorshift(rnd);
142	+	int j = randomKeys? rnd : i;
143		bs[i] = BigInteger.valueOf(j);
144	+	}
145	+
146	+	for (int i = 0; i < n; i++) {
147	+	rnd = xorshift(rnd);
148	+	int j = randomKeys? rnd : i;
149		es[i] = BigDecimal.valueOf(j);
119	–	j = randomKeys? xorshift(j) : j + 1;
150		}
151
152	<	List<Job> list = new ArrayList<Job>();
153	<	list.add(new Job("BigDecimal", es));
154	<	list.add(new Job("BigInteger", bs));
155	<	list.add(new Job("String    ", ss));
156	<	list.add(new Job("Double    ", ds));
157	<	list.add(new Job("Float     ", fs));
158	<	list.add(new Job("Long      ", ls));
159	<	list.add(new Job("Integer   ", is));
160	<	list.add(new Job("Object    ", os));
161	<
162	<	Job[] jobs = list.toArray(new Job[0]);
163	<	warmup(jobs);
164	<	warmup(jobs);
152	>	Job[] jobs = new Job[njobs];
153	>	jobs[0] = new Job("Object    ", os, Object.class);
154	>	jobs[1] = new Job("String    ", ss, String.class);
155	>	jobs[2] = new Job("Integer   ", is, Integer.class);
156	>	jobs[3] = new Job("Long      ", ls, Long.class);
157	>	jobs[4] = new Job("Float     ", fs, Float.class);
158	>	jobs[5] = new Job("Double    ", ds, Double.class);
159	>	jobs[6] = new Job("BigInteger", bs, BigInteger.class);
160	>	jobs[7] = new Job("BigDecimal", es, BigDecimal.class);
161	>
162	>	for (int i = 0; i < n; i +=2) {
163	>	rnd = xorshift(rnd);
164	>	int j = (rnd & 7); // change if njobs changes
165	>	ms[i] = jobs[j].items[i];
166	>	j = (j + 1) & 7;
167	>	ms[i+1] = jobs[j].items[i];
168	>	}
169	>
170	>	jobs[8] = new Job("Mixed     ", ms, Object.class);
171	>
172	>	warmup1(jobs[8]);
173	>	warmup2(jobs);
174	>	warmup1(jobs[8]);
175	>	warmup3(jobs);
176	>	warmup1(jobs[8]);
177	>	Thread.sleep(500);
178		time(jobs);
179		}
180
181	<	static void runWork(Job[] jobs, int maxIters) throws Throwable {
181	>	static void runWork(Job[] jobs, int minIters, int maxIters, long timeLimit) throws Throwable {
182		for (int k = 0; k <  nsizes; ++k) {
183		int len = sizes[k];
184		for (int i = 0; i < jobs.length; i++) {
142	–	jobs[i].setup(len);
185		Thread.sleep(50);
186	<	jobs[i].nanos[k] = jobs[i].work(len, maxIters);
186	>	jobs[i].nanos[k] = jobs[i].work(len, minIters, maxIters, timeLimit);
187		System.out.print(".");
188		}
189		}
190		System.out.println();
191		}
192
193	<	static void warmup(Job[] jobs) throws Throwable {
193	>	// First warmup -- run only mixed job to discourage type specialization
194	>	static void warmup1(Job job) throws Throwable {
195	>	for (int k = 0; k <  nsizes; ++k)
196	>	job.work(sizes[k], 1, 1, 0);
197	>	}
198	>
199	>	// Second, run each once
200	>	static void warmup2(Job[] jobs) throws Throwable {
201		System.out.print("warm up");
202	<	runWork(jobs, MIN_ITERS_PER_TEST);
202	>	runWork(jobs, 1, 1, 0);
203		long ck = jobs[0].checkSum;
204	<	for (int i = 1; i < jobs.length; i++) {
204	>	for (int i = 1; i < jobs.length - 1; i++) {
205		if (jobs[i].checkSum != ck)
206		throw new Error("CheckSum");
207		}
208		}
209
210	+	// Third: short timed runs
211	+	static void warmup3(Job[] jobs) throws Throwable {
212	+	System.out.print("warm up");
213	+	runWork(jobs, 1, MAX_ITERS_PER_TEST, NANOS_PER_WARMUP);
214	+	}
215	+
216		static void time(Job[] jobs) throws Throwable {
217		System.out.print("running");
218	<	runWork(jobs, MAX_ITERS_PER_TEST);
218	>	runWork(jobs, MIN_ITERS_PER_TEST, MAX_ITERS_PER_TEST, NANOS_PER_JOB);
219
220		System.out.print("Type/Size:");
221		for (int k = 0; k < nsizes; ++k)
222	<	System.out.printf("%8d", sizes[k]);
222	>	System.out.printf("%7d", sizes[k]);
223		System.out.println();
224
225		long[] aves = new long[nsizes];
#	Line 174 | Line 229 | public class MapMicroBenchmark {
229		System.out.print(jobs[i].name);
230		for (int k = 0; k < nsizes; ++k) {
231		long nanos = jobs[i].nanos[k];
232	<	System.out.printf("%8d", nanos);
232	>	System.out.printf("%7d", nanos);
233		aves[k] += nanos;
234		}
235		System.out.println();
#	Line 183 | Line 238 | public class MapMicroBenchmark {
238		System.out.println();
239		System.out.print("average   ");
240		for (int k = 0; k < nsizes; ++k)
241	<	System.out.printf("%8d", (aves[k] / njobs));
242	<	System.out.println();
241	>	System.out.printf("%7d", (aves[k] / njobs));
242	>	System.out.println("\n");
243		}
244
245
246		static final class Job {
247		final String name;
248	+	final Class elementClass;
249		long[] nanos = new long[nsizes];
250		final Object[] items;
251	<	final Object[] dups;
196	<	Object[] reordered;
251	>	Object[] searches;
252		volatile long checkSum;
253		volatile int lastSum;
254	<	Job(String name, Object[] items) {
254	>	Job(String name, Object[] items, Class elementClass) {
255		this.name = name;
256		this.items = items;
257	<	if (randomSearches)
203	<	this.dups = new Object[items.length];
204	<	else
205	<	this.dups = items;
206	<	}
207	<
208	<	public void setup(int len) {
257	>	this.elementClass = elementClass;
258		if (randomSearches) {
259	<	System.arraycopy(items, 0, dups, 0, len);
260	<	shuffle(dups, len);
261	<	reordered = dups;
259	>	scramble(items);
260	>	this.searches = new Object[items.length];
261	>	System.arraycopy(items, 0, searches, 0, items.length);
262	>	scramble(searches);
263		}
264		else
265	<	reordered = items;
265	>	this.searches = items;
266		}
267
268	<	public long work(int len, int maxIters) {
268	>	public long work(int len, int minIters, int maxIters, long timeLimit) {
269	>	Map m;
270	>	try {
271	>	m = (Map)mapClass.newInstance();
272	>	} catch(Exception e) {
273	>	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
274	>	}
275		Object[] ins = items;
276	<	Object[] keys = reordered;
276	>	Object[] keys = searches;
277
278		if (ins.length < len || keys.length < len)
279		throw new Error(name);
280		int half = len / 2;
281	<	Class eclass = ins[0].getClass();
281	>	int quarter = half / 2;
282		int sum = lastSum;
283		long startTime = System.nanoTime();
284		long elapsed;
229	–	Map m = newMap();
285		int j = 0;
286		for (;;) {
287		for (int i = 0; i < half; ++i) {
#	Line 235 | Line 290 | public class MapMicroBenchmark {
290		++sum;
291		}
292		checkSum += sum ^ (sum << 1); // help avoid loop merging
293	+	sum += len - half;
294		for (int i = 0; i < len; ++i) {
295		Object x = keys[i];
296		Object v = m.get(x);
297	<	if (v != null && v.getClass() == eclass) // touch v
298	<	sum += 2;
297	>	if (elementClass.isInstance(v)) // touch v
298	>	++sum;
299		}
300		checkSum += sum ^ (sum << 2);
301		for (int i = half; i < len; ++i) {
#	Line 249 | Line 305 | public class MapMicroBenchmark {
305		}
306		checkSum += sum ^ (sum << 3);
307		for (Object e : m.keySet()) {
308	<	if (e.getClass() == eclass)
308	>	if (elementClass.isInstance(e))
309		++sum;
310		}
311		checkSum += sum ^ (sum << 4);
312		for (Object e : m.values()) {
313	<	if (e.getClass() == eclass)
313	>	if (elementClass.isInstance(e))
314		++sum;
315		}
316		checkSum += sum ^ (sum << 5);
317		for (int i = len - 1; i >= 0; --i) {
318		Object x = keys[i];
319		Object v = m.get(x);
320	<	if (v != null && v.getClass() == eclass)
320	>	if (elementClass.isInstance(v))
321		++sum;
322		}
323		checkSum += sum ^ (sum << 6);
324		for (int i = 0; i < len; ++i) {
325		Object x = ins[i];
326		Object v = m.get(x);
327	<	if (v != null && v.getClass() == eclass)
327	>	if (elementClass.isInstance(v))
328		++sum;
329		}
330		checkSum += sum ^ (sum << 7);
#	Line 282 | Line 338 | public class MapMicroBenchmark {
338		for (int i = 0; i < len; ++i) {
339		Object x = keys[i];
340		Object v = ins[i];
341	<	if (v.equals(m.get(x)))
341	>	if (v == m.get(x))
342		++sum;
343		}
344		checkSum += sum ^ (sum << 9);
345		for (int i = len - 1; i >= 0; --i) {
346		Object x = ins[i];
347	<	if (m.get(x) != MISSING)
347	>	Object v = m.get(x);
348	>	if (elementClass.isInstance(v))
349		++sum;
350		}
351		checkSum += sum ^ (sum << 10);
352		for (int i = len - 1; i >= 0; --i) {
353		Object x = keys[i];
354		Object v = ins[i];
355	<	if (v.equals(m.get(x)))
355	>	if (v == m.get(x))
356		++sum;
357		}
358		checkSum += sum ^ (sum << 11);
359	<	if ((j & 1) == 1) { // lower remove rate
360	<	for (int i = 0; i < len; ++i) {
361	<	Object x = keys[i];
362	<	if (m.remove(x) != null)
306	<	++sum;
307	<	}
308	<	}
309	<	else {
310	<	m.clear();
311	<	sum += len;
359	>	for (int i = 0; i < quarter; ++i) {
360	>	Object x = keys[i];
361	>	if (m.remove(x) != null)
362	>	++sum;
363		}
364	+	m.clear();
365	+	sum += len - quarter;
366		checkSum += sum ^ (sum << 12);
367
368		elapsed = System.nanoTime() - startTime;
369		++j;
370	<	if (j >= MIN_ITERS_PER_TEST &&
371	<	(j >= maxIters || elapsed >= NANOS_PER_JOB))
370	>	if (j >= minIters &&
371	>	(j >= maxIters || elapsed >= timeLimit))
372		break;
373		}
374		long ops = ((long)j) * len * OPS_PER_ITER;
#	Line 335 | Line 388 | public class MapMicroBenchmark {
388		}
389
390
391	<	static final Random rng = new Random(3152688);
391	>	static final Random rng = new Random(3122688);
392	>
393	>	// Shuffle the subarrays for each size. This doesn't fully
394	>	// randomize, but the remaining partial locality is arguably a bit
395	>	// more realistic
396	>	static void scramble(Object[] a) {
397	>	for (int k = 0; k < sizes.length; ++k) {
398	>	int origin = k == 0? 0 : sizes[k-1];
399	>	for (int i = sizes[k]; i > origin + 1; i--) {
400	>	Object t = a[i-1];
401	>	int r = rng.nextInt(i - origin) + origin;
402	>	a[i-1] = a[r];
403	>	a[r] = t;
404	>	}
405	>	}
406	>	}
407
408	+	// plain array shuffle
409		static void shuffle(Object[] a, int size) {
410		for (int i= size; i>1; i--) {
411		Object t = a[i-1];
#	Line 346 | Line 415 | public class MapMicroBenchmark {
415		}
416		}
417
418	+
419	+
420		}
421

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines