Branchless programming

The short version:

• Modern CPUs start work before they know whether an if condition is true.
• A correct guess is cheap; a wrong guess means throwing speculative work away.
• Predictable branches are normally fast. Random-looking branches are harder to predict.
• Branchless programming expresses a decision as data or arithmetic instead of a change in control flow.
• It is an optimisation for measured hot paths, not a rule for everyday code.

Why CPUs guess

A modern CPU does not wait for one instruction to finish before beginning the next. It keeps a pipeline of work in progress and may execute several independent instructions at once.

That becomes awkward when it reaches a choice:

if condition:
    do A
else:
    do B

The CPU may not know the value of condition yet, but waiting would leave part of the processor idle. Instead, its branch predictor guesses which path will be taken and starts executing it speculatively.

• If the prediction is right, useful work has already been done.
• If the prediction is wrong, that work is discarded and execution restarts on the correct path.

Think of a barista who recognises a regular customer and starts making their usual coffee before they order. This works brilliantly if the customer is predictable. If they choose randomly each morning, the barista often has to pour away the first drink and start again.

The important distinction is therefore not branching versus no branching. It is predictable branching versus unpredictable branching.

The parcel-label factory

Imagine parcels moving through a factory. Each parcel needs either a domestic label or an international label, but reading its destination requires a scanner which takes a moment to return a result.

The label station is faster than the scanner and does not want to sit idle. While it waits, it predicts the result and starts printing the label it expects the parcel will need.

• If the prediction is correct, the label is ready as soon as the scan completes.
• If it is wrong, the station throws that label away and prints the other one. The work it did in advance was wasted.

This decision is made again for every parcel:

if the parcel is domestic:
    print a domestic label
else:
    print an international label

The station remembers what happened to previous parcels. If 999 domestic parcels arrive followed by one international parcel, predicting “domestic” works extremely well: there is likely to be only one surprise. If domestic and international parcels arrive in a random 50/50 order, recent parcels provide little help and labels are thrown away much more often.

That is analogous to a CPU's branch predictor. The scanner is the unfinished calculation needed to evaluate the condition. Printing a label early is speculative execution. Throwing away the wrong label is the recovery after a branch misprediction.

A branchless version could print both labels for every parcel, then use the scanner result to select the correct one. This performs more work even when the outcome is obvious, but its cost is consistent and it never has to stop to replace a wrongly predicted label.

Real branchless code does not always evaluate both alternatives; it might instead use arithmetic, a mask or a conditional-move instruction. The useful part of the analogy is the trade: do a fixed amount of work, or guess which work will be needed and occasionally pay to recover.

Patterns are easy; randomness is hard

Imagine filtering a million values:

result = []

for value in values:
    if value > threshold:
        result.append(value)

If almost every value is above the threshold, the condition is usually true. If almost none are above it, the condition is usually false. Either pattern gives the predictor something useful to learn.

If the values are randomly distributed and about half pass the test, the outcome resembles a series of coin flips. The CPU cannot reliably learn what comes next, so mispredictions become more frequent.

This explains a result that can initially look backwards: processing more data can be faster than processing less. A filter which keeps nearly every item performs more writes, but its branch may be easy to predict. A filter which keeps half of a random input performs fewer writes, yet may spend more time recovering from incorrect predictions.

Order matters too. For sorted data, the result might be false for the first half and true for the second. That is still a 50/50 split overall, but it has only one transition and is easy to predict. The same values in a random order are much less friendly to the predictor.

Turning control into data

Branchless programming avoids an unpredictable choice in the instruction stream. Instead of using a condition to decide which code runs, it uses the result as a value.

For example, a conventional minimum function looks like this:

if a < b:
    minimum = a
else:
    minimum = b

A compiler may represent this using a conditional-move or select instruction: calculate the condition, then select one of the two already available values. The program still makes a logical decision, but the CPU does not necessarily jump to a different sequence of instructions.

A filter can use a similar idea. It can write every value to the current output position, then advance that position by either zero or one:

output = array_with_capacity(length(input))
position = 0

for value in input:
    output[position] = value
    position += integer(value > threshold)

truncate output to position

The comparison produces 1 when the value should be kept and 0 when it should be rejected.

• For a kept value, position advances.
• For a rejected value, position stays put and the next iteration overwrites it.

The unpredictable control dependency has become a data dependency. There are still branches for the loop and perhaps bounds checks, but those usually follow a simple, predictable pattern.

Other common branchless building blocks include conditional moves, bit masks, lookup tables and vector instructions which operate on several values at once.

Why branchless is not automatically faster

Removing a branch does not remove work. It often replaces conditional work with unconditional work.

The filter above writes every input value, including values it will discard. The normal version writes only accepted values. If acceptance is rare and predictable, the branched version can win easily.

Branchless code may also:

• execute both sides of a decision when only one result is needed;
• introduce extra arithmetic or memory operations;
• create a chain of data dependencies that limits parallel execution;
• prevent a compiler from recognising a clearer, optimisable pattern;
• be harder for a reader to understand and maintain.

There is another wrinkle: source code containing if is not proof that the machine code contains a branch. Optimising compilers routinely turn simple conditions into conditional moves or vector operations. The reverse is also possible: an expression that looks branchless in source code may compile to a branch.

The machine code and the benchmark decide whether an implementation is branchless and whether that matters—not its appearance alone.

When should you use it?

Start with clear, idiomatic code. Then consider a branchless alternative only when:

1. A profiler identifies the code as a meaningful hot path.
2. The branch depends on data with difficult-to-predict outcomes.
3. A representative benchmark shows that the alternative is faster on the hardware you care about.
4. The improvement is worth the added complexity.

Benchmark realistic distributions, not just one convenient input. Test mostly true, mostly false, evenly mixed, sorted and random data where those cases can occur in production. Also check the compiler's optimised output: it may already have done the transformation for you.

The practical lesson

An if statement is not inherently slow. A predictable branch can be extremely cheap, while a branchless replacement can do unnecessary work. The troublesome case is a branch inside a hot loop whose outcomes are hard to predict.

Branchless programming gives us another way to express that work: turn control flow into data flow, trading misprediction risk for consistent computation. Sometimes that trade produces a large speed-up. Often the straightforward code remains best.

Measure first, keep the readable version as the baseline, and let evidence choose between them.

Inspired by Serhii Potapov's Branchless Rust: Making a Filter 4x Faster by Removing an if, which includes a reproducible Rust benchmark demonstrating the effect.