Branch prediction and speculative execution

The count_branch loop on this page reads ten million bytes and counts those at least 128. On shuffled data it takes about 2.7 ns a byte; on the same bytes sorted first, about 0.25 ns, roughly ten times faster, though it counts the same number. The bytes did not change, only their order, and with it how often one branch guessed right.

A modern core does not wait for a branch to resolve before going on. Branch prediction guesses which way the branch will go, and speculative executionspeculative execution: A core running instructions past a branch on the predictor's guess before it is known to be correct, discarding their results if the guess turns out wrong. runs ahead on that guess; a right guess is already done when the branch resolves, and a wrong one is thrown away. Here you measure what branch prediction costs when it fails and what the branch predictorbranch predictor: The hardware that guesses, from the history of earlier branches, which way a conditional branch will go, so the pipeline can keep fetching before the branch is resolved. can and cannot learn.

A branch the core cannot predict is the slow part

The loop that counts bytes at or above 128, count_branch in branch.s, has a data-dependent branch: for each byte it compares with 128 and jumps over the increment when the byte is below, so whether the branch is taken follows the data. Beside it, count_branchless turns the comparison into a 0 or 1 with cset and adds it, with no branch:

// branch.s (AArch64): two counting loops. a is in x0, n in x1; the result returns in x0.
        .text

// long count_branch(const uint8_t *a, long n): if (a[i] >= 128) count++;
        .p2align 4
        .globl  _count_branch
_count_branch:
        mov     x2, #0                  // i
        mov     x3, #0                  // count
.Lb_loop:
        cmp     x2, x1
        b.ge    .Lb_done
        ldrb    w5, [x0, x2]
        cmp     w5, #128
        b.lo    .Lb_skip                // below 128: skip the increment (a data-dependent branch)
        add     x3, x3, #1
.Lb_skip:
        add     x2, x2, #1
        b       .Lb_loop
.Lb_done:
        mov     x0, x3
        ret

// long count_branchless(const uint8_t *a, long n): count += (a[i] >= 128);
        .p2align 4
        .globl  _count_branchless
_count_branchless:
        mov     x2, #0                  // i
        mov     x3, #0                  // count
.Lbl_loop:
        cmp     x2, x1
        b.ge    .Lbl_done
        ldrb    w5, [x0, x2]
        cmp     w5, #128
        cset    w6, hs                  // w6 = 1 if byte >= 128, else 0: no data-dependent branch
        add     x3, x3, x6
        add     x2, x2, #1
        b       .Lbl_loop
.Lbl_done:
        mov     x0, x3
        ret

Step through one byte of the branchy loop, once with the guess right and once wrong:

A correct guess costs almost nothing. A wrong one is a pipeline flushpipeline flush: Discarding the instructions a core ran speculatively after a branch is resolved the other way, and refetching from the correct target; the cost of a misprediction.: the work on the predicted path is discarded and the core refetches from the correct target. LLVM’s scheduling models put that at 13 cycles on AMD’s Zen 4, 14 on Intel’s Skylake and 10 on Arm’s Neoverse V2. The run times the branchy count against the branchless one, on the bytes shuffled and then sorted:

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run("""
# The machine the timings come from, then build the counting loops and run them
/usr/sbin/sysctl -n machdep.cpu.brand_string
clang -O2 -o branch branch_main.c branch.s
./branch
""")

# The machine the timings come from, then build the counting loops and run them
$ /usr/sbin/sysctl -n machdep.cpu.brand_string
Apple M5 Pro
$ clang -O2 -o branch branch_main.c branch.s
$ ./branch
10000000 bytes, counting those >= 128, fastest of 11 runs
data       count    branchy ns/byte  branchless ns/byte
shuffled   4999537  2.658            0.261
sorted     4999537  0.250            0.250
branchy:    shuffled / sorted = 10.6x
branchless: shuffled / sorted = 1.0x
all four counts agree: yes

