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.19 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	+	* 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		*/
10	–	import java.util.*;
15		import java.io.*;
16	+	import java.util.*;
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.getConstructor().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) {
88	<	// force enough memory
89	<	Long[] junk = new Long[n];
90	<	for (int i = 0; i < junk.length; ++i) junk[i] = new Long(i);
146	>	static void getTest(String nm, int n, Map s, Object[] key, int expect) {
147		int sum = 0;
148	<	for (int i = 0; i < junk.length; ++i)
149	<	sum += (int)(junk[i].longValue() + i);
150	<	if (sum == 0) System.out.println("Useless number = " + sum);
151	<	junk = null;
152	<	//        System.gc();
148	>	timer.start(nm, n);
149	>	for (int i = 0; i < n; i++) {
150	>	Object v = s.get(key[i]);
151	>	if (v != null && v.getClass() == eclass)
152	>	++sum;
153	>	}
154	>	timer.finish();
155	>	reallyAssert(sum == expect);
156	>	checkSum += sum;
157		}
158
159	<
160	<	static void t1(String nm, int n, Map s, Object[] key, int expect) {
159	>	// unused
160	>	static void getTestBoxed(String nm, int n, Map s, Object[] key, int expect) {
161		int sum = 0;
162	<	int iters = 4;
163	<	timer.start(nm, n * iters);
164	<	for (int j = 0; j < iters; ++j) {
165	<	for (int i = 0; i < n; i++) {
106	<	if (s.get(key[i]) != null) ++sum;
107	<	}
162	>	Map<Integer,Integer> intMap = (Map<Integer,Integer>)s;
163	>	timer.start(nm, n);
164	>	for (int i = 0; i < n; i++) {
165	>	if (intMap.get(i) != i) ++sum;
166		}
167	<	timer.finish();
168	<	reallyAssert (sum == expect * iters);
167	>	timer.finish();
168	>	reallyAssert(sum == expect);
169		}
170
171	<	static void t2(String nm, int n, Map s, Object[] key, int expect) {
171	>	static void remTest(String nm, int n, Map s, Object[] key, int expect) {
172		int sum = 0;
173		timer.start(nm, n);
174		for (int i = 0; i < n; i++) {
175		if (s.remove(key[i]) != null) ++sum;
176		}
177	<	timer.finish();
178	<	reallyAssert (sum == expect);
177	>	timer.finish();
178	>	reallyAssert(sum == expect);
179	>	checkSum += sum;
180	>	}
181	>
182	>	static void clrTest(int n, Map s) {
183	>	String nm = "Remove Present         ";
184	>	timer.start(nm, n);
185	>	s.clear();
186	>	timer.finish();
187	>	reallyAssert(s.isEmpty());
188		}
189
190	<	static void t3(String nm, int n, Map s, Object[] key, int expect) {
190	>	static void putTest(String nm, int n, Map s, Object[] key, int expect) {
191		int sum = 0;
192		timer.start(nm, n);
193		for (int i = 0; i < n; i++) {
194	<	if (s.put(key[i], absent[i & absentMask]) == null) ++sum;
194	>	Object k = key[i];
195	>	Object v = s.put(k, k);
196	>	if (v == null) ++sum;
197		}
198	<	timer.finish();
199	<	reallyAssert (sum == expect);
198	>	timer.finish();
199	>	reallyAssert(sum == expect);
200	>	checkSum += sum;
201		}
202
203	<	static void t4(String nm, int n, Map s, Object[] key, int expect) {
203	>	static void keyTest(String nm, int n, Map s, Object[] key, int expect) {
204		int sum = 0;
205		timer.start(nm, n);
206		for (int i = 0; i < n; i++) {
207		if (s.containsKey(key[i])) ++sum;
208		}
209	<	timer.finish();
210	<	reallyAssert (sum == expect);
209	>	timer.finish();
210	>	reallyAssert(sum == expect);
211	>	checkSum += sum;
212	>	}
213	>
214	>	// version without timing for uncategorized tests
215	>	static void untimedKeyTest(String nm, int n, Map s, Object[] key, int expect) {
216	>	int sum = 0;
217	>	for (int i = 0; i < n; i++) {
218	>	if (s.containsKey(key[i])) ++sum;
219	>	}
220	>	reallyAssert(sum == expect);
221	>	checkSum += sum;
222		}
223
224	<	static void t5(String nm, int n, Map s, Object[] key, int expect) {
224	>	static void remHalfTest(String nm, int n, Map s, Object[] key, int expect) {
225		int sum = 0;
226		timer.start(nm, n/2);
227		for (int i = n-2; i >= 0; i-=2) {
228		if (s.remove(key[i]) != null) ++sum;
229		}
230	<	timer.finish();
231	<	reallyAssert (sum == expect);
230	>	timer.finish();
231	>	reallyAssert(sum == expect);
232	>	checkSum += sum;
233		}
234
235	<	static void t6(String nm, int n, Map s, Object[] k1, Object[] k2) {
235	>	static void valTest(Map s, Object[] key) {
236	>	int size = s.size();
237		int sum = 0;
238	<	timer.start(nm, n * 2);
239	<	for (int i = 0; i < n; i++) {
240	<	if (s.get(k1[i]) != null) ++sum;
241	<	if (s.get(k2[i & absentMask]) != null) ++sum;
242	<	}
160	<	timer.finish();
161	<	reallyAssert (sum == n);
238	>	timer.start("Traverse key or value  ", size);
239	>	if (s.containsValue(MISSING)) ++sum;
240	>	timer.finish();
241	>	reallyAssert(sum == 0);
242	>	checkSum += sum;
243		}
244
245	<	static void t7(String nm, int n, Map s, Object[] k1, Object[] k2) {
245	>	static Object kitTest(Map s, int size) {
246	>	Object last = null;
247		int sum = 0;
248	<	timer.start(nm, n * 2);
249	<	for (int i = 0; i < n; i++) {
250	<	if (s.containsKey(k1[i])) ++sum;
251	<	if (s.containsKey(k2[i & absentMask])) ++sum;
248	>	timer.start("Traverse key or value  ", size);
249	>	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
250	>	Object x = it.next();
251	>	if (x != last && x != null && x.getClass() == eclass)
252	>	++sum;
253	>	last = x;
254		}
255	<	timer.finish();
256	<	reallyAssert (sum == n);
255	>	timer.finish();
256	>	reallyAssert(sum == size);
257	>	checkSum += sum;
258	>	return last;
259		}
260
261	<	static void t8(String nm, int n, Map s, Object[] key, int expect) {
261	>	static Object vitTest(Map s, int size) {
262	>	Object last = null;
263		int sum = 0;
264	<	timer.start(nm, n);
265	<	for (int i = 0; i < n; i++) {
266	<	if (s.get(key[i]) != null) ++sum;
264	>	timer.start("Traverse key or value  ", size);
265	>	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
266	>	Object x = it.next();
267	>	if (x != last && x != null && x.getClass() == eclass)
268	>	++sum;
269	>	last = x;
270		}
271	<	timer.finish();
272	<	reallyAssert (sum == expect);
271	>	timer.finish();
272	>	reallyAssert(sum == size);
273	>	checkSum += sum;
274	>	return last;
275		}
276
277	<
186	<	static void t9(Map s) {
277	>	static void eitTest(Map s, int size) {
278		int sum = 0;
279	<	int iters = 20;
280	<	timer.start("ContainsValue (/n)     ", iters * s.size());
281	<	int step = absentSize / iters;
282	<	for (int i = 0; i < absentSize; i += step)
283	<	if (s.containsValue(absent[i])) ++sum;
284	<	timer.finish();
285	<	reallyAssert (sum != 0);
279	>	timer.start("Traverse entry         ", size);
280	>	for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
281	>	Map.Entry e = (Map.Entry)it.next();
282	>	Object k = e.getKey();
283	>	Object v = e.getValue();
284	>	if (k != null && k.getClass() == eclass &&
285	>	v != null && v.getClass() == eclass)
286	>	++sum;
287	>	}
288	>	timer.finish();
289	>	reallyAssert(sum == size);
290	>	checkSum += sum;
291		}
292
293	<
294	<	static void ktest(Map s, int size, Object[] key) {
295	<	timer.start("ContainsKey            ", size);
296	<	Set ks = s.keySet();
293	>	static void itRemTest(Map s, int size) {
294	>	int sz = s.size();
295	>	reallyAssert(sz == size);
296	>	timer.start("Remove Present         ", size);
297		int sum = 0;
298	<	for (int i = 0; i < size; i++) {
299	<	if (ks.contains(key[i])) ++sum;
298	>	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
299	>	it.next();
300	>	it.remove();
301	>	++sum;
302		}
303	<	timer.finish();
304	<	reallyAssert (sum == size);
303	>	timer.finish();
304	>	reallyAssert(sum == sz);
305	>	checkSum += sum;
306		}
307
308	<
309	<	static void ittest1(Map s, int size) {
308	>	static void itHalfRemTest(Map s, int size) {
309	>	int sz = s.size();
310	>	reallyAssert(sz == size);
311	>	timer.start("Remove Present         ", size);
312		int sum = 0;
212	–	timer.start("Iter Key               ", size);
313		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
314	<	if(it.next() != MISSING)
315	<	++sum;
314	>	it.next();
315	>	it.remove();
316	>	if (it.hasNext())
317	>	it.next();
318	>	++sum;
319		}
320	<	timer.finish();
321	<	reallyAssert (sum == size);
320	>	timer.finish();
321	>	reallyAssert(sum == sz / 2);
322	>	checkSum += sum;
323		}
324
325	<	static void ittest2(Map s, int size) {
326	<	int sum = 0;
327	<	timer.start("Iter Value             ", size);
328	<	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
329	<	if(it.next() != MISSING)
330	<	++sum;
325	>	static void putAllTest(String nm, int n, Map src, Map dst) {
326	>	timer.start(nm, n);
327	>	dst.putAll(src);
328	>	timer.finish();
329	>	reallyAssert(src.size() == dst.size());
330	>	}
331	>
332	>	static void serTest(Map s, int size) throws Exception {
333	>	if (!(s instanceof Serializable))
334	>	return;
335	>	System.out.print("Serialize              : ");
336	>
337	>	for (int i = 0; i < size; i++) {
338	>	s.put(new Integer(i), Boolean.TRUE);
339		}
340	<	timer.finish();
341	<	reallyAssert (sum == size);
340	>
341	>	long startTime = System.currentTimeMillis();
342	>
343	>	FileOutputStream fs = new FileOutputStream("MapCheck.dat");
344	>	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(fs));
345	>	out.writeObject(s);
346	>	out.close();
347	>
348	>	FileInputStream is = new FileInputStream("MapCheck.dat");
349	>	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(is));
350	>	Map m = (Map) in.readObject();
351	>
352	>	long endTime = System.currentTimeMillis();
353	>	long time = endTime - startTime;
354	>
355	>	System.out.print(time + "ms");
356	>
357	>	if (s instanceof IdentityHashMap) return;
358	>	reallyAssert(s.equals(m));
359	>	}
360	>
361	>	static void mainTest(Map s, Object[] key, Object[] absent) {
362	>	int size = key.length;
363	>
364	>	putTest("Add    Absent          ", size, s, key, size);
365	>	reallyAssert(s.size() == size);
366	>	getTest("Access Present         ", size, s, key, size);
367	>	getTest("Search Absent          ", size, s, absent, 0);
368	>	kitTest(s, size);
369	>	vitTest(s, size);
370	>	eitTest(s, size);
371	>	putTest("Modify Present         ", size, s, key, 0);
372	>	reallyAssert(s.size() == size);
373	>	untimedKeyTest("Access Present         ", size, s, key, size);
374	>	keyTest("Search Absent          ", size, s, absent, 0);
375	>	valTest(s, key);
376	>	remTest("Search Absent          ", size, s, absent, 0);
377	>	reallyAssert(s.size() == size);
378	>	remHalfTest("Remove Present         ", size, s, key, size / 2);
379	>	reallyAssert(s.size() == size / 2);
380	>	getTest("Access Present         ", size, s, key, size / 2);
381	>	putTest("Add    Absent          ", size, s, key, size / 2);
382	>	reallyAssert(s.size() == size);
383	>	getTest("Access Present         ", size, s, key, size);
384	>	getTest("Search Absent          ", size, s, absent, 0);
385	>	itRemTest(s, size);
386	>	putTest("Add    Absent          ", size, s, key, size);
387	>	reallyAssert(s.size() == size);
388	>	getTest("Access Present         ", size, s, key, size);
389	>	untimedKeyTest("Access Present         ", size, s, key, size);
390	>	kitTest(s, size);
391	>	vitTest(s, size);
392	>	eitTest(s, size);
393	>	twoMapTest1(s, key, absent);
394	>	twoMapTest2(s, key, absent);
395	>	}
396	>
397	>	static void twoMapTest1(Map s, Object[] key, Object[] absent) {
398	>	int size = s.size();
399	>	Map s2 = newMap();
400	>	putAllTest("Add    Absent          ", size, s, s2);
401	>	getTest("Access Present         ", size, s2, key, size);
402	>	itHalfRemTest(s2, size);
403	>	reallyAssert(s2.size() == size / 2);
404	>	itHalfRemTest(s2, size / 2);
405	>	reallyAssert(s2.size() == size / 4);
406	>	putTest("Add    Absent          ", size, s2, absent, size);
407	>	putTest("Add    Absent          ", size, s2, key, size * 3 / 4);
408	>	reallyAssert(s2.size() == size * 2);
409	>	clrTest(size, s2);
410		}
411	<	static void ittest3(Map s, int size) {
411	>
412	>	static void twoMapTest2(Map s, Object[] key, Object[] absent) {
413	>	int size = key.length;
414	>
415	>	Map s2 = newMap();
416	>	putAllTest("Add    Absent          ", size, s, s2);
417	>	putAllTest("Modify Present         ", size, s, s2);
418	>
419	>	Object lastkey = kitTest(s2, size);
420	>	Object hold = s2.get(lastkey);
421		int sum = 0;
422	<	timer.start("Iter Entry             ", size);
422	>
423	>	timer.start("Traverse entry         ", size * 12); // 12 until finish
424	>
425	>	int sh1 = s.hashCode() - s2.hashCode();
426	>	reallyAssert(sh1 == 0);
427	>
428	>	boolean eq1 = s2.equals(s);
429	>	boolean eq2 = s.equals(s2);
430	>	reallyAssert(eq1 && eq2);
431	>
432	>	Set es2 = s2.entrySet();
433		for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
434	<	if(it.next() != MISSING)
435	<	++sum;
434	>	Object entry = it.next();
435	>	if (es2.contains(entry)) ++sum;
436	>	}
437	>	reallyAssert(sum == size);
438	>
439	>	s2.put(lastkey, MISSING);
440	>
441	>	int sh2 = s.hashCode() - s2.hashCode();
442	>	reallyAssert(sh2 != 0);
443	>
444	>	eq1 = s2.equals(s);
445	>	eq2 = s.equals(s2);
446	>	reallyAssert(!eq1 && !eq2);
447	>
448	>	sum = 0;
449	>	for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
450	>	Map.Entry e = (Map.Entry)it.next();
451	>	e.setValue(absent[sum++]);
452	>	}
453	>	reallyAssert(sum == size);
454	>	for (Iterator it = s2.entrySet().iterator(); it.hasNext(); ) {
455	>	Map.Entry e = (Map.Entry)it.next();
456	>	e.setValue(s.get(e.getKey()));
457	>	}
458	>
459	>	timer.finish();
460	>
461	>	int rmiss = 0;
462	>	timer.start("Remove Present         ", size * 2);
463	>	Iterator s2i = s2.entrySet().iterator();
464	>	Set es = s.entrySet();
465	>	while (s2i.hasNext()) {
466	>	if (!es.remove(s2i.next()))
467	>	++rmiss;
468		}
469	<	timer.finish();
470	<	reallyAssert (sum == size);
469	>	timer.finish();
470	>	reallyAssert(rmiss == 0);
471	>
472	>	clrTest(size, s2);
473	>	reallyAssert(s2.isEmpty() && s.isEmpty());
474		}
475
476	<	static void ittest4(Map s, int size, int pos) {
476	>	static void itTest4(Map s, int size, int pos) {
477		IdentityHashMap seen = new IdentityHashMap(size);
478	<	reallyAssert (s.size() == size);
478	>	reallyAssert(s.size() == size);
479		int sum = 0;
480		timer.start("Iter XEntry            ", size);
481	<	Iterator it = s.entrySet().iterator();
481	>	Iterator it = s.entrySet().iterator();
482		Object k = null;
483		Object v = null;
484		for (int i = 0; i < size-pos; ++i) {
#	Line 255 | Line 489 | public class MapCheck {
489		if (x != MISSING)
490		++sum;
491		}
492	<	reallyAssert (s.containsKey(k));
492	>	reallyAssert(s.containsKey(k));
493		it.remove();
494	<	reallyAssert (!s.containsKey(k));
494	>	reallyAssert(!s.containsKey(k));
495		while (it.hasNext()) {
496		Map.Entry x = (Map.Entry)(it.next());
497		Object k2 = x.getKey();
#	Line 266 | Line 500 | public class MapCheck {
500		++sum;
501		}
502
503	<	reallyAssert (s.size() == size-1);
503	>	reallyAssert(s.size() == size-1);
504		s.put(k, v);
505	<	reallyAssert (seen.size() == size);
506	<	timer.finish();
507	<	reallyAssert (sum == size);
508	<	reallyAssert (s.size() == size);
509	<	}
510	<
511	<
512	<	static void ittest(Map s, int size) {
513	<	ittest1(s, size);
514	<	ittest2(s, size);
515	<	ittest3(s, size);
516	<	//        for (int i = 0; i < size-1; ++i)
517	<	//            ittest4(s, size, i);
518	<	}
519	<
520	<	static void entest1(Hashtable ht, int size) {
521	<	int sum = 0;
522	<
523	<	timer.start("Iter Enumeration Key   ", size);
524	<	for (Enumeration en = ht.keys(); en.hasMoreElements(); ) {
525	<	if (en.nextElement() != MISSING)
526	<	++sum;
527	<	}
528	<	timer.finish();
529	<	reallyAssert (sum == size);
530	<	}
531	<
532	<	static void entest2(Hashtable ht, int size) {
533	<	int sum = 0;
534	<	timer.start("Iter Enumeration Value ", size);
535	<	for (Enumeration en = ht.elements(); en.hasMoreElements(); ) {
536	<	if (en.nextElement() != MISSING)
537	<	++sum;
538	<	}
539	<	timer.finish();
540	<	reallyAssert (sum == size);
541	<	}
542	<
543	<
310	<	static void entest3(Hashtable ht, int size) {
311	<	int sum = 0;
312	<
313	<	timer.start("Iterf Enumeration Key  ", size);
314	<	Enumeration en = ht.keys();
315	<	for (int i = 0; i < size; ++i) {
316	<	if (en.nextElement() != MISSING)
317	<	++sum;
505	>	reallyAssert(seen.size() == size);
506	>	timer.finish();
507	>	reallyAssert(sum == size);
508	>	reallyAssert(s.size() == size);
509	>	}
510	>
511	>	static void initializeKeys(Object[] key, Object[] absent, int size) {
512	>	if (eclass == Object.class) {
513	>	for (int i = 0; i < size; ++i) key[i] = new Object();
514	>	for (int i = 0; i < size; ++i) absent[i] = new Object();
515	>	}
516	>	else if (eclass == Integer.class) {
517	>	initInts(key, absent, size);
518	>	}
519	>	else if (eclass == Float.class) {
520	>	initFloats(key, absent, size);
521	>	}
522	>	else if (eclass == Double.class) {
523	>	initDoubles(key, absent, size);
524	>	}
525	>	else if (eclass == String.class) {
526	>	initWords(size, key, absent);
527	>	}
528	>	else
529	>	throw new Error("unknown type");
530	>	}
531	>
532	>	static void initInts(Object[] key, Object[] absent, int size) {
533	>	for (int i = 0; i < size; ++i)
534	>	key[i] = Integer.valueOf(i);
535	>	Map m = newMap();
536	>	int k = 0;
537	>	while (k < size) {
538	>	int r = srng.next();
539	>	if (r < 0 || r >= size) {
540	>	Integer ir = Integer.valueOf(r);
541	>	if (m.put(ir, ir) == null)
542	>	absent[k++] = ir;
543	>	}
544		}
319	–	timer.finish();
320	–	reallyAssert (sum == size);
545		}
546
547	<	static void entest4(Hashtable ht, int size) {
548	<	int sum = 0;
325	<	timer.start("Iterf Enumeration Value", size);
326	<	Enumeration en = ht.elements();
547	>	static void initFloats(Object[] key, Object[] absent, int size) {
548	>	Map m = newMap();
549		for (int i = 0; i < size; ++i) {
550	<	if (en.nextElement() != MISSING)
551	<	++sum;
550	>	float r = Float.valueOf(i);
551	>	key[i] = r;
552	>	m.put(r, r);
553		}
554	<	timer.finish();
555	<	reallyAssert (sum == size);
556	<	}
557	<
558	<	static void entest(Map s, int size) {
559	<	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);
554	>	int k = 0;
555	>	while (k < size) {
556	>	float r = rng.nextFloat();
557	>	Float ir = Float.valueOf(r);
558	>	if (m.put(ir, ir) == null)
559	>	absent[k++] = ir;
560		}
561		}
562
563	<	static void rtest(Map s, int size) {
564	<	timer.start("Remove (iterator)      ", size);
565	<	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
566	<	it.next();
567	<	it.remove();
563	>	static void initDoubles(Object[] key, Object[] absent, int size) {
564	>	Map m = newMap();
565	>	for (int i = 0; i < size; ++i) {
566	>	double r = Double.valueOf(i);
567	>	key[i] = r;
568	>	m.put(r, r);
569		}
570	<	timer.finish();
571	<	}
572	<
573	<	static void rvtest(Map s, int size) {
574	<	timer.start("Remove (iterator)      ", size);
575	<	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
361	<	it.next();
362	<	it.remove();
570	>	int k = 0;
571	>	while (k < size) {
572	>	double r = rng.nextDouble();
573	>	Double ir = Double.valueOf(r);
574	>	if (m.put(ir, ir) == null)
575	>	absent[k++] = ir;
576		}
364	–	timer.finish();
577		}
578
579	+	// Use as many real words as possible, then use fake random words
580
581	<	static void dtest(Map s, int size, Object[] key) {
582	<	timer.start("Put (putAll)           ", size * 2);
583	<	Map s2 = null;
581	>	static void initWords(int size, Object[] key, Object[] abs) {
582	>	String fileName = "testwords.txt";
583	>	int ki = 0;
584	>	int ai = 0;
585		try {
586	<	s2 = (Map) (s.getClass().newInstance());
587	<	s2.putAll(s);
586	>	FileInputStream fr = new FileInputStream(fileName);
587	>	BufferedInputStream in = new BufferedInputStream(fr);
588	>	while (ki < size || ai < size) {
589	>	StringBuffer sb = new StringBuffer();
590	>	for (;;) {
591	>	int c = in.read();
592	>	if (c < 0) {
593	>	if (ki < size)
594	>	randomWords(key, ki, size);
595	>	if (ai < size)
596	>	randomWords(abs, ai, size);
597	>	in.close();
598	>	return;
599	>	}
600	>	if (c == '\n') {
601	>	String s = sb.toString();
602	>	if (ki < size)
603	>	key[ki++] = s;
604	>	else
605	>	abs[ai++] = s;
606	>	break;
607	>	}
608	>	sb.append((char) c);
609	>	}
610	>	}
611	>	in.close();
612		}
613	<	catch (Exception e) { e.printStackTrace(); return; }
614	<	timer.finish();
615	<
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;
613	>	catch (IOException ex) {
614	>	System.out.println("Can't read words file:" + ex);
615	>	throw new Error(ex);
616		}
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());
617		}
618
619	<	static void stest(Map s, int size) throws Exception {
620	<	if (!(s instanceof Serializable))
621	<	return;
622	<	System.out.print("Serialize              : ");
623	<
624	<	for (int i = 0; i < size; i++) {
625	<	s.put(new Integer(i), Boolean.TRUE);
619	>	static void randomWords(Object[] ws, int origin, int size) {
620	>	for (int i = origin; i < size; ++i) {
621	>	int k = 0;
622	>	int len = 2 + (srng.next() & 0xf);
623	>	char[] c = new char[len * 4 + 1];
624	>	for (int j = 1; j < len; ++j) {
625	>	int r = srng.next();
626	>	c[k++] = (char) (' ' + (r & 0x7f));
627	>	r >>>= 8;
628	>	c[k++] = (char) (' ' + (r & 0x7f));
629	>	r >>>= 8;
630	>	c[k++] = (char) (' ' + (r & 0x7f));
631	>	r >>>= 8;
632	>	c[k++] = (char) (' ' + (r & 0x7f));
633	>	}
634	>	c[k++] = (char) ((i & 31) | 1); // never == to any testword
635	>	ws[i] = new String(c);
636		}
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();
453	–
454	–	long endTime = System.currentTimeMillis();
455	–	long time = endTime - startTime;
456	–
457	–	System.out.print(time + "ms");
458	–
459	–	if (s instanceof IdentityHashMap) return;
460	–	reallyAssert (s.equals(m));
637		}
638
639	<
464	<	static void test(Map s, Object[] key) {
465	<	int size = key.length;
466	<
467	<	t3("Put (absent)           ", size, s, key, size);
468	<	t3("Put (present)          ", size, s, key, 0);
469	<	t7("ContainsKey            ", size, s, key, absent);
470	<	t4("ContainsKey            ", size, s, key, size);
471	<	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);
489	<	}
490	<
491	<	static class TestTimer {
639	>	static final class TestTimer {
640		private String name;
641		private long numOps;
642		private long startTime;
495	–	private String cname;
643
644		static final java.util.TreeMap accum = new java.util.TreeMap();
645	<
645	>
646		static void printStats() {
647		for (Iterator it = accum.entrySet().iterator(); it.hasNext(); ) {
648	<	Map.Entry e = (Map.Entry)(it.next());
649	<	Stats stats = ((Stats)(e.getValue()));
650	<	int n = stats.number;
651	<	double t;
652	<	if (n > 0)
653	<	t = stats.sum / n;
648	>	Map.Entry e = (Map.Entry) it.next();
649	>	Stats stats = (Stats) e.getValue();
650	>	System.out.print(e.getKey() + ": ");
651	>	long s;
652	>	long n = stats.number;
653	>	if (n == 0) {
654	>	n = stats.firstn;
655	>	s = stats.first;
656	>	}
657		else
658	<	t = stats.least;
659	<	long nano = Math.round(1000000.0 * t);
660	<	System.out.println(e.getKey() + ": " + nano);
658	>	s = stats.sum;
659	>
660	>	double t = ((double) s) / n;
661	>	long nano = Math.round(t);
662	>	System.out.printf("%6d", + nano);
663	>	System.out.println();
664		}
665		}
666	<
666	>
667		void start(String name, long numOps) {
668		this.name = name;
516	–	this.cname = classify();
669		this.numOps = numOps;
670	<	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;
670	>	startTime = System.nanoTime();
671		}
672
673		void finish() {
674	<	long endTime = System.currentTimeMillis();
537	<	long time = endTime - startTime;
538	<	double timePerOp = ((double)time)/numOps;
539	<
674	>	long elapsed = System.nanoTime() - startTime;
675		Object st = accum.get(name);
676		if (st == null)
677	<	accum.put(name, new Stats(timePerOp));
678	<	else {
679	<	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	<
677	>	accum.put(name, new Stats(elapsed, numOps));
678	>	else
679	>	((Stats) st).addTime(elapsed, numOps);
680		}
681
682		}
683
684	<	static class Stats {
685	<	double sum = 0;
686	<	double least;
687	<	int number = 0;
688	<	Stats(double t) { least = t; }
684	>	static final class Stats {
685	>	long sum;
686	>	long number;
687	>	long first;
688	>	long firstn;
689	>	Stats(long t, long n) {
690	>	first = t;
691	>	firstn = n;
692	>	}
693	>	void addTime(long t, long n) {
694	>	sum += t;
695	>	number += n;
696	>	}
697		}
698
573	–	static Random rng = new Random();
574	–
699		static void shuffle(Object[] keys) {
700		int size = keys.length;
701	<	for (int i=size; i>1; i--) {
701	>	for (int i = size; i > 1; i--) {
702		int r = rng.nextInt(i);
703		Object t = keys[i-1];
704		keys[i-1] = keys[r];
#	Line 582 | Line 706 | public class MapCheck {
706		}
707		}
708
709	<	}
709	>	static void shuffle(ArrayList keys) {
710	>	int size = keys.size();
711	>	for (int i = size; i > 1; i--) {
712	>	int r = rng.nextInt(i);
713	>	Object t = keys.get(i-1);
714	>	keys.set(i-1, keys.get(r));
715	>	keys.set(r, t);
716	>	}
717	>	}
718
719	+	}

Diff Legend

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