Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2 3
  ignore  |  Print  
  map performance  (Read 23804 times)
0 Members and 1 Guest are viewing this topic.
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Posted 2009-10-21 05:32:55 »

Edit: Latest source from later in the thread: http://n4te.com/temp/fast.7z

For kicks I benchmarked some map implementations on Android (G1):







Android couldn't run fastutil (too many classes in the JAR!) or alex14n's FastHashMap (uses 1.6 methods and I'm too lazy to update it).







CachingHashMap is JL235's class:
http://kenai.com/projects/sf-library/sources/sf/content/SF/src/com/studiofortress/sf/util/collections/CachingHashMap.java?rev=3
I thought it would be faster the second time (same map is used, just clear'ed) since the entry objects are reused, but the caching overhead came out the same as creating new objects. Of course GC is avoided.

The IntHashMap is this class:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-common/src/com/esotericsoftware/skorpios/util/IntHashMap.java
The FastIdentityHashMap and FastObjectHashMap are the same code as IntHashMap, tweaked a little.

HashMapV2 is from here:
http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-June/001961.html

Would love if you guys can catch me doing anything stupid or have other ideas on fast/efficient maps.

Offline jezek2
« Reply #1 - Posted 2009-10-21 07:09:34 »

Try GNU Trove, it has faster hashmaps, supports primitive types and it doesn't need to allocate Entry objects when traversing the map. Also you can adapt their benchmark code to other collections you're testing.
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #2 - Posted 2009-10-21 10:02:56 »

Updated first post with pretty charts and included Trove and some others.

Benchmark code:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
304  
305  
306  
307  
308  
309  
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Random;
import java.util.Map.Entry;

import javolution.util.FastMap;

import org.apache.commons.collections.map.HashedMap;
import org.apache.commons.collections.map.IdentityMap;

import cern.colt.map.OpenIntObjectHashMap;
import gnu.trove.map.hash.THashMap;
import gnu.trove.map.hash.TIntObjectHashMap;

public class MapTest {
   static int count = 1000000;
   static Integer[] randomInteger = new Integer[count];
   static int[] randomInt = new int[count];
   static boolean warmup = true;
   static HashMap<String, Long> testTimes = new HashMap();
   static ArrayList<Test> tests = new ArrayList();

   public static void main (String[] args) throws Exception {
      Random r = new Random();
      for (int i = 0; i < count; i++) {
         int value = -1;
         while (value == -1)
            value = r.nextInt();
         randomInt[i] = value;
         randomInteger[i] = value;
      }

      addTest("Java", new HashMapTest());
      addTest("Java", new IdentityHashMapTest());
      addTest("Javolution", new FastMapTest());
      addTest("JL235", new CachingHashMapTest());
      addTest("Nate", new FastObjectHashMapTest());
      addTest("Nate", new FastIdentityHashMapTest());
      addTest("Nate", new IntHashMapTest());
      addTest("Trove", new THashMapTest());
      addTest("Trove", new TIntObjectHashMapTest());
      addTest("Cern Cole", new OpenIntObjectHashMapTest());
      addTest("Commons Collections", new HashedMapTest());
      addTest("Commons Collections", new IdentityMapTest());
      addTest("Commons Lang", new ApacheIntHashMapTest());

      for (Test runnable : tests)
         for (int i = 0; i < 5; i++)
            runnable.run();
      warmup = false;

      for (Test runnable : tests) {
         for (int i = 0; i < 3; i++) {
            runnable.run();
         }
         System.out.println();
      }

      ArrayList<Entry> list = new ArrayList(testTimes.entrySet());
      Collections.sort(list, new Comparator<Entry>() {
         public int compare (Entry o1, Entry o2) {
            return (int)((Long)o1.getValue() - (Long)o2.getValue());
         }
      });
      chart("Get", list, " get");
      chart("Put", list, " put");

      HashMap totalTimes = new HashMap();
      for (String name : testTimes.keySet()) {
         name = name.replace(" get", "").replace(" put", "");
         long sum = 0;
         for (String name2 : testTimes.keySet())
            if (name2.equals(name + " get") || name2.equals(name + " put")) sum += testTimes.get(name2);
         totalTimes.put(name, sum);
      }
      list = new ArrayList(totalTimes.entrySet());
      Collections.sort(list, new Comparator<Entry>() {
         public int compare (Entry o1, Entry o2) {
            return (int)((Long)o1.getValue() - (Long)o2.getValue());
         }
      });
      chart("Get+Put", list, "");
   }

   static void addTest (String name, Test test) {
      test.name = test.getClass().getSimpleName().replace("Test", "") + ", " + name;
      tests.add(test);
   }

   static void chart (String title, ArrayList<Entry> list, String suffix) {
      StringBuilder names = new StringBuilder(512);
      StringBuilder times = new StringBuilder(512);
      long max = 0;
      int count = 0;
      for (Entry<String, Long> entry : list) {
         String name = entry.getKey();
         if (!name.endsWith(suffix)) continue;
         names.insert(0, '|');
         names.insert(0, name.substring(0, name.length() - suffix.length()));
         long time = entry.getValue();
         times.append(time);
         times.append(',');
         max = Math.max(max, time);
         count++;
      }
      times.setLength(times.length() - 1);
      names.setLength(names.length() - 1);
      int height = (count + 1) * 18;
      int width = Math.min(700, 300000 / height);
      System.out.println("http://chart.apis.google.com/chart?chtt=" + title + ", Desktop&" + "chs=" + width + "x" + height
         + "&chd=t:" + times + "&chds=0," + max + "&chxl=0:|" + names + "&cht=bhg&chbh=10&chxt=y");
   }

   static void gc () {
      if (warmup) return;
      System.gc();
      System.gc();
      try {
         Thread.sleep(50);
      } catch (InterruptedException ignored) {
      }
      System.gc();
      System.gc();
   }

   static abstract class Test implements Runnable {
      String name;
      long s;
      Object someValue = new Object();

      void start () {
         s = System.nanoTime();
      }

      void end (String suffix) {
         if (warmup) return;
         long e = System.nanoTime();
         long time = e - s;
         Long oldTime = testTimes.get(name + " " + suffix);
         if (oldTime == null || time < oldTime) testTimes.put(name + " " + suffix, time);
         System.out.println(name + " " + suffix + ": " + time / 1000000f + " ms");
      }
   }

   static class HashMapTest extends Test {
      HashMap map = new HashMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         HashMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInteger[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInteger[i]);
         end("get");
      }
   }

   static class FastMapTest extends Test {
      FastMap map = new FastMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         FastMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInteger[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInteger[i]);
         end("get");
      }
   }

   static class IntHashMapTest extends Test {
      IntHashMap map = new IntHashMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         IntHashMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInt[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInt[i]);
         end("get");
      }
   }

   static class CachingHashMapTest extends Test {
      CachingHashMap map = new CachingHashMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         CachingHashMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInteger[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInteger[i]);
         end("get");
      }
   }

   static class IdentityHashMapTest extends Test {
      IdentityHashMap map = new IdentityHashMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         IdentityHashMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInteger[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInteger[i]);
         end("get");
      }
   }

   static class FastIdentityHashMapTest extends Test {
      FastIdentityHashMap map = new FastIdentityHashMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         FastIdentityHashMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInteger[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInteger[i]);
         end("get");
      }
   }

   static class FastObjectHashMapTest extends Test {
      FastObjectHashMap map = new FastObjectHashMap(count * 2);

      public void run () {
         Object someValue = this.someValue;
         FastObjectHashMap map = this.map;
         map.clear();
         Integer[] randomInteger = MapTest.randomInteger;
         int count = MapTest.count;
         gc();

         start();
         for (int i = 0; i < count; i++)
            map.put(randomInteger[i], someValue);
         end("put");

         start();
         for (int i = 0; i < count; i++)
            map.get(randomInteger[i]);
         end("get");
      }
   }

