Xxhash: XXH as a hash function family

[sillycross]

I encountered some issues while trying to use XXH as the hash function for Cuckoo Hashing.

Currently I'm only working on 64-bit keys. Cuckoo Hashing requires two independent hash functions. I did the following attempts to get two hash values out of XXH:
(1) Use two different seeds. It turns out that the two hash results are somehow correlated and the hash table is unable to reach its theoretical max load factor.
(2) Change the PRIME32_3 in PROCESS4 to PRIME32_1 to get a different hash result. This worked for uniformly random 64-bit key distribution, but I have no idea how well it is in general (for other distributions or longer keys).

So I'm wondering what is the recommended practice to get two (or more) independent hash values from XXHash.

Thanks for your time!

[Cyan4973]

Hi @sillycross

Using 2 different seeds to generate 2 different hashes is perfectly acceptable practice.
Another possibility is to add some bytes to input, which achieves about the same objective, but is more problematic for buffer management.

I'm surprised you found out that the 2 hashes are somehow related.
The hash function has been using a bit-level analyzer to verify if there was any correlation between 2 hashes using 2 different seeds, and has not found any. So it was expected to be good.
If your test show otherwise, it could be that the test coverage used when designing xxh64 was not good enough, and I'll be glad to know more.

[sillycross]

Hi @Cyan4973

Thanks for the quick response!

Here are some more details of my test.
2-ary cuckoo hash is able to achieve 50% load factor if the hash functions are independent.
I initialized a table containing 2^25 slots, and insert random 64-bit integers until a cuckoo insertion fails. So if the two hash functions are both good and independent, it is expected to fail at around 2^24 insertion.

Below is the load factor reached at insertion failure with a few pairs of seeds:
0 and 233: 6.2%
0 and 12345: 13.4%
233 and 12345: 13.4%
2959555477 and 534897851 (two random primes): 22.5%
2959555477 with PRIME32_1 and 534897851 with PRIME32_3: 50.3%
0 with PRIME32_1 and 233 with PRIME32_3: 50.1%

As you can see, without changing the multiplier, the load factor can only reach from 6.2% to 22.5% (I tried a few other random primes as well). But if I use different multipliers in PROCESS4, one can reach maximum load factor even with the "bad" seeds like 0 and 233.

You can find the code here: https://gist.github.com/sillycross/80ea5dceba6c17d27a688175640b7058
Line 58 and 60 are the lines that change the multipliers. Line 36 and 37 are the two seeds.

[Cyan4973]

Thanks for details @sillycross .
I believe you made an excellent investigation.

Somehow, it seems the bit-correlation test wasn't enough.
I'll be sure to add a cuckoo hash test during the design stage of XXH128.
It's a pretty straightforward one as you describe it.

For a solution,
it seems you would need 2 different finalization stages,
one using PRIME32_3, aka current finalization stage,
and another one using PRIME32_1, for better independence of the hash produced.

It's difficult to add the second variant, as it breaks compatibility with established user base.
It might be possible to add it by labelling clearly as an "alternate ending".
However, there is a risk of confusion, which must be considered.

On short term, you are better off creating your own variant with this second finalization stage.
This will solve your problem right now.

On medium term, it seems a good idea to solve this issue in a generic way within xxhash library.

Btw, what's the "typical" size of your inputs ?

[sillycross]

Thanks for the response @Cyan4973 !

On short term
On medium term

I totally agree with you regarding the solution. Though I think more testing is still needed, to confirm that whether only changing the finalization part alone will prove sufficient, or we will also need to change the primes in the accumulation parts for keys that are longer.

Btw, what's the "typical" size of your inputs ?

At the current stage the inputs are supposed to be short strings (maybe 8-32 bytes?), but I might consider a little longer strings (128 bytes or so?) in the future as well depending on how the project works out.

[Cyan4973]

2-ary cuckoo hash is able to achieve 50% load factor if the hash functions are independent.

I'm interested in above sentence.

• What is 2-ary cuckoo hash ?
  
  
  
  • I understand cuckoo hash in general, but there are many parameters that can be selected, so I'm not sure which exact variant you test.
  
  
  • does that mean 2 slots per position ? or 2 possibles positions (hence 2 hashes) per input ?
  
  
• 50% load factor : at which point exactly does the process ends ?
  
  
  
  • does it stops as soon as a row is filled ?
  
  
  • or as soon as an already filled raw receives a new element, but before any cuckoo displacement ?
  
  
  • or after one cuckoo displacement ?
  
  
  • or after all possible cuckoo displacements, reaching a circular dependency issue ?
  
  
• Any source about this 50% load factor ?

[sillycross]

What is 2-ary cuckoo hash ?

It means there are two independent hash functions, i.e. a key will end up being positioned in either slot h1(key) or slot h2(key).
You can k-ary cuckoo hash for any k>=2. 2-ary gives you a maximum load factor of 50%, 3-ary gives you a maximum load factor of 91%. See https://en.wikipedia.org/wiki/Cuckoo_hashing#cite_ref-mitzenmacher2009survey_3-0

50% load factor : at which point exactly does the process ends ?

In my code it ends after 10000 cuckoo displacements, just for the ease of implementation. You can change it so that it only ends after a real cycle is detected, but that will not affect the result since with high probability the length of the cycle will be less than 10000.

Any source about this 50% load factor ?

The link in wikipedia above states about it. You can also verify it yourself by writing not many lines of code.

[sillycross]

Hmm, I just played a little bit more about the independence using different seeds.

I tried to create a bloom filter, and test the false positive rates.
The length of the bloom filter table is either a prime, or a power of 2.
The hash functions are either different seeds with default multipliers, or different seeds with different multipliers as well (all are random primes).

