A new C++ library for fixed sets of string keys has reported more than one billion lookups per second in a benchmark on Apple M4 hardware, illustrating the performance available when a program can build its lookup structure at compile time.
The work, by computer science professor Daniel Lemire and Francisco Geiman Thiesen, targets common tasks such as recognizing HTTP methods, header names, URL protocols or programming-language keywords. These applications often use a general-purpose hash map even though the accepted strings are known before the software runs and never change.
General hash tables must handle collisions, dynamic storage and arbitrary keys. The proposed approach instead creates a perfect hash function specifically for the supplied key set. Each recognized string maps to a unique slot, eliminating probing and linked collision chains during lookup. The concept is longstanding—the GNU gperf generator dates to 1989—but this implementation performs its search using C++23 compile-time evaluation and ships as a single header.
The hash combines the string length with small values from an association table indexed by selected characters. A power-of-two table permits the final reduction to use a bit mask. The compiler searches for association values that avoid collisions, using a bounded greedy process designed to stay within limits on constexpr computation. Runtime work can therefore shrink to a handful of loads, an addition and a mask before the candidate key is checked.
String comparison is also specialized. For short keys, the implementation loads a 16-byte vector, masks bytes beyond the input length and compares it with a zero-padded stored key. A boundary check selects a slower path when a wide load could cross a memory-page edge. The design trades multiple data-dependent branches for one boundary branch expected to behave consistently.
Lemire reported 1.3 nanoseconds per lookup for 20 standard HTTP header names on an Apple M3 Max using AppleClang 15. In that test, gperf took 7.7 nanoseconds, Abseil's flat_hash_map 10.9 nanoseconds and std::unordered_map 16.6 nanoseconds. Across several fixed key sets, the new implementation reportedly remained between 1.2 and 2 nanoseconds per lookup. On an Apple M4, the URL-protocol benchmark exceeded one billion operations per second.
Those numbers are author-run microbenchmarks, not a guarantee for every application. Performance will depend on processor, compiler, key set, calling context and surrounding work. The method also applies to immutable, predetermined keys rather than maps that must accept runtime insertions.
For parsers and servers with small stable vocabularies, however, the result shows why a general-purpose container may impose avoidable work. The benchmark code and plotting scripts were released alongside the library, allowing developers to test the claims against their own workloads.
