ViewVC Help

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

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

Comparing jsr166/src/test/loops/MapCheck.java (file contents):
Revision 1.2 by dl, Mon May 9 19:33:30 2005 UTC vs.
Revision 1.14 by jsr166, Mon Dec 5 04:08:46 2011 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	+	* When run with "s" second arg, this requires file "testwords", which
11	+	* is best used with real words.  We can't check in this file, but you
12	+	* can create one from a real dictionary (1 line per word) and then run
13	+	* linux "shuf" to randomize entries.
14		*/
15		import java.util.*;
16		import java.io.*;
17
18		public class MapCheck {
14	–
15	–	static final int absentSize = 1 << 17;
16	–	static final int absentMask = absentSize - 1;
17	–	static Object[] absent = new Object[absentSize];
18	–
19		static final Object MISSING = new Object();
20	–
20		static TestTimer timer = new TestTimer();
21	+	static Class eclass;
22	+	static Class mapClass = java.util.concurrent.ConcurrentHashMap.class;
23	+
24	+	static final LoopHelpers.SimpleRandom srng = new LoopHelpers.SimpleRandom();
25	+	static final Random rng = new Random(3152688);
26	+
27	+	static volatile int checkSum;
28
29		static void reallyAssert(boolean b) {
30		if (!b) throw new Error("Failed Assertion");
31		}
32
33		public static void main(String[] args) throws Exception {
34	<	Class mapClass = java.util.concurrent.ConcurrentHashMap.class;
35	<	int numTests = 50;
36	<	int size = 50000;
34	>	int numTests = 100;
35	>	int size = 36864; // about midway of HashMap resize interval
36	>
37	>	if (args.length == 0)
38	>	System.out.println("Usage: MapCheck mapclass [int|float|string|object] [trials] [size] [serialtest]");
39
40		if (args.length > 0) {
41		try {
42		mapClass = Class.forName(args[0]);
43	<	} catch(ClassNotFoundException e) {
43	>	} catch (ClassNotFoundException e) {
44		throw new RuntimeException("Class " + args[0] + " not found.");
45		}
46		}
47
48	<
49	<	if (args.length > 1)
50	<	numTests = Integer.parseInt(args[1]);
51	<
52	<	if (args.length > 2)
53	<	size = Integer.parseInt(args[2]);
54	<
55	<	boolean doSerializeTest = args.length > 3;
56	<
57	<	System.out.println("Testing " + mapClass.getName() + " trials: " + numTests + " size: " + size);
58	<
59	<	for (int i = 0; i < absentSize; ++i) absent[i] = new Object();
48	>	if (args.length > 1) {
49	>	String et = args[1].toLowerCase();
50	>	if (et.startsWith("i"))
51	>	eclass = java.lang.Integer.class;
52	>	else if (et.startsWith("f"))
53	>	eclass = java.lang.Float.class;
54	>	else if (et.startsWith("s"))
55	>	eclass = java.lang.String.class;
56	>	else if (et.startsWith("d"))
57	>	eclass = java.lang.Double.class;
58	>	}
59	>	if (eclass == null)
60	>	eclass = Object.class;
61	>
62	>	if (args.length > 2)
63	>	numTests = Integer.parseInt(args[2]);
64	>
65	>	if (args.length > 3)
66	>	size = Integer.parseInt(args[3]);
67	>
68	>	boolean doSerializeTest = args.length > 4;
69	>
70	>	while ((size & 3) != 0) ++size;
71	>
72	>	System.out.print("Class: " + mapClass.getName());
73	>	System.out.print(" elements: " + eclass.getName());
74	>	System.out.print(" trials: " + numTests);
75	>	System.out.print(" size: " + size);
76	>	System.out.println();
77
78		Object[] key = new Object[size];
79	<	for (int i = 0; i < size; ++i) key[i] = new Object();
79	>	Object[] absent = new Object[size];
80	>	initializeKeys(key, absent, size);
81
82	<	forceMem(size * 8);
82	>	precheck(size, key, absent);
83
84		for (int rep = 0; rep < numTests; ++rep) {
85	<	runTest(newMap(mapClass), key);
85	>	mainTest(newMap(), key, absent);
86	>	if ((rep & 3) == 3 && rep < numTests - 1) {
87	>	shuffle(key);
88	>	//                Thread.sleep(10);
89	>	}
90		}
91
92		TestTimer.printStats();
93
94	+	checkNullKey();
95
96		if (doSerializeTest)
97	<	stest(newMap(mapClass), size);
97	>	serTest(newMap(), size);
98		}
99
100	<	static Map newMap(Class cl) {
100	>	static Map newMap() {
101		try {
102	<	Map m = (Map)cl.newInstance();
103	<	return m;
104	<	} catch(Exception e) {
74	<	throw new RuntimeException("Can't instantiate " + cl + ": " + e);
102	>	return (Map) mapClass.newInstance();
103	>	} catch (Exception e) {
104	>	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
105		}
106		}
107
108	+	static void precheck(int n, Object[] key, Object[] abs) {
109	+	int ck = 0;
110	+	Map s = newMap();
111	+	for (int i = 0; i < n; i++) {
112	+	Object k = key[i];
113	+	if (k == null) throw new Error("Null key at" + i);
114	+	ck += System.identityHashCode(k);
115	+	Object v = s.put(k, k);
116	+	if (v != null)
117	+	throw new Error("Duplicate " +  k + " / " + v);
118	+	}
119	+	for (int i = 0; i < n; i++) {
120	+	Object k = abs[i];
121	+	if (k == null) throw new Error("Null key at" + i);
122	+	ck += System.identityHashCode(k);
123	+	Object v = s.put(k, k);
124	+	if (v != null)
125	+	throw new Error("Duplicate " +  k + " / " + v);
126	+	}
127	+	checkSum += ck;
128	+	}
129
130	<	static void runTest(Map s, Object[] key) {
131	<	shuffle(key);
132	<	int size = key.length;
133	<	long startTime = System.currentTimeMillis();
134	<	test(s, key);
135	<	long time = System.currentTimeMillis() - startTime;
130	>	static void checkNullKey() {
131	>	Map m = newMap();
132	>	Object x = new Object();
133	>	Object v;
134	>	try {
135	>	m.put(null, x);
136	>	v = m.get(null);
137	>	} catch (NullPointerException npe) {
138	>	System.out.println("Map does not allow null keys");
139	>	return;
140	>	}
141	>	if (v != x) throw new Error();
142	>	if (m.remove(null) != v) throw new Error();
143	>	if (m.get(null) != null) throw new Error();
144		}
145
146	<	static void forceMem(int n) {
147	<	// force enough memory
89	<	Long[] junk = new Long[n];
90	<	for (int i = 0; i < junk.length; ++i) junk[i] = new Long(i);
146	>
147	>	static void getTest(String nm, int n, Map s, Object[] key, int expect) {
148		int sum = 0;
149	<	for (int i = 0; i < junk.length; ++i)
150	<	sum += (int)(junk[i].longValue() + i);
151	<	if (sum == 0) System.out.println("Useless number = " + sum);
152	<	junk = null;
153	<	//        System.gc();
149	>	timer.start(nm, n);
150	>	for (int i = 0; i < n; i++) {
151	>	Object v = s.get(key[i]);
152	>	if (v != null && v.getClass() == eclass)
153	>	++sum;
154	>	}
155	>	timer.finish();
156	>	reallyAssert(sum == expect);
157	>	checkSum += sum;
158		}
159
160
161	<	static void t1(String nm, int n, Map s, Object[] key, int expect) {
161	>	// unused
162	>	static void getTestBoxed(String nm, int n, Map s, Object[] key, int expect) {
163		int sum = 0;
164	<	int iters = 4;
165	<	timer.start(nm, n * iters);
166	<	for (int j = 0; j < iters; ++j) {
167	<	for (int i = 0; i < n; i++) {
106	<	if (s.get(key[i]) != null) ++sum;
107	<	}
164	>	Map<Integer,Integer> intMap = (Map<Integer,Integer>)s;
165	>	timer.start(nm, n);
166	>	for (int i = 0; i < n; i++) {
167	>	if (intMap.get(i) != i) ++sum;
168		}
169	<	timer.finish();
170	<	reallyAssert (sum == expect * iters);
169	>	timer.finish();
170	>	reallyAssert(sum == expect);
171		}
172
173	<	static void t2(String nm, int n, Map s, Object[] key, int expect) {
173	>	static void remTest(String nm, int n, Map s, Object[] key, int expect) {
174		int sum = 0;
175		timer.start(nm, n);
176		for (int i = 0; i < n; i++) {
177		if (s.remove(key[i]) != null) ++sum;
178		}
179	<	timer.finish();
180	<	reallyAssert (sum == expect);
179	>	timer.finish();
180	>	reallyAssert(sum == expect);
181	>	checkSum += sum;
182		}
183
184	<	static void t3(String nm, int n, Map s, Object[] key, int expect) {
184	>	static void clrTest(int n, Map s) {
185	>	String nm = "Remove Present         ";
186	>	timer.start(nm, n);
187	>	s.clear();
188	>	timer.finish();
189	>	reallyAssert(s.isEmpty());
190	>	}
191	>
192	>	static void putTest(String nm, int n, Map s, Object[] key, int expect) {
193		int sum = 0;
194		timer.start(nm, n);
195		for (int i = 0; i < n; i++) {
196	<	if (s.put(key[i], absent[i & absentMask]) == null) ++sum;
196	>	Object k = key[i];
197	>	Object v = s.put(k, k);
198	>	if (v == null) ++sum;
199		}
200	<	timer.finish();
201	<	reallyAssert (sum == expect);
200	>	timer.finish();
201	>	reallyAssert(sum == expect);
202	>	checkSum += sum;
203		}
204
205	<	static void t4(String nm, int n, Map s, Object[] key, int expect) {
205	>	static void keyTest(String nm, int n, Map s, Object[] key, int expect) {
206		int sum = 0;
207		timer.start(nm, n);
208		for (int i = 0; i < n; i++) {
209		if (s.containsKey(key[i])) ++sum;
210		}
211	<	timer.finish();
212	<	reallyAssert (sum == expect);
211	>	timer.finish();
212	>	reallyAssert(sum == expect);
213	>	checkSum += sum;
214		}
215
216	<	static void t5(String nm, int n, Map s, Object[] key, int expect) {
216	>	// version without timing for uncategorized tests
217	>	static void untimedKeyTest(String nm, int n, Map s, Object[] key, int expect) {
218	>	int sum = 0;
219	>	for (int i = 0; i < n; i++) {
220	>	if (s.containsKey(key[i])) ++sum;
221	>	}
222	>	reallyAssert(sum == expect);
223	>	checkSum += sum;
224	>	}
225	>
226	>	static void remHalfTest(String nm, int n, Map s, Object[] key, int expect) {
227		int sum = 0;
228		timer.start(nm, n/2);
229		for (int i = n-2; i >= 0; i-=2) {
230		if (s.remove(key[i]) != null) ++sum;
231		}
232	<	timer.finish();
233	<	reallyAssert (sum == expect);
232	>	timer.finish();
233	>	reallyAssert(sum == expect);
234	>	checkSum += sum;
235		}
236
237	<	static void t6(String nm, int n, Map s, Object[] k1, Object[] k2) {
237	>	static void valTest(Map s, Object[] key) {
238	>	int size = s.size();
239		int sum = 0;
240	<	timer.start(nm, n * 2);
241	<	for (int i = 0; i < n; i++) {
242	<	if (s.get(k1[i]) != null) ++sum;
243	<	if (s.get(k2[i & absentMask]) != null) ++sum;
244	<	}
160	<	timer.finish();
161	<	reallyAssert (sum == n);
240	>	timer.start("Traverse key or value  ", size);
241	>	if (s.containsValue(MISSING)) ++sum;
242	>	timer.finish();
243	>	reallyAssert(sum == 0);
244	>	checkSum += sum;
245		}
246
247	<	static void t7(String nm, int n, Map s, Object[] k1, Object[] k2) {
247	>
248	>	static Object kitTest(Map s, int size) {
249	>	Object last = null;
250		int sum = 0;
251	<	timer.start(nm, n * 2);
252	<	for (int i = 0; i < n; i++) {
253	<	if (s.containsKey(k1[i])) ++sum;
254	<	if (s.containsKey(k2[i & absentMask])) ++sum;
251	>	timer.start("Traverse key or value  ", size);
252	>	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
253	>	Object x = it.next();
254	>	if (x != last && x != null && x.getClass() == eclass)
255	>	++sum;
256	>	last = x;
257		}
258	<	timer.finish();
259	<	reallyAssert (sum == n);
258	>	timer.finish();
259	>	reallyAssert(sum == size);
260	>	checkSum += sum;
261	>	return last;
262		}
263
264	<	static void t8(String nm, int n, Map s, Object[] key, int expect) {
264	>	static Object vitTest(Map s, int size) {
265	>	Object last = null;
266		int sum = 0;
267	<	timer.start(nm, n);
268	<	for (int i = 0; i < n; i++) {
269	<	if (s.get(key[i]) != null) ++sum;
267	>	timer.start("Traverse key or value  ", size);
268	>	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
269	>	Object x = it.next();
270	>	if (x != last && x != null && x.getClass() == eclass)
271	>	++sum;
272	>	last = x;
273		}
274	<	timer.finish();
275	<	reallyAssert (sum == expect);
274	>	timer.finish();
275	>	reallyAssert(sum == size);
276	>	checkSum += sum;
277	>	return last;
278		}
279
280	<
186	<	static void t9(Map s) {
280	>	static void eitTest(Map s, int size) {
281		int sum = 0;
282	<	int iters = 20;
283	<	timer.start("ContainsValue (/n)     ", iters * s.size());
284	<	int step = absentSize / iters;
285	<	for (int i = 0; i < absentSize; i += step)
286	<	if (s.containsValue(absent[i])) ++sum;
287	<	timer.finish();
288	<	reallyAssert (sum != 0);
282	>	timer.start("Traverse entry         ", size);
283	>	for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
284	>	Map.Entry e = (Map.Entry)it.next();
285	>	Object k = e.getKey();
286	>	Object v = e.getValue();
287	>	if (k != null && k.getClass() == eclass &&
288	>	v != null && v.getClass() == eclass)
289	>	++sum;
290	>	}
291	>	timer.finish();
292	>	reallyAssert(sum == size);
293	>	checkSum += sum;
294		}
295
296	<
297	<	static void ktest(Map s, int size, Object[] key) {
298	<	timer.start("ContainsKey            ", size);
299	<	Set ks = s.keySet();
296	>	static void itRemTest(Map s, int size) {
297	>	int sz = s.size();
298	>	reallyAssert(sz == size);
299	>	timer.start("Remove Present         ", size);
300		int sum = 0;
301	<	for (int i = 0; i < size; i++) {
302	<	if (ks.contains(key[i])) ++sum;
301	>	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
302	>	it.next();
303	>	it.remove();
304	>	++sum;
305		}
306	<	timer.finish();
307	<	reallyAssert (sum == size);
306	>	timer.finish();
307	>	reallyAssert(sum == sz);
308	>	checkSum += sum;
309		}
310
311	<
312	<	static void ittest1(Map s, int size) {
311	>	static void itHalfRemTest(Map s, int size) {
312	>	int sz = s.size();
313	>	reallyAssert(sz == size);
314	>	timer.start("Remove Present         ", size);
315		int sum = 0;
212	–	timer.start("Iter Key               ", size);
316		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
317	<	if(it.next() != MISSING)
318	<	++sum;
317	>	it.next();
318	>	it.remove();
319	>	if (it.hasNext())
320	>	it.next();
321	>	++sum;
322		}
323	<	timer.finish();
324	<	reallyAssert (sum == size);
323	>	timer.finish();
324	>	reallyAssert(sum == sz / 2);
325	>	checkSum += sum;
326		}
327
328	<	static void ittest2(Map s, int size) {
329	<	int sum = 0;
330	<	timer.start("Iter Value             ", size);
331	<	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
332	<	if(it.next() != MISSING)
333	<	++sum;
328	>	static void putAllTest(String nm, int n, Map src, Map dst) {
329	>	timer.start(nm, n);
330	>	dst.putAll(src);
331	>	timer.finish();
332	>	reallyAssert(src.size() == dst.size());
333	>	}
334	>
335	>	static void serTest(Map s, int size) throws Exception {
336	>	if (!(s instanceof Serializable))
337	>	return;
338	>	System.out.print("Serialize              : ");
339	>
340	>	for (int i = 0; i < size; i++) {
341	>	s.put(new Integer(i), Boolean.TRUE);
342		}
343	<	timer.finish();
344	<	reallyAssert (sum == size);
343	>
344	>	long startTime = System.currentTimeMillis();
345	>
346	>	FileOutputStream fs = new FileOutputStream("MapCheck.dat");
347	>	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(fs));
348	>	out.writeObject(s);
349	>	out.close();
350	>
351	>	FileInputStream is = new FileInputStream("MapCheck.dat");
352	>	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(is));
353	>	Map m = (Map) in.readObject();
354	>
355	>	long endTime = System.currentTimeMillis();
356	>	long time = endTime - startTime;
357	>
358	>	System.out.print(time + "ms");
359	>
360	>	if (s instanceof IdentityHashMap) return;
361	>	reallyAssert(s.equals(m));
362		}
363	<	static void ittest3(Map s, int size) {
363	>
364	>	static void mainTest(Map s, Object[] key, Object[] absent) {
365	>	int size = key.length;
366	>
367	>	putTest("Add    Absent          ", size, s, key, size);
368	>	reallyAssert(s.size() == size);
369	>	getTest("Access Present         ", size, s, key, size);
370	>	getTest("Search Absent          ", size, s, absent, 0);
371	>	kitTest(s, size);
372	>	vitTest(s, size);
373	>	eitTest(s, size);
374	>	putTest("Modify Present         ", size, s, key, 0);
375	>	reallyAssert(s.size() == size);
376	>	untimedKeyTest("Access Present         ", size, s, key, size);
377	>	keyTest("Search Absent          ", size, s, absent, 0);
378	>	valTest(s, key);
379	>	remTest("Search Absent          ", size, s, absent, 0);
380	>	reallyAssert(s.size() == size);
381	>	remHalfTest("Remove Present         ", size, s, key, size / 2);
382	>	reallyAssert(s.size() == size / 2);
383	>	getTest("Access Present         ", size, s, key, size / 2);
384	>	putTest("Add    Absent          ", size, s, key, size / 2);
385	>	reallyAssert(s.size() == size);
386	>	getTest("Access Present         ", size, s, key, size);
387	>	getTest("Search Absent          ", size, s, absent, 0);
388	>	itRemTest(s, size);
389	>	putTest("Add    Absent          ", size, s, key, size);
390	>	reallyAssert(s.size() == size);
391	>	getTest("Access Present         ", size, s, key, size);
392	>	untimedKeyTest("Access Present         ", size, s, key, size);
393	>	kitTest(s, size);
394	>	vitTest(s, size);
395	>	eitTest(s, size);
396	>	twoMapTest1(s, key, absent);
397	>	twoMapTest2(s, key, absent);
398	>	}
399	>
400	>	static void twoMapTest1(Map s, Object[] key, Object[] absent) {
401	>	int size = s.size();
402	>	Map s2 = newMap();
403	>	putAllTest("Add    Absent          ", size, s, s2);
404	>	getTest("Access Present         ", size, s2, key, size);
405	>	itHalfRemTest(s2, size);
406	>	reallyAssert(s2.size() == size / 2);
407	>	itHalfRemTest(s2, size / 2);
408	>	reallyAssert(s2.size() == size / 4);
409	>	putTest("Add    Absent          ", size, s2, absent, size);
410	>	putTest("Add    Absent          ", size, s2, key, size * 3 / 4);
411	>	reallyAssert(s2.size() == size * 2);
412	>	clrTest(size, s2);
413	>	}
414	>
415	>	static void twoMapTest2(Map s, Object[] key, Object[] absent) {
416	>	int size = key.length;
417	>
418	>	Map s2 = newMap();
419	>	putAllTest("Add    Absent          ", size, s, s2);
420	>	putAllTest("Modify Present         ", size, s, s2);
421	>
422	>	Object lastkey = kitTest(s2, size);
423	>	Object hold = s2.get(lastkey);
424		int sum = 0;
425	<	timer.start("Iter Entry             ", size);
425	>
426	>	timer.start("Traverse entry         ", size * 12); // 12 until finish
427	>
428	>	int sh1 = s.hashCode() - s2.hashCode();
429	>	reallyAssert(sh1 == 0);
430	>
431	>	boolean eq1 = s2.equals(s);
432	>	boolean eq2 = s.equals(s2);
433	>	reallyAssert(eq1 && eq2);
434	>
435	>	Set es2 = s2.entrySet();
436		for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
437	<	if(it.next() != MISSING)
438	<	++sum;
437	>	Object entry = it.next();
438	>	if (es2.contains(entry)) ++sum;
439	>	}
440	>	reallyAssert(sum == size);
441	>
442	>	s2.put(lastkey, MISSING);
443	>
444	>	int sh2 = s.hashCode() - s2.hashCode();
445	>	reallyAssert(sh2 != 0);
446	>
447	>	eq1 = s2.equals(s);
448	>	eq2 = s.equals(s2);
449	>	reallyAssert(!eq1 && !eq2);
450	>
451	>	sum = 0;
452	>	for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
453	>	Map.Entry e = (Map.Entry)it.next();
454	>	e.setValue(absent[sum++]);
455	>	}
456	>	reallyAssert(sum == size);
457	>	for (Iterator it = s2.entrySet().iterator(); it.hasNext(); ) {
458	>	Map.Entry e = (Map.Entry)it.next();
459	>	e.setValue(s.get(e.getKey()));
460	>	}
461	>
462	>	timer.finish();
463	>
464	>	int rmiss = 0;
465	>	timer.start("Remove Present         ", size * 2);
466	>	Iterator s2i = s2.entrySet().iterator();
467	>	Set es = s.entrySet();
468	>	while (s2i.hasNext()) {
469	>	if (!es.remove(s2i.next()))
470	>	++rmiss;
471		}
472	<	timer.finish();
473	<	reallyAssert (sum == size);
472	>	timer.finish();
473	>	reallyAssert(rmiss == 0);
474	>
475	>	clrTest(size, s2);
476	>	reallyAssert(s2.isEmpty() && s.isEmpty());
477		}
478
479	<	static void ittest4(Map s, int size, int pos) {
479	>	static void itTest4(Map s, int size, int pos) {
480		IdentityHashMap seen = new IdentityHashMap(size);
481	<	reallyAssert (s.size() == size);
481	>	reallyAssert(s.size() == size);
482		int sum = 0;
483		timer.start("Iter XEntry            ", size);
484	<	Iterator it = s.entrySet().iterator();
484	>	Iterator it = s.entrySet().iterator();
485		Object k = null;
486		Object v = null;
487		for (int i = 0; i < size-pos; ++i) {
#	Line 255 | Line 492 | public class MapCheck {
492		if (x != MISSING)
493		++sum;
494		}
495	<	reallyAssert (s.containsKey(k));
495	>	reallyAssert(s.containsKey(k));
496		it.remove();
497	<	reallyAssert (!s.containsKey(k));
497	>	reallyAssert(!s.containsKey(k));
498		while (it.hasNext()) {
499		Map.Entry x = (Map.Entry)(it.next());
500		Object k2 = x.getKey();
#	Line 266 | Line 503 | public class MapCheck {
503		++sum;
504		}
505
506	<	reallyAssert (s.size() == size-1);
506	>	reallyAssert(s.size() == size-1);
507		s.put(k, v);
508	<	reallyAssert (seen.size() == size);
509	<	timer.finish();
510	<	reallyAssert (sum == size);
511	<	reallyAssert (s.size() == size);
508	>	reallyAssert(seen.size() == size);
509	>	timer.finish();
510	>	reallyAssert(sum == size);
511	>	reallyAssert(s.size() == size);
512		}
513
514
278	–	static void ittest(Map s, int size) {
279	–	ittest1(s, size);
280	–	ittest2(s, size);
281	–	ittest3(s, size);
282	–	//        for (int i = 0; i < size-1; ++i)
283	–	//            ittest4(s, size, i);
284	–	}
285	–
286	–	static void entest1(Hashtable ht, int size) {
287	–	int sum = 0;
515
516	<	timer.start("Iter Enumeration Key   ", size);
517	<	for (Enumeration en = ht.keys(); en.hasMoreElements(); ) {
518	<	if (en.nextElement() != MISSING)
519	<	++sum;
516	>	static void initializeKeys(Object[] key, Object[] absent, int size) {
517	>	if (eclass == Object.class) {
518	>	for (int i = 0; i < size; ++i) key[i] = new Object();
519	>	for (int i = 0; i < size; ++i) absent[i] = new Object();
520		}
521	<	timer.finish();
522	<	reallyAssert (sum == size);
523	<	}
524	<
525	<	static void entest2(Hashtable ht, int size) {
299	<	int sum = 0;
300	<	timer.start("Iter Enumeration Value ", size);
301	<	for (Enumeration en = ht.elements(); en.hasMoreElements(); ) {
302	<	if (en.nextElement() != MISSING)
303	<	++sum;
521	>	else if (eclass == Integer.class) {
522	>	initInts(key, absent, size);
523	>	}
524	>	else if (eclass == Float.class) {
525	>	initFloats(key, absent, size);
526		}
527	<	timer.finish();
528	<	reallyAssert (sum == size);
527	>	else if (eclass == Double.class) {
528	>	initDoubles(key, absent, size);
529	>	}
530	>	else if (eclass == String.class) {
531	>	initWords(size, key, absent);
532	>	}
533	>	else
534	>	throw new Error("unknown type");
535		}
536
537	<
538	<	static void entest3(Hashtable ht, int size) {
539	<	int sum = 0;
540	<
541	<	timer.start("Iterf Enumeration Key  ", size);
542	<	Enumeration en = ht.keys();
543	<	for (int i = 0; i < size; ++i) {
544	<	if (en.nextElement() != MISSING)
545	<	++sum;
537	>	static void initInts(Object[] key, Object[] absent, int size) {
538	>	for (int i = 0; i < size; ++i)
539	>	key[i] = Integer.valueOf(i);
540	>	Map m = newMap();
541	>	int k = 0;
542	>	while (k < size) {
543	>	int r = srng.next();
544	>	if (r < 0 || r >= size) {
545	>	Integer ir = Integer.valueOf(r);
546	>	if (m.put(ir, ir) == null)
547	>	absent[k++] = ir;
548	>	}
549		}
319	–	timer.finish();
320	–	reallyAssert (sum == size);
550		}
551
552	<	static void entest4(Hashtable ht, int size) {
553	<	int sum = 0;
325	<	timer.start("Iterf Enumeration Value", size);
326	<	Enumeration en = ht.elements();
552	>	static void initFloats(Object[] key, Object[] absent, int size) {
553	>	Map m = newMap();
554		for (int i = 0; i < size; ++i) {
555	<	if (en.nextElement() != MISSING)
556	<	++sum;
555	>	float r = Float.valueOf(i);
556	>	key[i] = r;
557	>	m.put(r, r);
558		}
559	<	timer.finish();
560	<	reallyAssert (sum == size);
561	<	}
562	<
563	<	static void entest(Map s, int size) {
564	<	if (s instanceof Hashtable) {
337	<	Hashtable ht = (Hashtable)s;
338	<	//            entest3(ht, size);
339	<	//            entest4(ht, size);
340	<	entest1(ht, size);
341	<	entest2(ht, size);
342	<	entest1(ht, size);
343	<	entest2(ht, size);
344	<	entest1(ht, size);
345	<	entest2(ht, size);
559	>	int k = 0;
560	>	while (k < size) {
561	>	float r = rng.nextFloat();
562	>	Float ir = Float.valueOf(r);
563	>	if (m.put(ir, ir) == null)
564	>	absent[k++] = ir;
565		}
566		}
567
568	<	static void rtest(Map s, int size) {
569	<	timer.start("Remove (iterator)      ", size);
570	<	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
571	<	it.next();
572	<	it.remove();
568	>	static void initDoubles(Object[] key, Object[] absent, int size) {
569	>	Map m = newMap();
570	>	for (int i = 0; i < size; ++i) {
571	>	double r = Double.valueOf(i);
572	>	key[i] = r;
573	>	m.put(r, r);
574		}
575	<	timer.finish();
576	<	}
577	<
578	<	static void rvtest(Map s, int size) {
579	<	timer.start("Remove (iterator)      ", size);
580	<	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
361	<	it.next();
362	<	it.remove();
575	>	int k = 0;
576	>	while (k < size) {
577	>	double r = rng.nextDouble();
578	>	Double ir = Double.valueOf(r);
579	>	if (m.put(ir, ir) == null)
580	>	absent[k++] = ir;
581		}
364	–	timer.finish();
582		}
583
584	+	// Use as many real words as possible, then use fake random words
585
586	<	static void dtest(Map s, int size, Object[] key) {
587	<	timer.start("Put (putAll)           ", size * 2);
588	<	Map s2 = null;
586	>	static void initWords(int size, Object[] key, Object[] abs) {
587	>	String fileName = "testwords.txt";
588	>	int ki = 0;
589	>	int ai = 0;
590		try {
591	<	s2 = (Map) (s.getClass().newInstance());
592	<	s2.putAll(s);
591	>	FileInputStream fr = new FileInputStream(fileName);
592	>	BufferedInputStream in = new BufferedInputStream(fr);
593	>	while (ki < size || ai < size) {
594	>	StringBuffer sb = new StringBuffer();
595	>	for (;;) {
596	>	int c = in.read();
597	>	if (c < 0) {
598	>	if (ki < size)
599	>	randomWords(key, ki, size);
600	>	if (ai < size)
601	>	randomWords(abs, ai, size);
602	>	in.close();
603	>	return;
604	>	}
605	>	if (c == '\n') {
606	>	String s = sb.toString();
607	>	if (ki < size)
608	>	key[ki++] = s;
609	>	else
610	>	abs[ai++] = s;
611	>	break;
612	>	}
613	>	sb.append((char) c);
614	>	}
615	>	}
616	>	in.close();
617		}
618	<	catch (Exception e) { e.printStackTrace(); return; }
619	<	timer.finish();
620	<
378	<	timer.start("Iter Equals            ", size * 2);
379	<	boolean eqt = s2.equals(s) && s.equals(s2);
380	<	reallyAssert (eqt);
381	<	timer.finish();
382	<
383	<	timer.start("Iter HashCode          ", size * 2);
384	<	int shc = s.hashCode();
385	<	int s2hc = s2.hashCode();
386	<	reallyAssert (shc == s2hc);
387	<	timer.finish();
388	<
389	<	timer.start("Put (present)          ", size);
390	<	s2.putAll(s);
391	<	timer.finish();
392	<
393	<	timer.start("Iter EntrySet contains ", size * 2);
394	<	Set es2 = s2.entrySet();
395	<	int sum = 0;
396	<	for (Iterator i1 = s.entrySet().iterator(); i1.hasNext(); ) {
397	<	Object entry = i1.next();
398	<	if (es2.contains(entry)) ++sum;
618	>	catch (IOException ex) {
619	>	System.out.println("Can't read words file:" + ex);
620	>	throw new Error(ex);
621		}
400	–	timer.finish();
401	–	reallyAssert (sum == size);
402	–
403	–	t6("Get                    ", size, s2, key, absent);
404	–
405	–	Object hold = s2.get(key[size-1]);
406	–	s2.put(key[size-1], absent[0]);
407	–	timer.start("Iter Equals            ", size * 2);
408	–	eqt = s2.equals(s) && s.equals(s2);
409	–	reallyAssert (!eqt);
410	–	timer.finish();
411	–
412	–	timer.start("Iter HashCode          ", size * 2);
413	–	int s1h = s.hashCode();
414	–	int s2h = s2.hashCode();
415	–	reallyAssert (s1h != s2h);
416	–	timer.finish();
417	–
418	–	s2.put(key[size-1], hold);
419	–	timer.start("Remove (iterator)      ", size * 2);
420	–	Iterator s2i = s2.entrySet().iterator();
421	–	Set es = s.entrySet();
422	–	while (s2i.hasNext())
423	–	es.remove(s2i.next());
424	–	timer.finish();
425	–
426	–	reallyAssert (s.isEmpty());
427	–
428	–	timer.start("Clear                  ", size);
429	–	s2.clear();
430	–	timer.finish();
431	–	reallyAssert (s2.isEmpty() && s.isEmpty());
622		}
623
434	–	static void stest(Map s, int size) throws Exception {
435	–	if (!(s instanceof Serializable))
436	–	return;
437	–	System.out.print("Serialize              : ");
438	–
439	–	for (int i = 0; i < size; i++) {
440	–	s.put(new Integer(i), Boolean.TRUE);
441	–	}
442	–
443	–	long startTime = System.currentTimeMillis();
444	–
445	–	FileOutputStream fs = new FileOutputStream("MapCheck.dat");
446	–	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(fs));
447	–	out.writeObject(s);
448	–	out.close();
449	–
450	–	FileInputStream is = new FileInputStream("MapCheck.dat");
451	–	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(is));
452	–	Map m = (Map)in.readObject();
624
625	<	long endTime = System.currentTimeMillis();
626	<	long time = endTime - startTime;
627	<
628	<	System.out.print(time + "ms");
629	<
630	<	if (s instanceof IdentityHashMap) return;
631	<	reallyAssert (s.equals(m));
632	<	}
633	<
634	<
635	<	static void test(Map s, Object[] key) {
636	<	int size = key.length;
637	<
638	<	t3("Put (absent)           ", size, s, key, size);
639	<	t3("Put (present)          ", size, s, key, 0);
640	<	t7("ContainsKey            ", size, s, key, absent);
641	<	t4("ContainsKey            ", size, s, key, size);
642	<	ktest(s, size, key);
472	<	t4("ContainsKey            ", absentSize, s, absent, 0);
473	<	t6("Get                    ", size, s, key, absent);
474	<	t1("Get (present)          ", size, s, key, size);
475	<	t1("Get (absent)           ", absentSize, s, absent, 0);
476	<	t2("Remove (absent)        ", absentSize, s, absent, 0);
477	<	t5("Remove (present)       ", size, s, key, size / 2);
478	<	t3("Put (half present)     ", size, s, key, size / 2);
479	<
480	<	ittest(s, size);
481	<	entest(s, size);
482	<	t9(s);
483	<	rtest(s, size);
484	<
485	<	t4("ContainsKey            ", size, s, key, 0);
486	<	t2("Remove (absent)        ", size, s, key, 0);
487	<	t3("Put (presized)         ", size, s, key, size);
488	<	dtest(s, size, key);
625	>	static void randomWords(Object[] ws, int origin, int size) {
626	>	for (int i = origin; i < size; ++i) {
627	>	int k = 0;
628	>	int len = 2 + (srng.next() & 0xf);
629	>	char[] c = new char[len * 4 + 1];
630	>	for (int j = 1; j < len; ++j) {
631	>	int r = srng.next();
632	>	c[k++] = (char) (' ' + (r & 0x7f));
633	>	r >>>= 8;
634	>	c[k++] = (char) (' ' + (r & 0x7f));
635	>	r >>>= 8;
636	>	c[k++] = (char) (' ' + (r & 0x7f));
637	>	r >>>= 8;
638	>	c[k++] = (char) (' ' + (r & 0x7f));
639	>	}
640	>	c[k++] = (char) ((i & 31) | 1); // never == to any testword
641	>	ws[i] = new String(c);
642	>	}
643		}
644
645	<	static class TestTimer {
645	>	static final class TestTimer {
646		private String name;
647		private long numOps;
648		private long startTime;
495	–	private String cname;
649
650		static final java.util.TreeMap accum = new java.util.TreeMap();
651	<
651	>
652		static void printStats() {
653		for (Iterator it = accum.entrySet().iterator(); it.hasNext(); ) {
654	<	Map.Entry e = (Map.Entry)(it.next());
655	<	Stats stats = ((Stats)(e.getValue()));
656	<	int n = stats.number;
657	<	double t;
658	<	if (n > 0)
659	<	t = stats.sum / n;
654	>	Map.Entry e = (Map.Entry) it.next();
655	>	Stats stats = (Stats) e.getValue();
656	>	System.out.print(e.getKey() + ": ");
657	>	long s;
658	>	long n = stats.number;
659	>	if (n == 0) {
660	>	n = stats.firstn;
661	>	s = stats.first;
662	>	}
663		else
664	<	t = stats.least;
665	<	long nano = Math.round(1000000.0 * t);
666	<	System.out.println(e.getKey() + ": " + nano);
664	>	s = stats.sum;
665	>
666	>	double t = ((double) s) / n;
667	>	long nano = Math.round(t);
668	>	System.out.printf("%6d", + nano);
669	>	System.out.println();
670		}
671		}
672	<
672	>
673		void start(String name, long numOps) {
674		this.name = name;
516	–	this.cname = classify();
675		this.numOps = numOps;
676	<	startTime = System.currentTimeMillis();
519	<	}
520	<
521	<
522	<	String classify() {
523	<	if (name.startsWith("Get"))
524	<	return "Get                    ";
525	<	else if (name.startsWith("Put"))
526	<	return "Put                    ";
527	<	else if (name.startsWith("Remove"))
528	<	return "Remove                 ";
529	<	else if (name.startsWith("Iter"))
530	<	return "Iter                   ";
531	<	else
532	<	return null;
676	>	startTime = System.nanoTime();
677		}
678
679		void finish() {
680	<	long endTime = System.currentTimeMillis();
537	<	long time = endTime - startTime;
538	<	double timePerOp = ((double)time)/numOps;
539	<
680	>	long elapsed = System.nanoTime() - startTime;
681		Object st = accum.get(name);
682		if (st == null)
683	<	accum.put(name, new Stats(timePerOp));
684	<	else {
685	<	Stats stats = (Stats) st;
545	<	stats.sum += timePerOp;
546	<	stats.number++;
547	<	if (timePerOp < stats.least) stats.least = timePerOp;
548	<	}
549	<
550	<	if (cname != null) {
551	<	st = accum.get(cname);
552	<	if (st == null)
553	<	accum.put(cname, new Stats(timePerOp));
554	<	else {
555	<	Stats stats = (Stats) st;
556	<	stats.sum += timePerOp;
557	<	stats.number++;
558	<	if (timePerOp < stats.least) stats.least = timePerOp;
559	<	}
560	<	}
561	<
683	>	accum.put(name, new Stats(elapsed, numOps));
684	>	else
685	>	((Stats) st).addTime(elapsed, numOps);
686		}
687
688		}
689
690	<	static class Stats {
691	<	double sum = 0;
692	<	double least;
693	<	int number = 0;
694	<	Stats(double t) { least = t; }
690	>	static final class Stats {
691	>	long sum;
692	>	long number;
693	>	long first;
694	>	long firstn;
695	>	Stats(long t, long n) {
696	>	first = t;
697	>	firstn = n;
698	>	}
699	>	void addTime(long t, long n) {
700	>	sum += t;
701	>	number += n;
702	>	}
703		}
704
573	–	static Random rng = new Random();
705
706		static void shuffle(Object[] keys) {
707		int size = keys.length;
708	<	for (int i=size; i>1; i--) {
708	>	for (int i= size; i>1; i--) {
709		int r = rng.nextInt(i);
710		Object t = keys[i-1];
711		keys[i-1] = keys[r];
#	Line 582 | Line 713 | public class MapCheck {
713		}
714		}
715
716	<	}
716	>	static void shuffle(ArrayList keys) {
717	>	int size = keys.size();
718	>	for (int i= size; i>1; i--) {
719	>	int r = rng.nextInt(i);
720	>	Object t = keys.get(i-1);
721	>	keys.set(i-1, keys.get(r));
722	>	keys.set(r, t);
723	>	}
724	>	}
725
726	+	}

Diff Legend

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