tag:blogger.com,1999:blog-8891884956165580080.post395382491472990739..comments2022-01-03T11:01:08.576+01:00Comments on Database Architects: All hash table sizes you will ever needThomas Neumannhttp://www.blogger.com/profile/15209393663505917383noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-8891884956165580080.post-37218725289059285442020-10-11T20:26:24.688+02:002020-10-11T20:26:24.688+02:00Thank you for pointing out that problem. When rewr...Thank you for pointing out that problem. When rewriting the code for this blog post I introduced a silly mistake into the primality test and did not check the result... This is fixed now, I have updated the file to really use prime numbers.<br /><br />I have computed the magic values using the algorithm from Hackers Delight. The source code used to be available online, but apparently the domain has been captured by some domain grabber. You can find an implementation of that algorithm in the LLVM project (APInt::magicu I think).<br /><br />I could put the code on Github if you find that easier to use. It is just a single header anyway.Thomas Neumannhttps://www.blogger.com/profile/15209393663505917383noreply@blogger.comtag:blogger.com,1999:blog-8891884956165580080.post-75685501189519620612020-10-11T19:15:56.494+02:002020-10-11T19:15:56.494+02:00I've looked at the linked primes.hpp file and ...I've looked at the linked primes.hpp file and noticed that (currently) its primes array contains many non-prime numbers, e.g. 9, 15, 27, 33, 35, 45, 51 etc.<br /><br />That means that currently 724 of the 841 included hash table sizes aren't prime numbers.<br /><br /><br />Perhaps it's also worthwhile to just use the binary search functions from the algorithm STL header instead of re-implementing it in the pick method.<br /><br /><br />I'm wondering what library/method you used to compute the magic/shift values. Looking at an example it doesn't look like you have used libdivide for this. So, did you use another open source library for this or did you roll your own?<br /><br /><br />Have you thought about also publishing your code in a git repository - e.g. on Github? This would simplify its usage in other projects.Georg Sauthoffhttps://gms.tfnoreply@blogger.comtag:blogger.com,1999:blog-8891884956165580080.post-31042547076223603592020-02-07T09:08:23.265+01:002020-02-07T09:08:23.265+01:00Good point about the hash function range. Maybe in...Good point about the hash function range. Maybe indeed for unordered_map replacement it is too aggressive / unsafe. Especially with the _terrible_ default hash functions in some places. <br /><br />But for the "real" hash functions Daniel's solution might be a bit easier and faster. And allows completely arbitrary hash table sizes, not that it matters much :)<br /><br />cheerios!Marcinhttps://www.blogger.com/profile/14718662695714901635noreply@blogger.comtag:blogger.com,1999:blog-8891884956165580080.post-86643863432791199632020-02-07T07:43:33.477+01:002020-02-07T07:43:33.477+01:00Hi Marcin, when you look at the generated assemble...Hi Marcin, when you look at the generated assembler code you see that no (full) 128-bit computation is performed: https://godbolt.org/z/yoLmWk<br /><br />We intentionally perform two shifts in the code, one the get the upper word after multiplication and one for the result. The first shift is a no-op, as the MUL instruction always places the high result word in RDX anyway. Thus the code is quite cheap, even though it looks a bit expensive.<br /><br />The approach from Daniel Lemire has stronger requirements on the hash value, i.e., it requires that all hash values spread over the whole integer domain immediately. This makes it unsuitable for unordered_map, where some people use identity hashing or other very weak hash functions. Using modulo prime is more forgiving there.Thomas Neumannhttps://www.blogger.com/profile/15209393663505917383noreply@blogger.comtag:blogger.com,1999:blog-8891884956165580080.post-13429991336824609922020-02-07T00:37:03.539+01:002020-02-07T00:37:03.539+01:00Hey Thomas, good stuff as always. I was surprised ...Hey Thomas, good stuff as always. I was surprised about 0.63ns (2 cycles roughly!), esp. with 128-bit computations, but for independent computations it seems it actually works :)<br /><br />I also thought Daniel Lemire's alternative to modulo would be faster (https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/), but at least in my quick benchmark the difference was (surprisingly) very small, maybe 10-20%. Marcinhttps://www.blogger.com/profile/14718662695714901635noreply@blogger.com