?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Make ObjectIdMap follow Map specification with regard to backed keySet() etc
[egit.git] / org.spearce.jgit / tst / org / spearce / jgit / lib / ObjectIdMapTest.java
blob299b1bea481c8d27097192bead62a68e94aa9130
1 /*
2 * Copyright (C) 2006 Robin Rosenberg <robin.rosenberg@dewire.com>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License, version 2, as published by the Free Software Foundation.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
16 */
17 package org.spearce.jgit.lib;
18
19 import java.util.Arrays;
20 import java.util.Collection;
21 import java.util.Comparator;
22 import java.util.HashMap;
23 import java.util.Iterator;
24 import java.util.Map;
25 import java.util.TreeMap;
26
27 import junit.framework.AssertionFailedError;
28 import junit.framework.TestCase;
29
30 /**
31 * Test functionality and performance.
32 *
33 * Performance (put performance) is included because that is the very reason
34 * that {@link ObjectIdMap} exists.
35 *
36 */
37 public class ObjectIdMapTest extends TestCase {
38
39 ObjectId[] ids = new ObjectId[500000];
40
41 protected void setUp() throws Exception {
42 int b=0;
43 for (int i=0; i<ids.length; ++i) {
44 byte[] data = new byte[Constants.OBJECT_ID_LENGTH];
45 for (int j=0; j<Constants.OBJECT_ID_LENGTH; ++j)
46 data[j] = (byte) (b++^0xEE);
47 ids[i] = new ObjectId(data);
48 }
49 }
50
51 protected void tearDown() throws Exception {
52 ids = null; // avoid out of memory
53 }
54
55 /**
56 * Test performance of {@link ObjectIdMap#put(ObjectId, Object)}
57 */
58 @SuppressWarnings("unchecked")
59 public void testBothPut() {
60 long d1=0;
61 long d2=0;
62 long d3=0;
63 long d4=0;
64 long d5=0;
65 long d6=0;
66
67 for (int j=0; j<64; ++j) {
68 int x =
69 ((j & 1)!=0 ? 1 : 0) |
70 ((j & 2)!=0 ? 2 : 0) |
71 ((j & 4)!=0 ? 16 : 0) |
72 ((j & 8)!=0 ? 32 : 0) |
73 ((j & 16)!=0 ? 4 : 0) |
74 ((j & 32)!=0 ? 8 : 0);
75
76 if ((x&1) == 0) {
77 long t0 = System.currentTimeMillis();
78
79 Map treeMap = new TreeMap();
80 for (int i=0; i<ids.length; ++i)
81 treeMap.put(ids[i],ids[i]);
82
83 long t1 = System.currentTimeMillis();
84 d1 += t1-t0;
85 }
86 if ((x&2) == 0) {
87 long t0 = System.currentTimeMillis();
88 Map hashMap = new HashMap();
89 for (int i=0; i<ids.length; ++i)
90 hashMap.put(ids[i],ids[i]);
91 long t1 = System.currentTimeMillis();
92 d2 += t1-t0;
93 }
94
95 if ((x&4) == 0) {
96 long t0= System.currentTimeMillis();
97
98 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
99 for (int i=0; i<ids.length; ++i)
100 levelMapWithTree.put(ids[i],ids[i]);
101
102 long t1 = System.currentTimeMillis();
103 d3 += t1-t0;
104 }
105
106 if ((x&8) == 0) {
107 long t0 = System.currentTimeMillis();
108 Map levelMapWithHash = new ObjectIdMap(new HashMap());
109 for (int i=0; i<ids.length; ++i)
110 levelMapWithHash.put(ids[i],ids[i]);
111
112 long t1 = System.currentTimeMillis();
113
114 d4 += t1-t0;
115 }
116
117 if ((x&16) == 0) {
118 long t0= System.currentTimeMillis();
119
120 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
121
122 public int compare(Object arg0, Object arg1) {
123 byte[] b0=((ObjectId)arg0).getBytes();
124 byte[] b1=((ObjectId)arg1).getBytes();
125 for (int i=1; i<Constants.OBJECT_ID_LENGTH; ++i) {
126 int a=b0[i]&0xff;
127 int b=b1[i]&0xff;
128 int c=a-b;
129 if (c!=0)
130 return c;
131 }
132 return 0;
133 }
134
135 }));
136 for (int i=0; i<ids.length; ++i)
137 levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
138
139 long t1 = System.currentTimeMillis();
140 d5 += t1-t0;
141 }
142
143 if ((j&32) == 0) {
144 long t0= System.currentTimeMillis();
145
146 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
147
148 public int compare(Object arg0, Object arg1) {
149 return ((Comparable)arg0).compareTo(arg1);
150 }
151
152 }));
153 for (int i=0; i<ids.length; ++i)
154 levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
155
156 long t1 = System.currentTimeMillis();
157 d6 += t1-t0;
158 }
159 }
160
161 System.out.println("TreeMap ="+d1);
162 System.out.println("HashMap ="+d2);
163 System.out.println("Partitioned TreeMap ObjectId.compare ="+d3);
164 System.out.println("Partitioned HashMap ="+d4);
165 System.out.println("Partitioned TreeMap enhanced compare ="+d5);
166 System.out.println("Partitioned TreeMap dummy compare ="+d6);
167 assertFaster(1.2f, 3f, d5, d2);
168 }
169
170 /**
171 * Test performance of {@link ObjectIdMap#get(Object)}
172 */
173 @SuppressWarnings("unchecked")
174 public void testBothGet() {
175 long d1=0;
176 long d2=0;
177 long d3=0;
178 long d4=0;
179 long d5=0;
180 long d6=0;
181
182 Map treeMap = new TreeMap();
183 for (int i=0; i<ids.length; ++i)
184 treeMap.put(ids[i],ids[i]);
185
186 Map hashMap = new HashMap();
187 for (int i=0; i<ids.length; ++i)
188 hashMap.put(ids[i],ids[i]);
189
190 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
191 for (int i=0; i<ids.length; ++i)
192 levelMapWithTree.put(ids[i],ids[i]);
193
194 Map levelMapWithHash = new ObjectIdMap(new HashMap());
195 for (int i=0; i<ids.length; ++i)
196 levelMapWithHash.put(ids[i],ids[i]);
197
198 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
199 public int compare(Object arg0, Object arg1) {
200 byte[] b0=((ObjectId)arg0).getBytes();
201 byte[] b1=((ObjectId)arg1).getBytes();
202 for (int i=1; i<Constants.OBJECT_ID_LENGTH; ++i) {
203 int a=b0[i]&0xff;
204 int b=b1[i]&0xff;
205 int c=a-b;
206 if (c!=0)
207 return c;
208 }
209 return 0;
210 }
211 }));
212 for (int i=0; i<ids.length; ++i)
213 levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
214
215 Map levelMapWithTreeAndSpecialCompare2 = new ObjectIdMap(new TreeMap(new Comparator() {
216 public int compare(Object arg0, Object arg1) {
217 return ((Comparable)arg0).compareTo(arg1);
218 }
219 }));
220 for (int i=0; i<ids.length; ++i)
221 levelMapWithTreeAndSpecialCompare2.put(ids[i],ids[i]);
222
223 for (int j=0; j<64; ++j) {
224 int x =
225 ((j & 1)!=0 ? 1 : 0) |
226 ((j & 2)!=0 ? 2 : 0) |
227 ((j & 4)!=0 ? 16 : 0) |
228 ((j & 8)!=0 ? 32 : 0) |
229 ((j & 16)!=0 ? 4 : 0) |
230 ((j & 32)!=0 ? 8 : 0);
231
232 if ((x&1) == 0) {
233 long t0 = System.currentTimeMillis();
234
235 for (int i=0; i<ids.length; ++i)
236 treeMap.get(ids[i]);
237
238 long t1 = System.currentTimeMillis();
239 d1 += t1-t0;
240 }
241 if ((x&2) == 0) {
242 long t0 = System.currentTimeMillis();
243 for (int i=0; i<ids.length; ++i)
244 hashMap.get(ids[i]);
245 long t1 = System.currentTimeMillis();
246 d2 += t1-t0;
247 }
248
249 if ((x&4) == 0) {
250 long t0= System.currentTimeMillis();
251
252 for (int i=0; i<ids.length; ++i)
253 levelMapWithTree.get(ids[i]);
254
255 long t1 = System.currentTimeMillis();
256 d3 += t1-t0;
257 }
258
259 if ((x&8) == 0) {
260 long t0 = System.currentTimeMillis();
261 for (int i=0; i<ids.length; ++i)
262 levelMapWithHash.get(ids[i]);
263
264 long t1 = System.currentTimeMillis();
265
266 d4 += t1-t0;
267 }
268
269 if ((x&16) == 0) {
270 long t0= System.currentTimeMillis();
271
272 for (int i=0; i<ids.length; ++i)
273 levelMapWithTreeAndSpecialCompare.get(ids[i]);
274
275 long t1 = System.currentTimeMillis();
276 d5 += t1-t0;
277 }
278
279 if ((j&32) == 0) {
280 long t0= System.currentTimeMillis();
281
282 for (int i=0; i<ids.length; ++i)
283 levelMapWithTreeAndSpecialCompare2.get(ids[i]);
284
285 long t1 = System.currentTimeMillis();
286 d6 += t1-t0;
287 }
288 }
289
290 System.out.println("TreeMap ="+d1);
291 System.out.println("HashMap ="+d2);
292 System.out.println("Partitioned TreeMap ObjectId.compare ="+d3);
293 System.out.println("Partitioned HashMap ="+d4);
294 System.out.println("Partitioned TreeMap enhanced compare ="+d5);
295 System.out.println("Partitioned TreeMap dummy compare ="+d6);
296 assertFaster(1.0f, 3f, d5, d2); // d5 is twice as fast
297 }
298
299 /**
300 * Test performance of {@link ObjectIdMap#keySet()} iterator
301 */
302 @SuppressWarnings("unchecked")
303 public void testBothIterate() {
304 long d1=0;
305 long d2=0;
306 long d3=0;
307 long d4=0;
308 long d5=0;
309 long d6=0;
310
311 Map treeMap = new TreeMap();
312 for (int i=0; i<ids.length; ++i)
313 treeMap.put(ids[i],ids[i]);
314
315 Map hashMap = new HashMap();
316 for (int i=0; i<ids.length; ++i)
317 hashMap.put(ids[i],ids[i]);
318
319 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
320 for (int i=0; i<ids.length; ++i)
321 levelMapWithTree.put(ids[i],ids[i]);
322
323 Map levelMapWithHash = new ObjectIdMap(new HashMap());
324 for (int i=0; i<ids.length; ++i)
325 levelMapWithHash.put(ids[i],ids[i]);
326
327 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
328 public int compare(Object arg0, Object arg1) {
329 byte[] b0=((ObjectId)arg0).getBytes();
330 byte[] b1=((ObjectId)arg1).getBytes();
331 for (int i=1; i<Constants.OBJECT_ID_LENGTH; ++i) {
332 int a=b0[i]&0xff;
333 int b=b1[i]&0xff;
334 int c=a-b;
335 if (c!=0)
336 return c;
337 }
338 return 0;
339 }
340 }));
341 for (int i=0; i<ids.length; ++i)
342 levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
343
344 Map levelMapWithTreeAndSpecialCompare2 = new ObjectIdMap(new TreeMap(new Comparator() {
345 public int compare(Object arg0, Object arg1) {
346 return ((Comparable)arg0).compareTo(arg1);
347 }
348 }));
349 for (int i=0; i<ids.length; ++i)
350 levelMapWithTreeAndSpecialCompare2.put(ids[i],ids[i]);
351
352 for (int j=0; j<64; ++j) {
353 int x =
354 ((j & 1)!=0 ? 1 : 0) |
355 ((j & 2)!=0 ? 2 : 0) |
356 ((j & 4)!=0 ? 16 : 0) |
357 ((j & 8)!=0 ? 32 : 0) |
358 ((j & 16)!=0 ? 4 : 0) |
359 ((j & 32)!=0 ? 8 : 0);
360
361 if ((x&1) == 0) {
362 long t0 = System.currentTimeMillis();
363
364 for (int l=0; l<100; ++l)
365 for (Iterator k=treeMap.keySet().iterator(); k.hasNext(); )
366 k.next();
367
368 long t1 = System.currentTimeMillis();
369 d1 += t1-t0;
370 }
371 if ((x&2) == 0) {
372 long t0 = System.currentTimeMillis();
373 for (int l=0; l<100; ++l)
374 for (Iterator k=hashMap.keySet().iterator(); k.hasNext(); )
375 k.next();
376 long t1 = System.currentTimeMillis();
377 d2 += t1-t0;
378 }
379
380 if ((x&4) == 0) {
381 long t0= System.currentTimeMillis();
382
383 for (int l=0; l<100; ++l)
384 for (Iterator k=levelMapWithTree.keySet().iterator(); k.hasNext(); )
385 k.next();
386
387 long t1 = System.currentTimeMillis();
388 d3 += t1-t0;
389 }
390
391 if ((x&8) == 0) {
392 long t0 = System.currentTimeMillis();
393
394 for (int l=0; l<100; ++l)
395 for (Iterator k=levelMapWithHash.keySet().iterator(); k.hasNext(); )
396 k.next();
397
398 long t1 = System.currentTimeMillis();
399
400 d4 += t1-t0;
401 }
402
403 if ((x&16) == 0) {
404 long t0= System.currentTimeMillis();
405
406 for (int l=0; l<100; ++l)
407 for (Iterator k=levelMapWithTreeAndSpecialCompare.keySet().iterator(); k.hasNext(); )
408 k.next();
409
410 long t1 = System.currentTimeMillis();
411 d5 += t1-t0;
412 }
413
414 if ((j&32) == 0) {
415 long t0= System.currentTimeMillis();
416
417 for (int l=0; l<100; ++l)
418 for (Iterator k=levelMapWithTreeAndSpecialCompare2.keySet().iterator(); k.hasNext(); )
419 k.next();
420
421 long t1 = System.currentTimeMillis();
422 d6 += t1-t0;
423 }
424 }
425
426 System.out.println("TreeMap ="+d1);
427 System.out.println("HashMap ="+d2);
428 System.out.println("Partitioned TreeMap ObjectId.compare ="+d3);
429 System.out.println("Partitioned HashMap ="+d4);
430 System.out.println("Partitioned TreeMap enhanced compare ="+d5);
431 System.out.println("Partitioned TreeMap dummy compare ="+d6);
432 assertSlower(5f, 15f, d5, d2);
433 }
434
435 /**
436 * Test performance of {@link ObjectIdMap#values()}
437 */
438 @SuppressWarnings("unchecked")
439 public void testBothValues() {
440 long d1=0;
441 long d2=0;
442 long d3=0;
443 long d4=0;
444 long d5=0;
445 long d6=0;
446
447 Map treeMap = new TreeMap();
448 for (int i=0; i<ids.length; ++i)
449 treeMap.put(ids[i],ids[i]);
450
451 Map hashMap = new HashMap();
452 for (int i=0; i<ids.length; ++i)
453 hashMap.put(ids[i],ids[i]);
454
455 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
456 for (int i=0; i<ids.length; ++i)
457 levelMapWithTree.put(ids[i],ids[i]);
458
459 Map levelMapWithHash = new ObjectIdMap(new HashMap());
460 for (int i=0; i<ids.length; ++i)
461 levelMapWithHash.put(ids[i],ids[i]);
462
463 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
464 public int compare(Object arg0, Object arg1) {
465 byte[] b0=((ObjectId)arg0).getBytes();
466 byte[] b1=((ObjectId)arg1).getBytes();
467 for (int i=1; i<Constants.OBJECT_ID_LENGTH; ++i) {
468 int a=b0[i]&0xff;
469 int b=b1[i]&0xff;
470 int c=a-b;
471 if (c!=0)
472 return c;
473 }
474 return 0;
475 }
476 }));
477 for (int i=0; i<ids.length; ++i)
478 levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
479
480 Map levelMapWithTreeAndSpecialCompare2 = new ObjectIdMap(new TreeMap(new Comparator() {
481 public int compare(Object arg0, Object arg1) {
482 return ((Comparable)arg0).compareTo(arg1);
483 }
484 }));
485 for (int i=0; i<ids.length; ++i)
486 levelMapWithTreeAndSpecialCompare2.put(ids[i],ids[i]);
487
488 for (int j=0; j<8192; ++j) {
489 int x =
490 ((j & 1)!=0 ? 1 : 0) |
491 ((j & 2)!=0 ? 2 : 0) |
492 ((j & 4)!=0 ? 16 : 0) |
493 ((j & 8)!=0 ? 32 : 0) |
494 ((j & 16)!=0 ? 4 : 0) |
495 ((j & 32)!=0 ? 8 : 0);
496
497 if ((x&1) == 0) {
498 long t0 = System.currentTimeMillis();
499
500 for (int l=0; l<100; ++l)
501 treeMap.values();
502
503 long t1 = System.currentTimeMillis();
504 d1 += t1-t0;
505 }
506 if ((x&2) == 0) {
507 long t0 = System.currentTimeMillis();
508
509 for (int l=0; l<100; ++l)
510 hashMap.values();
511
512 long t1 = System.currentTimeMillis();
513 d2 += t1-t0;
514 }
515
516 if ((x&4) == 0) {
517 long t0= System.currentTimeMillis();
518
519 for (int l=0; l<100; ++l)
520 levelMapWithTree.values();
521
522 long t1 = System.currentTimeMillis();
523 d3 += t1-t0;
524 }
525
526 if ((x&8) == 0) {
527 long t0 = System.currentTimeMillis();
528
529 for (int l=0; l<100; ++l)
530 levelMapWithHash.values();
531
532 long t1 = System.currentTimeMillis();
533
534 d4 += t1-t0;
535 }
536
537 if ((x&16) == 0) {
538 long t0= System.currentTimeMillis();
539
540 for (int l=0; l<100; ++l)
541 levelMapWithTreeAndSpecialCompare.values();
542
543 long t1 = System.currentTimeMillis();
544 d5 += t1-t0;
545 }
546
547 if ((j&32) == 0) {
548 long t0= System.currentTimeMillis();
549
550 for (int l=0; l<100; ++l)
551 levelMapWithTreeAndSpecialCompare2.values();
552
553 long t1 = System.currentTimeMillis();
554 d6 += t1-t0;
555 }
556 }
557
558 System.out.println("TreeMap ="+d1);
559 System.out.println("HashMap ="+d2);
560 System.out.println("Partitioned TreeMap ObjectId.compare ="+d3);
561 System.out.println("Partitioned HashMap ="+d4);
562 System.out.println("Partitioned TreeMap enhanced compare ="+d5);
563 System.out.println("Partitioned TreeMap dummy compare ="+d6);
564 assertFaster(1.5f, 3f, d5, d2);
565 }
566
567 /**
568 * Verify that ObjectIdMap and TreeMap functionally are equivalent.
569 */
570 @SuppressWarnings("unchecked")
571 public void testFunc() {
572 Map treeMap = new TreeMap();
573 for (int i=0; i<ids.length/100; ++i)
574 treeMap.put(ids[i],ids[i]);
575 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
576 for (int i=0; i<ids.length/100; ++i)
577 levelMapWithTree.put(ids[i],ids[i]);
578
579 assertEquals(treeMap, levelMapWithTree);
580 assertEquals(treeMap.values(), levelMapWithTree.values());
581 assertEquals(treeMap.keySet(), levelMapWithTree.keySet());
582
583 treeMap.remove(ids[30]);
584 levelMapWithTree.remove(ids[30]);
585 assertFalse(treeMap.containsKey(ids[30]));
586 assertFalse(levelMapWithTree.containsKey(ids[30]));
587 assertEquals(treeMap.values(), levelMapWithTree.values());
588 assertEquals(treeMap.keySet(), levelMapWithTree.keySet());
589 }
590
591 void assertEquals(Collection a, Collection b) {
592 Object[] aa = a.toArray();
593 Object[] ba = b.toArray();
594 Arrays.sort(aa);
595 Arrays.sort(ba);
596 assertTrue(Arrays.equals(aa, ba));
597 }
598
599 void assertSlower(float min,float max, long d5, long d2) {
600 float ratio = d5/(float)d2;
601 ratio = ((int)(ratio*10+0.5))/10.0f;
602 if (ratio < min || ratio > max)
603 throw new AssertionFailedError("Expected (slower) "+ min + " <= " + ratio + " <= " + max);
604 StackTraceElement frame = new Throwable().getStackTrace()[1];
605 System.out.println("Expected slower (ok) "+ frame.getClassName()+"."+frame.getMethodName() + " in range: " + min + " <= " + ratio + " <= " + max);
606 }
607
608 void assertFaster(float min,float max, long d5, long d2) {
609 float ratio = d2/(float)d5;
610 ratio = ((int)(ratio*10+0.5))/10.0f;
611 if (ratio < min || ratio > max)
612 throw new AssertionFailedError("Expected (faster) "+ min + " <= " + ratio + " <= " + max);
613 StackTraceElement frame = new Throwable().getStackTrace()[1];
614 System.out.println("Expected faster (ok) "+ frame.getClassName()+"."+frame.getMethodName() + " in range: " + min + " <= " + ratio + " <= " + max);
615 }
616 }
Eclipse Git Team Provider