tag:blogger.com,1999:blog-3973020588456062013.post6445045609003550627..comments2020-08-13T13:46:09.690-07:00Comments on Mostly mangling: NASAM: Not Another Strange Acronym Mixer!Pelle Evensenhttp://www.blogger.com/profile/03828317178444752816noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3973020588456062013.post-13699569751573501732020-08-04T12:51:14.366-07:002020-08-04T12:51:14.366-07:00I'm using a linear probing hash table with bac...I'm using a linear probing hash table with back shift deletion (https://github.com/rigtorp/HashMap) and have been using the Murmur3 mixer to hash 64bit integers. Since it's a linear probing hash table it's important to have a good hash.<br /><br />I tried using your improved moremur, splitmix, rrmxmx and in addition hardware assisted crc32:<br /> struct Hash {<br /> size_t operator()(uint64_t h) const noexcept {<br /> return _mm_crc32_u64(0, h);<br /> }<br /> };<br /><br />It turns out that crc32 results in slightly better performance on my workload. The other ones gives identical performance. In the end it seems that hash table performance is not very sensitive to the choice of hash function, it just needs to be good enough.<br /><br />I tired using murmur but replacing the constants with truncated values of sqrt(2) and the golden ratio and it's just as good:<br /> struct Hash {<br /> // primes near 32 + sqrt(2) + golden ratio<br /> size_t operator()(uint64_t x) const noexcept {<br /> x ^= x >> 23;<br /> x *= 0xf553b2c6e459cdafUL;<br /> x ^= x >> 29;<br /> x *= 0x8c579260172965b1UL;<br /> x ^= x >> 31;<br /> return x;<br /> }<br /> };<br /><br />It seems that the xor-shift-mult construction is quite robust to the choice of constants. Using shifts that are close to 32 and constants that are random seems to result in a decent hash function.Erik Rigtorphttps://www.blogger.com/profile/12054256810184481856noreply@blogger.comtag:blogger.com,1999:blog-3973020588456062013.post-67749745027722222842020-08-04T11:20:33.418-07:002020-08-04T11:20:33.418-07:00I found this paper (https://bigdata.uni-saarland.d...I found this paper (https://bigdata.uni-saarland.de/publications/p249-richter.pdf) were they show that even the overhead of Murmur finalizer over multiply-and-shift is not always worth it.Erik Rigtorphttps://www.blogger.com/profile/12054256810184481856noreply@blogger.comtag:blogger.com,1999:blog-3973020588456062013.post-26284089478885071262020-08-04T05:45:39.188-07:002020-08-04T05:45:39.188-07:00The operations used are restricted since I don'...The operations used are restricted since I don't want to use any x86-intrinsics. Regardless of hardware/software platform, the performance should be at least decent.<br /><br />Maybe I should post a generator that uses 2 or 3 rounds of AES that at least on Ryzen is very fast (faster than Romu2jr, SFC64, Xoroshiro*) with a guaranteed period 2^128 and about 0.35 cpb on a Ryzen 1700X.<br /><br />I did some basic experimenting with AES but Other Parts Of Life (most likely "my day job") came in between. I'll post some snippets with benchmark data as soon as I've verified that I didn't abandon the experiments due to statistical failures.<br /><br /><br /><br />Pelle Evensenhttps://www.blogger.com/profile/03828317178444752816noreply@blogger.comtag:blogger.com,1999:blog-3973020588456062013.post-76246346279349556182020-08-04T04:56:28.808-07:002020-08-04T04:56:28.808-07:00Thanks for your kind words. Indeed it is a trade o...Thanks for your kind words. Indeed it is a trade off.<br /><br />IIRC, someone already did just that, tracing the Pareto frontier with NASAM included but I can't seem to find the URL now. It *might* have been Tommy Ettinger but Google doesn't help me right now.Pelle Evensenhttps://www.blogger.com/profile/03828317178444752816noreply@blogger.comtag:blogger.com,1999:blog-3973020588456062013.post-83457885656931685062020-08-03T19:35:28.946-07:002020-08-03T19:35:28.946-07:00Also have you looked at constructions using carry ...Also have you looked at constructions using carry less multiplication (https://www.felixcloutier.com/x86/pclmulqdq) like https://github.com/lemire/clhash ? Erik Rigtorphttps://www.blogger.com/profile/12054256810184481856noreply@blogger.comtag:blogger.com,1999:blog-3973020588456062013.post-8072295522971064912020-08-03T19:08:45.370-07:002020-08-03T19:08:45.370-07:00Hej Pelle! I have a need for fast lookups and inse...Hej Pelle! I have a need for fast lookups and insertions of 64bit integer keys in hashtables. As such I've been reading your awesome articles on 64bit mixing functions.<br /><br />It's possible to construct a lot of different mixing functions, but for practical applications there is a trade off between quality of the hash function and speed. We can use a zero overhead identiy hash function or use a very strong cryptographic hash function at the other end of the speed spectrum. Depending on the hash function quality we will see different collision rates in a hash table. There is some application dependent optimal trade off between collision rate and hashing speed that maximizes performance. The applications optimal hash functions must lie on the Pareto frontier. As such you can construct this Pareto frontier and discard any mixing function that is strictly dominated.<br /><br />I would love to see a article analyzing the Pareto efficiency of all the mixing functions you have presented.<br /><br />Thank you for your interesting articles!Erik Rigtorphttps://www.blogger.com/profile/12054256810184481856noreply@blogger.com