5 ms·
Doing Boyer and Moore proud. I think that if you want to support all verbs, you face at least 3 'ambiguities' whether you first check the first, second, or thi
by MaxBarraclough 5y ago
Doing Boyer and Moore proud.
I think that if you want to support all verbs, you face at least 3 'ambiguities' whether you first check the first, second, or third character of the string. (It must be at most the third, as the shortest verbs are 3 characters long.)
First checking the first character is ambiguous between POST, PUT and PATCH. First checking the second character is ambiguous between HEAD, DELETE, and GET. First checking the third character is ambiguous between GET, PUT, OPTIONS, and PATCH. [0]
edit As danachow points out, the verbs are not all used with the same frequency. If real-world performance is the goal we'd presumably want to optimise for the GET case, which presumably means first checking the first character, as the 'G' is unique to GET.
[0] https://developer.mozilla.org/en-US/docs/Web/HTTP/Methods https://developer.mozilla.org/en-US/docs/Web/HTTP/Methods
- stormbrew 5y agoSeems likely an optimal algorithm could probably get there just looking sequentially at the first three letters in order. Would be an interesting code-golf.
- sseagull 5y agoA bit of a micro-optimization, but couldn’t you interpret 4 bytes (including the trailing null on the three-letter verbs) as a 32-bit unsigned int and then do integer comparisons or a case statement?
- dlsa 5y agoYou could add a computed goto to really spice things up.
- stazz1 5y agocall it "adventure plumbing"
- morelisp 5y agoThis is close to what nginx does today, if your platform supports unaligned reads. The check for 'O' is a specific fast-path only for HEAD, most others are done via ordinary comparisons.
- legulere 5y agoNGINX does exactly that (after finding the space character after the verb): https://github.com/nginx/nginx/blob/7587778a33bea0ce6f203a8c4de18e33f38b9582/src/http/ngx_http_parse.c#L38 https://github.com/nginx/nginx/blob/7587778a33bea0ce6f203a8c... There are several points to note: This trick only works if the architecture supports unaligned memory access. Macros are used instead of functions, so you don't have to rely on the compiler to do inlining. The shifts and ors should get optimized out by the compiler. I once tried something similar in C#, but sadly the JIT doesn't do that optimization.
- sseagull 5y agoAh nice! I was interested in looking but don’t know the codebase. That method does look better. My idea assumes that the method has already been checked to see if it is a valid method, which has its own cost. Otherwise, POSABC would be parsed as POST. Their method does that more or less on the fly.
- MaxBarraclough 5y ago> This trick only works if the architecture supports unaligned memory access Presumably then it's relying on undefined behaviour.
- stormbrew 5y agopretty sure it's just implementation defined. In the sense that the implementation defines the allowed alignment, if nothing else (ie. on x86 the allowed alignment is 1 byte even if that's not optimal).
- MaxBarraclough 5y agoI don't think so. What I can find on this topic with a quick search points to it being outright UB. https://stackoverflow.com/a/47622343/ https://stackoverflow.com/a/47622343/ https://stackoverflow.com/a/28895321/ https://stackoverflow.com/a/28895321/ https://blog.quarkslab.com/unaligned-accesses-in-cc-what-why-and-solutions-to-do-it-properly.html https://blog.quarkslab.com/unaligned-accesses-in-cc-what-why...
- cft 5y agoMost requests in reality are GET. So if you first check for G, if (m[0] == 'G') { r->method = NGX_HTTP_GET; break; } else if (m[0] == 'P') { switch(m[1]) { ... } } else if ... this should be fast enough.
- deleted 5y ago[deleted]
- tentacleuno 5y agoHow would this work if the method field was something like "Gibberish"? Would this have any security vulnerabilities?
- deleted 5y ago[deleted]
- w-ll 5y agoIf its "Gibberish" I'd suggest it's safer to assume it as a Get request regardless. Something I don't see many people talk about, but I've setup web instances with both read and write clusters similar to db's, and have the nicety to getting more umph from the read cluster by making sure it only hits read db nodes and disabling any framework stuff for tracking changes on a model.
- jcampbell1 5y agoDid you experience any read after write inconsistencies that present as heisenbugs?
- dotancohen 5y agoWould you expect that to be more of an issue under GP's method than with traditional sharding and replication? Presumably writes are then replicated to all instances, just not all instances accept them.
- Cthulhu_ 5y ago