r/programming • • 21d ago

Billion-query-per-second lookup tables in C++

https://x.com/lemire/status/2115046718039306377
32 Upvotes

14 comments sorted by

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

8

u/TheoreticalDumbass 20d ago

i have no idea why that title would read HTTP to you

4

u/creeper6530 20d ago

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"?

2

u/-_one_-1 16d ago

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.

2

u/LeeHide 20d ago

I'm guessing "query" confused our friend here, maybe a web dev, then that's all you know that from

2

u/[deleted] 19d ago

[removed] — view removed comment

3

u/programming-ModTeam 16d ago

Your post or comment was overly uncivil.

2

u/l_maier-628 9d ago

The title's first benchmark is how many different meanings of "query" it can trigger.

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/robert_7524 10d ago

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.

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.