Below are the results:

Settings: using prime table size = no, using different XXH multipliers = yes
Expected Error Rate: 0.00009995
Actual Error Rate: 0.00010650 (+6.6%)

Settings: using prime table size = yes, using different XXH multipliers = yes
Expected Error Rate: 0.00010013
Actual Error Rate: 0.00011375 (+13.6%)

Settings: using prime table size = no, using different XXH multipliers = no
Expected Error Rate: 0.00009995
Actual Error Rate: 0.00015325 (+53.3%)

Settings: using prime table size = yes, using different XXH multipliers = no
Expected Error Rate: 0.00010013
Actual Error Rate: 0.00013975 (+39.6%)

So it looks like, whether the hash table size is a prime or a power of 2 does not really matter. Using different multipliers slightly improves the independence of the results.

Code attached: https://gist.github.com/sillycross/0747ed177fa87fdd9512d2d79db5c371
The expected error rates are computed using https://hur.st/bloomfilter/?n=3500000&p=&m=67095419&k=

Also, for 3-ary cuckoo hashing, XXH worked fine with 3 seeds, even without changing the multipliers.
So I kind of think the really bad case is only 2-ary cuckoo hashing.

[Cyan4973]

Thanks for the pointers @sillycross , it's a very interesting read !

Small request :
Another way to use a single hash in order to generate 2 keys is to grab a different set of bits from the same hash. This mostly works cleanly for a power of 2 table size.
For XXH64, this works as long as you need <= 32 bit to designate a position in a 2-ary construction (and <= 21 bit for 3-ary).

Would you mind testing if this allows reaching the theoretical limit of 50% for 2-ary and 91% for 3-ary ?

The bit correlation test is supposed to be very strong for this scenario,
but given that it failed the multi-seed scenario,
I'm now wondering if it does work as well as claimed.

[sillycross]

Splitting 64-bit hash results from XXH64 into two 32-bit integers, and using the lower bits reached 50% load factor for 2-ary cuckoo.

void GetHash(uint64_t key, uint32_t& h1 /out/, uint32_t& h2 /out/)
{
uint64_t h64 = XXH64(reinterpret_cast(&key), 8 /len/, 0 /seed/);
h1 = h64;
h2 = h64 >> 32;
h1 %= HtSize;
h2 %= HtSize;
}

[Cyan4973]

Okay, thanks for the verification !
So the bit correlation test is not completely bad.
It's just not thorough enough on the multi-seed scenario. That's a good clue to improve the test system !

[sillycross]

FYI it looks like XXH64 with different seeds is much more problematic than XXH32.
As stated in the previous comments, XXH32 can at least reach 6% ~ 22% load factor.
For XXH64 the situation seems to be much worse:
seed 0 and 233: fail at 20255 insertion (0.06% load factor)
seed 2959555477 and 534897851: fail at 7875 insertion (0.02% load factor)

[sillycross]

Sorry please ignore the previous comment, it's a stupid c_i I made..
actually XXH64 is working ok with different seeds. You can reach 50% load factor with XXH64

[Cyan4973]

So the multi-seed correlation issue is limited to XXH32 ? not XXH64 ?

[sillycross]

Yes, I think so, at least as far as what I have tested.

[sillycross]

Okay, I think things are kind of interesting now.

The following fix solved the correlation issue for XXH32:

#define PROCESS4 \
h32 += XXH_get32bits(p) * PRIME32_3; \

In the above code, change += to ^=

However, it looks like I cannot reproduce the correlation issue by changing the ^= to += in XXH64_finalize (even if I change the PROCESS8 to two PROCESS4).

Anyway, it seems really really wired that += and ^= is making such a big difference for XXH32....

[Cyan4973]

The finalization stage of XXH64 is a bit stronger than XXH32.
This was required because a new test was introduced between the 2 versions (related to bit correlation by the way), and the simpler finalization of XXH32 was failing it.

However, it's nice to know that a simple + => ^ can be that effective. This will be useful to design a lighter but still efficient finalization stage.

[sillycross]

I know nothing about bit analyzer, but would it be possible you concatenate XXH32(key, 0)||XXH32(key, 233) to get a 64-bit value, and feed it into the analyzer to see if it can find any correlation?
I'm just kind of curious about it.

[Cyan4973]

yes, that's a good idea, it's definitely doable.

Problem is, the test system requires a bit of setup time, and I have not invested time into it recently.

Also : the newer test that was added for XXH64 failed for XXH32, and it might be the right one to run to ensure proper randomization for different seeds.

[sillycross]

Thanks, this has solved the issue for my project's purpose anyway.

Changing += to ^= in XXH32 will definitely introduce back-compatibility problem, and as most systems are already 64-bits so there seems not a good reason to use XXH32 (I was using it only because I need to vectorize compute multiple string's hashing value), so i'm not sure how worthy it is to introduce an extra XXH32 function just to solve this issue.
Well I'm not the guy maintaining the repo so it's not a problem for me to worry anyway :)

[sillycross]

Update regarding the correlation between multiple seeds of XXH32:
It looks like changing += to ^= is not sufficient. It solved the issue for uniform random data, but issue still exists on another distribution (I can describe it / simplify it if you think knowing that would be helpful).
XXH64 is still good enough to reach near-maximum load factor.

[Cyan4973]

Thanks for the feedback.
I will try the ^ variant on the new test that XXH32 failed,
and see if it solves the situation (for this test), or if it is still flagged as a fail.
The second case is more probable, given your feedback,
It would hint the new test added for XXH64 works well enough to detect this flaw.