Comment by hermitdev
20 hours ago
What people refer to when they say "branchless code" is something very particular, and it refers to not triggering the CPU's branch prediction. That is, don't make the CPU have to guess which fork in the code you're going to take. This is usually accomplished in one of two ways: either bit twiddling hacks or specialized instructions that do not affect the CPU's branch prediction, such as the 'cmov' family in x86. If you search for `examples of branchless code using conditional moves` using your search engine of choice, you'll find numerous examples.
A trivial example is actually written with a branch in C/C++, but relies on compiler optimizations to kick in. If you compile a ternary operator in C/C++ (and probably rust, C# and other languages) such as in:
int min_branchless(int a, int b) {
return a < b ? a : b; // Often emits cmov with -O2
}
With gcc/clang a -O2, one would expect the compiler to emit the following assembly:
cmp edi, esi
cmovle eax, edi ; select a if a <= b
ret
There's numerical tricks for other operations/comparisons, and compilers know a lot of them. But, I just suggest compiling your code and configuring your compiler to emit the generated assembly with references to the code it was generated from (you should be able to get it to emit source line references in the assembly). You'll likely be surprised at the optimizations applied at -02, and utterly confused by what you find at -03.
edit: Also, it doesn't mean to never branch, but to minimize branching, especially in tight loops. Branch outside loops, not inside, for instance.
e.g. don't do:
for (...) {
if (condition independent of loop variable) {
...
} else {
...
}
}
do:
if (condition independent of loop variable) {
for (...) {
...
}
} else {
for (...) {
...
}
}
Yes, and back when hand-writing vectorized kernels via intrinsics, one learned to do the equivalent of (pseudocode here - picture SSE, AltiVec, NEON, etc.):
where each lane of the conditionmask has either all bits set or all bits clear, depending on the outcome of the conditional test for that lane.
The processor obviously does execute both branches here, so there's going to be wasted work. But since it's just a linear sequence of operations it can often schedule them independently and run them out-of-order and in parallel. And of course, if there's any shared computation between the two branches, the compiler can do common subexpression elimination.
That said, that sort of approach where you go ahead and do both and then blend them was definitely the kind of optimization where you'd want to profile rather than doing it blindly. But it was a pretty common thing to do when hand-vectorizing code. (Thankfully, auto-vectorizers are pretty good at doing this sort of optimization for you these days. It's been a very long time now since I've had to hand-write vector intrinsics.)
Rust is an expression language and so it doesn't have "the ternary operator"† you can use conditionals like if anywhere in your expression anyway.
If you want to tell the Rust compiler that you're certain a branch predictor can't help here [be very sure, most often humans are wrong which is why historically these "I know better than the branch predictor" features get ignored by optimisers] you can core::hint::select_unpredictable(condition, a, b) rather than using a dedicated operator.
† That's not its actual name, some languages have an operator with three operands which does something else, such as fused multiply-add so in a multi-lingual context better to say explicitly you mean the ternary conditional operator.
The latter example, sounds like something trivially done by the compiler. I mean I would sometimes, adhere to it, but only if the loops afterwards become substantially different. If I would just repeat most of the loop body, I would prefer the former.