C++ Branch Prediction: Measuring Mispredictions, cmov, [[likely]] and PGO

A modern CPU doesn’t wait for an if condition before continuing. It guesses which way the branch will go, starts executing that path, and throws the work away if the guess turns out wrong. A correct guess costs almost nothing. A wrong guess costs a pipeline refill, which on current desktop cores is on the order of 15–20 cycles. Agner Fog’s microarchitecture manual lists figures per CPU family if you need the number for a specific chip.

So there are two questions to ask about any branch: is it hot, and is it predictable? A branch that goes the same way 99% of the time, or follows a short repeating pattern, is nearly free. A branch that depends on random data and runs 10 million times is where the time goes.

The sorted-array experiment, measured on two compilers

The best-known demonstration is the Stack Overflow question “Why is processing a sorted array faster than processing an unsorted array?”. Here is a version of that experiment:

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

long long sumAbove(const std::vector<int>& v, int threshold) {
    long long sum = 0;
    for (int x : v)
        if (x >= threshold) sum += x;
    return sum;
}

template <class F>
double bestOfFive(F f) {
    double best = 1e30;
    for (int rep = 0; rep < 5; ++rep) {
        auto t0 = std::chrono::steady_clock::now();
        f();
        auto t1 = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(t1 - t0).count());
    }
    return best;
}

int main() {
    std::vector<int> data(10'000'000);
    std::mt19937 gen(42);
    std::uniform_int_distribution<int> dist(0, 255);
    for (int& x : data) x = dist(gen);

    long long r1 = 0, r2 = 0;
    double random = bestOfFive([&] { r1 = sumAbove(data, 128); });
    std::sort(data.begin(), data.end());
    double sorted = bestOfFive([&] { r2 = sumAbove(data, 128); });

    std::printf("random: %.1f ms  sorted: %.1f ms  (sums %lld %lld)\n", random, sorted, r1, r2);
}

The accumulator is long long on purpose. Ten million values averaging around 190 overflow an int, and signed overflow is undefined behavior. That’s a bug the naive version of this benchmark often has.

On my machine (Ryzen 7 5800X, Windows), the results were:

Build	Random input	Sorted input
MSVC 2022 /O2	27.3 ms	3.6 ms
g++ 10.3 -O1	4.6 ms	4.6 ms
g++ 10.3 -O2	4.6 ms	4.4 ms
g++ 10.3 -O3	1.7 ms	1.7 ms
g++ 10.3 -O2 -fno-if-conversion -fno-if-conversion2 -fno-tree-vectorize	27.5 ms	4.0 ms

The famous 7× effect appears with MSVC and disappears with GCC. Your absolute numbers will differ, but the pattern is the interesting part. The generated code explains it. GCC at -O2 compiles the loop body to a compare plus a conditional move:

	addq	%r8, %rdx
	cmpl	%r9d, %ecx
	cmovge	%rdx, %r8

There is no data-dependent jump left to mispredict, so the order of the data doesn’t matter. At -O3 GCC also vectorizes the loop, which is faster again. MSVC keeps a real conditional jump:

	cmp	r8d, edx
	jl	SHORT $LN11@sumAbove
	add	rax, r8

With random bytes and a threshold of 128, that jl goes either way with 50% probability, and the predictor can’t do better than chance. Turning off GCC’s if-conversion and vectorization brings back the branch, and the 7× gap comes back with it.

Two lessons came out of this for me. First, “sort your data to help the branch predictor” is advice about the machine code, not about the C++ source. Before any branch work, I look at the disassembly of the hot loop (g++ -O2 -S, cl /FA, or Compiler Explorer). Second, a benchmark that shows a big difference under one compiler is not evidence that the difference exists in your build. I have watched people “optimize” a branch that the release compiler had already turned into cmov, and then measure noise.

Making the branch go away

If profiling shows a hot, mispredicting branch, the usual fix is to express the computation so that the result is selected instead of jumped to.

// Branchy: MSVC /O2 kept this as a conditional jump
if (x >= threshold) sum += x;

// Select: both compilers produced branch-free code for this
sum += (x >= threshold) ? x : 0;

// Mask: explicit, no conditional at all
sum += x & -static_cast<int>(x >= threshold);

With the ternary and the mask forms, both compilers produced branch-free code in my test, and random and sorted inputs ran at about the same speed (roughly 2–7 ms depending on compiler and variant). The ternary form is the one I’d write. It reads naturally and gives the optimizer a clean select. The mask trick is for when you need to force the issue.

Keep in mind that none of these forms guarantees a cmov. The compiler decides based on its own cost model, and the same source can compile to a branch in a different context or at a different optimization level. If a hot loop depends on it, check the assembly again after compiler upgrades.

Branchless code is not free either:

• It always evaluates both sides. If one side is expensive, or calls a function, a well-predicted branch that skips it is cheaper.
• It turns a control dependency into a data dependency. The CPU can’t start on the next iteration’s dependent work until the select resolves, while a correctly predicted branch lets it run ahead speculatively.
• It can’t skip work that is illegal on the other path, for example dereferencing a pointer that may be null.

The rule I follow: branchless for hot branches that are close to 50/50 on real data, ordinary branches everywhere else.

