快速和慢速的 if 语句：现代处理器的分支预测

| 2015-10-12

语句的性能取决于它的判断条件是否拥有可预测模式，你知道吗？如果条件始终为真或者始终为假，处理器内的分支预测逻辑会选择该模式。此外，如果该模式不可预测，if语句的开销将更大。本文将解释为什么现代处理器要这样做。

接下来，我们在不同条件下测试该循环的性能：

for (int i = 0; i < max; i++) if (<condition>) sum++;

以下是不同真-假模式下该循环的耗时：

条件	Pattern/模式	时间 (ms)
(i & 0×80000000) == 0	T repeated	322
(i & 0xffffffff) == 0	F repeated	276
(i & 1) == 0	TF alternating	760
(i & 3) == 0	TFFFTFFF…	513
(i & 2) == 0	TTFFTTFF…	1675
(i & 4) == 0	TTTTFFFFTTTTFFFF…	1275
(i & 8) == 0	8T 8F 8T 8F …	752
(i & 16) == 0	16T 16F 16T 16F …	490

语句在“坏”真-假模式下比在“好”模式下慢了近六倍！当然，模式的好坏取决于编译器产生的具体指令集和具体处理器。

让我们看看处理器计数器

了解处理器如何利用时间的一种方式是查看硬件计数器。为帮助性能调试，现代处理器在执行代码时跟踪各种计数器：执行指令的数量，各种类型内存访问的数量，遇到分支的数量等等。要读取计数器，你需要像Visual Studio 2010预览版或旗舰版中的profiler，AMD Code Analyst或者Intel VTune类似的工具。

为了验证我们观察到的性能降低是由于if语句造成的，我们可以查看分支预测错误计数器：

TF pattern

最糟糕的模式（TTFFTTFF…）将导致744次分支预测错误，而好的模式下大约只有10次。无疑坏情况花费最长的1.67秒，而好模式下仅花费大约300毫秒！

接下来分析分支预测做了什么，以及为什么它会对处理器性能有这么大影响。

分支预测扮演什么角色？

为解释分支预测是什么以及为何会影响性能参数，首先我们需要了解一下现代处理器的工作原理。为了执行每条指令，CPU会经历以下这些（可能更多）步骤：

1. 取指：读取下一条指令。

2. 译码：完成指令的翻译。

3. 执行：执行指令。

4. 回写：保存结果到内存。

一个重要的优化是流水线阶段可同时处理不同指令。那么，在读取一条指令时，第二条指令正在译码，第三条指令正在执行，而第四条指令正在回写。现代处理器有10-31级流水线（例如，Pentium 4 Prescott有31级），为优化性能，保持所有阶段尽可能一直工作非常重要。

pipeline

图像来源于https://commons.wikimedia.org/wiki/File:Pipeline,_4_stage.svg

分支（即条件跳转）给处理器流水线提出一个难题。在获取一条指令后，处理器需要获取下一条指令。但是下一条指令有两种可能！处理器不确定取哪一条，直到分支条件指令执行到流水线结束。

与暂停流水线直至分支条件指令完全执行不同，现代处理器尝试预测是否需要进行跳转。然后处理器会读取它认为正确的下一条指令。如果预测出错，处理器会丢弃在流水线上执行了部分的指令。在维基分支预测器实现页面上，可以看到处理器获取并解释分支统计数据的一些经典技术。

现代分支预测器适合分析简单模式：全真，全假，真-假交替等。但是如果模式超出分支预测器的预测，性能影响将会非常严重。幸好大部分分支很容易预测，比如下面两个高亮的例子：

int SumArray(int[] array) {
    if (array == null) throw new ArgumentNullException("array");

    int sum=0;
    for(int i=0; i<array.Length; i++) sum += array[i];
    return sum;
}

第一个高亮的条件检查输入的合法性，那么该分支很少会执行。第二条高亮条件是循环终止条件。这也几乎总是朝着一个方向走,除非处理的数组非常短。所以，在这些情况下,与大多数情况类似,处理器分支预测逻辑可以有效防止处理器流水线暂停。