4 ms·

Many compilers will implement d += *d != c; with a branch, and depending on the data pattern the branch predictor will be bamboozled. The branchless ve

• loup-vaillant 16y ago
  Gasp! I thought it would be easy to just transfer the compare flag to a general purpose register. I suppose x86 doesn't have such an instruction?
  • Daniel_Newby 16y ago
    I lied! A quick test shows that GCC uses the x86 SETE instruction (set register on condition equal). Cool. However, code like this: if (x == 14) { y = 10; } else { y = 20; } uses branches, although I think x86-64 has conditional load instructions.
• nkurz 16y ago
  I just tossed together a quick branchless version, and was a little surprised to see that it was significantly slower than the straightforward pointer version on random data: about 1.5x the cycles. Presumably this gap would narrow if checking for char_to_remove was less predictable. Here's the code I tested. I think it works, but I barely checked it. I'm sure there are better ways to calculate 'increment'. Not sure if these would be enough to close the gap, though. void condense_by_removing_branchless(char *z_terminated, char char_to_remove) { char *condensed = z_terminated; while (*z_terminated) { *condensed = *z_terminated; int diff = *condensed - char_to_remove; int increment = -((diff | -diff) >> ((sizeof(int) * 8) - 1)); condensed += increment; z_terminated++; } *condensed = 0; }