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

It's cool that you can do this now with constexpr instead of a pre-build step. The idea is pretty old though. I remember reading an article in a computer magazine in the 90s about how a web browser (Mozilla) works. They made a big point about how difficult parsing tags is, and that you can't just `if tag == "HTML"` for performance reasons. Instead they pre-baked an optimal hash table and used that. I remember it vividly because that was my first contact with hash tables and the explanation was pretty good. Looking back I find it funny that they considered tag lookup the hard part of a browser :-).

To my taste, that’s too many pointer chases and mispredicted branches.

I once needed something like that which was performance sensitive. Specifically, deserializer of a custom binary format which used string tags for stuff, essentially a tree data structure with string keys. I didn’t have too many of these keys, a key represents a serializable field of some C++ type.

I restricted length of the strings to 16 bytes which was good enough for my use case, and zero padded them into 16 bytes SIMD vector.

On x86-64-v2 and newer AMD64 CPUs, comparing these vectors for equality takes two instructions, pxor and ptest; _mm_xor_si128 and _mm_testz_si128 in C++. That includes the load because pxor can fuse loading of one of the arguments. Searching for a key is then a linear scan over a small aligned block of memory which during de-serialisation is guaranteed to stay hot in L1D. No pointer chases, no inner loops, 2 very fast instructions per test.

I wonder if you have a lookup table for values that _rarely_ change you could use the same approach (with maybe one caveat that you'd need to track the lifetime of the old variant of the hash table)

I understand this has uses outside of HTTP request methods/verbs, but it's not a great example as you can invent new ones for your RESTful service.

[flagged]

[flagged]

[flagged]

[dead]