When Bloom filters don't bloom
In the final program `mmuniq` I did a couple of, I think, interesting hacks.<p><a href="https://github.com/cloudflare/cloudflare-blog/blob/master/2020-02-mmuniq/mmuniq.c" rel="nofollow">https://github.com/cloudflare/cloudflare-blog/blob/master/20...</a><p>First, I used a hash function using aesni (aesenc) instruction set. See this:<p><a href="https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab5a" rel="nofollow">https://gist.github.com/majek/96dd615ed6c8aa64f60aac14e3f6ab...</a><p>While I have little proof it's a good hash, it seems enough, and is _slightly_ (5-10%?) faster than siphash24 in this context.<p>Then I mixed counting hash with finding new lines \n. This allows me to do only one user-data load into XMM registers.<p>Most importantly, to offset the RAM latency cost, I'm doing 64 prefetches as I parse the input, and only after this I actually touch the hash table. The memory latency is still the biggest time sync, but at least this seem to speed up the program 2x or more. Hash table without this batching+prefetch is 6-8 seconds. With batching goes down below 3s.<p>I suspect linear probing / open addressing of the hash table may have some penalty. While it plays nicely with the cache prefetch, it generally leads to longer chains. This means we need to keep the hash table sparse, not loaded above 0.6-0.75. See this<p><a href="https://en.wikipedia.org/wiki/File:Hash_table_average_insertion_time.png" rel="nofollow">https://en.wikipedia.org/wiki/File:Hash_table_average_insert...</a><p>from <a href="https://en.wikipedia.org/wiki/Hash_table" rel="nofollow">https://en.wikipedia.org/wiki/Hash_table</a>