branchless code

Since a mispredicted branch costs a pipeline flush, one way to eliminate that risk is to eliminate the branch itself. Branchless code rewrites a small conditional so that it computes a result with arithmetic and bit tricks instead of jumping. The CPU then runs a fixed, predictable sequence of instructions with no fork in the path — and therefore no branch to predict, and no flush if it would have been mispredicted.

The simplest realization uses a conditional move (the x86 cmov instruction) or predication: instead of 'if cond, jump and assign x = a, else assign x = b', the hardware computes both candidate values and selects one based on the condition, all without changing the instruction stream. By hand you often do the same with arithmetic on a boolean: for example max(a, b) without a branch can be written as b + ((a - b) & -(a > b)), where (a > b) is 0 or 1, -(...) is an all-zeros or all-ones mask, and the mask selects whether to add (a - b) or not. Many such idioms exist (clamping, sign, absolute value, selecting between two values), and compilers will sometimes generate them automatically when they judge a branch unpredictable.

Be candid about the trade-off, because branchless is not automatically faster. A conditional move always executes the work of BOTH paths and creates a data dependency on the condition, so for a branch the predictor handles well it is usually SLOWER than just branching — you pay to compute the unused side every time, and you may lengthen a dependency chain. Branchless code wins specifically when the branch is unpredictable (data-dependent, near 50/50, no learnable pattern), where the saved misprediction penalty outweighs the wasted work. The honest rule is: branchless is a targeted fix for a measured misprediction problem, not a general style. Always benchmark both versions on representative data.