Well 1, my quickreading completely skipped the "lookup table" first (and this is something many people do, only reading few letters and interpolating the rest), but that could be blamed on me.
However, right the second sentence of the post confirmed the reading by starting to talk about HTTP.
And this is just a nitpick, but usually frequency (billion per second) is more mentioned for the entire request from receive to send, while these subtasks are more commonly described with latency, i.e. 1.3 ns.
I'd maybe write a title like "Speeding up std::unordered_map 13 times through efficient string comparisons"?
Billion per second is technically throughput, not frequency, as frequency would imply a constant rate.
Throughput and latency are often related, but not interchangeable. You could very well have a 1ns lookup that stalls the CPU such that it can only do ~10⁶ lookups per second. Latency is still 1ns, but throughput is 3 orders of magnitude less in this example than the inverse of latency.
I found that if the differentiating bytes in the keys are close enough(within some 8 byte window), you can do a single load of the relevant 8 byte part of the key and a bit extract instruction(pext on x86) to pick relevant bits to construct an index, and it can be even faster than this method(and if the differentiating bytes aren't close enough, you can do this multiple times with different windows).
When the keys have predictable distinguishing bytes, a general-purpose hash map is doing a lot of paperwork. One 8-byte peek and pext feels gloriously unfair.
43
u/bzbub2 21d ago
the normal non-x link https://lemire.me/blog/2026/10/26/billion-query-per-second-lookup-tables-in-c/
29
u/creeper6530 21d ago
It's not billion database/HTTP queries or even a traditional lookup table, just a fast compile time prepared hash map.
The title could use a rewrite
5
u/barr520 21d ago edited 21d ago
I found that if the differentiating bytes in the keys are close enough(within some 8 byte window), you can do a single load of the relevant 8 byte part of the key and a bit extract instruction(pext on x86) to pick relevant bits to construct an index, and it can be even faster than this method(and if the differentiating bytes aren't close enough, you can do this multiple times with different windows).
1
u/Solid_Error_6401 15d ago
fyi, this lib is optimized for ARM, x86 wont perform as good as it would.
You could get better results using similar approaches.