Post

Ragnar {Groot Koerkamp}
@curiouscoding.nl

My secret 4th ALGO paper is out! We show a tight space lower on non-minimal k-perfect hash functions, generalize PtrHash into a non-minimal k-PHF, and then use it to develop a hash set implementation that is up to 1.6x faster than other hash sets! With Stefan {Hermann, Walzer} and Peter Sanders

arXiv cs.DS Data Structures and Algorithms@csds-bot.bsky.social

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, Stefan Walzer: Non-minimal k-perfect hashing: Tight lower bounds and an application to fast static hash tables https://arxiv.org/abs/2607.07257 https://arxiv.org/pdf/2607.07257 https://arxiv.org/html/2607.07257

Ragnar {Groot Koerkamp}
@curiouscoding.nl

Basically: given a set of keys, we can use a 1-PHF to map the keys to distinct slots in an array. Then store the key itself in that slot to have a single-cache-miss hash set. Our k-PHF hash set variant maps e.g. k=8 64-bit keys to a cache line, and then uses SIMD instructions to check if it's there

0 reposts0 likes

Ragnar {Groot Koerkamp}
@curiouscoding.nl

So now, a non-minimal 8-PHF suffices, which only needs 0.08 bits/key at load factor 80%, compared to 0.86 bits/key for k=1 at load factor 80% or 1.44 bits/key for k=1 and a minimal PHF with load factor 1. Since it's 10x smaller, it fits in a lower cache and supports faster queries or larger inputs.

Ragnar {Groot Koerkamp}
@curiouscoding.nl

The main k-PHF-set speedup figure, with our results in blue. On my laptop (top row), the k-PHF allows throughput very close to the maximal memory throughput up to n=2^28, whereas previous methods only reached that up to 2^24. Also, it performs equally well for both positive and negative queries.

Ragnar {Groot Koerkamp}
@curiouscoding.nl

Great! I haven't done much work on the API and docs yet, and in fact the StaticHashSet part of it is for now only really exposed/used in the static_hash_set/src/main.rs. Feel free to play around with it, but otherwise I'll get to it over the weekend. Note also that it's only optimized for sets atm