The branchy loop is about ten times slower on shuffled bytes than on the same bytes sorted. The branchless loop runs at the same speed on both, a ratio of 1.0: its time does not depend on the data’s order because there is no guess to get wrong. All four runs count the same 4,999,537 bytes.

What the predictor learns, and when it fails

The predictor guesses each branch from the recent history of how it and its neighbours have gone. A branch that is almost always taken is predicted taken and is right almost always; a branch that alternates with no pattern defeats it. That is the whole difference between the two runs above. Sorted bytes make the branch taken for every low byte, which skips the increment, and then not taken for every high byte: one switch, which the predictor learns at once. Shuffled bytes make it a coin flip, so about half the guesses are wrong and the loop pays a flush on half its passes.

This is why the same instructions run fast or slow on different data. Three threads follow. A compiler can replace the data-dependent branch with a conditional select that has nothing to mispredict. The predictor’s memory is finite, so a repeating pattern is learned only while it is short enough to fit. And speculative execution has a cost beyond speed: a speculative load can leave a trace in the cache that outlasts the discarded work. That trace, a side channelside channel: A way to learn a secret not from the data itself but from a measurable effect of handling it, such as how long an operation took or whether a cache line was loaded. left by speculative execution past a bounds check, is the mechanism of Spectre variant 1, bounds check bypass, and the reason for the defences this lesson ends with.

Practise

Work on copies of branch.s, above, and of branch_main.c:

// branch_main.c: count how many of 10,000,000 bytes are >= 128, four ways, and time each.
// A branchy count has an if; a branchless count adds the comparison's 0/1 result. The data is either
// sorted (so a run of lows is followed by a run of highs: the branch is easy to predict) or shuffled
// (so each byte is a coin flip: the branch is hard to predict). The four combinations show when a branch costs.
#include <pthread/qos.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long count_branch(const uint8_t *a, long n);      // in branch.s: if (a[i] >= 128) count++;
long count_branchless(const uint8_t *a, long n);   // in branch.s: count += (a[i] >= 128);

enum { N = 10000000, REPEAT = 11 };
static uint8_t data[N];

static uint64_t now(void) { return clock_gettime_nsec_np(CLOCK_UPTIME_RAW); }

// A small deterministic generator, so the run repeats exactly.
static uint64_t seed = 0x2545F4914F6CDD1DULL;
static uint32_t next_rand(void) {
    seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17;
    return (uint32_t)(seed >> 32);
}

static int by_byte(const void *a, const void *b) { return (int)*(const uint8_t *)a - (int)*(const uint8_t *)b; }

static uint64_t best_ns(long (*f)(const uint8_t *, long), long *out) {
    uint64_t best = UINT64_MAX;
    for (int r = 0; r < REPEAT; r++) {
        uint64_t t0 = now();
        *out = f(data, N);
        uint64_t t = now() - t0;
        if (t < best) best = t;
    }
    return best;
}

int main(void) {
    pthread_set_qos_class_self_np(QOS_CLASS_USER_INTERACTIVE, 0);
    for (long i = 0; i < N; i++) data[i] = (uint8_t)next_rand();
    long c;
    printf("%d bytes, counting those >= 128, fastest of %d runs\n", N, REPEAT);
    printf("data       count    branchy ns/byte  branchless ns/byte\n");
    // shuffled first: every byte is an independent draw, so >=128 is about a coin flip
    uint64_t sb = best_ns(count_branch, &c);
    long cs = c;
    uint64_t sl = best_ns(count_branchless, &c);
    long ls = c;
    printf("shuffled   %-8ld %-16.3f %.3f\n", cs, (double)sb / N, (double)sl / N);
    // sort, so all the lows come before all the highs: the branch is taken for every low byte, then never again
    qsort(data, N, 1, by_byte);
    uint64_t pb = best_ns(count_branch, &c);
    long cp = c;
    uint64_t pl = best_ns(count_branchless, &c);
    long lp = c;
    printf("sorted     %-8ld %-16.3f %.3f\n", cp, (double)pb / N, (double)pl / N);
    // The time ratios say whether the data's order matters; the counts show all four runs did the same work.
    int same = cs == cp && ls == cs && lp == cs;
    printf("branchy:    shuffled / sorted = %.1fx\n", (double)sb / pb);
    printf("branchless: shuffled / sorted = %.1fx\n", (double)sl / pl);
    printf("all four counts agree: %s\n", same ? "yes" : "no");
    return same ? 0 : 1;
}

