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.3 by dl, Thu Sep 15 16:55:40 2005 UTC vs.
Revision 1.4 by dl, Wed Jul 1 12:11:44 2009 UTC

#	Line 6 | Line 6
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 dictonary (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;
30	<	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) {
44		throw new RuntimeException("Class " + args[0] + " not found.");
45		}
46	<	}
39	<
46	>	}
47
48	<	if (args.length > 1)
49	<	numTests = Integer.parseInt(args[1]);
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	>	}
57	>	if (eclass == null)
58	>	eclass = Object.class;
59
60		if (args.length > 2)
61	<	size = Integer.parseInt(args[2]);
61	>	numTests = Integer.parseInt(args[2]);
62	>
63	>	if (args.length > 3)
64	>	size = Integer.parseInt(args[3]);
65
66	<	boolean doSerializeTest = args.length > 3;
66	>	boolean doSerializeTest = args.length > 4;
67
68	<	System.out.println("Testing " + mapClass.getName() + " trials: " + numTests + " size: " + size);
68	>	while ((size & 3) != 0) ++size;
69
70	<	for (int i = 0; i < absentSize; ++i) absent[i] = new Object();
70	>	System.out.print("Class: " + mapClass.getName());
71	>	System.out.print(" elements: " + eclass.getName());
72	>	System.out.print(" trials: " + numTests);
73	>	System.out.print(" size: " + size);
74	>	System.out.println();
75
76		Object[] key = new Object[size];
77	<	for (int i = 0; i < size; ++i) key[i] = new Object();
77	>	Object[] absent = new Object[size];
78	>	initializeKeys(key, absent, size);
79
80	<	forceMem(size * 8);
80	>	precheck(size,  key, absent);
81
82		for (int rep = 0; rep < numTests; ++rep) {
83	<	runTest(newMap(mapClass), key);
83	>	mainTest(newMap(), key, absent);
84	>	if ((rep & 3) == 3 && rep < numTests - 1) {
85	>	shuffle(key);
86	>	//                Thread.sleep(10);
87	>	}
88		}
89
90		TestTimer.printStats();
91
92	+	checkNullKey();
93
94		if (doSerializeTest)
95	<	stest(newMap(mapClass), size);
95	>	serTest(newMap(), size);
96		}
97
98	<	static Map newMap(Class cl) {
98	>	static Map newMap() {
99		try {
100	<	Map m = (Map)cl.newInstance();
72	<	return m;
100	>	return (Map)mapClass.newInstance();
101		} catch(Exception e) {
102	<	throw new RuntimeException("Can't instantiate " + cl + ": " + e);
102	>	throw new RuntimeException("Can't instantiate " + mapClass + ": " + e);
103		}
104		}
105
106	+	static void precheck(int n, Object[] key, Object[] abs) {
107	+	int ck = 0;
108	+	Map s = newMap();
109	+	for (int i = 0; i < n; i++) {
110	+	Object k = key[i];
111	+	if (k == null) throw new Error("Null key at" + i);
112	+	ck += System.identityHashCode(k);
113	+	Object v = s.put(k, k);
114	+	if (v != null)
115	+	throw new Error("Duplicate " +  k + " / " + v);
116	+	}
117	+	for (int i = 0; i < n; i++) {
118	+	Object k = abs[i];
119	+	if (k == null) throw new Error("Null key at" + i);
120	+	ck += System.identityHashCode(k);
121	+	Object v = s.put(k, k);
122	+	if (v != null)
123	+	throw new Error("Duplicate " +  k + " / " + v);
124	+	}
125	+	checkSum += ck;
126	+	}
127
128	<	static void runTest(Map s, Object[] key) {
129	<	shuffle(key);
130	<	int size = key.length;
131	<	long startTime = System.currentTimeMillis();
132	<	test(s, key);
133	<	long time = System.currentTimeMillis() - startTime;
128	>	static void checkNullKey() {
129	>	Map m = newMap();
130	>	Object x = new Object();
131	>	Object v;
132	>	try {
133	>	m.put(null, x);
134	>	v = m.get(null);
135	>	} catch(NullPointerException npe) {
136	>	System.out.println("Map does not allow null keys");
137	>	return;
138	>	}
139	>	if (v != x) throw new Error();
140	>	if (m.remove(null) != v) throw new Error();
141	>	if (m.get(null) != null) throw new Error();
142		}
143
144	<	static void forceMem(int n) {
145	<	// force enough memory
89	<	Long[] junk = new Long[n];
90	<	for (int i = 0; i < junk.length; ++i) junk[i] = new Long(i);
144	>
145	>	static void getTest(String nm, int n, Map s, Object[] key, int expect) {
146		int sum = 0;
147	<	for (int i = 0; i < junk.length; ++i)
148	<	sum += (int)(junk[i].longValue() + i);
149	<	if (sum == 0) System.out.println("Useless number = " + sum);
150	<	junk = null;
151	<	//        System.gc();
147	>	timer.start(nm, n);
148	>	for (int i = 0; i < n; i++) {
149	>	Object v = s.get(key[i]);
150	>	if (v != null && v.getClass() == eclass)
151	>	++sum;
152	>	}
153	>	timer.finish();
154	>	reallyAssert (sum == expect);
155	>	checkSum += sum;
156		}
157
158
159	<	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 ((Integer)(intMap.get(i)) != i) ++sum;
166		}
167		timer.finish();
168	<	reallyAssert (sum == expect * iters);
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++) {
#	Line 118 | Line 176 | public class MapCheck {
176		}
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);
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++) {
#	Line 138 | Line 208 | public class MapCheck {
208		}
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) {
#	Line 148 | Line 229 | public class MapCheck {
229		}
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++) {
157	<	if (s.get(k1[i]) != null) ++sum;
158	<	if (s.get(k2[i & absentMask]) != null) ++sum;
159	<	}
238	>	timer.start("Traverse access key/val", size);
239	>	if (s.containsValue(MISSING)) ++sum;
240		timer.finish();
241	<	reallyAssert (sum == n);
241	>	reallyAssert (sum == 0);
242	>	checkSum += sum;
243		}
244
245	<	static void t7(String nm, int n, Map s, Object[] k1, Object[] k2) {
245	>
246	>	static Object kitTest(Map s, int size) {
247	>	Object last = null;
248		int sum = 0;
249	<	timer.start(nm, n * 2);
250	<	for (int i = 0; i < n; i++) {
251	<	if (s.containsKey(k1[i])) ++sum;
252	<	if (s.containsKey(k2[i & absentMask])) ++sum;
249	>	timer.start("Traverse access key/val", size);
250	>	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
251	>	Object x = it.next();
252	>	if (x != last && x != null && x.getClass() == eclass)
253	>	++sum;
254	>	last = x;
255		}
256		timer.finish();
257	<	reallyAssert (sum == n);
257	>	reallyAssert (sum == size);
258	>	checkSum += sum;
259	>	return last;
260		}
261
262	<	static void t8(String nm, int n, Map s, Object[] key, int expect) {
262	>	static Object vitTest(Map s, int size) {
263	>	Object last = null;
264		int sum = 0;
265	<	timer.start(nm, n);
266	<	for (int i = 0; i < n; i++) {
267	<	if (s.get(key[i]) != null) ++sum;
265	>	timer.start("Traverse access key/val", size);
266	>	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
267	>	Object x = it.next();
268	>	if (x != last && x != null && x.getClass() == eclass)
269	>	++sum;
270	>	last = x;
271		}
272		timer.finish();
273	<	reallyAssert (sum == expect);
273	>	reallyAssert (sum == size);
274	>	checkSum += sum;
275	>	return last;
276		}
277
278	<
186	<	static void t9(Map s) {
278	>	static void eitTest(Map s, int size) {
279		int sum = 0;
280	<	int iters = 20;
281	<	timer.start("ContainsValue (/n)     ", iters * s.size());
282	<	int step = absentSize / iters;
283	<	for (int i = 0; i < absentSize; i += step)
284	<	if (s.containsValue(absent[i])) ++sum;
280	>	timer.start("Traverse access entry  ", size);
281	>	for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
282	>	Map.Entry e = (Map.Entry)it.next();
283	>	Object k = e.getKey();
284	>	Object v = e.getValue();
285	>	if (k != null && k.getClass() == eclass &&
286	>	v != null && v.getClass() == eclass)
287	>	++sum;
288	>	}
289		timer.finish();
290	<	reallyAssert (sum != 0);
290	>	reallyAssert (sum == size);
291	>	checkSum += sum;
292		}
293
294	<
295	<	static void ktest(Map s, int size, Object[] key) {
296	<	timer.start("ContainsKey            ", size);
297	<	Set ks = s.keySet();
294	>	static void itRemTest(Map s, int size) {
295	>	int sz = s.size();
296	>	reallyAssert (sz == size);
297	>	timer.start("Remove Present         ", size);
298		int sum = 0;
299	<	for (int i = 0; i < size; i++) {
300	<	if (ks.contains(key[i])) ++sum;
299	>	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
300	>	it.next();
301	>	it.remove();
302	>	++sum;
303		}
304		timer.finish();
305	<	reallyAssert (sum == size);
305	>	reallyAssert (sum == sz);
306	>	checkSum += sum;
307		}
308
309	<
310	<	static void ittest1(Map s, int size) {
309	>	static void itHalfRemTest(Map s, int size) {
310	>	int sz = s.size();
311	>	reallyAssert (sz == size);
312	>	timer.start("Remove Present         ", size);
313		int sum = 0;
212	–	timer.start("Iter Key               ", size);
314		for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
315	<	if(it.next() != MISSING)
316	<	++sum;
315	>	it.next();
316	>	it.remove();
317	>	if (it.hasNext())
318	>	it.next();
319	>	++sum;
320		}
321		timer.finish();
322	<	reallyAssert (sum == size);
322	>	reallyAssert (sum == sz / 2);
323	>	checkSum += sum;
324		}
325
326	<	static void ittest2(Map s, int size) {
327	<	int sum = 0;
328	<	timer.start("Iter Value             ", size);
224	<	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
225	<	if(it.next() != MISSING)
226	<	++sum;
227	<	}
326	>	static void putAllTest(String nm, int n, Map src, Map dst) {
327	>	timer.start(nm, n);
328	>	dst.putAll(src);
329		timer.finish();
330	<	reallyAssert (sum == size);
330	>	reallyAssert (src.size() == dst.size());
331	>	}
332	>
333	>	static void serTest(Map s, int size) throws Exception {
334	>	if (!(s instanceof Serializable))
335	>	return;
336	>	System.out.print("Serialize              : ");
337	>
338	>	for (int i = 0; i < size; i++) {
339	>	s.put(new Integer(i), Boolean.TRUE);
340	>	}
341	>
342	>	long startTime = System.currentTimeMillis();
343	>
344	>	FileOutputStream fs = new FileOutputStream("MapCheck.dat");
345	>	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(fs));
346	>	out.writeObject(s);
347	>	out.close();
348	>
349	>	FileInputStream is = new FileInputStream("MapCheck.dat");
350	>	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(is));
351	>	Map m = (Map)in.readObject();
352	>
353	>	long endTime = System.currentTimeMillis();
354	>	long time = endTime - startTime;
355	>
356	>	System.out.print(time + "ms");
357	>
358	>	if (s instanceof IdentityHashMap) return;
359	>	reallyAssert (s.equals(m));
360		}
361	<	static void ittest3(Map s, int size) {
361	>
362	>	static void mainTest(Map s, Object[] key, Object[] absent) {
363	>	int size = key.length;
364	>
365	>	putTest("Add    Absent          ", size, s, key, size);
366	>	reallyAssert(s.size() == size);
367	>	getTest("Access Present         ", size, s, key, size);
368	>	getTest("Search Absent          ", size, s, absent, 0);
369	>	kitTest(s, size);
370	>	vitTest(s, size);
371	>	eitTest(s, size);
372	>	putTest("Modify Present         ", size, s, key, 0);
373	>	reallyAssert(s.size() == size);
374	>	untimedKeyTest("Access Present         ", size, s, key, size);
375	>	keyTest("Search Absent          ", size, s, absent, 0);
376	>	valTest(s, key);
377	>	remTest("Search Absent          ", size, s, absent, 0);
378	>	reallyAssert(s.size() == size);
379	>	remHalfTest("Remove Present         ", size, s, key, size / 2);
380	>	reallyAssert(s.size() == size / 2);
381	>	getTest("Access Present         ", size, s, key, size / 2);
382	>	putTest("Add    Absent          ", size, s, key, size / 2);
383	>	reallyAssert(s.size() == size);
384	>	getTest("Access Present         ", size, s, key, size);
385	>	getTest("Search Absent          ", size, s, absent, 0);
386	>	itRemTest(s, size);
387	>	putTest("Add    Absent          ", size, s, key, size);
388	>	reallyAssert(s.size() == size);
389	>	getTest("Access Present         ", size, s, key, size);
390	>	untimedKeyTest("Access Present         ", size, s, key, size);
391	>	kitTest(s, size);
392	>	vitTest(s, size);
393	>	eitTest(s, size);
394	>	twoMapTest1(s, key, absent);
395	>	twoMapTest2(s, key, absent);
396	>	}
397	>
398	>	static void twoMapTest1(Map s, Object[] key, Object[] absent) {
399	>	int size = s.size();
400	>	Map s2 = newMap();
401	>	putAllTest("Add    Absent          ", size, s, s2);
402	>	getTest("Access Present         ", size, s2, key, size);
403	>	itHalfRemTest(s2, size);
404	>	reallyAssert(s2.size() == size / 2);
405	>	itHalfRemTest(s2, size / 2);
406	>	reallyAssert(s2.size() == size / 4);
407	>	putTest("Add    Absent          ", size, s2, absent, size);
408	>	putTest("Add    Absent          ", size, s2, key, size * 3 / 4);
409	>	reallyAssert(s2.size() == size * 2);
410	>	clrTest(size, s2);
411	>	}
412	>
413	>	static void twoMapTest2(Map s, Object[] key, Object[] absent) {
414	>	int size = key.length;
415	>
416	>	Map s2 = newMap();
417	>	putAllTest("Add    Absent          ", size, s, s2);
418	>	putAllTest("Modify Present         ", size, s, s2);
419	>
420	>	Object lastkey = kitTest(s2, size);
421	>	Object hold = s2.get(lastkey);
422		int sum = 0;
423	<	int hsum = 0;
424	<	timer.start("Iter Entry             ", size);
423	>
424	>	timer.start("Traverse access entry  ", size * 12); // 12 until finish
425	>
426	>	int sh1 = s.hashCode() - s2.hashCode();
427	>	reallyAssert (sh1 == 0);
428	>
429	>	boolean eq1 = s2.equals(s);
430	>	boolean eq2 = s.equals(s2);
431	>	reallyAssert (eq1 && eq2);
432	>
433	>	Set es2 = s2.entrySet();
434	>	for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
435	>	Object entry = it.next();
436	>	if (es2.contains(entry)) ++sum;
437	>	}
438	>	reallyAssert (sum == size);
439	>
440	>	s2.put(lastkey, MISSING);
441	>
442	>	int sh2 = s.hashCode() - s2.hashCode();
443	>	reallyAssert (sh2 != 0);
444	>
445	>	eq1 = s2.equals(s);
446	>	eq2 = s.equals(s2);
447	>	reallyAssert (!eq1 && !eq2);
448	>
449	>	sum = 0;
450		for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) {
451		Map.Entry e = (Map.Entry)it.next();
452	<	if(e != MISSING) {
238	<	hsum += System.identityHashCode(e.getKey());
239	<	hsum += System.identityHashCode(e.getValue());
240	<	hsum >>>= 1;
241	<	++sum;
242	<	}
452	>	e.setValue(absent[sum++]);
453		}
244	–	timer.finish();
245	–	reallyAssert(size == 0 || hsum >= 0);
454		reallyAssert (sum == size);
455	+	for (Iterator it = s2.entrySet().iterator(); it.hasNext(); ) {
456	+	Map.Entry e = (Map.Entry)it.next();
457	+	e.setValue(s.get(e.getKey()));
458	+	}
459	+
460	+	timer.finish();
461	+
462	+	int rmiss = 0;
463	+	timer.start("Remove Present         ", size * 2);
464	+	Iterator s2i = s2.entrySet().iterator();
465	+	Set es = s.entrySet();
466	+	while (s2i.hasNext()) {
467	+	if (!es.remove(s2i.next()))
468	+	++rmiss;
469	+	}
470	+	timer.finish();
471	+	reallyAssert(rmiss == 0);
472	+
473	+	clrTest(size, s2);
474	+	reallyAssert (s2.isEmpty() && s.isEmpty());
475		}
476
477	<	static void ittest4(Map s, int size, int pos) {
477	>	static void itTest4(Map s, int size, int pos) {
478		IdentityHashMap seen = new IdentityHashMap(size);
479		reallyAssert (s.size() == size);
480		int sum = 0;
#	Line 282 | Line 510 | public class MapCheck {
510		}
511
512
285	–	static void ittest(Map s, int size) {
286	–	ittest1(s, size);
287	–	ittest2(s, size);
288	–	ittest3(s, size);
289	–	//        for (int i = 0; i < size-1; ++i)
290	–	//            ittest4(s, size, i);
291	–	}
292	–
293	–	static void entest1(Hashtable ht, int size) {
294	–	int sum = 0;
295	–
296	–	timer.start("Iter Enumeration Key   ", size);
297	–	for (Enumeration en = ht.keys(); en.hasMoreElements(); ) {
298	–	if (en.nextElement() != MISSING)
299	–	++sum;
300	–	}
301	–	timer.finish();
302	–	reallyAssert (sum == size);
303	–	}
513
514	<	static void entest2(Hashtable ht, int size) {
515	<	int sum = 0;
516	<	timer.start("Iter Enumeration Value ", size);
517	<	for (Enumeration en = ht.elements(); en.hasMoreElements(); ) {
518	<	if (en.nextElement() != MISSING)
519	<	++sum;
520	<	}
521	<	timer.finish();
522	<	reallyAssert (sum == size);
523	<	}
524	<
525	<
526	<	static void entest3(Hashtable ht, int size) {
527	<	int sum = 0;
528	<
529	<	timer.start("Iterf Enumeration Key  ", size);
530	<	Enumeration en = ht.keys();
531	<	for (int i = 0; i < size; ++i) {
532	<	if (en.nextElement() != MISSING)
533	<	++sum;
514	>	static void initializeKeys(Object[] key, Object[] absent, int size) {
515	>	if (eclass == Object.class) {
516	>	for (int i = 0; i < size; ++i) key[i] = new Object();
517	>	for (int i = 0; i < size; ++i) absent[i] = new Object();
518	>	}
519	>	else if (eclass == Integer.class) {
520	>	initInts(key, absent, size);
521	>	}
522	>	else if (eclass == Float.class) {
523	>	initFloats(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		}
326	–	timer.finish();
327	–	reallyAssert (sum == size);
545		}
546
547	<	static void entest4(Hashtable ht, int size) {
548	<	int sum = 0;
332	<	timer.start("Iterf Enumeration Value", size);
333	<	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) {
344	<	Hashtable ht = (Hashtable)s;
345	<	//            entest3(ht, size);
346	<	//            entest4(ht, size);
347	<	entest1(ht, size);
348	<	entest2(ht, size);
349	<	entest1(ht, size);
350	<	entest2(ht, size);
351	<	entest1(ht, size);
352	<	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) {
357	<	timer.start("Remove (iterator)      ", size);
358	<	for (Iterator it = s.keySet().iterator(); it.hasNext(); ) {
359	<	it.next();
360	<	it.remove();
361	<	}
362	<	timer.finish();
363	<	}
563	>	// Use as many real words as possible, then use fake random words
564
565	<	static void rvtest(Map s, int size) {
566	<	timer.start("Remove (iterator)      ", size);
567	<	for (Iterator it = s.values().iterator(); it.hasNext(); ) {
568	<	it.next();
369	<	it.remove();
370	<	}
371	<	timer.finish();
372	<	}
373	<
374	<
375	<	static void dtest(Map s, int size, Object[] key) {
376	<	timer.start("Put (putAll)           ", size * 2);
377	<	Map s2 = null;
565	>	static void initWords(int size, Object[] key, Object[] abs) {
566	>	String fileName = "testwords.txt";
567	>	int ki = 0;
568	>	int ai = 0;
569		try {
570	<	s2 = (Map) (s.getClass().newInstance());
571	<	s2.putAll(s);
570	>	FileInputStream fr = new FileInputStream(fileName);
571	>	BufferedInputStream in = new BufferedInputStream(fr);
572	>	while (ki < size || ai < size) {
573	>	StringBuffer sb = new StringBuffer();
574	>	for (;;) {
575	>	int c = in.read();
576	>	if (c < 0) {
577	>	if (ki < size)
578	>	randomWords(key, ki, size);
579	>	if (ai < size)
580	>	randomWords(abs, ai, size);
581	>	in.close();
582	>	return;
583	>	}
584	>	if (c == '\n') {
585	>	String s = sb.toString();
586	>	if (ki < size)
587	>	key[ki++] = s;
588	>	else
589	>	abs[ai++] = s;
590	>	break;
591	>	}
592	>	sb.append((char)c);
593	>	}
594	>	}
595	>	in.close();
596		}
597	<	catch (Exception e) { e.printStackTrace(); return; }
598	<	timer.finish();
599	<
385	<	timer.start("Iter Equals            ", size * 2);
386	<	boolean eqt = s2.equals(s) && s.equals(s2);
387	<	reallyAssert (eqt);
388	<	timer.finish();
389	<
390	<	timer.start("Iter HashCode          ", size * 2);
391	<	int shc = s.hashCode();
392	<	int s2hc = s2.hashCode();
393	<	reallyAssert (shc == s2hc);
394	<	timer.finish();
395	<
396	<	timer.start("Put (present)          ", size);
397	<	s2.putAll(s);
398	<	timer.finish();
399	<
400	<	timer.start("Iter EntrySet contains ", size * 2);
401	<	Set es2 = s2.entrySet();
402	<	int sum = 0;
403	<	for (Iterator i1 = s.entrySet().iterator(); i1.hasNext(); ) {
404	<	Object entry = i1.next();
405	<	if (es2.contains(entry)) ++sum;
597	>	catch (IOException ex) {
598	>	System.out.println("Can't read words file:" + ex);
599	>	throw new Error(ex);
600		}
407	–	timer.finish();
408	–	reallyAssert (sum == size);
409	–
410	–	t6("Get                    ", size, s2, key, absent);
411	–
412	–	Object hold = s2.get(key[size-1]);
413	–	s2.put(key[size-1], absent[0]);
414	–	timer.start("Iter Equals            ", size * 2);
415	–	eqt = s2.equals(s) && s.equals(s2);
416	–	reallyAssert (!eqt);
417	–	timer.finish();
418	–
419	–	timer.start("Iter HashCode          ", size * 2);
420	–	int s1h = s.hashCode();
421	–	int s2h = s2.hashCode();
422	–	reallyAssert (s1h != s2h);
423	–	timer.finish();
424	–
425	–	s2.put(key[size-1], hold);
426	–	timer.start("Remove (iterator)      ", size * 2);
427	–	Iterator s2i = s2.entrySet().iterator();
428	–	Set es = s.entrySet();
429	–	while (s2i.hasNext())
430	–	es.remove(s2i.next());
431	–	timer.finish();
432	–
433	–	reallyAssert (s.isEmpty());
434	–
435	–	timer.start("Clear                  ", size);
436	–	s2.clear();
437	–	timer.finish();
438	–	reallyAssert (s2.isEmpty() && s.isEmpty());
601		}
602
441	–	static void stest(Map s, int size) throws Exception {
442	–	if (!(s instanceof Serializable))
443	–	return;
444	–	System.out.print("Serialize              : ");
445	–
446	–	for (int i = 0; i < size; i++) {
447	–	s.put(new Integer(i), Boolean.TRUE);
448	–	}
449	–
450	–	long startTime = System.currentTimeMillis();
451	–
452	–	FileOutputStream fs = new FileOutputStream("MapCheck.dat");
453	–	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(fs));
454	–	out.writeObject(s);
455	–	out.close();
456	–
457	–	FileInputStream is = new FileInputStream("MapCheck.dat");
458	–	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(is));
459	–	Map m = (Map)in.readObject();
603
604	<	long endTime = System.currentTimeMillis();
605	<	long time = endTime - startTime;
606	<
607	<	System.out.print(time + "ms");
608	<
609	<	if (s instanceof IdentityHashMap) return;
610	<	reallyAssert (s.equals(m));
611	<	}
612	<
613	<
614	<	static void test(Map s, Object[] key) {
615	<	int size = key.length;
616	<
617	<	t3("Put (absent)           ", size, s, key, size);
618	<	t3("Put (present)          ", size, s, key, 0);
619	<	t7("ContainsKey            ", size, s, key, absent);
620	<	t4("ContainsKey            ", size, s, key, size);
621	<	ktest(s, size, key);
479	<	t4("ContainsKey            ", absentSize, s, absent, 0);
480	<	t6("Get                    ", size, s, key, absent);
481	<	t1("Get (present)          ", size, s, key, size);
482	<	t1("Get (absent)           ", absentSize, s, absent, 0);
483	<	t2("Remove (absent)        ", absentSize, s, absent, 0);
484	<	t5("Remove (present)       ", size, s, key, size / 2);
485	<	t3("Put (half present)     ", size, s, key, size / 2);
486	<
487	<	ittest(s, size);
488	<	entest(s, size);
489	<	t9(s);
490	<	rtest(s, size);
491	<
492	<	t4("ContainsKey            ", size, s, key, 0);
493	<	t2("Remove (absent)        ", size, s, key, 0);
494	<	t3("Put (presized)         ", size, s, key, size);
495	<	dtest(s, size, key);
604	>	static void randomWords(Object[] ws, int origin, int size) {
605	>	for (int i = origin; i < size; ++i) {
606	>	int k = 0;
607	>	int len = 2 + (srng.next() & 0xf);
608	>	char[] c = new char[len * 4 + 1];
609	>	for (int j = 1; j < len; ++j) {
610	>	int r = srng.next();
611	>	c[k++] = (char)(' ' + (r & 0x7f));
612	>	r >>>= 8;
613	>	c[k++] = (char)(' ' + (r & 0x7f));
614	>	r >>>= 8;
615	>	c[k++] = (char)(' ' + (r & 0x7f));
616	>	r >>>= 8;
617	>	c[k++] = (char)(' ' + (r & 0x7f));
618	>	}
619	>	c[k++] = (char)((i & 31) | 1); // never == to any testword
620	>	ws[i] = new String(c);
621	>	}
622		}
623
624	<	static class TestTimer {
624	>	static final class TestTimer {
625		private String name;
626		private long numOps;
627		private long startTime;
502	–	private String cname;
628
629		static final java.util.TreeMap accum = new java.util.TreeMap();
630
#	Line 507 | Line 632 | public class MapCheck {
632		for (Iterator it = accum.entrySet().iterator(); it.hasNext(); ) {
633		Map.Entry e = (Map.Entry)(it.next());
634		Stats stats = ((Stats)(e.getValue()));
635	<	int n = stats.number;
636	<	double t;
637	<	if (n > 0)
638	<	t = stats.sum / n;
639	<	else
640	<	t = stats.least;
641	<	long nano = Math.round(1000000.0 * t);
642	<	System.out.println(e.getKey() + ": " + nano);
635	>	System.out.print(e.getKey() + ": ");
636	>	long s;
637	>	long n = stats.number;
638	>	if (n == 0) {
639	>	n = stats.firstn;
640	>	s = stats.first;
641	>	}
642	>	else
643	>	s = stats.sum;
644	>
645	>	double t = ((double)s) / n;
646	>	long nano = Math.round(t);
647	>	System.out.printf("%6d", + nano);
648	>	System.out.println();
649		}
650		}
651
652		void start(String name, long numOps) {
653		this.name = name;
523	–	this.cname = classify();
654		this.numOps = numOps;
655	<	startTime = System.currentTimeMillis();
526	<	}
527	<
528	<
529	<	String classify() {
530	<	if (name.startsWith("Get"))
531	<	return "Get                    ";
532	<	else if (name.startsWith("Put"))
533	<	return "Put                    ";
534	<	else if (name.startsWith("Remove"))
535	<	return "Remove                 ";
536	<	else if (name.startsWith("Iter"))
537	<	return "Iter                   ";
538	<	else
539	<	return null;
655	>	startTime = System.nanoTime();
656		}
657
658		void finish() {
659	<	long endTime = System.currentTimeMillis();
544	<	long time = endTime - startTime;
545	<	double timePerOp = ((double)time)/numOps;
546	<
659	>	long elapsed = System.nanoTime() - startTime;
660		Object st = accum.get(name);
661		if (st == null)
662	<	accum.put(name, new Stats(timePerOp));
663	<	else {
664	<	Stats stats = (Stats) st;
552	<	stats.sum += timePerOp;
553	<	stats.number++;
554	<	if (timePerOp < stats.least) stats.least = timePerOp;
555	<	}
556	<
557	<	if (cname != null) {
558	<	st = accum.get(cname);
559	<	if (st == null)
560	<	accum.put(cname, new Stats(timePerOp));
561	<	else {
562	<	Stats stats = (Stats) st;
563	<	stats.sum += timePerOp;
564	<	stats.number++;
565	<	if (timePerOp < stats.least) stats.least = timePerOp;
566	<	}
567	<	}
568	<
662	>	accum.put(name, new Stats(elapsed, numOps));
663	>	else
664	>	((Stats)st).addTime(elapsed, numOps);
665		}
666
667		}
668
669	<	static class Stats {
670	<	double sum = 0;
671	<	double least;
672	<	int number = 0;
673	<	Stats(double t) { least = t; }
669	>	static final class Stats {
670	>	long sum;
671	>	long number;
672	>	long first;
673	>	long firstn;
674	>	Stats(long t, long n) {
675	>	first = t;
676	>	firstn = n;
677	>	}
678	>	void addTime(long t, long n) {
679	>	sum += t;
680	>	number += n;
681	>	}
682		}
683
580	–	static Random rng = new Random();
684
685		static void shuffle(Object[] keys) {
686		int size = keys.length;
687	<	for (int i=size; i>1; i--) {
687	>	for (int i= size; i>1; i--) {
688		int r = rng.nextInt(i);
689		Object t = keys[i-1];
690		keys[i-1] = keys[r];
#	Line 589 | Line 692 | public class MapCheck {
692		}
693		}
694
695	+	static void shuffle(ArrayList keys) {
696	+	int size = keys.size();
697	+	for (int i= size; i>1; i--) {
698	+	int r = rng.nextInt(i);
699	+	Object t = keys.get(i-1);
700	+	keys.set(i-1, keys.get(r));
701	+	keys.set(r, t);
702	+	}
703	+	}
704	+
705		}
706

Diff Legend

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