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.3 by dl, Wed Apr 19 15:10:47 2006 UTC vs.
Revision 1.16 by jsr166, Sun Oct 23 03:03:23 2016 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();
70	<	return m;
75	<	} catch(Exception e) {
69	>	return (NavigableMap) cl.getConstructor().newInstance();
70	>	} catch (Exception e) {
71		throw new RuntimeException("Can't instantiate " + cl + ": " + e);
72		}
73		}
74
80	–
75		static void runTest(NavigableMap s, Integer[] key) {
76		shuffle(key);
77		int size = key.length;
#	Line 95 | Line 89 | public class NavigableMapCheck {
89		if (s.get(key[i]) != null) ++sum;
90		}
91		}
92	<	timer.finish();
93	<	reallyAssert (sum == expect * iters);
92	>	timer.finish();
93	>	reallyAssert(sum == expect * iters);
94		}
95
96		static void t2(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 105 | Line 99 | public class NavigableMapCheck {
99		for (int i = 0; i < n; i++) {
100		if (s.remove(key[i]) != null) ++sum;
101		}
102	<	timer.finish();
103	<	reallyAssert (sum == expect);
102	>	timer.finish();
103	>	reallyAssert(sum == expect);
104		}
105
106		static void t3(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 115 | Line 109 | public class NavigableMapCheck {
109		for (int i = 0; i < n; i++) {
110		if (s.put(key[i], absent[i & absentMask]) == null) ++sum;
111		}
112	<	timer.finish();
113	<	reallyAssert (sum == expect);
112	>	timer.finish();
113	>	reallyAssert(sum == expect);
114		}
115
116		static void t4(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 125 | Line 119 | public class NavigableMapCheck {
119		for (int i = 0; i < n; i++) {
120		if (s.containsKey(key[i])) ++sum;
121		}
122	<	timer.finish();
123	<	reallyAssert (sum == expect);
122	>	timer.finish();
123	>	reallyAssert(sum == expect);
124		}
125
126		static void t5(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 135 | Line 129 | public class NavigableMapCheck {
129		for (int i = n-2; i >= 0; i-=2) {
130		if (s.remove(key[i]) != null) ++sum;
131		}
132	<	timer.finish();
133	<	reallyAssert (sum == expect);
132	>	timer.finish();
133	>	reallyAssert(sum == expect);
134		}
135
136		static void t6(String nm, int n, NavigableMap s, Integer[] k1, Integer[] k2) {
#	Line 146 | Line 140 | public class NavigableMapCheck {
140		if (s.get(k1[i]) != null) ++sum;
141		if (s.get(k2[i & absentMask]) != null) ++sum;
142		}
143	<	timer.finish();
144	<	reallyAssert (sum == n);
143	>	timer.finish();
144	>	reallyAssert(sum == n);
145		}
146
147		static void t7(String nm, int n, NavigableMap s, Integer[] k1, Integer[] k2) {
#	Line 157 | Line 151 | public class NavigableMapCheck {
151		if (s.containsKey(k1[i])) ++sum;
152		if (s.containsKey(k2[i & absentMask])) ++sum;
153		}
154	<	timer.finish();
155	<	reallyAssert (sum == n);
154	>	timer.finish();
155	>	reallyAssert(sum == n);
156		}
157
158		static void t8(String nm, int n, NavigableMap s, Integer[] key, int expect) {
#	Line 167 | Line 161 | public class NavigableMapCheck {
161		for (int i = 0; i < n; i++) {
162		if (s.get(key[i]) != null) ++sum;
163		}
164	<	timer.finish();
165	<	reallyAssert (sum == expect);
164	>	timer.finish();
165	>	reallyAssert(sum == expect);
166		}
167
174	–
168		static void t9(NavigableMap s) {
169		int sum = 0;
170		int iters = 20;
#	Line 179 | Line 172 | public class NavigableMapCheck {
172		int step = absentSize / iters;
173		for (int i = 0; i < absentSize; i += step)
174		if (s.containsValue(absent[i])) ++sum;
175	<	timer.finish();
176	<	reallyAssert (sum != 0);
175	>	timer.finish();
176	>	reallyAssert(sum != 0);
177		}
178
179		static void higherTest(NavigableMap s) {
#	Line 192 | Line 185 | public class NavigableMapCheck {
185		++sum;
186		e = s.higherEntry(e.getKey());
187		}
188	<	timer.finish();
189	<	reallyAssert (sum == iters);
188	>	timer.finish();
189	>	reallyAssert(sum == iters);
190		}
191
192		static void lowerTest(NavigableMap s) {
#	Line 205 | Line 198 | public class NavigableMapCheck {
198		++sum;
199		e = s.higherEntry(e.getKey());
200		}
201	<	timer.finish();
202	<	reallyAssert (sum == iters);
201	>	timer.finish();
202	>	reallyAssert(sum == iters);
203		}
204
205		static void ceilingTest(NavigableMap s) {
#	Line 219 | Line 212 | public class NavigableMapCheck {
212		if (e != null)
213		++sum;
214		}
215	<	timer.finish();
216	<	reallyAssert (sum == iters);
215	>	timer.finish();
216	>	reallyAssert(sum == iters);
217		}
218
219		static void floorTest(NavigableMap s) {
#	Line 233 | Line 226 | public class NavigableMapCheck {
226		if (e != null)
227		++sum;
228		}
229	<	timer.finish();
230	<	reallyAssert (sum == iters-1);
229	>	timer.finish();
230	>	reallyAssert(sum == iters-1);
231		}
232
240	–
233		static void ktest(NavigableMap s, int size, Integer[] key) {
234		timer.start("ContainsKey            ", size);
235		Set ks = s.keySet();
#	Line 245 | Line 237 | public class NavigableMapCheck {
237		for (int i = 0; i < size; i++) {
238		if (ks.contains(key[i])) ++sum;
239		}
240	<	timer.finish();
241	<	reallyAssert (sum == size);
240	>	timer.finish();
241	>	reallyAssert(sum == size);
242		}
243
252	–
244		static void ittest1(NavigableMap s, int size) {
245		int sum = 0;
246		timer.start("Iter Key               ", size);
247		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
248	<	if(it.next() != MISSING)
248	>	if (it.next() != MISSING)
249		++sum;
250		}
251	<	timer.finish();
252	<	reallyAssert (sum == size);
251	>	timer.finish();
252	>	reallyAssert(sum == size);
253		}
254
255		static void ittest2(NavigableMap s, int size) {
256		int sum = 0;
257		timer.start("Iter Value             ", size);
258		for (Iterator it = s.values().iterator(); it.hasNext(); ) {
259	<	if(it.next() != MISSING)
259	>	if (it.next() != MISSING)
260		++sum;
261		}
262	<	timer.finish();
263	<	reallyAssert (sum == size);
262	>	timer.finish();
263	>	reallyAssert(sum == size);
264		}
265		static void ittest3(NavigableMap s, int size) {
266		int sum = 0;
267		timer.start("Iter Entry             ", size);
268		for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
269	<	if(it.next() != MISSING)
269	>	if (it.next() != MISSING)
270		++sum;
271		}
272	<	timer.finish();
273	<	reallyAssert (sum == size);
272	>	timer.finish();
273	>	reallyAssert(sum == size);
274		}
275
276		static void ittest(NavigableMap s, int size) {
#	Line 292 | Line 283 | public class NavigableMapCheck {
283		int sum = 0;
284		timer.start("Desc Iter Key          ", size);
285		for (Iterator it = s.descendingKeySet().iterator(); it.hasNext(); ) {
286	<	if(it.next() != MISSING)
286	>	if (it.next() != MISSING)
287		++sum;
288		}
289	<	timer.finish();
290	<	reallyAssert (sum == size);
289	>	timer.finish();
290	>	reallyAssert(sum == size);
291		}
292
302	–
293		static void rittest(NavigableMap s, int size) {
294		rittest1(s, size);
295		//        rittest2(s, size);
296		}
297
308	–
298		static void rtest(NavigableMap s, int size) {
299		timer.start("Remove (iterator)      ", size);
300		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
301		it.next();
302		it.remove();
303		}
304	<	timer.finish();
304	>	timer.finish();
305		}
306
307		static void rvtest(NavigableMap s, int size) {
#	Line 321 | Line 310 | public class NavigableMapCheck {
310		it.next();
311		it.remove();
312		}
313	<	timer.finish();
313	>	timer.finish();
314		}
315
327	–
316		static void dtest(NavigableMap s, int size, Integer[] key) {
317		timer.start("Put (putAll)           ", size * 2);
318	<	NavigableMap s2 = null;
318	>	final NavigableMap s2;
319		try {
320	<	s2 = (NavigableMap) (s.getClass().newInstance());
320	>	s2 = (NavigableMap) s.getClass().getConstructor().newInstance();
321		s2.putAll(s);
322		}
323		catch (Exception e) { e.printStackTrace(); return; }
324	<	timer.finish();
325	<
324	>	timer.finish();
325	>
326		timer.start("Iter Equals            ", size * 2);
327		boolean eqt = s2.equals(s) && s.equals(s2);
328	<	reallyAssert (eqt);
329	<	timer.finish();
328	>	reallyAssert(eqt);
329	>	timer.finish();
330
331		timer.start("Iter HashCode          ", size * 2);
332		int shc = s.hashCode();
333		int s2hc = s2.hashCode();
334	<	reallyAssert (shc == s2hc);
335	<	timer.finish();
334	>	reallyAssert(shc == s2hc);
335	>	timer.finish();
336
337		timer.start("Put (present)          ", size);
338		s2.putAll(s);
339	<	timer.finish();
339	>	timer.finish();
340
341		timer.start("Iter EntrySet contains ", size * 2);
342		Set es2 = s2.entrySet();
#	Line 357 | Line 345 | public class NavigableMapCheck {
345		Object entry = i1.next();
346		if (es2.contains(entry)) ++sum;
347		}
348	<	timer.finish();
349	<	reallyAssert (sum == size);
348	>	timer.finish();
349	>	reallyAssert(sum == size);
350
351		t6("Get                    ", size, s2, key, absent);
352
#	Line 366 | Line 354 | public class NavigableMapCheck {
354		s2.put(key[size-1], absent[0]);
355		timer.start("Iter Equals            ", size * 2);
356		eqt = s2.equals(s) && s.equals(s2);
357	<	reallyAssert (!eqt);
358	<	timer.finish();
357	>	reallyAssert(!eqt);
358	>	timer.finish();
359
360		timer.start("Iter HashCode          ", size * 2);
361		int s1h = s.hashCode();
362		int s2h = s2.hashCode();
363	<	reallyAssert (s1h != s2h);
364	<	timer.finish();
363	>	reallyAssert(s1h != s2h);
364	>	timer.finish();
365
366		s2.put(key[size-1], hold);
367		timer.start("Remove (iterator)      ", size * 2);
#	Line 381 | Line 369 | public class NavigableMapCheck {
369		Set es = s.entrySet();
370		while (s2i.hasNext())
371		es.remove(s2i.next());
372	<	timer.finish();
372	>	timer.finish();
373
374	<	reallyAssert (s.isEmpty());
374	>	reallyAssert(s.isEmpty());
375
376		timer.start("Clear                  ", size);
377		s2.clear();
378	<	timer.finish();
379	<	reallyAssert (s2.isEmpty() && s.isEmpty());
378	>	timer.finish();
379	>	reallyAssert(s2.isEmpty() && s.isEmpty());
380		}
381
394	–
395	–
382		static void test(NavigableMap s, Integer[] key) {
383		int size = key.length;
384
#	Line 431 | Line 417 | public class NavigableMapCheck {
417		private String cname;
418
419		static final java.util.TreeMap accum = new java.util.TreeMap();
420	<
420	>
421		static void printStats() {
422		for (Iterator it = accum.entrySet().iterator(); it.hasNext(); ) {
423	<	Map.Entry e = (Map.Entry)(it.next());
424	<	Stats stats = ((Stats)(e.getValue()));
423	>	Map.Entry e = (Map.Entry) it.next();
424	>	Stats stats = (Stats) e.getValue();
425		int n = stats.number;
426		double t;
427	<	if (n > 0)
427	>	if (n > 0)
428		t = stats.sum / n;
429		else
430		t = stats.least;
#	Line 446 | Line 432 | public class NavigableMapCheck {
432		System.out.println(e.getKey() + ": " + nano);
433		}
434		}
435	<
435	>
436		void start(String name, long numOps) {
437		this.name = name;
438		this.cname = classify();
439		this.numOps = numOps;
440		startTime = System.currentTimeMillis();
441		}
456	–
442
443		String classify() {
444		if (name.startsWith("Get"))
#	Line 464 | Line 449 | public class NavigableMapCheck {
449		return "Remove                 ";
450		else if (name.startsWith("Iter"))
451		return "Iter                   ";
452	<	else
452	>	else
453		return null;
454		}
455
456		void finish() {
457		long endTime = System.currentTimeMillis();
458		long time = endTime - startTime;
459	<	double timePerOp = ((double)time)/numOps;
459	>	double timePerOp = (double) time /numOps;
460
461		Object st = accum.get(name);
462		if (st == null)
#	Line 494 | Line 479 | public class NavigableMapCheck {
479		if (timePerOp < stats.least) stats.least = timePerOp;
480		}
481		}
497	–
482		}
499	–
483		}
484
485		static class Stats {
#	Line 506 | Line 489 | public class NavigableMapCheck {
489		Stats(double t) { least = t; }
490		}
491
492	<	static Random rng = new Random();
492	>	static Random rng = new Random(111);
493
494		static void shuffle(Integer[] keys) {
495		int size = keys.length;
496	<	for (int i=size; i>1; i--) {
496	>	for (int i = size; i > 1; i--) {
497		int r = rng.nextInt(i);
498		Integer t = keys[i-1];
499		keys[i-1] = keys[r];
#	Line 519 | Line 502 | public class NavigableMapCheck {
502		}
503
504		}
522	–

Diff Legend

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