org.spearce.jgit/tst/org/spearce/jgit/lib/ObjectIdMapTest.java

   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.Map;
  24 import java.util.TreeMap;
  25
  26 import junit.framework.TestCase;
  27
  28 /**
  29  * Test functionality and performance.
  30  *
  31  * Performance is included because that is the very reason that
  32  * {@link ObjectIdMap} exists.
  33  *
  34  */
  35 public class ObjectIdMapTest extends TestCase {
  36
  37         ObjectId[] ids = new ObjectId[500000];
  38
  39         protected void setUp() throws Exception {
  40                 int b=0;
  41                 for (int i=0; i<ids.length; ++i) {
  42                         byte[] data = new byte[Constants.OBJECT_ID_LENGTH];
  43                         for (int j=0; j<Constants.OBJECT_ID_LENGTH; ++j)
  44                                 data[j] = (byte) (b++^0xEE);
  45                         ids[i] = new ObjectId(data);
  46                 }
  47         }
  48
  49         protected void tearDown() throws Exception {
  50                 ids = null; // avoid out of memory
  51         }
  52
  53         public void testBoth() {
  54                 long d1=0;
  55                 long d2=0;
  56                 long d3=0;
  57                 long d4=0;
  58                 long d5=0;
  59                 long d6=0;
  60
  61                 for (int j=0; j<64; ++j) {
  62                         int x =
  63                                 ((j & 1)!=0  ? 1 : 0) |
  64                                 ((j & 2)!=0  ? 2 : 0) |
  65                                 ((j & 4)!=0  ? 16 : 0) |
  66                                 ((j & 8)!=0  ? 32 : 0) |
  67                                 ((j & 16)!=0 ? 4 : 0) |
  68                                 ((j & 32)!=0 ? 8 : 0);
  69
  70                         if ((x&1) == 0) {
  71                                 long t0 = System.currentTimeMillis();
  72
  73                                 Map treeMap = new TreeMap();
  74                                 for (int i=0; i<ids.length; ++i)
  75                                         treeMap.put(ids[i],ids[i]);
  76
  77                                 long t1 = System.currentTimeMillis();
  78                                 d1 += t1-t0;
  79                         }
  80                         if ((x&2) == 0) {
  81                                 long t0 = System.currentTimeMillis();
  82                                 Map hashMap = new HashMap();
  83                                 for (int i=0; i<ids.length; ++i)
  84                                         hashMap.put(ids[i],ids[i]);
  85                                 long t1 = System.currentTimeMillis();
  86                                 d2 += t1-t0;
  87                         }
  88
  89                         if ((x&4) == 0) {
  90                                 long t0= System.currentTimeMillis();
  91
  92                                 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
  93                                 for (int i=0; i<ids.length; ++i)
  94                                         levelMapWithTree.put(ids[i],ids[i]);
  95
  96                                 long t1 = System.currentTimeMillis();
  97                                 d3 += t1-t0;
  98                         }
  99
 100                         if ((x&8) == 0) {
 101                                 long t0 = System.currentTimeMillis();
 102                                 Map levelMapWithHash = new ObjectIdMap(new HashMap());
 103                                 for (int i=0; i<ids.length; ++i)
 104                                         levelMapWithHash.put(ids[i],ids[i]);
 105
 106                                 long t1 = System.currentTimeMillis();
 107
 108                                 d4 += t1-t0;
 109                         }
 110
 111                         if ((x&16) == 0) {
 112                                 long t0= System.currentTimeMillis();
 113
 114                                 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
 115
 116                                         public int compare(Object arg0, Object arg1) {
 117                                                 byte[] b0=((ObjectId)arg0).getBytes();
 118                                                 byte[] b1=((ObjectId)arg1).getBytes();
 119                                                 for (int i=1; i<Constants.OBJECT_ID_LENGTH; ++i) {
 120                                                         int a=b0[i]&0xff;
 121                                                         int b=b1[i]&0xff;
 122                                                         int c=a-b;
 123                                                         if (c!=0)
 124                                                                 return c;
 125                                                 }
 126                                                 return 0;
 127                                         }
 128
 129                                 }));
 130                                 for (int i=0; i<ids.length; ++i)
 131                                         levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
 132
 133                                 long t1 = System.currentTimeMillis();
 134                                 d5 += t1-t0;
 135                         }
 136
 137                         if ((j&32) == 0) {
 138                                 long t0= System.currentTimeMillis();
 139
 140                                 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
 141
 142                                         public int compare(Object arg0, Object arg1) {
 143                                                 return ((Comparable)arg0).compareTo(arg1);
 144                                         }
 145
 146                                 }));
 147                                 for (int i=0; i<ids.length; ++i)
 148                                         levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
 149
 150                                 long t1 = System.currentTimeMillis();
 151                                 d6 += t1-t0;
 152                         }
 153                 }
 154
 155                 System.out.println("TreeMap                              ="+d1);
 156                 System.out.println("HashMap                              ="+d2);
 157                 System.out.println("Partitioned TreeMap ObjectId.compare ="+d3);
 158                 System.out.println("Partitioned HashMap                  ="+d4);
 159                 System.out.println("Partitioned TreeMap enhanced compare ="+d5);
 160                 System.out.println("Partitioned TreeMap dummy    compare ="+d6);
 161                 assertEquals(d5*2/10000, d2/10000); // d5 is twice as fast
 162         }
 163
 164         /**
 165          * Verify that ObjectIdMap and TreeMap functionally are equivalent.
 166          */
 167         @SuppressWarnings("unchecked")
 168         public void testFunc() {
 169                 Map treeMap = new TreeMap();
 170                 for (int i=0; i<ids.length/100; ++i)
 171                         treeMap.put(ids[i],ids[i]);
 172                 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
 173                 for (int i=0; i<ids.length/100; ++i)
 174                         levelMapWithTree.put(ids[i],ids[i]);
 175
 176                 assertEquals(treeMap, levelMapWithTree);
 177                 assertEquals(treeMap.values(), levelMapWithTree.values());
 178                 assertEquals(treeMap.keySet(), levelMapWithTree.keySet());
 179
 180                 treeMap.remove(ids[30]);
 181                 levelMapWithTree.remove(ids[30]);
 182                 assertFalse(treeMap.containsKey(ids[30]));
 183                 assertFalse(levelMapWithTree.containsKey(ids[30]));
 184                 assertEquals(treeMap.values(), levelMapWithTree.values());
 185                 assertEquals(treeMap.keySet(), levelMapWithTree.keySet());
 186         }
 187
 188         void assertEquals(Collection a, Collection b) {
 189                 Object[] aa = a.toArray();
 190                 Object[] ba = b.toArray();
 191                 Arrays.sort(aa);
 192                 Arrays.sort(ba);
 193                 assertTrue(Arrays.equals(aa, ba));
 194         }
 195 }