--- title: "If the Keys Are Known at Compile Time, Stop Hashing at Runtime" slug: "perfect-hashing-compile-time" language: "en" date: "2026-10-28T01:55:00.642Z" updated: "2026-10-28T01:55:00.000Z" description: "A perfect hash turns string lookup into five cycles. The trick is moving collision resolution into the compiler, and one careful vector comparison." canonical: "https://fix.slopit.io/perfect-hashing-compile-time/" tags: ["cpp", "performance", "algorithms", "systems"] --- A lot of software is a string-to-value lookup wearing a costume. HTTP methods, header names, URL schemes, language keywords, ticker symbols. In C++ the default answer is `std::unordered_map`, which works, and which pays at runtime for a flexibility nobody uses: hash the whole string, pick a bucket, follow a pointer, compare, maybe walk a chain. Daniel Lemire's post on perfect hashing makes the obvious point that the keys are known when you write the code, so the collisions can be solved then, not now. The result is a lookup in about five cycles. ## The old idea, done at compile time A perfect hash function maps a known key set to slots with no collisions. The GNU `gperf` tool has generated such functions since 1989. The construction is almost embarrassingly simple: the slot is the key length plus a couple of small values looked up by character position, modulo a power-of-two table size. For the HTTP methods, using only the first character: set `asso['G'] = 0`, `asso['P'] = 1`, `asso['D'] = 0`. Then GET lands in slot 3, PUT in 4, POST in 5, DELETE in 6. To look up PUT, compute slot 4, compare one stored key, done. To look up PATCH, land in slot 6, compare against DELETE, miss. No probing, no chain, one comparison. The association values are found greedily at compile time: sort characters by how many keys they touch, try 0, 1, 2, … until nothing collides, never revise. That bounded work matters because C++ compilers cap what a `constexpr` function may do. The library Lemire built with Francisco Geiman Thiesen does this in ordinary C++23, with no external code generator: you write `make_perfect_map, ...>()` and the compiler searches for the hash function while compiling. ## The second half is the interesting one A perfect hash gets you to the right slot cheaply. It doesn't solve the comparison — you still have to check that the string you looked up matches the key stored there. The textbook comparison is a byte loop with a branch per byte, which is dozens of instructions and several hard-to-predict branches. Their approach treats the key as a vector: load 16 bytes unconditionally, even if the key is three bytes long; use a shuffle instruction to zero the bytes past the end; compare once. The stored keys are zero-padded at compile time, so one vector comparison handles the whole thing. Roughly forty instructions and eight branches become five instructions and no branch. There's a delightful hazard in that trick. Reading 16 bytes from a 3-byte key is out of bounds. It's safe as long as the read doesn't cross a page boundary, and pages are at least 4 KB, so the code checks whether the address is within 16 bytes of the end of its page and takes a slower path if so. They replaced several unpredictable branches with one branch that is almost always the same. That's the kind of optimisation that only makes sense if you know the memory model, and it's a good reminder that "undefined behaviour" and "works on every real machine" are different claims. This one is careful about the distinction. ## The numbers On an Apple M3 Max with AppleClang 15, looking up the 20 standard HTTP header names in random order: - This library: ~1.3 ns per lookup, about 5 cycles. - `gperf`: 7.7 ns. - Abseil's `flat_hash_map`: 10.9 ns. - `std::unordered_map`: 16.6 ns. That's roughly 13x faster than the standard library. Across seven key sets — from six URL protocols to the S&P 100 tickers — it stays between 1.2 and 2 ns, 3 to 6 times faster than `gperf`, and up to 17 times faster on JavaScript reserved words, where `gperf` struggles. On an M4 with URL protocols, it exceeds a billion lookups per second. The explanation is boring in the best way: no function call, no pointer chase, no heap node, almost no branch misprediction. The processor retires over eight instructions per cycle. ## What it costs Two things, and both are worth naming. The keys are frozen at compile time. That's fine for HTTP methods and language keywords; it's wrong for configuration, plugin registries, or anything loaded at runtime. You're trading flexibility for a constant factor, and the trade only works if the flexibility was never used. And compile time is now doing real work. The greedy search is bounded, but it's still search, and it's running inside a `constexpr` evaluation with compiler limits. For a handful of keys that's nothing; for a large set it becomes part of your build. ## The general lesson Move work to compile time when the inputs are static. That sentence covers a lot of good engineering: constexpr, templates, code generation, precomputed tables, ahead-of-time compilation. It also covers a lot of bad engineering, when the inputs weren't static after all and someone shipped a rebuild to change a string. The perfect-hash post is a clean case because the boundary is obvious: the keys are literals in your source. The lookup table costs nothing at runtime because the collision resolution happened in the compiler. Five cycles is what's left after you delete the part of the problem that didn't need to exist. *Source: [Billion-query-per-second lookup tables in C++ — Daniel Lemire](https://lemire.me/blog/2026/10/26/billion-query-per-second-lookup-tables-in-c/).*