ViewVC Help

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

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

Comparing jsr166/src/test/loops/NavigableMapCheck.java (file contents):
Revision 1.4 by dl, Mon Feb 19 00:46:06 2007 UTC vs.
Revision 1.15 by jsr166, Mon Aug 10 03:13:33 2015 UTC

#	Line 1 | Line 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
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6		/**
7		* @test
8		* @synopsis Times and checks basic map operations
9		*/
10	–	import java.util.*;
10		import java.io.*;
11	+	import java.util.*;
12
13		public class NavigableMapCheck {
14
#	Line 25 | Line 25 | public class NavigableMapCheck {
25		}
26
27		public static void main(String[] args) throws Exception {
28	<	Class mapClass = null;
28	>	Class<?> mapClass = null;
29		int numTests = 50;
30		int size = 50000;
31
32		if (args.length > 0) {
33		try {
34		mapClass = Class.forName(args[0]);
35	<	} catch(ClassNotFoundException e) {
35	>	} catch (ClassNotFoundException e) {
36		throw new RuntimeException("Class " + args[0] + " not found.");
37		}
38		}
39
40	<
41	<	if (args.length > 1)
40	>	if (args.length > 1)
41		numTests = Integer.parseInt(args[1]);
42
43	<	if (args.length > 2)
43	>	if (args.length > 2)
44		size = Integer.parseInt(args[2]);
45
46		System.out.println("Testing " + mapClass.getName() + " trials: " + numTests + " size: " + size);
47
49	–
48		absentSize = 8;
49		while (absentSize < size) absentSize <<= 1;
50		absentMask = absentSize - 1;
51		absent = new Integer[absentSize];
52
53	<	for (int i = 0; i < absentSize; ++i)
53	>	for (int i = 0; i < absentSize; ++i)
54		absent[i] = new Integer(i * 2);
55
56		Integer[] key = new Integer[size];
57	<	for (int i = 0; i < size; ++i)
57	>	for (int i = 0; i < size; ++i)
58		key[i] = new Integer(i * 2 + 1);
59
62	–
60		for (int rep = 0; rep < numTests; ++rep) {
61		runTest(newMap(mapClass), key);
62		}
63
64		TestTimer.printStats();
68	–
65		}
66
67	<	static NavigableMap newMap(Class cl) {
67	>	static NavigableMap newMap(Class<?> cl) {
68		try {
69	<	NavigableMap m = (NavigableMap)cl.newInstance();
69	>	NavigableMap m = (NavigableMap) cl.newInstance();
70		return m;
71	<	} catch(Exception e) {
71	>	} catch (Exception e) {
72		throw new RuntimeException("Can't instantiate " + cl + ": " + e);
73		}
74		}
75
80	–
76		static void runTest(NavigableMap s, Integer[] key) {
77		shuffle(key);
78		int size = key.length;
#	Line 95 | Line 90 | public class NavigableMapCheck {
90		if (s.get(key[i]) != null) ++sum;
91		}
92		}
93	<	timer.finish();
94	<	reallyAssert (sum == expect * iters);
93	>	timer.finish();
94	>	reallyAssert(sum == expect * iters);
95		}
96
97		static void t2(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 105 | Line 100 | public class NavigableMapCheck {
100		for (int i = 0; i < n; i++) {
101		if (s.remove(key[i]) != null) ++sum;
102		}
103	<	timer.finish();
104	<	reallyAssert (sum == expect);
103	>	timer.finish();
104	>	reallyAssert(sum == expect);
105		}
106
107		static void t3(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 115 | Line 110 | public class NavigableMapCheck {
110		for (int i = 0; i < n; i++) {
111		if (s.put(key[i], absent[i & absentMask]) == null) ++sum;
112		}
113	<	timer.finish();
114	<	reallyAssert (sum == expect);
113	>	timer.finish();
114	>	reallyAssert(sum == expect);
115		}
116
117		static void t4(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 125 | Line 120 | public class NavigableMapCheck {
120		for (int i = 0; i < n; i++) {
121		if (s.containsKey(key[i])) ++sum;
122		}
123	<	timer.finish();
124	<	reallyAssert (sum == expect);
123	>	timer.finish();
124	>	reallyAssert(sum == expect);
125		}
126
127		static void t5(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 135 | Line 130 | public class NavigableMapCheck {
130		for (int i = n-2; i >= 0; i-=2) {
131		if (s.remove(key[i]) != null) ++sum;
132		}
133	<	timer.finish();
134	<	reallyAssert (sum == expect);
133	>	timer.finish();
134	>	reallyAssert(sum == expect);
135		}
136
137		static void t6(String nm, int n, NavigableMap s, Integer[] k1, Integer[] k2) {
#	Line 146 | Line 141 | public class NavigableMapCheck {
141		if (s.get(k1[i]) != null) ++sum;
142		if (s.get(k2[i & absentMask]) != null) ++sum;
143		}
144	<	timer.finish();
145	<	reallyAssert (sum == n);
144	>	timer.finish();
145	>	reallyAssert(sum == n);
146		}
147
148		static void t7(String nm, int n, NavigableMap s, Integer[] k1, Integer[] k2) {
#	Line 157 | Line 152 | public class NavigableMapCheck {
152		if (s.containsKey(k1[i])) ++sum;
153		if (s.containsKey(k2[i & absentMask])) ++sum;
154		}
155	<	timer.finish();
156	<	reallyAssert (sum == n);
155	>	timer.finish();
156	>	reallyAssert(sum == n);
157		}
158
159		static void t8(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 167 | Line 162 | public class NavigableMapCheck {
162		for (int i = 0; i < n; i++) {
163		if (s.get(key[i]) != null) ++sum;
164		}
165	<	timer.finish();
166	<	reallyAssert (sum == expect);
165	>	timer.finish();
166	>	reallyAssert(sum == expect);
167		}
168
174	–
169		static void t9(NavigableMap s) {
170		int sum = 0;
171		int iters = 20;
#	Line 179 | Line 173 | public class NavigableMapCheck {
173		int step = absentSize / iters;
174		for (int i = 0; i < absentSize; i += step)
175		if (s.containsValue(absent[i])) ++sum;
176	<	timer.finish();
177	<	reallyAssert (sum != 0);
176	>	timer.finish();
177	>	reallyAssert(sum != 0);
178		}
179
180		static void higherTest(NavigableMap s) {
#	Line 192 | Line 186 | public class NavigableMapCheck {
186		++sum;
187		e = s.higherEntry(e.getKey());
188		}
189	<	timer.finish();
190	<	reallyAssert (sum == iters);
189	>	timer.finish();
190	>	reallyAssert(sum == iters);
191		}
192
193		static void lowerTest(NavigableMap s) {
#	Line 205 | Line 199 | public class NavigableMapCheck {
199		++sum;
200		e = s.higherEntry(e.getKey());
201		}
202	<	timer.finish();
203	<	reallyAssert (sum == iters);
202	>	timer.finish();
203	>	reallyAssert(sum == iters);
204		}
205
206		static void ceilingTest(NavigableMap s) {
#	Line 219 | Line 213 | public class NavigableMapCheck {
213		if (e != null)
214		++sum;
215		}
216	<	timer.finish();
217	<	reallyAssert (sum == iters);
216	>	timer.finish();
217	>	reallyAssert(sum == iters);
218		}
219
220		static void floorTest(NavigableMap s) {
#	Line 233 | Line 227 | public class NavigableMapCheck {
227		if (e != null)
228		++sum;
229		}
230	<	timer.finish();
231	<	reallyAssert (sum == iters-1);
230	>	timer.finish();
231	>	reallyAssert(sum == iters-1);
232		}
233
240	–
234		static void ktest(NavigableMap s, int size, Integer[] key) {
235		timer.start("ContainsKey            ", size);
236		Set ks = s.keySet();
#	Line 245 | Line 238 | public class NavigableMapCheck {
238		for (int i = 0; i < size; i++) {
239		if (ks.contains(key[i])) ++sum;
240		}
241	<	timer.finish();
242	<	reallyAssert (sum == size);
241	>	timer.finish();
242	>	reallyAssert(sum == size);
243		}
244
252	–
245		static void ittest1(NavigableMap s, int size) {
246		int sum = 0;
247		timer.start("Iter Key               ", size);
248		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
249	<	if(it.next() != MISSING)
249	>	if (it.next() != MISSING)
250		++sum;
251		}
252	<	timer.finish();
253	<	reallyAssert (sum == size);
252	>	timer.finish();
253	>	reallyAssert(sum == size);
254		}
255
256		static void ittest2(NavigableMap s, int size) {
257		int sum = 0;
258		timer.start("Iter Value             ", size);
259		for (Iterator it = s.values().iterator(); it.hasNext(); ) {
260	<	if(it.next() != MISSING)
260	>	if (it.next() != MISSING)
261		++sum;
262		}
263	<	timer.finish();
264	<	reallyAssert (sum == size);
263	>	timer.finish();
264	>	reallyAssert(sum == size);
265		}
266		static void ittest3(NavigableMap s, int size) {
267		int sum = 0;
268		timer.start("Iter Entry             ", size);
269		for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
270	<	if(it.next() != MISSING)
270	>	if (it.next() != MISSING)
271		++sum;
272		}
273	<	timer.finish();
274	<	reallyAssert (sum == size);
273	>	timer.finish();
274	>	reallyAssert(sum == size);
275		}
276
277		static void ittest(NavigableMap s, int size) {
#	Line 292 | Line 284 | public class NavigableMapCheck {
284		int sum = 0;
285		timer.start("Desc Iter Key          ", size);
286		for (Iterator it = s.descendingKeySet().iterator(); it.hasNext(); ) {
287	<	if(it.next() != MISSING)
287	>	if (it.next() != MISSING)
288		++sum;
289		}
290	<	timer.finish();
291	<	reallyAssert (sum == size);
290	>	timer.finish();
291	>	reallyAssert(sum == size);
292		}
293
302	–
294		static void rittest(NavigableMap s, int size) {
295		rittest1(s, size);
296		//        rittest2(s, size);
297		}
298
308	–
299		static void rtest(NavigableMap s, int size) {
300		timer.start("Remove (iterator)      ", size);
301		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
302		it.next();
303		it.remove();
304		}
305	<	timer.finish();
305	>	timer.finish();
306		}
307
308		static void rvtest(NavigableMap s, int size) {
#	Line 321 | Line 311 | public class NavigableMapCheck {
311		it.next();
312		it.remove();
313		}
314	<	timer.finish();
314	>	timer.finish();
315		}
316
327	–
317		static void dtest(NavigableMap s, int size, Integer[] key) {
318		timer.start("Put (putAll)           ", size * 2);
319		NavigableMap s2 = null;
#	Line 333 | Line 322 | public class NavigableMapCheck {
322		s2.putAll(s);
323		}
324		catch (Exception e) { e.printStackTrace(); return; }
325	<	timer.finish();
326	<
325	>	timer.finish();
326	>
327		timer.start("Iter Equals            ", size * 2);
328		boolean eqt = s2.equals(s) && s.equals(s2);
329	<	reallyAssert (eqt);
330	<	timer.finish();
329	>	reallyAssert(eqt);
330	>	timer.finish();
331
332		timer.start("Iter HashCode          ", size * 2);
333		int shc = s.hashCode();
334		int s2hc = s2.hashCode();
335	<	reallyAssert (shc == s2hc);
336	<	timer.finish();
335	>	reallyAssert(shc == s2hc);
336	>	timer.finish();
337
338		timer.start("Put (present)          ", size);
339		s2.putAll(s);
340	<	timer.finish();
340	>	timer.finish();
341
342		timer.start("Iter EntrySet contains ", size * 2);
343		Set es2 = s2.entrySet();
#	Line 357 | Line 346 | public class NavigableMapCheck {
346		Object entry = i1.next();
347		if (es2.contains(entry)) ++sum;
348		}
349	<	timer.finish();
350	<	reallyAssert (sum == size);
349	>	timer.finish();
350	>	reallyAssert(sum == size);
351
352		t6("Get                    ", size, s2, key, absent);
353
#	Line 366 | Line 355 | public class NavigableMapCheck {
355		s2.put(key[size-1], absent[0]);
356		timer.start("Iter Equals            ", size * 2);
357		eqt = s2.equals(s) && s.equals(s2);
358	<	reallyAssert (!eqt);
359	<	timer.finish();
358	>	reallyAssert(!eqt);
359	>	timer.finish();
360
361		timer.start("Iter HashCode          ", size * 2);
362		int s1h = s.hashCode();
363		int s2h = s2.hashCode();
364	<	reallyAssert (s1h != s2h);
365	<	timer.finish();
364	>	reallyAssert(s1h != s2h);
365	>	timer.finish();
366
367		s2.put(key[size-1], hold);
368		timer.start("Remove (iterator)      ", size * 2);
#	Line 381 | Line 370 | public class NavigableMapCheck {
370		Set es = s.entrySet();
371		while (s2i.hasNext())
372		es.remove(s2i.next());
373	<	timer.finish();
373	>	timer.finish();
374
375	<	reallyAssert (s.isEmpty());
375	>	reallyAssert(s.isEmpty());
376
377		timer.start("Clear                  ", size);
378		s2.clear();
379	<	timer.finish();
380	<	reallyAssert (s2.isEmpty() && s.isEmpty());
379	>	timer.finish();
380	>	reallyAssert(s2.isEmpty() && s.isEmpty());
381		}
382
394	–
395	–
383		static void test(NavigableMap s, Integer[] key) {
384		int size = key.length;
385
#	Line 431 | Line 418 | public class NavigableMapCheck {
418		private String cname;
419
420		static final java.util.TreeMap accum = new java.util.TreeMap();
421	<
421	>
422		static void printStats() {
423		for (Iterator it = accum.entrySet().iterator(); it.hasNext(); ) {
424	<	Map.Entry e = (Map.Entry)(it.next());
425	<	Stats stats = ((Stats)(e.getValue()));
424	>	Map.Entry e = (Map.Entry) it.next();
425	>	Stats stats = (Stats) e.getValue();
426		int n = stats.number;
427		double t;
428	<	if (n > 0)
428	>	if (n > 0)
429		t = stats.sum / n;
430		else
431		t = stats.least;
#	Line 446 | Line 433 | public class NavigableMapCheck {
433		System.out.println(e.getKey() + ": " + nano);
434		}
435		}
436	<
436	>
437		void start(String name, long numOps) {
438		this.name = name;
439		this.cname = classify();
440		this.numOps = numOps;
441		startTime = System.currentTimeMillis();
442		}
456	–
443
444		String classify() {
445		if (name.startsWith("Get"))
#	Line 464 | Line 450 | public class NavigableMapCheck {
450		return "Remove                 ";
451		else if (name.startsWith("Iter"))
452		return "Iter                   ";
453	<	else
453	>	else
454		return null;
455		}
456
457		void finish() {
458		long endTime = System.currentTimeMillis();
459		long time = endTime - startTime;
460	<	double timePerOp = ((double)time)/numOps;
460	>	double timePerOp = (double) time /numOps;
461
462		Object st = accum.get(name);
463		if (st == null)
#	Line 494 | Line 480 | public class NavigableMapCheck {
480		if (timePerOp < stats.least) stats.least = timePerOp;
481		}
482		}
497	–
483		}
499	–
484		}
485
486		static class Stats {
#	Line 510 | Line 494 | public class NavigableMapCheck {
494
495		static void shuffle(Integer[] keys) {
496		int size = keys.length;
497	<	for (int i=size; i>1; i--) {
497	>	for (int i = size; i > 1; i--) {
498		int r = rng.nextInt(i);
499		Integer t = keys[i-1];
500		keys[i-1] = keys[r];
#	Line 519 | Line 503 | public class NavigableMapCheck {
503		}
504
505		}
522	–

Diff Legend

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