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

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 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.

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)

[flagged]

[flagged]

[dead]