Branch Prediction and Memory Bandwidth

This chapter covers two hardware realities that dominate performance: branch prediction and memory bandwidth.

Why This Matters

Branches stall the pipeline when mispredicted, and memory bandwidth is often the true bottleneck for data-heavy code. Understanding both lets you write code that the hardware executes efficiently.

Prerequisites

• c.cpu.3 — CPU execution and caches.

Core Concept

Branch prediction

Modern CPUs predict the outcome of a branch and speculatively execute ahead. A misprediction discards the speculative work and costs many cycles. Predictors learn patterns; unpredictable (random) branches are expensive.

Memory bandwidth

Memory has a maximum transfer rate (bandwidth). Data-heavy loops are often limited by how fast they can move data to/from memory, not by ALU speed. The arithmetic intensity (FLOPs per byte loaded) determines whether a loop is compute-bound or memory-bound.

Examples

Predictable vs. unpredictable branches

int sum_above(const int *a, int n, int t)
{
    int s = 0;
    for (int i = 0; i < n; i++)
        if (a[i] > t) s += a[i];   /* branch */
    return s;
}

If a is sorted, the branch is predictable; if random, it mispredicts often. The sorted version can be several times faster.

Reducing branches

/* branchless: use arithmetic instead of if */
s += (a[i] > t) ? a[i] : 0;          /* still may compile to cmov */

Compilers often use conditional moves (cmov) to avoid branches, but the predictability of the data still matters.

How It Works

The predictor tracks branch history. A branch that always goes the same way is predicted perfectly; an alternating or random branch mispredicts. Misprediction flushes the pipeline, costing ~15–20 cycles on modern CPUs.

Variations

Loop unrolling and software pipelining

Compilers restructure loops to reduce branch frequency and hide latency.

Prefetching

Software prefetch (__builtin_prefetch) or hardware prefetchers bring data into cache before it is needed.

Common Mistakes

• Sorting data unnecessarily or, conversely, ignoring branch predictability.
• Optimizing for ALU when the loop is memory-bound.
• Not measuring — branch/memory effects are hard to predict by eye.

Undefined Behavior

• None inherent.

Portability

• Branch prediction and bandwidth are hardware properties; the *techniques*

(branchless code, locality) are portable.

Under the Hood

perf stat -e branch-misses measures mispredictions; perf stat -e cache-misses and memory bandwidth counters reveal memory bottlenecks.

Practical Usage

• Make branches predictable (sort data, process in order).
• Use branchless idioms in hot loops where mispredictions dominate.
• Increase arithmetic intensity to hide memory latency.

Exercises

1. Benchmark the sorted vs. random branch example and measure with perf stat. 2. Convert a hot if into a branchless expression and compare. 3. Explain why a loop with low arithmetic intensity is memory-bound.

Deep Challenge

Optimize a "sum of elements above a threshold" loop for both sorted and random input, measuring branch misses and time. Explain the trade-offs of a branchless vs. branchy version.

Related Concepts

• c.cpu.3 — caches/execution.
• c.perf.2 — locality.
• c.perf.1 — profiling.

References

• Intel/ARM optimization manuals; Agner Fog's optimization resources.

Verification

• Branch prediction and bandwidth behavior are hardware facts. HARDWARE
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Branch prediction
• [ ] Misprediction cost
• [ ] Branchless code
• [ ] Memory bandwidth

Mastery levels