推测执行 vs 无分支代码

推测执行与无分支代码：隐藏的性能权衡

现代处理器每秒执行数十亿次操作，但内存访问速度的增长却相对缓慢。这种差距意味着等待数据成为性能损失的主要来源。处理器已从被动执行器演变为主动的数据流管理器：乱序执行、依赖重排序和推测执行。

分支预测允许提前启动加载操作，从而隐藏内存延迟。一次预测错误会消耗10-20个周期，但等待L3或DRAM则需要数百个周期。无分支代码消除了预测错误，但也剥夺了处理器的推测能力。

从顺序执行到推测执行的演变

早期系统严格按照顺序执行指令。IBM System/360 Model 91引入了Tomasulo算法以实现乱序执行：指令在操作数就绪时启动。

推测执行后来出现在超标量处理器中，如英特尔奔腾Pro（1995年）。一个40微操作的流水线保持数十条指令在飞行中，基于历史预测分支。

for (size_t i = 0; i < n; i++) {
    if (arr[i] >= 0) {
          ... code_true ...;
    } else {
        ... code_false ...;
    }
}

在这里，如果数据不在L1中，加载arr[i]可能导致10-100+个周期的停顿。处理器预测分支，启动code_true，并初始化预取。预测错误时——刷新并重新开始。

无分支与有分支：缓存依赖性

简化有分支代码：

if (arr[i] > 0) {
    result++;
}

变为：

result += (arr[i] > 0);

• 数据在L1中：无分支胜出——无预测错误，延迟最小。
• L2中：中性，预测错误的成本较低。
• L3/DRAM中：有分支更快——推测触发早期预取，隐藏延迟。

无分支将延迟移入关键路径：处理器在比较前等待数据，没有重叠计算。

值搜索：无条件加载的成本

原始代码：

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    if (keys[i] == target) {
        result = values[i];
    }
}
return result;

无分支代码：

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    result = (keys[i] == target) ? values[i] : result;
}
return result;

在无分支代码中，values[i]在每次迭代中加载，浪费了整个数组的带宽。原始代码只读取直到匹配为止。

二分搜索：依赖链

有分支代码：

while (low < high) {
    size_t mid = low + (high - low) / 2;
    if (keys[mid] < target)
        low = mid + 1;
    else
        high = mid;
}

处理器推测性地计算下一个mid并预取keys[mid]。

无分支代码：

while (low < high) {
    size_t mid = low + (high - low) / 2;
    size_t step = (high - low) / 2;
    low  = (keys[mid] < target) ? mid + 1 : low;
    high = (keys[mid] < target) ? high    : mid;
}

对比较结果的依赖阻碍了推测：下一个mid等待low/high的写入。

• 一半的预测是错误的，但早期预取与刷新重叠。
• 无分支：更多指令，后期加载，显式内存延迟。

关键要点

• 推测通过触发预测分支上的预取来隐藏内存延迟。
• 无分支消除了预测错误，但在L3/DRAM访问时恶化性能。
• 在目标硬件上分析：L1——无分支，大数组——有分支。
• 游戏机移植常因忽略这些效应而受影响。
• 无分支链中的依赖阻碍了乱序优化。

在L1中随机数据时，无分支占优。在有模式或大容量数据时，有分支因推测加载而胜出。

— Editorial Team