snip... you get the point. Forums won't let me post the whole thing.


Edit: Updated with even more maps. Looks like IntHashMap, FastIdentityHashMap, and FastObjectHashMap have the fastest gets for the 3 purposes. As mentioned, these are all basically the same code. Anyone see anything wrong with this code?

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Abuse

JGO Knight


Medals: 14


falling into the abyss of reality


« Reply #3 - Posted 2009-10-21 11:17:37 »

While I like your pretty charts, I think they'd be more readable if they were sorted by their name, rather than their performance (as is the norm for performance comparison charts).

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline princec

« JGO Spiffy Duke »


Medals: 429
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2009-10-21 12:12:41 »

Depends if you just want to know which one's the fastest Wink

Cas Smiley

Offline CommanderKeith
« Reply #5 - Posted 2009-10-21 13:52:19 »

Wow, nice work. Thanks for putting all of this together.  Cool

Your FastIdentityHashMaps look like they're king. Are these maps that you made yourself?


Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #6 - Posted 2009-10-21 16:09:50 »

While I like your pretty charts, I think they'd be more readable if they were sorted by their name, rather than their performance (as is the norm for performance comparison charts).

Really? Ok, fixed and added some colors.

Wow, nice work. Thanks for putting all of this together.  Cool

Your FastIdentityHashMaps look like they're king. Are these maps that you made yourself?

Sure, it was kind of fun. Smiley I lifted the ~10 lines that makes the charts from another benchmark. It is surprisingly easy to make charts, thanks Google! Hear that Riven? I expect not to see any more benchmarks without proper charts! Tongue

Of course, these results should be taken with a grain of salt. Memory usage isn't considered, maps are tested with only one data set, not all maps use the same double hashing that HashMap uses, iteration isn't tested, getting keys not in the map isn't tested, etc.

Actually I resurrected the IntHashMap code from an old project... I really ought to find the original code and give proper recognition! I am pretty sure it was originally lifted from here...
http://www.koders.com/java/fid128CB47B2558DD20EA15852E444D7928D1E698DD.aspx
I will add the appropriate credits to source I distribute. It has been tweaked a little since then. Also, for FastIdentityHashMap I just made the keys Objects and called hashCode(), and for FastObjectHashMap I just replaced == with equals().

I added HashMapV2 from a recent mailing list discussion (linked in first post). It does amazingly well on Android for puts and holds its own for gets. It is probably more complete/robust than FastObjectHashMap (it is certainly fancier). Too bad it is GPL.

Offline JL235

JGO Coder


Medals: 10



« Reply #7 - Posted 2009-10-21 16:57:34 »

First thanks for putting this together. I will definitely be looking at the other types of maps as a result of this. But could you bring back the ordering? It's now hard to compare implementations.

