lowlatency · advanced

Branch Prediction & Branchless Code

Modern CPUs are deeply pipelined and execute speculatively, with a branch predictor guessing each branch's direction and running ahead; a correct guess is nearly free, but a misprediction flushes and restarts the pipeline at a penalty of roughly 15-20 cycles. Predictable branches (almost always taken or not taken) are fine — the real cost is a data-dependent branch in a hot loop that the predictor cannot learn, such as comparing against random data (the well-known 'sorted array is faster than unsorted' result is exactly this effect). When such a hot branch is unpredictable, you can go branchless by converting control flow into arithmetic: bit masks (x & -(cond) yields x or 0), conditional moves (cmov, which compilers often emit automatically), std::min/std::max in place of if, table lookups indexed by a condition, or predication — turning the branch into straight-line code with nothing to mispredict, at the cost of always computing both paths. This is a micro-optimization warranted only in hot, unpredictable inner loops; elsewhere it harms readability and can even be slower, so check the generated assembly and measure the branch-miss rate with perf stat (branch-misses) before and after. Often the better fix is to make the branch predictable (for example by sorting the data so the condition is monotonic) or to hint the predictor with C++20 [[likely]]/[[unlikely]] or __builtin_expect when one side genuinely dominates — profile, don't guess.

The code

// Unpredictable branch in a hot loop -> pipeline flush on mispredict
for (int x : data)
    if (x >= 128)
        sum += x; // data-dependent branch

// Branchless: turn control flow into arithmetic / cmov
sum += x & -(x >= 128); // mask: (x>=128)?x:0  (no branch)
                        // also: std::min/std::max, conditional-move, table lookups
                        // hint the predictor:  if (x) [[likely]] { ... }   // C++20

What this lesson walks through

1. 01Why a misprediction hurts
2. 02Going branchless
3. 03Gotcha — branchless isn't always faster
4. 04When to bother — measure first

Modern CPUs are deeply pipelined and execute speculatively: the branch predictor guesses each branch's direction and runs ahead. A correct guess is nearly free, but a MISPREDICT flushes the pipeline and restarts — typically a ~15-20 cycle penalty. Predictable branches (almost always taken/not-taken) are fine; the killer is a data-dependent branch in a hot loop that the predictor can't learn — e.g. comparing against random data.