Branch prediction

A processor does not wait to find out which way an if goes: it guesses and starts working. A right guess is free and a wrong one throws the work away, about 15 cycles lost. How often it guesses right depends on the data: the same loop over the same SPY returns costs 8.3 times fewer cycles once the returns are sorted.

A processor works like an assembly line: while one instruction runs, the next ones are already being fetched and decoded. An if breaks the line, because the next instruction depends on its answer, and the answer is not ready yet. So the processor makes a branch prediction and runs ahead on it. If the guess was right nothing is lost. If it was wrong the work done on the wrong path is thrown away and the line restarts, which costs about 15 cycles on a modern core, as much as a visit to the L2 cache. We write the outcome of a branch as True when it is taken. In a trading loop a branch is, for instance, if daily_return > 0, and the stream of its outcomes is simply one True or False per day.

def taken_sequence(values, threshold):    return [bool(value > threshold) for value in values]def always_taken_mispredicts(outcomes):    return sum(1 for outcome in outcomes if not outcome)returns = [0.004, -0.012, 0.007, 0.001, -0.003, 0.009]outcomes = taken_sequence(returns, 0)print(outcomes)print(always_taken_mispredicts(outcomes), "misses out of", len(outcomes))

[True, False, True, True, False, True]
2 misses out of 6

Of six days, four had a positive return, so the branch is taken four times and not taken twice. The simplest predictor, always taken, is wrong exactly on the two False outcomes. It is right as often as the branch is taken, and it ignores the history.

Real processors use the history. The 1-bit predictor remembers what the branch did last time and guesses the same again. It is good when outcomes come in runs, but it pays twice for every stray outcome: once when the stray one arrives and once when the run resumes. The 2-bit predictor fixes that with a counter from 0 to 3 that stops at both ends. It guesses "taken" at 2 and 3, moves one step toward each outcome, and so it needs two outcomes in a row against its guess to change its mind. We start the 1-bit guess at "not taken" and the counter at 1.

def one_bit_mispredicts(outcomes):    guess = False    wrong = 0    for outcome in outcomes:        if guess != outcome:            wrong += 1        guess = outcome    return wrongdef two_bit_mispredicts(outcomes):    counter = 1    wrong = 0    for outcome in outcomes:        if (counter >= 2) != outcome:            wrong += 1        counter = min(3, counter + 1) if outcome else max(0, counter - 1)1    return wrongruns = [True] * 4 + [False] * 4 + [True] * 4stray = [True] * 6 + [False] + [True] * 6for name, stream in (("runs", runs), ("one stray", stray)):    print(name, "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", two_bit_mispredicts(stream))

runs | 1-bit 3 | 2-bit 5
one stray | 1-bit 3 | 2-bit 2

1. 1The counter moves one step toward the outcome and stops at 0 and 3: this is what makes it saturating.

On the runs of four, both predictors miss three times (the first guess, and the two turns). With one stray False among taken outcomes the 1-bit predictor misses three times and the 2-bit predictor only once, because the counter drops from 3 to 2 and still guesses "taken". That is why real processors prefer counters. Keep in mind the other side: when outcomes have no pattern, no predictor can do better than guessing the more frequent answer.

To turn misses into time we add them up: every branch costs a base of one cycle and every miss adds a penalty of 15. Now the experiment that this lecture is named for: take the first 4,000 daily returns of SPY and run the branch return > 0 twice, over the returns in date order and over the same returns sorted. Sorting changes nothing about the numbers, only their order, but it changes the outcomes from a coin flip into two long runs: all the False first and all the True after.

def cycles(n_branches, mispredicts, penalty=PENALTY, base=BASE_CYCLES):    return base * n_branches + penalty * mispredictsdef sorted_stream(values, threshold):    return taken_sequence(sorted(values), threshold)returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:4000]for name, stream in (("unsorted", taken_sequence(returns, 0)), ("sorted", sorted_stream(returns, 0))):    wrong = two_bit_mispredicts(stream)    print(name, "| always", always_taken_mispredicts(stream), "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", wrong, "|", cycles(len(stream), wrong), "cycles")

unsorted | always 1800 | 1-bit 2035 | 2-bit 1950 | 33250 cycles
sorted | always 1800 | 1-bit 1 | 2-bit 2 | 4030 cycles

In date order 2,200 of the 4,000 returns are positive, so the branch is taken 55% of the time, and it jumps from one answer to the other almost without a pattern: always-taken misses 1,800 times, the 1-bit predictor 2,035 and the 2-bit predictor 1,950. The predictors with a memory are even worse than the plain guess, because they follow every flip. Sorted, the outcomes are 1,800 False followed by 2,200 True, and the 2-bit predictor misses only 2 times. The cost falls from 33,250 to 4,030 cycles, 8.3 times fewer, with the very same data and the very same loop.

The lab follows the lecture: the outcomes of a branch, the three predictors, the cost in cycles, the sorted stream, and a study of the SPY returns in date order and sorted.

• Function · questionBuilds on
• taken_sequence(values, threshold)What does the branch do for each value?Plain arithmetic
• always_taken_mispredicts(outcomes)How often is "always taken" wrong?Plain arithmetic
• one_bit_mispredicts(outcomes)And a predictor that remembers the last outcome?Plain arithmetic
• two_bit_mispredicts(outcomes)And a saturating counter?Plain arithmetic
• cycles(n_branches, mispredicts)What does it all cost?Plain arithmetic
• sorted_stream(values, threshold)What if the values were sorted first?taken_sequence
• study(bars)How much does sorting save on SPY?sorted_streamtwo_bit_mispredictscycles

Next topic: the capstone puts the whole skill together. You are given a table of ticks and a workload that reads it, and you re-lay it out as rows, columns or blocks, count the cache misses of each layout with the cache you built, price them with the latency model of the first topic, and prove which layout wins.