Billion-query-per-second lookup tables in C++
24 points by signal-11
24 points by signal-11
For the article's key set {"GET", "POST", "PUT", "DELETE", "PATCH"} you can use the perfect hash function (0x13340001u * (n ^ s[0])) >> 29 into {0, 1, ..., 7}, assuming the length n is provided with s and s[n] is 0 (so that unconditionally indexing s[0] gives a well-defined value).
That's 5 cycles of latency on typical processors after s[0] is loaded. The article's (length + asso[key[i]] + ...) % table_size adapted to this example yields (n + a[s[0]]) & 7. The multiply-shift form is 1 cycle less than that on modern AMD (4 cycle L1 latency) and 1-2 cycles less on modern Intel (4-5 cycle L1 latency).
You can probably do even better.
Reading past the end of a buffer is fine as long as you do not cross into another memory page, and pages are at least 4 kilobytes.
No, reading past the end of a buffer is UB no matter what.
It's fine at the level of the concrete machine (if you know the architecture and take precautions like avoiding page crossings), not the abstract machine. In practice that means you have to do it with inline (or out-of-line) assembly to avoid UB, which is how you implement a fast strlen.
But to your point and what might be more relevant to the library described in the article: I've seen a lot of people mistakenly assume that using SIMD load/store intrinsics like _mm_loadu_si128 will free them from the abstract machine. That is absolutely not the case. Modern optimizing compilers can and will treat those like any other load/store operation, so it's not just a theoretical objection.
Using inline assembly doesn't mean you don't have to think about UB, but at least it's possible to use inline assembly as an ingredient in constructing the desired solution.
Of course, but he’s writing about C++, not even intrinsics or inline assembly. It is something incredibly naive to write in my opinion.
Now I’m wondering what good use cases there are for this technique, where the speed boost is noticeable on (non-embedded) CPUs. What fraction of handling an HTTP request is looking up headers?
Parsing JSON is one, where typically one does a switch on the first character of a keyword. Sort of a degenerate case of this. In languages with more complex grammars I don’t know if identifying reserved words is a hot spot.
maybe logging, where you typically have INFO, WARN, DEBUG, TRACE or similar levels and they behave slightly different (like stdout vs stderr).
It would probably be most useful to quickly bail on levels which are disabled because by the time you involve string formatting and possibly unbuffered IO I feel like the map lookup is not going to be your main concern.