map performance

[Roquen]

An interesting addition to your set of graphs would be a plot of memory requirements.

[delt0r]

Nate, yes but i didn't bother. 3 keys really doesn't make a huge difference. One of the appeals of cuckoo is that its quite simple. Adding a stash just adds more complications. In particular most of my usage does not require growing the hashMap once it gets to its proper size. In this case rehashes are very rare (like 1 in 10000). This can of course result in a map with a load factor below what was asked for. But again this really is just as a hash table. In these cases in my code i have made some real gains.

But in most cases Map performance just does not matter. Everything else you are doing is many times slower anyway. 

[Nate]

An interesting addition to your set of graphs would be a plot of memory requirements.

Memory charts would be sweet. Caliper doesn't seem to have anything built-in. :/

Nate, yes but i didn't bother. 3 keys really doesn't make a huge difference. One of the appeals of cuckoo is that its quite simple. Adding a stash just adds more complications. In particular most of my usage does not require growing the hashMap once it gets to its proper size. In this case rehashes are very rare (like 1 in 10000). This can of course result in a map with a load factor below what was asked for. But again this really is just as a hash table. In these cases in my code i have made some real gains.

But in most cases Map performance just does not matter. Everything else you are doing is many times slower anyway. 

I may try out a stash with 3 hashes and see how it affects puts. I am mostly interested in get performance, but this stuff is fun. I am pretty sure a stash will avoid many hundreds of pushes. I'm guessing even small maps will benefit, as I saw a 64 element map loop 70 times on a put.

Re: performance, besides the fun of it all, I think this could be nice to use on Android. There using HashMap sometimes isn't feasible, since it allocates on put and GC is slooow.

Games published by our own members! Check 'em out!

[delt0r]

I was under the impression that Android was catching up to hotspots. At any rate i do very little allocation. But my target was always the desktop or servers.

BTW i use a randomized "pushing", so i pick the "push" hash randomly from the 3. I don't see loops very often. But like you, I wanted fast contains/get. And cuckoo really shines there.

[Nate]

Android has a JIT now, but GC is still slow AFAIK.

Ahhh, I had a bug. I don't see loops very often now. Adding 50k random ints the max number of pushes required for a single put is ~7 to ~15.

I have a feeling that the hash functions I stole from delt0r aren't different enough. I ran into this:

1   2   3

hash1(1620722920) & 63 == 24 hash2(1620722920) & 63 == 24 hash3(1620722920) & 63 == 24

Here are my hash functions:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17

private static final int PRIME1 = 0xbe1f14b1; private static final int PRIME2 = 0xb4b82e39; private static final int PRIME3 = 0xced1c241; private int capacity = 64; private int hashShift = 31 - Integer.numberOfTrailingZeros(capacity); private int hash1 (int h) {    h *= PRIME1;    return h ^ (h >>> hashShift); } private int hash2 (int h) {    h *= PRIME2;    return h ^ (h >>> hashShift); } private int hash3 (int h) {    h *= PRIME3;    return h ^ (h >>> hashShift); }

When all 3 hashes are the same, the cuckoo can get stuck in a loop until it gives up and doubles the size of the backing array. Any ideas on how the hash functions could be designed to avoid this?

[pjt33]

When all 3 hashes are the same, the cuckoo can get stuck in a loop until it gives up and doubles the size of the backing array. Any ideas on how the hash functions could be designed to avoid this?

Compute all three at once and fix them:

1   2   3   4   5   6   7   8

h1 = f1(hash) % capacity; h2 = f2(hash) % (capacity - 1); h3 = f3(hash) % (capacity - 2); if (h2 >= h1) h2++; int inc = 0; if (h3 >= h1) inc++; if (h3 >= h2) inc++; h3 += inc;

[delt0r]

well there is a proof that if a1 and a2 are different then
H(a1)=H(a2) with proablity of 1/(2^wordsize)
where H(x) is alsmost what i use...
(p*x)>>>(32-wordsize)
for odd p.

Hence the reason i used it. My tests I use 3 random 32 bit primes p. This "family" of hash functions has been shown to be good for a number of cases, in particular cuckoo hashing.

Of course using just 4 bits, even a perfect hash function has a probability of 1/256 for a 3 way collision. Perhaps more importantly the probability of no collision in all three functions is only 82%.
 

[delt0r]

Ops my math was wrong.. Well its correct for 4 bits. But 63 is 6bit... so the probabilities are 1/(64*64) for a 3 way collision, and 95.4% chance of no collision at all (1 in 20).

If you leave out the h^ part you would have all different results i think. Note you can tune the random primes.

BTW pjt33, % is horrendously slow.

[delt0r]

NOTE: Nates  post below was lost due to the attack. However i still get email notifications.

Leaving out the h^ didn't result in different results. Tuning the primes allows the above input to succeed, but fails with other input. If your math is right for the 3 way collision probability it seems difficult to have efficient memory usage for small maps without a stash. Even with larger maps, getting unlucky means you'll waste huge amount of memory (and time rehashing) without a stash.

Here is a paper about cuckoo hash functions:
http://www.siam.org/proceedings/soda/2009/SODA09_087_dietzfelbingerm.pdf
Unfortunately my greek isn't that good. Could someone translate the essence of this to layman terms? Does this help us choose better hash functions?

This recent paper is neat, it talks about both queuing cuckoo moves and using the queue as a stash:
http://www.wisdom.weizmann.ac.il/~naor/PAPERS/deamortized_cuckoo.pdf

It does not matter how perfect your hash function. If you want high load factors (ie 90%) then you need large table sizes for the statistics. There is no way around it. Its roughly called the birthday paradox, which is that the probability of any 2 people having the same birthday in a room is much higher than people intuitively think.

Example: A table of size 1000 with 100 entries. For just one hash function the probability of at least one collision is 1-P{no collision} equals .99436.

But now lets consider just two entries. The probability that all 3 hash functions all distinct values is 0.997. The probability that all 100 entries all have 3 distinct values for all 3 hash functions however is just 0.741. In other words without even considering pairwise collisions there is a 25% chance that at least one entry returns the same value for 2 of its 3 hash functions.

We could continue. However I implemented, a "perfect hash function" (ie true random, well SecureRandom) and the results for my tests were the same the hash function I used above. I still typically leave the load factor at about 0.75 since puts a bit quicker here.

[Nate]

I'm going to move my cuckoo discussion over to delt0r's thread. I'll start a new thread to post map performance charts as this one has become somewhat long and unkempt.

1	throw new ThreadDeath();