alt Hacker NewsGreat explanation of why a branchless approach results in such a speed up. I've never really had to deal with performance optimization at this level. Generally it's probably best not to get too involved letting the CPU black box do its thing.
I do wonder, would the performance characteristics of branchless vs branching be consistent across different CPUs/architectures? If you had a CPU that wasn't trying to be fancy with branch prediction, would the regular algo be faster?
Replies
Virtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier.
If you're running on a very old CPU, yes, the regular algo should be faster.
Another recent story from github about case folding as part of code search, the simple version of the code had a couple of ifs, and the branchless version was actually slower.
They have a stupendously fast version and it is also branchless, but it just required more than branchless alone.
I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most.
The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
CPUs aren't black boxes. They are actually much better documented than almost all the software that runs on them.
If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica.
The regular algo will be lightyears slower on any CPU that does not have a branch predictor.