4 ms·

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

ot 9y ago
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 :)
- userbinator 9y ago
  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
CalChris 9y ago
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.
- TwoBit 9y ago
  Did Intel disprove Linus?
  - CalChris 9y ago
    Obviate would be a better choice of word.
- tedunangst 9y ago
  Something 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. :)

ot 9y ago

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

userbinator 9y ago
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

CalChris 9y ago

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.

TwoBit 9y ago
Did Intel disprove Linus?
- CalChris 9y ago
  Obviate would be a better choice of word.
tedunangst 9y ago
Something 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. :)