1. Change the threshold in branch.s from 128 to 200 and predict, before you run, how the shuffled branchy time changes.
2. Change the data generator in branch_main.c to fill the array with a fixed repeating pattern, 0, 255, 0, 255, and predict whether the branchy loop is fast or slow on it before you measure.

The exercise works the measurement backwards: from the sorted and shuffled times and the share of wrong guesses, it estimates what one misprediction costs in cycles.

def time_per_byte(base_ns, miss_rate, penalty_cycles, ghz):
    """Expected nanoseconds a byte: the time with every guess right, plus the mispredictions' share."""
    return 0.0  # replace with your code


def penalty_cycles(sorted_ns, shuffled_ns, miss_rate, ghz):
    """The misprediction penalty, in cycles, that explains the shuffled time."""
    return 0.0  # replace with your code

"""Sample tests: times close to the page's run, and a few made-up loops."""

from cost import penalty_cycles, time_per_byte


def test_no_misses_costs_nothing_extra():
    assert round(time_per_byte(0.25, 0.0, 15, 4.0), 6) == 0.25


def test_half_the_bytes_mispredicted():
    assert round(time_per_byte(0.25, 0.5, 16, 4.0), 6) == 2.25


def test_a_slower_clock_makes_each_miss_longer():
    assert round(time_per_byte(0.5, 0.25, 12, 2.0), 6) == 2.0


def test_penalty_from_times_close_to_the_page():
    assert round(penalty_cycles(0.25, 2.65, 0.5, 4.0), 6) == 19.2


def test_penalty_of_a_made_up_loop():
    assert round(penalty_cycles(1.0, 2.0, 0.25, 3.0), 6) == 12.0


def test_fewer_misses_mean_a_larger_penalty_for_the_same_gap():
    assert round(penalty_cycles(0.4, 0.9, 0.1, 2.0), 6) == 10.0


def test_the_two_functions_undo_each_other():
    shuffled = time_per_byte(0.31, 0.5, 14, 3.5)
    assert round(penalty_cycles(0.31, shuffled, 0.5, 3.5), 6) == 14.0

Removing the branch the predictor can miss Pro: opens with a Pro, Premium or Ultimate pass

How far ahead the predictor can see Pro: opens with a Pro, Premium or Ultimate pass

Speculation, side channels and the defences Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

A warm-up: a loop that filters an array is slow, and a colleague blames the cache. How would you check whether it is really branch misprediction?

I would first look at the branch in the loop and ask whether its outcome follows the data unpredictably, as a filter on a near-even condition does. Then I would sort the input, so the branch becomes predictable, and measure again: the loop still reads the same memory in the same order, so if the time falls sharply the cost was misprediction, not the cache. A second check is a branchless version, whose time should no longer depend on the order. On Linux, perf stat reads the branch-miss counter directly and settles it.

Three further questions build on it: diagnosing a data-dependent slowdown, choosing branchless, and a speculative side channel:

Key takeaways

• A correct branch prediction costs almost nothing; a misprediction flushes the speculative work and refetches, ten or more cycles on current cores.
• The predictor learns from history, so a branch that follows unpredictable data is slow: sorting the data made the same branchy loop about ten times faster.
• Speculative execution runs ahead on every guess, and a speculative load can leave a trace in the cache that outlasts the discarded work.