6 ms·
> My primary — and totally arbitrary — goal was to beat the performance of Bjoern Hoehrmann’s DFA-based decoder. The thing is, that decoder could be already br
by ot 9y ago
> My primary — and totally arbitrary — goal was to beat the performance of Bjoern Hoehrmann’s DFA-based decoder.
The thing is, that decoder could be already branchless. The core of the algorithm is:
*codep = (*state != UTF8_ACCEPT) ?
(byte & 0x3fu) | (*codep << 6) :
(0xff >> type) & (byte);
Which can be compiled with a conditional move (CMOV) instead of a branch. In fact:
> With GCC 6.3.0 on an i7-6700, my decoder is about 20% faster than the DFA decoder in the benchmark. With Clang 3.8.1 it’s just 1% faster.
There's a chance that when inlined into the benchmark Clang uses a CMOV while GCC uses a branch. As he correctly points out, his benchmark is the worst case for branch prediction:
> The even distribution of lengths greatly favors a branchless decoder. The random distribution inhibits branch prediction.
- tedunangst 9y agoCMOV isn't necessarily faster than no branches. There's still data dependencies which can prevent reordering. But considerably faster than a misprediction.
- ot 9y agoSure, but if you look at the implementation in the article, that's a much longer dependency chain: *c = (uint32_t)(s[0] & masks[len]) << 18; *c |= (uint32_t)(s[1] & 0x3f) << 12; *c |= (uint32_t)(s[2] & 0x3f) << 6; *c |= (uint32_t)(s[3] & 0x3f) << 0; *c >>= shiftc[len]; /* Accumulate the various error conditions. */ *e = (*c < mins[len]) << 6; *e |= ((*c >> 11) == 0x1b) << 7; // surrogate half? *e |= (s[1] & 0xc0) >> 2; *e |= (s[2] & 0xc0) >> 4; *e |= (s[3] ) >> 6; *e ^= 0x2a; // top two bits of each tail byte correct? *e >>= shifte[len]; Plus, all those loads are not making it easy for the processor to pipeline. And *e = (*c < mins[len]) << 6; is really a CMOV in disguise :)
- userbinator 9y agois really a CMOV in disguise :) I don't see how using CMOV would be appropriate there --- I'd compile it as something more like this: ; eax = *c, ebx = mins[len] cmp eax, ebx sbb eax, eax and eax, 64 ; eax = (*c < mins[len]) << 6
- CalChris 9y agoI dunno what you mean by CMOV vs “no” branches. However, CMOV is single cycle latency in Kaby Lake. Also, I don’t know if those data dependencies wouldn’t also cause similar problems for resolving a conditional branch. It may be possible to construct a scenario where CMOV is marginally slower but I think we can put Linus Torvalds’ CMOV rant in the bit bucket. Intel recommends CMOV with a proviso. Assembly/Compiler Coding Rule 2: Use the SETCC and CMOV instructions to eliminate unpredictable conditional branches where possible. Do not do this for predictable branches. The Intel C Compiler uses it.
- TwoBit 9y agoDid Intel disprove Linus?
- CalChris 9y agoObviate would be a better choice of word.
- tedunangst 9y agoSomething like X = flag ? X : 0; X = test ? X : 0; Vs X |= flag; X |= test; The latter is more obviously branch less. How exactly the two perform probably requires some testing. And somewhat more general point, since we're writing C and not asm, depends how much you want to depend on the compiler to use the right instructions. To backtrack on my point a bit, whether CMOV gets used is an important consideration. > There's a chance that when inlined into the benchmark Clang uses a CMOV And a chance it won't. :)
- d33 9y agoThat looks way oversimplified. I once wrote a minimal HTTP server in Lua for Nmap project and part of the problem was UTF8 security. Consider get_next_char_len function here to see some of the edge cases: https://github.com/nmap/nmap/blob/b7a5a6/ncat/scripts/httpd.lua https://github.com/nmap/nmap/blob/b7a5a6/ncat/scripts/httpd....
- loeg 9y agoThe Lua code is just excessively verbose.
- d33 9y agoWhat do you mean? How else would you implement a check for whether the prefix length is valid?
- loeg 9y agoHere's the code to do it: https://github.com/skeeto/branchless-utf8/blob/master/utf8.h https://github.com/skeeto/branchless-utf8/blob/master/utf8.h It's pretty straightforward. He uses a lookup table for the first byte ("lengths") and then later checks that subsequent bytes have the correct continuation prefix (0xc0 mask / 0x2a value). I think it checks all of the same conditions as your Lua code.
- feelin_googley 9y agoMimimal but useful. I just tried this httpd.lua script with djb's tcpserver and was pleasantly surprised. It is quick and handles large PDFs well enough. I like that there are no third party libraries. If directory listing and output for video could be added I might try using something like this on a local LAN as a replacement for the httpd binary I am using.
- d33 9y agoGlad to hear you like it! What do you mean by output for video? As for video listing, Lua doesn't provide a cross-platform way to do this, but I might have hacks for Unix/Windows that parse the output of dir/ls commands. Interested? Can't promise I find it though.