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.Comparator;
  20 import java.util.HashMap;
  21 import java.util.Map;
  22 import java.util.TreeMap;
  23
  24 import junit.framework.TestCase;
  25 import junit.textui.TestRunner;
  26
  27 public class ObjectIdMapTest extends TestCase {
  28
  29         ObjectId[] ids = new ObjectId[1000000];
  30
  31         protected void setUp() throws Exception {
  32                 int b=0;
  33                 for (int i=0; i<ids.length; ++i) {
  34                         byte[] data = new byte[Constants.OBJECT_ID_LENGTH];
  35                         for (int j=0; j<Constants.OBJECT_ID_LENGTH; ++j)
  36                                 data[j] = (byte) (b++^0xEE);
  37                         ids[i] = new ObjectId(data);
  38                 }
  39         }
  40
  41         protected void tearDown() throws Exception {
  42                 ids = null; // avoid out of memory
  43         }
  44
  45         public void testBoth() {
  46                 long d1=0;
  47                 long d2=0;
  48                 long d3=0;
  49                 long d4=0;
  50                 long d5=0;
  51                 long d6=0;
  52
  53                 for (int j=0; j<64; ++j) {
  54                         int x =
  55                                 ((j & 1)!=0  ? 1 : 0) |
  56                                 ((j & 2)!=0  ? 2 : 0) |
  57                                 ((j & 4)!=0  ? 16 : 0) |
  58                                 ((j & 8)!=0  ? 32 : 0) |
  59                                 ((j & 16)!=0 ? 4 : 0) |
  60                                 ((j & 32)!=0 ? 8 : 0);
  61
  62                         if ((x&1) == 0) {
  63                                 long t0 = System.currentTimeMillis();
  64
  65                                 Map treeMap = new TreeMap();
  66                                 for (int i=0; i<ids.length; ++i)
  67                                         treeMap.put(ids[i],ids[i]);
  68
  69                                 long t1 = System.currentTimeMillis();
  70                                 d1 += t1-t0;
  71                         }
  72                         if ((x&2) == 0) {
  73                                 long t0 = System.currentTimeMillis();
  74                                 Map hashMap = new HashMap();
  75                                 for (int i=0; i<ids.length; ++i)
  76                                         hashMap.put(ids[i],ids[i]);
  77                                 long t1 = System.currentTimeMillis();
  78                                 d2 += t1-t0;
  79                         }
  80
  81                         if ((x&4) == 0) {
  82                                 long t0= System.currentTimeMillis();
  83
  84                                 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
  85                                 for (int i=0; i<ids.length; ++i)
  86                                         levelMapWithTree.put(ids[i],ids[i]);
  87
  88                                 long t1 = System.currentTimeMillis();
  89                                 d3 += t1-t0;
  90                         }
  91
  92                         if ((x&8) == 0) {
  93                                 long t0 = System.currentTimeMillis();
  94                                 Map levelMapWithHash = new ObjectIdMap(new HashMap());
  95                                 for (int i=0; i<ids.length; ++i)
  96                                         levelMapWithHash.put(ids[i],ids[i]);
  97
  98                                 long t1 = System.currentTimeMillis();
  99
 100                                 d4 += t1-t0;
 101                         }
 102
 103                         if ((x&16) == 0) {
 104                                 long t0= System.currentTimeMillis();
 105
 106                                 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
 107
 108                                         public int compare(Object arg0, Object arg1) {
 109                                                 byte[] b0=((ObjectId)arg0).getBytes();
 110                                                 byte[] b1=((ObjectId)arg1).getBytes();
 111                                                 for (int i=1; i<Constants.OBJECT_ID_LENGTH; ++i) {
 112                                                         int a=b0[i]&0xff;
 113                                                         int b=b1[i]&0xff;
 114                                                         int c=a-b;
 115                                                         if (c!=0)
 116                                                                 return c;
 117                                                 }
 118                                                 return 0;
 119                                         }
 120
 121                                 }));
 122                                 for (int i=0; i<ids.length; ++i)
 123                                         levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
 124
 125                                 long t1 = System.currentTimeMillis();
 126                                 d5 += t1-t0;
 127                         }
 128
 129                         if ((j&32) == 0) {
 130                                 long t0= System.currentTimeMillis();
 131
 132                                 Map levelMapWithTreeAndSpecialCompare = new ObjectIdMap(new TreeMap(new Comparator() {
 133
 134                                         public int compare(Object arg0, Object arg1) {
 135                                                 return ((Comparable)arg0).compareTo(arg1);
 136                                         }
 137
 138                                 }));
 139                                 for (int i=0; i<ids.length; ++i)
 140                                         levelMapWithTreeAndSpecialCompare.put(ids[i],ids[i]);
 141
 142                                 long t1 = System.currentTimeMillis();
 143                                 d6 += t1-t0;
 144                         }
 145                 }
 146
 147                 System.out.println("TreeMap                              ="+d1);
 148                 System.out.println("HashMap                              ="+d2);
 149                 System.out.println("Partitioned TreeMap ObjectId.compare ="+d3);
 150                 System.out.println("Partitioned HashMap                  ="+d4);
 151                 System.out.println("Partitioned TreeMap enhanced compare ="+d5);
 152                 System.out.println("Partitioned TreeMap dummy    compare ="+d6);
 153                 assertEquals(d5*10/10000, d2*8/10000); // d5 is ~20% better
 154         }
 155
 156         public void testFunc() {
 157                 Map treeMap = new TreeMap();
 158                 for (int i=0; i<ids.length/100; ++i)
 159                         treeMap.put(ids[i],ids[i]);
 160                 Map levelMapWithTree = new ObjectIdMap(new TreeMap());
 161                 for (int i=0; i<ids.length/100; ++i)
 162                         levelMapWithTree.put(ids[i],ids[i]);
 163
 164                 assertEquals(treeMap, levelMapWithTree);
 165         }
 166
 167         public static void main(String[] args) {
 168                 TestRunner.run(ObjectIdMapTest.class);
 169         }
 170 }