Hacker News Reader

Comment by ot | Hacker News Reader

> 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.

View on HN

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:

https://github.com/nmap/nmap/blob/b7a5a6/ncat/scripts/httpd....

The Lua code is just excessively verbose.

What do you mean? How else would you implement a check for whether the prefix length is valid?

Here's the code to do it: 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.

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.

CMOV isn't necessarily faster than no branches. There's still data dependencies which can prevent reordering. But considerably faster than a misprediction.

Sure, 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 :)

is 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

I 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.

Did Intel disprove Linus?

Obviate would be a better choice of word.

Something like

    X = flag ? X : 0;
    X = test ? X : 0;

    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. :)

Reply on news.ycombinator.com