Step 3 of 5

Branches and branch prediction

Modern processors are pipelined: they work on many instructions at once, and they start on the instructions after an if before they know which way it goes. To do that, a branch predictor guesses, based on what the branch did before. A correct guess costs almost nothing. A wrong guess means throwing away the work in flight and starting again, roughly 15 to 20 cycles.

A branch the predictor can learn (always taken, or taken in long runs) is nearly free. A branch that's random is expensive. The classic demonstration adds up only the values that are 128 or more, from 10 million random bytes:

for (int x : data) if (x >= 128) sum += x;

With the compiler's branch-removing optimizations switched off, this loop took 292 ms over random data and 52 ms over the same data sorted, where the branch becomes predictable (false for the first half, true for the second). With normal g++ -O2, the compiler replaced the if with branch-free instructions on its own, and both versions took about 45 ms (4-core Linux machine). Two lessons in one: unpredictable branches are costly, and compilers already remove the simple ones.

Writing branch-free code

When a hot loop has an unpredictable decision the compiler can't remove, turn the condition into arithmetic. A comparison is 0 or 1, so it can be multiplied or added:

#include <iostream>
#include <vector>

long sum_big_branchy(const std::vector<int>& v) {
    long s = 0;
    for (int x : v) if (x >= 128) s += x;
    return s;
}

long sum_big_branchless(const std::vector<int>& v) {
    long s = 0;
    for (int x : v) s += (x >= 128) * x;      // (x >= 128) is 0 or 1
    return s;
}

int main() {
    std::vector<int> v = {5, 200, 130, 7, 255, 0, 128};
    std::cout << sum_big_branchy(v) << " " << sum_big_branchless(v) << "\n";
}

713 713

Other tools: [[likely]] and [[unlikely]] (C++20) tell the compiler which way a branch usually goes, so it lays out the common path first. Sorting or partitioning data before processing it makes branches predictable. And lookup tables replace chains of ifs.

Don't do this everywhere. Branch-free code is harder to read, and it always does both sides of the work. It pays off only in hot loops over unpredictable data, and only a profiler (perf stat reports "branch-misses") can tell you that you have one.

Your turn: write both functions without if, ?:, &&, || or library min/max. count_in_range(v, lo, hi) counts values with lo <= x <= hi (combine two comparisons with & or *), and max_branchless(a, b) returns the larger int using the mask trick: -(b > a) is all 1-bits when b is bigger and 0 otherwise, so a ^ ((a ^ b) & -(b > a)) picks b or a.

Previous: Arrays of structs vs structs of arrays Next: False sharing and alignment