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.
That 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:
Mimimal 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.
Glad 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.
Briefly tested with a few filetypes and a couple of browsers, including Safari. Problem loading video/mp4, i.e., problem with "HTTP streaming". Maybe need to handle Range: header?
Of course, any examples in Lua of different approaches to UNIX directory listing via HTTP are appreciated. Still a Lua noob.
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.
CMOV isn't necessarily faster than no branches. There's still data dependencies which can prevent reordering. But considerably faster than a misprediction.
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 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
The thing is, that decoder could be already branchless. The core of the algorithm is:
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.