Using your code I made a few changes and ran my own benchmarks. This was only between the IdentifyMap, HashMap, CachingHashMap and FastMap (tbh I couldn't be bothered to go get them all).
  • I upped the number of iterations to run per test from 3 to 60
  • It stores all times and then takes the average at the end (so you have an average time over 60 runs)
  • The gc call was removed from inside test iterations (I thought this was unfair because it gives maps some breathing space which they don't get in real life)
  • I added the gc call to before the start of each test, to encourage the garbage collector to run and so not pass garbage on to the next test
The main goal was to try to benchmark longer-term performance and including the cost of garbage collection on top. At the very least this is more relevant for me (as I've personally found GC to sometimes become an issue). Here are the results:

When I scanned through the values as they were coming out I noticed that the HashMap would have an iteration that ran 5 to 10 times slower then the others. None of the other maps had these outlier values, and I'm presuming it must be the GC kicking in. This is what slows it down. It's also interesting that mine is slower then the HashMap for get, but faster for put and when those times are combined. Which type of map people should use really depends on the situation.

To run the benchmark I also added the -Xmx512m command line so it ran with enough memory, but I found that if I also added Xms512m it improved the performance of the HashMap:

Presumably there is no (or very little) garbage collecting going on as a result.

Finally, identity maps are not real maps!

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #8 - Posted 2009-10-21 17:12:12 »

Oy, take the order out, put the ordering in... I don't know!? Tongue

I'll post a zip of my code later today so you can more easily run all the tests.

GC is unpredictable, so I think it is better to remove it entirely rather than have it affect some of the tests sometimes. We can add memory usage pretty easily. I would like to find some way to reliably measure GC activity.

Interesting that bumping the JVM's memory gave you better performance. I'll give that a shot.

Re: identity maps, sometimes they are useful (eg, autoboxed primitive keys or when Class is your key), and they are fast. I really only care about the 3 scenarios: int keys, object keys, and identity keys. Memory usage and large data sets I'm not too worried about, mostly I just care about get. Oh, and I'd like the classes to be small (eg, not a half meg library -- I'm looking at you, Javolution).

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #9 - Posted 2009-10-22 16:21:00 »

I added a class called CachingFastMap. It is the same as FastMap (formerly known as FastObjectHashMap) except it keeps around its entry objects when entries are removed or the map is cleared. Like JL235's CachingHashMap class, this is to avoid garbage collection if you are constantly putting and clearing a map. It scores very well for puts on Android, where memory allocation (and GC!) is expensive.

In the "fast.maps" package you'll find the classes listed as "Nate" in the charts. All these are based on a modified version of IntHashMap from an Apache project. They are fast, minimal, and easy to customize. Eg, if you needed a ShortHashMap, a CachingLongHashMap, a different hashing algorithm, or whatever, you could modify one of these classes and have the map you need in a couple minutes.

I fixed up my classes quite a bit. You can get the source for it all here (3.1mb):
http://n4te.com/temp/fast.zip
Note fastutil is not included because the JAR is 13mb+! That makes Trove's 2mb look like a good bargain!

The desktop tests are run with -Xms1024m. I added Hashtable. Also, I put the sorting back until someone complains again. Tongue With so many implementations, it is hard to see what is faster when they are alphabetical.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #10 - Posted 2009-10-22 16:36:06 »

Hear that Riven? I expect not to see any more benchmarks without proper charts! Tongue
* Riven makes notes

for FastObjectHashMap I just replaced == with equals().
That works great, until you put nulls in your map.


I'm going to have a go at some fancy impl. !

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #11 - Posted 2009-10-22 17:56:42 »

Yeah, I can get around that easily by not allowing null keys. :p

Looking forward to seeing what you come up with! Smiley

Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2009-10-22 18:10:04 »

Yeah, I can get around that easily by not allowing null keys. :p

or...

private static final Object NULL = new Object();
public void put(Object key, Object val)
{
    if(key==null) key = NULL;
    ...
}
public Object get(Object key)
{
    if(key==null) key = NULL;
    ...
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline CommanderKeith
« Reply #13 - Posted 2009-10-23 00:26:27 »

Hi Nate,

Thanks for making the CachingFastMap. I modified your source to make a CachingFastIdentityMap by copying the code from FastIdentityMap, and it seems to have made the code slower - after profiling I find that a large amount of CPU time is used calling:

1  
java.lang.System.identityHashCode


What's the reason for calling this? Is it ok to replace it with Object.hashcode() which appears to be faster?

Here's my source for CachingFastIdentityMap without the calls to System.identityHashCode, replaced by Object.hashcode().

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
/*
 * Copyright 2002-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */


package fast.maps;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * A hash map using primitive ints as keys rather than objects.
 * @author Justin Couch
 * @author Alex Chaffee (alex@apache.org)
 * @author Stephen Colebourne
 * @author Nathan Sweet
 */

public class CachingFastMap<K, V> implements Iterable<CachingFastMap.Entry<K, V>> {
   Entry[] table;
   private final float loadFactor;
   private int size, mask, capacity, threshold;
   private ArrayList<Entry> freeEntries;

   /**
    * Same as: FastMap(16, 0.75f);
    */

   public CachingFastMap () {
      this(16, 0.75f);
   }

   /**
    * Same as: FastMap(initialCapacity, 0.75f);
    */

   public CachingFastMap (int initialCapacity) {
      this(initialCapacity, 0.75f);
   }

   public CachingFastMap (int initialCapacity, float loadFactor) {
      if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large.");
      if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
      if (loadFactor <= 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
      capacity = 1;
      while (capacity < initialCapacity)
         capacity <<= 1;
      this.loadFactor = loadFactor;
      this.threshold = (int)(capacity * loadFactor);
      this.table = new Entry[capacity];
      this.mask = capacity - 1;
      freeEntries = new ArrayList(capacity);
   }

   public void clearCache () {
      freeEntries.clear();
   }

   public void cache (int count) {
      for (int i = freeEntries.size(); i < count; i++)
         freeEntries.add(new Entry());
   }

   public V put (K key, V value) {
      int hash = key.hashCode();
      Entry[] table = this.table;
      int index = hash & mask;
      // Check if key already exists.
      for (Entry e = table[index]; e != null; e = e.next) {
         if (!e.key.equals(key)) continue;
         Object oldValue = e.value;
         e.value = value;
         return (V)oldValue;
      }
      int freeEntriesSize = freeEntries.size();
      Entry entry = freeEntriesSize > 0 ? freeEntries.remove(freeEntriesSize - 1) : new Entry();
      entry.hash = hash;
      entry.key = key;
      entry.value = value;
      entry.next = table[index];
      table[index] = entry;
      if (size++ >= threshold) {
         // Rehash.
         int newCapacity = 2 * capacity;
         Entry[] newTable = new Entry[newCapacity];
         int newMask = newCapacity - 1;
         for (int i = 0; i < table.length; i++) {
            Entry e = table[i];
            if (e == null) continue;
            do {
               Entry next = e.next;
               index = e.hash & newMask;
               e.next = newTable[index];
               newTable[index] = e;
               e = next;
            } while (e != null);
         }
         this.table = newTable;
         capacity = newCapacity;
         threshold *= 2;
         mask = capacity - 1;
      }
      return null;
   }

   public V get (K key) {
      int index = key.hashCode() & mask;
      for (Entry e = table[index]; e != null; e = e.next)
         if (e.key.equals(key)) return (V)e.value;
      return null;
   }

   public boolean containsValue (V value) {
      Entry[] table = this.table;
      for (int i = table.length - 1; i >= 0; i--)
         for (Entry e = table[i]; e != null; e = e.next)
            if (e.value.equals(value)) return true;
      return false;
   }

   public boolean containsKey (K key) {
      int index = key.hashCode() & mask;
      for (Entry e = table[index]; e != null; e = e.next)
         if (e.key.equals(key)) return true;
      return false;
   }

   public V remove (K key) {
      int index = key.hashCode() & mask;
      Entry prev = table[index];
      Entry e = prev;
      while (e != null) {
         Entry next = e.next;
         if (e.key.equals(key)) {
            size--;
            if (prev == e)
               table[index] = next;
            else
               prev.next = next;
            freeEntries.add(e);
            return (V)e.value;
         }
         prev = e;
         e = next;
      }
      return null;
   }

   public int size () {
      return size;
   }

   public boolean isEmpty () {
      return size == 0;
   }

   public void clear () {
      Entry[] table = this.table;
      for (int index = table.length - 1; index >= 0; index--) {
         for (Entry e = table[index]; e != null; e = e.next)
            freeEntries.add(e);
         table[index] = null;
      }
      size = 0;
   }

   public EntryIterator iterator () {
      return new EntryIterator();
   }

   public class EntryIterator implements Iterator<Entry<K, V>> {
      private int nextIndex;
      private Entry<K, V> current;

      EntryIterator () {
         reset();
      }

      public void reset () {
         current = null;
         // Find first bucket.
         Entry[] table = CachingFastMap.this.table;
         int i;
         for (i = table.length - 1; i >= 0; i--)
            if (table[i] != null) break;
         nextIndex = i;
      }

      public boolean hasNext () {
         if (nextIndex >= 0) return true;
         Entry e = current;
         return e != null && e.next != null;
      }

      public Entry<K, V> next () {
         // Next entry in current bucket.
         Entry e = current;
         if (e != null) {
            e = e.next;
            if (e != null) {
               current = e;
               return e;
            }
         }
         // Use the bucket at nextIndex and find the next nextIndex.
         Entry[] table = CachingFastMap.this.table;
         int i = nextIndex;
         e = current = table[i];
         while (--i >= 0)
            if (table[i] != null) break;
         nextIndex = i;
         return e;
      }

      public void remove () {
         CachingFastMap.this.remove(current.key);
      }
   }

   static public class Entry<K, V> {
      int hash;
      K key;
      V value;
      Entry next;

      public K getKey () {
         return key;
      }

      public V getValue () {
         return value;
      }
   }
}

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #14 - Posted 2009-10-23 02:08:27 »

I'm surprised System.identityHashCode is slower. Using System.identityHashCode means that if you are using objects that have overridden hashCode and equals, even if two objects are .equal() they will (probably) be put in a different hash buckets. Using Object.hashCode may cause more duplicate hashes, but in practice probably makes little difference. If your objects don't override hashCode then there is no difference.

If you have a huge number of objects in your map, you should probably run the benchmarks with a higher number of objects (uses 10,000 currently). Java's IdentityHashMap is pretty impressive. It puts the keys and values alternating in a single array (supposedly good for large data sets) and doesn't need to create or reuse entry objects.

Offline pjt33
« Reply #15 - Posted 2009-10-23 07:24:36 »

As mentioned, these are all basically the same code. Anyone see anything wrong with this code?
Yes. get and put both take int as the type of the key, but containsKey takes long and casts it to int. There may be a good reason for doing this, but I can't see it.
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2009-10-23 07:43:07 »

I noticed that too yesterday.

You can see that it is immediately casted to int in the method body. So it must have been a typo, that was 'corrected' incorrectly.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline delt0r

JGO Knight


Medals: 30
Exp: 18 years


Computers can do that?


« Reply #17 - Posted 2009-10-23 17:05:02 »

I recently implemented a cuckoo hashMap for my work (3 hash functions for load factors ~.75). Its was  5x faster or more than the standard hashMap over all and much faster for contains and remove, and about 2-3x faster than using linear probing (IdentitiyHashMap uses this) and this is without tuning. I am surprised that none of these implementations use cuckoo probing as far as I can tell. You don't even need to have Entry objects. It seems to offer big gains for primitives as well. 

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #18 - Posted 2009-10-24 07:46:58 »

Yes. get and put both take int as the type of the key, but containsKey takes long and casts it to int. There may be a good reason for doing this, but I can't see it.
Ah. I should update the source I linked to. The FastIntMap class in the zip I posted is the latest and has this fixed. The original class was LongToIntHashMap and somehow a long got left in. I wasn't using the containsKey method so didn't catch it sooner. Smiley

delt0r, cuckoo hashing looks very interesting! It looks like it is better for my needs (fast for small tables, which ironically isn't what the benchmarks are testing) and is easy to implement. Can you post your implementation, delt0r? I gave it a half assed try (not much time, have a big project to finish this weekend). I've updated the benchmarks (desktop only) in the first post and here is my class:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
/*
 * Copyright 2002-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */


/**
 * A hash map using primitive ints as keys rather than objects.
 * @author Justin Couch
 * @author Alex Chaffee (alex@apache.org)
 * @author Stephen Colebourne
 * @author Nathan Sweet
 */

public class CuckooFastMap<K, V> {
   Entry[] table;
   private final float loadFactor;
   private int size, mask, capacity, threshold;

   /**
    * Same as: FastMap(16, 0.50f);
    */

   public CuckooFastMap () {
      this(16, 0.50f);
   }

   /**
    * Same as: FastMap(initialCapacity, 0.50f);
    */

   public CuckooFastMap (int initialCapacity) {
      this(initialCapacity, 0.50f);
   }

   public CuckooFastMap (int initialCapacity, float loadFactor) {
      if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large.");
      if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
      if (loadFactor <= 0) throw new IllegalArgumentException("initialCapacity must be greater than zero.");
      capacity = 1;
      while (capacity < initialCapacity)
         capacity <<= 1;
      this.loadFactor = loadFactor;
      this.threshold = (int)(capacity * loadFactor);
      this.table = new Entry[capacity];
      this.mask = capacity - 1;
   }

   public V put (K key, V value) {
      int hash = key.hashCode();
      int index;
      while (true) {
         Entry[] table = this.table;
         index = hash & mask;
         // Check if key already exists.
         Entry e = table[index];
         if (e == null) break;
         index = (((hash >>> 15) * (mask + 1)) >>> 17) & mask;
         e = table[index];
         if (e == null) break;
         rehash(2 * capacity);
      }
      table[index] = new Entry(hash, key, value);
      if (size++ >= threshold) rehash(2 * capacity);
      return null;
   }

   private void rehash (int newCapacity) {
      Entry[] newTable = new Entry[newCapacity];
      int newMask = newCapacity - 1;
      for (int i = 0; i < table.length; i++) {
         Entry e = table[i];
         if (e == null) continue;
         int hash = e.hash;
         int index = hash & newMask;
         if (newTable[index] != null) {
            index = (((hash >>> 15) * (newMask + 1)) >>> 17) & newMask;
            if (newTable[index] != null) {
               rehash(newCapacity * 2);
               return;
            }
         }
         newTable[index] = e;
      }
      this.table = newTable;
      capacity = newCapacity;
      threshold *= 2;
      mask = capacity - 1;
   }

   public V get (K key) {
      Entry[] table = this.table;
      int hash = key.hashCode();
      int mask = this.mask;
      int index = hash & mask;
      Entry e = table[index];
      if (e != null && e.key.equals(key)) return (V)e.value;
      index = (((hash >>> 15) * (mask + 1)) >>> 17) & mask;
      e = table[index];
      if (e != null && e.key.equals(key)) return (V)e.value;
      return null;
   }

   public int size () {
      return size;
   }

   public boolean isEmpty () {
      return size == 0;
   }

   public void clear () {
      Entry[] table = this.table;
      for (int index = table.length - 1; index >= 0; index--)
         table[index] = null;
      size = 0;
   }

   static public class Entry<K, V> {
      final int hash;
      final K key;
      V value;

      Entry (int hash, K key, V value) {
         this.hash = hash;
         this.key = key;
         this.value = value;
      }

      public K getKey () {
         return key;
      }

      public V getValue () {
         return value;
      }
   }
}


When an object is put in with the first hash, this code doesn't put it there and move the existing entry, it just tries to put it in the alternate hash slot and rehashes if entries are already in both slots. This causes it to rehash a lot but it was all I have time to do ATM. Smiley Also, I don't know my second hash is the best idea (it is Riven's random number algorithm, I now solve all my problems with it! Tongue). The get time is still extremely interesting! However it seems to vary quite a bit each time I run the test. I guess sometimes more lookups take the worst case scenario route (which would happen less often for smaller maps, the tests currently use 10,000 entries). Could also be due to my shoddy implementation. Smiley

Offline delt0r

JGO Knight


Medals: 30
Exp: 18 years


Computers can do that?


« Reply #19 - Posted 2009-10-24 12:17:59 »

My implementation does not conform to the java.util.map spec. In particular getValues keySet and entrySet are *not* backed by the hash map.

2ndly, I have not yet done a primitives version yet. 

3rdly I use simple hash functions and rely on hashCode to be good. With the hash table itself being a power of 2 for simple masking rather than % which is painfully slow. For example the 3 hash values i use is given by the following code.
1  
2  
3  
4  
5  
6  
int hash =e.hashCode();
int hash2 =1 + ((hash * PRIME) + (hash >>> 16)); //EDIT to fix this line.. added () where it was needed.
int hash3 =2 + (hash ^ (hash >>> 16)) * PRIME; //PRIME is a random 32 bit prime number (aka a prime with hamming weight of about 16).
hash =hash & mask;
hash2 =hash2 & mask;
hash3 =hash3 & mask;


Finally I don't use entry objects.  I use a Object[] table where even entrys are keys and odd entrys are values. I am doing a *lot* of put/remove and this is where this table is much faster than others I have tried. However I have not tried all in the above list.  The idea is that if the hashTable is small then everything will be in cache and it would be very fast. However it turned out it was very fast even with large sizes (millions or more)  and modest load factors 0.75. In particular it has better performance with pathological cases than anything i tested. Basically it has no pathological cases.

I doubt this would beat everything on the list, and I want to add a better rehashing performance (use incremental hashing or whatever its called).

If you still want the code I can post it. BUT be warned its somewhat untested, quite uncommented and reasonably untuned/optimised (no profiling yet).

I have no special talents. I am only passionately curious.--Albert Einstein
Offline gouessej
« Reply #20 - Posted 2009-10-24 13:49:34 »

Too bad it is GPL.
Why is it bad on your view? It is a choice, it has a meaning, we don't use this license to bother people, I use it because it respects my political convictions. Sorry for this short off-topic remark.

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #21 - Posted 2009-10-24 22:40:36 »

Thanks for the additional information delt0r. I would love to see what you have, even if it isn't perfect yet.

gouessej, because I write software to pay the bills in addition to doing it as a hobby. Using a GPL'ed library would mean open sourcing my whole app, which is not something I want to do for my commercial software.

Offline CommanderKeith
« Reply #22 - Posted 2009-10-25 03:16:22 »

This is a great discussion, so many good techniques. Thanks Nate for doing such an awesome job of benchmarking all this stuff.

In the map I'm using for the A* algorithm I make the key and object the same object so I should probably make a map where there's only one array of keys and no entry objects (unless I'm missing something obvious  Tongue  persecutioncomplex ). I'll give it a go and post the code once I get it working

Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #23 - Posted 2009-10-25 03:43:14 »

CommanderKeith, you might post your code and maybe we can come up with something that specifically fits it.

Reading about cuckoo hashing I came across bloom filters, pretty neat stuff:
http://en.wikipedia.org/wiki/Bloom_filter

Offline delt0r

JGO Knight


Medals: 30
Exp: 18 years


Computers can do that?


« Reply #24 - Posted 2009-10-25 08:34:49 »

So with all the warnings I previously gave, here is the src:
http://www.cibiv.univie.ac.at/~greg/CuckooHashMapSrc.jar
I place this in the public domain etc, and without warranty etc.

These class do not conform to the general contract for Map. In particular values(), keySet() and entrySet() return copys of the hash map at that point in time. 
Removing elements from these returned Collections will have no effect on the map.

We do not "rehash" values returned from Object.hashCode() has the Collection class do. We require that Objects stored have taken proper measures to ensure than they provide sufficient randomness.

Please treat this code as a work in progress. It is fast for remove and contains and similar to  other implementations for put. But as i said, I have never even ran a profiler on it. And probably won't, at least not on its own. ie i bench mark it in the app as its used in the app. 

Cuckoo hashing however has expected worst case O(1) time for retrieval, contains, delete and even add. This is in contrast to chaining and linear probing that provide O(n) worst case performance.

Note that using a load factor of larger than 0.75 will generally result in resized before the limit is reached.  Hence the load factor will in practice never be much higher than 0.75 . In fact i think you can prove that it would be between 0.75 and 0.86 or something with 3 hash functions.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline delt0r

JGO Knight


Medals: 30
Exp: 18 years


Computers can do that?


« Reply #25 - Posted 2009-10-25 11:26:07 »

Sorry, there was a minor defect in one of the hashs. Thats now fixed. At any rate it does not affect correctness.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #26 - Posted 2009-10-25 20:45:27 »

Sweet! Thanks delt0r. I'll be playing with it as soon as I get a chance!

Offline CommanderKeith
« Reply #27 - Posted 2009-10-30 13:43:13 »

CommanderKeith, you might post your code and maybe we can come up with something that specifically fits it.


Thanks! my project isn't really bottlenecked by map gets or puts, but it's maxing out the garbage collector with too many HashMap.Entry's so I tried the Caching style maps you and JL345 made and they were perfect.   Cool

But delt0r's cuckoo hashing idea was too cool too refuse since:
* it doesn't use entry objects so there's no garbage at all or any need for object pooling,
* the key is the object so there's no double-storage of references.

The only disadvantage for me I guess is that the hash function is never stored so contains(obj) [or get(obj)] might be a tad slower since the hash of the object being put'ed has to be compared to at least 1 other object's hash code, so at least 2 hashcodes have to be computed.
This is the main modification which speeds up the map in my case:

1  
2  
3  
//int hash =System.identityHashCode(e);
// is replaced by:
int hash =e.hashCode();


I was wondering delt0r, would your implementation be faster if you didn't calculate hash2 and hash3 until you knew you actually needed them?

Cheers,
Keith

PS: here's delt0r's code as I'm using it, with some minor modifications
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
304  
305  
306  
307  
308  
309  
310  
311  
312  
313  
314  
315  
316  
317  
318  
319  
320  
321  
322  
323  
324  
325  
326  
327  
328  
329  
330  
331  
332  
333  
334  
335  
336  
337  
338  
339  
340  
341  
342  
343  
344  
345  
346  
347  
348  
349  
350  
351  
352  
353  
354  
355  
356  
357  
358  
359  
360  
361  
362  
363  
364  
365  
366  
367  
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */


package astarpathfinder.core;

import java.lang.reflect.Array;
import java.util.*;

//import at.mabs.util.IdentityHashSetLinearProbe;

/**
 * Checking to see how fast a 3 way cuckoo hashing is compared to linear probing.
 *
 * The deletes should be *much* faster.
 *
 * Performance is as good or much better than Linear probing except for pathological cases where its about
 * the same (5% faster). It was never slower. Over all the performance is 2-5x faster than java.util.hashSet
 * and sometimes much more (for crazy cases that probably never happen)
 *
 * @author greg ewing
 *
 * I put this into the public domain
 *
 * @param <T>
 */

public class CIdentityHashSet<T> implements Set<T> {
   private T[] table;
   private int size;
   private double loadFactor;
   private int mask =0;
   private int threshold;
   private static int PRIME =2053368389;// random 31 bit prime cus primes are cool

   public CIdentityHashSet(){
      this(1024, 0.75);
   }

   public CIdentityHashSet(int initSize, double loadFactor) {
      this.loadFactor =loadFactor;
      int pow2Size =Integer.highestOneBit(initSize);
      if (pow2Size < initSize)
         pow2Size <<=1;
      table =(T[]) new Object[pow2Size];
      mask =pow2Size - 1;
      threshold =(int) (pow2Size * loadFactor);
   }

   @Override
   public boolean add(T e) {
      if (e == null)
         throw new RuntimeException("Does not permit nulls");

      //int hash =System.identityHashCode(e);
      int hash =e.hashCode();
      int hash2 =1 + ((hash * PRIME) + (hash >>> 16));
      int hash3 =2 + (hash ^ (hash >>> 16)) * PRIME;
      hash =hash & mask;
      hash2 =hash2 & mask;
      hash3 =hash3 & mask;
      //inlining for performance. makes add about 20% faster
      if (table[hash] == e || table[hash2] == e || table[hash3] == e)
         return false;
      if(table[hash]==null){
         table[hash]=e;
      }else if(table[hash2]==null){
         table[hash2]=e;
      }else if(table[hash3]==null){
         table[hash3]=e;
      }else{
         T pushed=table[hash];
         table[hash]=e;
         //System.out.println("Pushing "+e);
         pushInsert(pushed);
      }
      size++;
      // check size... to avoid cascading rehashes.
      if (size > threshold)
         rehash();
      return true;
   }

   private boolean pushInsert(T e) {
      //int hash =System.identityHashCode(e);
      int hash =e.hashCode();
      int hash2 =1 + ((hash * PRIME) + (hash >>> 16));
      int hash3 =2 + (hash ^ (hash >>> 16)) * PRIME;
      hash =hash & mask;
      hash2 =hash2 & mask;
      hash3 =hash3 & mask;
      while (true) {
         for (int i =0; i < table.length; i++) {
            if (table[hash] == null) {
               table[hash] =e;
               // System.out.println("Iter1:"+i);
               return true;
            }
            if (table[hash2] == null) {
               table[hash2] =e;
               // System.out.println("Iter2:"+i);
               return true;
            }
            if (table[hash3] == null) {
               table[hash3] =e;
               // System.out.println("Iter3:"+i+"\t"+hash+"\t"+hash2+"\t"+hash3);
               return true;
            }
            // didn't add --evict hash element
            T pushed =table[hash];
            table[hash] =e;
            e =pushed;
            int oldHash =hash;
            // now get all the hashes for the new element
            //int hash =System.identityHashCode(e);
         hash =e.hashCode();
            hash2 =1 + ((hash * PRIME) + (hash >>> 16));
            hash3 =2 + (hash ^ (hash >>> 16)) * PRIME;
            hash =hash & mask;
            hash2 =hash2 & mask;
            hash3 =hash3 & mask;
            // check the patalogical case of old=new.
            if (hash == oldHash) {
               hash =hash3;
               //hash3 =oldHash;// swap
            }

         }
         //System.out.println("PushRehash");
         rehash();
         // the last element we still have now has invalid hash codes
         // this should be very rare and so expensive that this hardly matters
         //int hash =System.identityHashCode(e);
         hash =e.hashCode();
         hash2 =1 + ((hash * PRIME) + (hash >>> 16));
         hash3 =2 + (hash ^ (hash >>> 16)) * PRIME;
         hash =hash & mask;
         hash2 =hash2 & mask;
         hash3 =hash3 & mask;
      }
      // return false;

   }

   // must readd all old elements once done...
   private void rehash() {
      T[] oldTable =table;
      int oldSize =size;

      table =(T[]) new Object[table.length * 2];
      size =0;
      mask =table.length - 1;// power of 2 assumed...
      threshold =(int) (table.length * loadFactor);

      for (int i =0; i < oldTable.length; i++) {
         if (oldTable[i] != null)
            add(oldTable[i]);
      }
      assert (size == oldSize);
      //System.out.println("Rehash:" + table.length);
   }

   @Override
   public boolean addAll(Collection<? extends T> c) {
      boolean flag =false;
      for (T e : c) {
         flag |=add(e);
      }
      return flag;
   }

   @Override
   public void clear() {
      size =0;
      Arrays.fill(table, null);
   }

   @Override
   public boolean contains(Object e) {
      if (e == null)
         return false;
      //int hash =System.identityHashCode(e);
      int hash =e.hashCode();
      int hash2 =1 + ((hash * PRIME) + (hash >>> 16));
      int hash3 =2 + (hash ^ (hash >>> 16)) * PRIME;
      hash =hash & mask;
      hash2 =hash2 & mask;
      hash3 =hash3 & mask;

      if (table[hash] == e || table[hash2] == e || table[hash3] == e)
         return true;
      return false;
   }
   public T get(T e){
      if (contains(e)){
         return e;
      }
      return null;
   }
   public T put(T e, Object obj){
      add(e);
      return null;
   }

   @Override
   public boolean containsAll(Collection<?> c) {
      for (Object e : c) {
         if (!contains(e)){
            return false;
         }
      }

      return true;
   }

   @Override
   public boolean isEmpty() {
      return size == 0;
   }

   @Override
   public Iterator<T> iterator() {

      return new Iterator<T>() {
         private int count =0;
         private int size =CIdentityHashSet.this.size;
         private int currentIndex =-1;
         private boolean removed =false;

         @Override
         public boolean hasNext() {

            return count < size;
         }

         @Override
         public T next() {
            if(count==size)
               throw new NoSuchElementException();
            count++;
            currentIndex++;
            while (table[currentIndex] == null) {
               currentIndex++;
            }
            removed =false;
            return table[currentIndex];
         }

         @Override
         public void remove() {
            if (removed)
               throw new NoSuchElementException("Element Already removed");
            // not the most effecent...
            CIdentityHashSet.this.remove(table[currentIndex]);
            size--;
            currentIndex--;
            count--;
            removed =true;
         }

      };
   }

   @Override
   public boolean remove(Object o) {
      if (o == null)
         return false;
      //int hash =System.identityHashCode(e);
      int hash =o.hashCode();
      int hash2 =1 + ((hash * PRIME) + (hash >>> 16));
      int hash3 =2 + (hash ^ (hash >>> 16)) * PRIME;
      hash =hash & mask;
      hash2 =hash2 & mask;
      hash3 =hash3 & mask;

      if (table[hash] == o) {
         table[hash] =null;
         size--;
         return true;
      }
      if (table[hash2] == o) {
         table[hash2] =null;
         size--;
         return true;
      }
      if (table[hash3] == o) {
         table[hash3] =null;
         size--;
         return true;
      }
      return false;
   }

   @Override
   public boolean removeAll(Collection<?> c) {
      boolean flag =false;
      for (Object o : c) {
         flag |=remove(o);
      }
      return flag;
   }

   @Override
   public boolean retainAll(Collection<?> c) {
      boolean flag =false;
      for(int i=0;i<table.length;i++){
         T e=table[i];
         if(e!=null && !c.contains(e)){
            table[i]=null;
            size--;
            flag=true;
         }
      }
      return flag;
   }

   @Override
   public int size() {

      return size;
   }

   @Override
   public <E> E[] toArray(E[] a) {
      if(a.length<size){
         a=(E[])Array.newInstance(a.getClass().getComponentType(),size);
      }
      int index=0;
      for(int i=0;i<table.length;i++){
         if(table[i]!=null)
            a[index++]=(E)table[i];
      }
      return a;
   }

   @Override
   public Object[] toArray() {
      Object[] array=new Object[size];
      int index=0;
      for(int i=0;i<table.length;i++){
         if(table[i]!=null)
            array[index++]=table[i];
      }
      return array;
   }

   public String toString() {
      StringBuilder builder =new StringBuilder();
      builder.append("IdentSet:" + size + "(");
      for (int i =0; i < table.length; i++) {
         if (table[i] != null) {
            builder.append(table[i].toString() + ",");
         }
      }
      builder.append(")");
      return builder.toString();
   }





   public static void main(String[] arg) {

   }

}

Offline delt0r

JGO Knight


Medals: 30
Exp: 18 years


Computers can do that?


« Reply #28 - Posted 2009-10-30 14:17:54 »

There are a few no brainiers  to speed up my implementation. Lazy calculation of the hashes is one. Better hash cals is another. Get rid of the multiply for starters. There are other things too.

However you will probably be disappointed with the performance increase as it would probably close to undetectable. However what I do for some of my sets is to have a special object type with 3 final int fields. Since i only need identity, these are filled with random ints at creation time, these are then my 3 hash values and I don't need to calculate anything.

It does increase performance. But only a little. The best part of cuckoo hashing is worst case O(1) performance.

But good implementations is nothing compared to just being smarter with how you use them in the first place.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline CommanderKeith
« Reply #29 - Posted 2009-10-31 08:13:02 »

However what I do for some of my sets is to have a special object type with 3 final int fields. Since i only need identity, these are filled with random ints at creation time, these are then my 3 hash values and I don't need to calculate anything.


That's pretty clever. Thanks for the code, it's smoothed out my A* path-finder so there's no GC pauses and it's super fast which is fantastic  Cool

Pages: [1] 2 3
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (29 views)
2014-12-15 11:26:44

Mr.CodeIt (20 views)
2014-12-14 21:50:38

BurntPizza (40 views)
2014-12-10 00:41:13

BurntPizza (75 views)
2014-12-08 06:46:31

JscottyBieshaar (37 views)
2014-12-05 14:39:02

SHC (50 views)
2014-12-03 18:27:13

CopyableCougar4 (47 views)
2014-11-29 23:32:03

toopeicgaming1999 (113 views)
2014-11-26 17:22:04

toopeicgaming1999 (100 views)
2014-11-26 17:20:36

toopeicgaming1999 (30 views)
2014-11-26 17:20:08
Resources for WIP games
by kpars
2014-12-18 12:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-10 00:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-03 00:36:02

List of Learning Resources
by Longor1996
2014-08-16 12:40:00

List of Learning Resources
by SilverTiger
2014-08-05 21:33:27

Resources for WIP games
by CogWheelz
2014-08-01 18:20:17

Resources for WIP games
by CogWheelz
2014-08-01 18:19:50

List of Learning Resources
by SilverTiger
2014-07-31 18:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!