map performance

Roquen · October 12, 2010, 3:17pm

Yeah, if you’re not kicking out a placed entry, then you’re performing a classic multi-hash instead of cuckoo hashing. Is your .75 what you’re seeing with your data set? I’d expect (significantly) higher than that in general.

delt0r · October 12, 2010, 3:28pm

Not sure i understand what you are asking? 0.75 is the limit of not requiring a rehash with high probability for 3 hash functions assuming pseudo randomness. Note that it can be higher but in a real hash map with a finite table size it can also be smaller, but with a very small probability.

If you have the pathological case of all keys returning the same hash code… your boned.

It should be noted that i have just noticed that my “rehashing” for 3 hashes is brain dead. I am fixing it now.

Roquen · October 12, 2010, 5:41pm

Looks like we’re talking the same language. I’d expect 3 hash functions on random data to be around .9

delt0r · October 12, 2010, 7:25pm

Turns out the proofs show no resizes with load factor <0.75 the upper bound is around 0.8 IIRC.

Note i have updated my implementation with better hashing. Its faster in the general case, but slower in stupid pathological cases. For example I ran a test with Integers as the keys. However Integer(1).hashCode==1. This created nice access patterns for ordered keys because i assumed hashCode was somewhat random (it should be) and didn’t rehash hashCode(). Now i hash the hashCode() value and random order is similar to “ordered” key puts.

I also noted big differences in performance with cache coherence issues – a typical problem with hashmaps. Basically a get/put combination with the same key is more than 2x faster than with different keys.

Nate · December 27, 2010, 10:42am

Ran across this interesting paper on map comparison, including cuckoo hashing:

Also, I wanted a hashmap that doesn’t allocate for use on Android. I implemented one using open addressing and linear probing. I use separate arrays for keys/values. I tried interleaving keys/values but got worse performance (ObjectMap2 in the source). Source link in the first post has been updated.

The new classes are named ObjectMap, IdentityMap (Nate), and IntMap in the charts below. They seem to perform pretty well, with the added benefit of not allocating. It’s too bad about ObjectMap#put, though get is fast. While there are some tests in FastMapTests, these new classes aren’t yet tested all that thoroughly, so use with care. Also, the methods returning an iterator/iterable are not thread safe (see javadocs), which is easy to change if you don’t want that.

krasse · December 27, 2010, 2:51pm

How about iteration over the keys returned by the map’s keySet()?

I often do that and I always use a LinkedHashMap then instead.

I’ll be back soon…

krasse · December 27, 2010, 3:18pm

Added another test for iteration for those maps that implement the Map interface:


start();
Set keySet = map.keySet();
for (Object o : keySet) {
  o.getClass();
}
end("iter");

http://chart.apis.google.com/chart?chtt=Iter, Desktop&chs=700x219&chd=t:2262299,2638045,7433067,9545836,10368636,10577880,10600090,11035690,12975812,30803566,33112309&chds=0,33112309&chxl=0:|CachingHashMap, JL235|CHashMap (cuckoo), delt0r|Hashtable, Java|HashedMap, Commons Collections|HashMap, Java|IdentityMap, Commons Collections|IdentityMap, Nate|THashMap, Trove|IdentityHashMap, Java|FastHashMap, alex14n|LinkedHashMap, Java&cht=bhg&chbh=10&chxt=y&chco=660000|660033|660066|660099|6600CC|6600FF|663300|663333|663366|663399|6633CC|6633FF|666600|666633|666666

Here are also my results for put and get:

LinkedHashMap seems to be superior for iteration but not as good for put/get on my machina.

delt0r · December 27, 2010, 3:24pm

Something is definitely wrong with my implementation. Either that or you are using Sequential Integers as the keys, and some other imps don’t hash properly (as mine wasn’t when it was getting very “high” performance) and this will result is “perfect” hashing that will not represent true performance.

krasse · December 27, 2010, 9:19pm

I don’t know if you refer to my “iteration” test results but I simply use the same random integers in the put-test.

delt0r · December 28, 2010, 11:31am

sounds like its my end. I will look into it. It really shouldn’t be that slow.

Nate · December 28, 2010, 12:03pm

I messed around and implemented the benchmarks with Caliper. The links are below. There is data for client/server VMs, 32/64bit VMs, 2000/10000/50000 map entries, and all combinations of those. Note that you can scroll down and uncheck stuff under the “Variables” section to hide information you don’t care about. You can also use the left/right arrows in the table header to group the information differently. These benchmarks include d3ltor’s latest cuckoo.jar, LinkedHashMap, and there are now benchmarks for entry iteration. I separated the maps that use object keys from the maps that use int keys.

Benchmark source code

MapGet
MapPut
MapIterate

IntMapGet
IntMapPut
IntMapIterate

Caliper is pretty cool. It is somewhat lacking in docs though. I also managed to crash something server side for the online results. I had to create a new account and file a bug. I’ll probably use Caliper more often for benchmarking. The view of the data is awesome and the benchmarks are easy to write.

Some notes:

Seems like d3ltor’s cuckoo map has some issue with iteration.
The put numbers are X puts and then a clear. Unfortunately I don’t have a way to measure only the puts and not the clear.
CachingFastMap had a bug in clear, will be fixed next time I do a run.
IntMap uses Integer.MIN_VALUE to represent an unused key. This makes initializing the array ghetto. Need to try using zero internally (eg by adding Integer.MIN_VALUE to the key) to do the same, though this means a subtraction when getting a key out of the map.

delt0r · December 28, 2010, 8:51pm

Its probably my code that crashed the server. :persecutioncomplex:

I found my problem. I was being so stupid that i can’t believe that i did that. I am sure that even a drunk monkey would not have done what i did…

For cuckoo hashing you use 3 (in my case) independant hashes. Only i did this…


h1=hash(o.hashCode());
h2=hash(h1);
h3=hash(h2);

So i have in effect a single hash code. Since a collision in the first hash code will produce a collision for all 3. As a result my load factors where around the 5% range!

This is now fixed. Also i have added a Pure int key hash map too. Its quite a bit faster.

Hopefully Nate you could run my new code so i don’t look so bad. :-\

I should add that my implementations do not return backed Collections for the map methods that return them. It creates new Collections.

Nate · December 28, 2010, 10:38pm

Glad this stuff proved useful.

The server only collects the data for a run and displays it. Bug is here:

Running new benchmarks now! I included CIntHashMap, fixed CachingFastMap, and added IntMap2 which internally uses 0 for an empty key (Integer.MIN_VALUE is still an invalid key).

BTW, the cuckoo.jar attached to the post wasn’t as newer as the one at your URL. Maybe easier to just host in one place.

There is no need to calculate all 3 hashes up front. You could move the calculation to just before it is needed. Not a big deal, but every little bit helps.

delt0r · December 28, 2010, 11:22pm

Updated the attachment. I will not be at this university for much longer. So rather than another dead link, i wanted the attachment.

I do a little bit of lazy hashing. Not much, but put, get and remove have it. Its does not make much difference. Cache access patterns and .hashCode() seem to be the big overheads.

Nate · December 29, 2010, 6:22am

d3ltor, your cuckoo map looks much better now, though iteration is slow from putting everything into a Set first.

I wish I could see the int map results but the Caliper results site is still broken.

delt0r · December 29, 2010, 8:27am

Iteration is something i almost never do with a hash map, and I often don’t want backed copies. That’s why it did it that. However since it does produce such poor performance, and its in fact breaking the contract of Map, maybe i should revise this?

Oh and Thanks Nate for all the hard work. ++

delt0r · December 29, 2010, 10:04am

I checked a few things. Turns out that Collections.* and other utils use iteration a lot, and this just would not work with my classes. Also i was iterating though things sometimes.

So now my Maps return fully backed Collections and iterators. Iteration is about 30-80x faster.

Nate: appreciation*=appreciation

krasse · December 29, 2010, 10:20am

Thanks Nate for all your work and for showing me all those tools that I didn’t know existed!

Nate · December 29, 2010, 11:19pm

Benchmarks updated. CHashMap iteration is definitely more in line with the other maps now.

d3ltor, have you thought of using a “stash” for keys that would otherwise cause a rehash? Maybe this would let you get away with only 2 hashes and/or reduce rehashes. I wonder how often you see a rehash?

Nate · December 30, 2010, 5:39am

I’ve been messing with my own cuckoo implementation, doing int keys first. I’ve implemented both 2 and 3 hashes and I’m not seeing much of a difference, even with different load factors and initial capacities:

CuckooPut3
CuckooGet3

I expected a 0.9 load factor to have fewer collisions and cause the 2 hash cuckoo to rehash. Turns out in both cases a single rehash occurs due to unrecoverable collisions, the 3 hash cuckoo just runs into a problem later. I just realized I’m limiting the number of bucket “pushes” due to collisions to 100. This should probably be based on (or equal to?) the capacity. Sure enough, removing the limit allows the 3 hash cuckoo to have 50k items without a rehash (not shown in above benchmarks). Checking the max number of 3 hash cuckoo pushes for 50k random integer keys and 0.9 load, I see it takes ~90 to ~160 loops (a range due to the “random walk”). The max for 50 (not 50k) random int keys and 0.9 load is ~19 to ~70. So it seems for small capacities, the limit may be > capacity. What would be a good way to determine the limit?

The 3 hash cuckoo doesn’t seem to incur much penalty for the extra hash, so I think I’ll go with it. I’m still not sure about a stash. It could allow a lower “push” limit, which might save time on puts while also avoiding rehashing. For a 3 hash cuckoo, 50k random int keys and 0.9 load causes only 0 to ~5 collisions to loop more than 5 times, even though some of these collisions loop ~90 to ~160 times, as described above. So for a 3 hash cuckoo, the stash would stop some of this excessive looping at the cost of having to check every key in the stash if a key otherwise could not be found on a get.

Source link in the first post has been updated with the latest. My cuckoo classes aren’t finished, but they and the benchmarks are there if anyone wants to check them out. Code reviews are appreciated!