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).
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.
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.
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.
pervognsen | 7 hours ago
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.
gignico | an hour ago
No, reading past the end of a buffer is UB no matter what.
pervognsen | an hour ago
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.
gignico | 50 minutes ago
Of course, but he’s writing about C++, not even intrinsics or inline assembly. It is something incredibly naive to write in my opinion.
snej | 7 hours ago
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.
fs111 | 6 hours ago
maybe logging, where you typically have
INFO, WARN, DEBUG, TRACEor similar levels and they behave slightly different (like stdout vs stderr).masklinn | 3 hours ago
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.