分支预测

处理器不会等到知道 if 往哪边走才行动：它先猜，然后开始干活。猜对不花代价，猜错就要把已做的活丢掉，大约损失 15 个周期。猜对的频率取决于数据：同一个循环处理同样的 SPY 收益率，排序之后周期数少 8.3 倍。

处理器像一条流水线：一条指令在执行时，后面的指令已经在取指和译码。if 会打断流水线，因为下一条指令取决于它的答案，而答案还没出来。所以处理器会做一次分支预测并按它往前跑。猜对了，什么都不损失。猜错了，在错误路径上做的工作要丢掉，流水线重新开始，在现代内核上大约要 15 个周期，和访问一次 L2 缓存差不多。我们把分支的结果写成 True（当分支跳转时）。在交易循环里，分支比如是 if daily_return > 0，它的结果流就是每天一个 True 或 False。

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

六天里有四天收益为正，所以分支跳转四次、不跳转两次。最简单的预测器是总是跳转，它恰好只在两个 False 结果上猜错。它猜对的比例等于分支跳转的比例，并且不看历史。

真实的处理器会利用历史。1 位预测器记住分支上一次的行为，并猜同样的结果。结果成串出现时它表现很好，但每个孤立的异常结果它要错两次：一次在它出现时，一次在原来的串恢复时。2 位预测器用一个在两端停住的 0 到 3 的计数器解决了这个问题。它在 2 和 3 时猜“跳转”，每个结果让它走一步，所以要连续两个与猜测相反的结果才会改主意。我们让 1 位预测器从“不跳转”开始，计数器从 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. 1计数器朝结果方向走一步，并停在 0 和 3：这就是“饱和”的含义。

在四个一串的序列上，两个预测器都错三次（第一次猜测和两次转折）。在一串跳转中夹一个孤立的 False 时，1 位预测器错三次，2 位预测器只错一次，因为计数器只是从 3 降到 2，仍然猜“跳转”。这就是真实处理器偏爱计数器的原因。也要记住另一面：当结果没有规律时，没有任何预测器能比猜更常见的答案做得更好。

要把猜错换算成时间，只需相加：每个分支花一个基础周期，每次猜错再加 15 的惩罚。下面就是本讲得名的实验：取 SPY 的前 4,000 个日收益率，把分支 return > 0 跑两遍，一遍按日期顺序，一遍按排序后的顺序。排序不改变数字本身，只改变它们的顺序，却把结果从抛硬币变成了两个长串：先是全部的 False，然后是全部的 True。

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

按日期顺序，4,000 个收益率里有 2,200 个为正，所以分支有 55% 的时间跳转，并且几乎没有规律地在两种答案之间来回跳：总是跳转错 1,800 次，1 位预测器错 2,035 次，2 位预测器错 1,950 次。有记忆的预测器甚至比简单的猜测更差，因为它们会跟着每一次翻转走。排序之后，结果是 1,800 个 False 接着 2,200 个 True，2 位预测器只错 2 次。代价从 33,250 个周期降到 4,030，少了 8.3 倍，数据和循环完全相同。

实验沿着本讲走：分支的结果、三个预测器、以周期计的代价、排序后的结果流，以及对日期顺序和排序后的 SPY 收益率的研究。

• 函数 · 问题依赖
• taken_sequence(values, threshold)分支对每个值怎么走？简单算术
• always_taken_mispredicts(outcomes)“总是跳转”会错多少次？简单算术
• one_bit_mispredicts(outcomes)记住上一个结果的预测器呢？简单算术
• two_bit_mispredicts(outcomes)饱和计数器呢？简单算术
• cycles(n_branches, mispredicts)这一切总共花多少？简单算术
• sorted_stream(values, threshold)如果先把值排序呢？taken_sequence
• study(bars)排序在 SPY 上能省多少？sorted_streamtwo_bit_mispredictscycles

下一个主题：结业项目把整个技能串起来。给你一张逐笔数据表和一个读取它的工作负载，你把它重新排布成行、列或块，用自己造的缓存数出每种布局的缓存缺失，用第一个主题的延迟模型算出代价，并证明哪种布局胜出。