Changing the data instead of the code

When the branch must stay (the two paths do different, non-trivial work), you can sometimes make it predictable by grouping the data so that all the “yes” items come first.

Sorting does that, but it costs O(n log n) and is only worth it if the grouped data is reused many times, or if it is sorted anyway for another reason. When only the condition matters, std::partition does the grouping in one O(n) pass:

auto mid = std::partition(items.begin(), items.end(),
                          [](const Item& it) { return it.isSpecial(); });
for (auto it = items.begin(); it != mid; ++it) handleSpecial(*it);
for (auto it = mid; it != items.end(); ++it) handleNormal(*it);

After partitioning, the branch disappears entirely. Each loop has a single, fully predictable job. The same idea applies at design time: keeping different kinds of records in separate containers, rather than filtering one mixed container on every pass, removes the branch before anyone has to optimize it.

Indirect branches: virtual calls and switch tables

Virtual calls, function pointers and switch jump tables are indirect branches. The CPU has to predict the target address, not just taken/not-taken. A loop over std::vector<Shape*> where each element is a random Circle, Square or Triangle gives the indirect predictor a random target on each iteration.

The same fixes apply. Group objects by type, either by sorting the pointer vector by dynamic type or by storing each type in its own container, and each call site sees a single target:

std::vector<Circle> circles;
std::vector<Rectangle> rectangles;

double total = 0;
for (const auto& c : circles) total += c.area();      // one target, often inlined
for (const auto& r : rectangles) total += r.area();

The separate containers also let the compiler inline area() and often vectorize the loops, which usually matters more than the prediction itself.

A lookup table replaces a chain of comparisons with one indexed load:

#include <array>
#include <string_view>

constexpr std::array<std::string_view, 7> kDayNames = {
    "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

std::string_view dayName(unsigned day) {
    return day < kDayNames.size() ? kDayNames[day] : "invalid";
}

(The if chain version of this in many tutorials declares the function as returning int while returning string literals, which doesn’t compile. Use std::string_view or const char*.)

[[likely]] and [[unlikely]]: what they do and don’t do

C++20 added two attributes for marking the expected path:

#include <stdexcept>

int parseDigit(char c) {
    if (c < '0' || c > '9') [[unlikely]] {
        throw std::invalid_argument("not a digit");
    }
    return c - '0';
}

The attribute goes after the condition, on the statement that is likely or unlikely to run. It can also be applied to case labels in a switch.

What they change is the compiler’s view of branch probabilities. The compiler uses that to decide which block becomes the straight-line fall-through, whether to move the cold block to the end of the function or into a separate section, and how much to inline or unroll on each side. They do not program the hardware predictor. That still learns from what actually happens at runtime.

That makes them useful mainly for code layout of genuinely rare paths, such as error handling, assertions and slow-path allocations, where keeping the hot path compact helps the instruction cache. They don’t help a branch that is unpredictable, since no static hint can be right about a coin flip. And a wrong hint has a real cost: the compiler moves code you actually run into the cold section.

The failure mode I’ve seen with these is hints that were correct when written and became wrong later. A [[likely]] on “cache hit” is fine until a workload change makes the cache mostly miss. The attribute stays in the source, nobody re-measures, and the hot path now jumps out of line every time. If a hint encodes a claim about data, it needs the same scrutiny as a hard-coded threshold.

Profile-guided optimization

PGO gives the compiler measured branch probabilities instead of guesses or hints. It then does the same things [[likely]] would, but for every branch and based on data. It also informs inlining, function ordering, and the conversion of indirect calls to guarded direct calls.

GCC:

g++ -O2 -fprofile-generate app.cpp -o app
./app < representative-input        # writes .gcda files
g++ -O2 -fprofile-use app.cpp -o app

Clang (the raw profile must be merged first):

clang++ -O2 -fprofile-generate app.cpp -o app
./app < representative-input        # writes .profraw files
llvm-profdata merge -output=default.profdata *.profraw
clang++ -O2 -fprofile-use=default.profdata app.cpp -o app

MSVC (PGO is a linker feature and requires whole-program optimization):

cl /O2 /GL app.cpp /link /LTCG /GENPROFILE
app.exe                             # writes .pgc files
cl /O2 /GL app.cpp /link /LTCG /USEPROFILE

The entire value of PGO depends on the training run matching production. Profile with test fixtures that exercise the error paths, and the compiler will optimize for errors. Treat the training workload as part of the build, keep it in version control, and refresh it when behavior changes.

Measuring before and after

All of the above assumes you know which branch is the problem. The counters exist on every current CPU:

• Linux: perf stat -e branches,branch-misses ./app prints the total branch count and the miss ratio. perf record -e branch-misses ./app followed by perf annotate attributes misses to instructions.
• Windows: Intel VTune and AMD uProf show branch-miss events per function and per source line.

A low overall miss ratio can still hide one hot, bad branch, so look at where the misses are, not just how many there are. Then check the assembly, change one thing, and measure again with a benchmark that uses realistic data. Random test data makes every branch look unpredictable. Constant test data makes every branch look free.

Related Articles

• Profiling C++ before optimizing
• Benchmarking C++ code
• C++ cache optimization
• C++ exception performance
• C++ performance optimization