hashify v0.3: compile-time perfect hashing, now 4 to 12 times faster than phf
hashify is a procedural macro crate that turns a fixed set of keys into a perfect hash lookup at compile time. The generated code has no runtime dependencies, never allocates and contains no unsafe. We use it throughout Stalwart to recognise IMAP commands, JMAP properties, header names and a few hundred other keyword sets.
hashify 0.3 has been rewritten with a new lookup engine and one less decision to make. Earlier versions had you choose between the tiny_* macros and the regular ones. Now every invocation looks at its keys and generates what suits them:
- Up to 16 keys, you get a decision tree in the spirit of
gperf --switch: amatchon the key length, then on whichever byte (or XOR of two bytes) tells the remaining keys apart. No hash is computed at all, and LLVM turns the tree into jump tables and comparisons against constants. - From 17 to 64 keys, the macro searches for a seed that sends every key to its own slot in a power-of-two table, so a lookup is one multiplication, a shift and a load.
- Past 64 keys it builds a minimal perfect hash function that borrows from two recent papers, PtrHash by Ragnar Groot Koerkamp and PHast by Piotr Beling and Peter Sanders. Keys are split into buckets, each bucket stores a single byte (its pilot), and a key's slot comes from its hash and that pilot through two multiply-high operations. The pilot search evicts conflicting buckets the way cuckoo hashing does, and that is what lets one byte per bucket suffice: for typical inputs the table ends up with exactly one slot per key. hashify 0.2 was built on PTHash; the compact pilots and the eviction come from the newer work.
This is how it compares with phf 0.14, per lookup, measured with criterion on an Apple M5 Max and Rust 1.98. "In order" looks up every key once in a fixed order; "random" performs 4096 lookups in a shuffled order, half of them for keys one bit away from a real one.
| Keys | phf | hashify map! |
hashify fnc_map! |
|---|---|---|---|
| 9 HTTP methods, in order | 8.38 ns | 0.67 ns | 0.68 ns |
| 9 HTTP methods, random | 8.23 ns | 1.51 ns | 1.50 ns |
| 26 IMAP commands, in order | 8.69 ns | 0.93 ns | 0.88 ns |
| 26 IMAP commands, random | 8.55 ns | 1.00 ns | 1.12 ns |
| 128 Sieve keywords, in order | 8.72 ns | 1.73 ns | 1.96 ns |
| 128 Sieve keywords, random | 8.41 ns | 1.80 ns | 1.89 ns |
| 149 charset names, in order | 9.54 ns | 1.68 ns | 1.72 ns |
| 149 charset names, random | 9.22 ns | 1.76 ns | 2.14 ns |
| 2125 HTML entities, in order | 8.93 ns | 1.72 ns | 1.76 ns |
| 2125 HTML entities, random | 8.66 ns | 1.82 ns | 1.90 ns |
That works out to 4.3x to 12.4x faster than phf, and the difference is biggest on small sets, where the decision tree never hashes anything.
The switch points between strategies came out of benchmarks and were checked against the lookups Stalwart performs, so if your key sets tell a different story, I'd like to see them. Code, benchmarks and docs live at https://github.com/stalwartlabs/hashify.
PS: I read the No more core dumps post and I think this announcement meets the criteria.