Branchless Code: A Trade, Not an Upgrade
Replacing an unpredictable branch with arithmetic converts a variable cost into a fixed one. That is a win when the branch mispredicts often and the work it guards is trivial — and a loss in every other case, which is most of them.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
What the transformation actually does
A branch has a cost distribution: nearly zero when predicted correctly, a pipeline refill when not. Its expected cost is the mispredict rate times the penalty.
A branchless version has a fixed cost: both sides are evaluated and one result is selected. There is no prediction, so there is no misprediction — but there is also no skipping. The work you were avoiding is now always performed.
So the comparison is: mispredict_rate × penalty versus cost_of_the_work_you_no_longer_skip. On a predictable branch the left side is near zero and the transformation is a pure loss. On a coin-flip branch guarding one cheap arithmetic operation, the left side is large and the right side is tiny, and it is a clear win.
| Branch predictability | Guarded work | Verdict |
|---|---|---|
| Predictable | Cheap | Keep the branch — nothing to gain |
| Predictable | Expensive | Definitely keep the branch — it is saving real work |
| Unpredictable | Cheap | Branchless likely wins — the classic good case |
| Unpredictable | Expensive | Usually keep the branch — doing both sides costs more than mispredicting |
| Unpredictable | Has side effects or may fault | Must keep the branch — both sides cannot be executed |
The good case, concretely
The transformation below is the one that reliably works: a data-dependent condition over random values, guarding a single cheap operation, inside a hot loop. The branch mispredicts about half the time; the "work" being unconditionally performed is one arithmetic operation.
Note that the branchless version does strictly more arithmetic. That is not a mistake — it is the trade. It executes more instructions and runs faster, which is a useful counterexample to instruction-count reasoning and a direct illustration of why IPC: Instructions Per Cycle must be read alongside instruction counts rather than instead of them.
Whether a compiler already does this for you varies. Many compilers will emit a conditional move for simple cases, particularly when they have profile data suggesting the branch is unpredictable. Check the disassembly before hand-writing anything: the most common outcome of a manual branchless rewrite is an equivalent to what the compiler already produced, in less readable source.
1for (i = 0; i < n; i++) {2 if (data[i] >= threshold) // ~50/50 on random data:3 sum += data[i]; // the predictor cannot learn it4}5// Cost per element: mispredict_rate x refill_penalty1for (i = 0; i < n; i++) {2 mask = -(data[i] >= threshold); // 0 or all-ones3 sum += data[i] & mask; // adds 0 when not selected4}5// Cost per element: two extra cheap operations, no prediction.6// More instructions. Fewer cycles. Both statements are true.The branchless version executes more instructions but has no control-flow uncertainty, so the front end never stalls. It wins here because the guarded work was one addition — the thing we stopped skipping was nearly free. Replace the addition with an expensive call and the trade inverts completely.
Why it is over-applied
The technique has an appealing story — "branches are slow, remove them" — that is wrong in the general case. Most branches are highly predictable, so most branch removal buys nothing while costing readability and often adding work.
There are also cases where it is not merely unhelpful but *incorrect*. If either side has a side effect, may fault, or is expensive enough that executing it unnecessarily is a real cost, unconditional evaluation is not a valid transformation. A null check cannot be made branchless by dereferencing both ways.
The disciplined position: treat branchless as a targeted fix for a *measured* misprediction problem on a *cheap* guarded operation. Use the branch-miss counter to establish the problem exists, apply the transformation to that specific site, and measure again. Applying it as a general style is how codebases end up with unreadable bit manipulation that is no faster than the obvious version, and sometimes slower.
- Measure first: a branch-miss counter, at the specific site, before changing anything.
- Only for cheap guarded work: if the branch skips something expensive, keeping it is the optimisation.
- Never when a side has side effects or can fault: unconditional evaluation would be incorrect, not just slow.
- Check what the compiler already emitted: it frequently applies this itself given profile data.
- Measure again: on a predictable branch this transformation reliably makes things slower.
Key points
- Branchless trades a variable cost (mispredict rate × penalty) for a fixed cost (always doing both sides).
- It wins when the branch is unpredictable and the guarded work is cheap — and loses otherwise.
- The transformation typically executes more instructions and can still be faster, which refutes instruction-count reasoning.
- It is invalid where a side has side effects or may fault.
- Most branches in real code are predictable, which is why the technique is more often over-applied than under-applied.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Branch version → front end: the predictor guesses; a wrong guess costs a pipeline refill (Misprediction: What a Wrong Guess Costs).
- 2Branchless version → both sides evaluated: neither result is skipped, so no control-flow prediction is required.
- 3Select operation → data dependency: a conditional move or mask picks the result, creating a data dependency rather than a control one.
- 4Data dependency → scheduler: the dependency is handled by forwarding and out-of-order scheduling like any other operand.
- 5Fixed cost → predictable timing: runtime becomes independent of the data, which is also why constant-time cryptographic code uses this shape.
- • "Branchless is faster" — it is faster in one specific regime and slower in the others.
- • "More instructions means slower" — the branchless version executes more instructions and can still win.
- • "The compiler cannot do this" — it frequently can and does, especially with profile-guided information.
Consequences, controls and cost
- • Filtering and comparison-heavy loops over random data can improve substantially from the transformation.
- • The same transformation applied to predictable branches makes code slower and much harder to read.
- • Timing becomes data-independent, which is a security property as well as a performance one.
- • Establish with counters that a specific branch mispredicts frequently before transforming anything.
- • Apply only where the guarded work is cheap and free of side effects.
- • Inspect the compiler output first — it often already emitted a conditional move.
- • Prefer making the branch predictable (sorting, partitioning) over removing it, when the data allows.
- • Read branch misses at the specific site with sampling, not just the aggregate rate for the program.
- • Benchmark both versions on realistic data, including the predictable case, to confirm you are in the winning regime.
- • Inspect the disassembly of both versions; if the compiler already emits a conditional move, there is nothing to gain.
- • Readability drops sharply; mask-and-arithmetic idioms are much harder to review than a conditional.
- • The win is microarchitecture-dependent and can evaporate on a core with a better predictor or a slower conditional move.
- • Always doing both sides costs energy even when it saves time, which matters on battery-powered and dense server deployments.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICThe break-even point depends on mispredict penalty and conditional-move cost on the specific core; a design with a very good predictor shifts it toward keeping branches.
- PLATFORM-SPECIFICWhether the compiler emits a conditional move depends on compiler, version, optimisation level and profile data. Two toolchains can produce entirely different code from identical source here.
Misconceptions
Apply it
Where the rest of this lives
Whether your if becomes a branch or a conditional move is an if-conversion decision made by the compiler back end, often informed by profile data. Reading the emitted code is the only way to know which you got.