了解分支预测效率

Question

我尝试测量分支预测成本，我创建了一个小程序。

它在堆栈上创建了一个小缓冲区，用随机的 0/1 填充。我可以用 N 设置缓冲区的大小。该代码重复导致相同 1<<N 个随机数的分支。

现在，我预计，如果 1<<N 足够大（比如 >100），那么分支预测器将不会有效（因为它必须预测 >100 个随机数）。然而，这些是结果（在 5820k 机器上），随着 N 的增长，程序变慢了：

N   time
=========
8   2.2
9   2.2
10  2.2
11  2.2
12  2.3
13  4.6
14  9.5
15  11.6
16  12.7
20  12.9

作为参考，如果缓冲区用零初始化（使用注释init），时间或多或少是常数，对于N 8..16，它在1.5-1.7之间变化.

我的问题是：分支预测器能否有效预测如此大量的随机数？如果不是，那这是怎么回事？

（更多解释：代码执行 2^32 个分支，与 N 无关。所以我预计，代码运行相同的速度，无论 N，因为根本无法预测分支。但似乎如果缓冲区大小小于 4096（N<=12），某些东西会使代码变快。分支预测对 4096 个随机数是否有效？）

代码如下：

#include <cstdint>
#include <iostream>

volatile uint64_t init[2] = { 314159165, 27182818 };
// volatile uint64_t init[2] = { 0, 0 };
volatile uint64_t one = 1;

uint64_t next(uint64_t s[2]) {
    uint64_t s1 = s[0];
    uint64_t s0 = s[1];
    uint64_t result = s0 + s1;
    s[0] = s0;
    s1 ^= s1 << 23;
    s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5);
    return result;
}

int main() {
    uint64_t s[2];
    s[0] = init[0];
    s[1] = init[1];

    uint64_t sum = 0;

#if 1
    const int N = 16;

    unsigned char buffer[1<<N];
    for (int i=0; i<1<<N; i++) buffer[i] = next(s)&1;

    for (uint64_t i=0; i<uint64_t(1)<<(32-N); i++) {
        for (int j=0; j<1<<N; j++) {
            if (buffer[j]) {
                sum += one;
            }
        }
    }
#else
    for (uint64_t i=0; i<uint64_t(1)<<32; i++) {
        if (next(s)&1) {
            sum += one;
        }
    }

#endif
    std::cout<<sum<<"\n";
}

（该代码还包含一个非缓冲版本，使用 #if 0。它的运行速度与使用 N=16 的缓冲版本大致相同）

这是内部循环反汇编（用 clang 编译。它为 8..16 之间的所有 N 生成相同的代码，只是循环计数不同。Clang 展开循环两次）：

  401270:       80 3c 0c 00             cmp    BYTE PTR [rsp+rcx*1],0x0
  401274:       74 07                   je     40127d <main+0xad>
  401276:       48 03 35 e3 2d 00 00    add    rsi,QWORD PTR [rip+0x2de3]        # 404060 <one>
  40127d:       80 7c 0c 01 00          cmp    BYTE PTR [rsp+rcx*1+0x1],0x0
  401282:       74 07                   je     40128b <main+0xbb>
  401284:       48 03 35 d5 2d 00 00    add    rsi,QWORD PTR [rip+0x2dd5]        # 404060 <one>
  40128b:       48 83 c1 02             add    rcx,0x2
  40128f:       48 81 f9 00 00 01 00    cmp    rcx,0x10000
  401296:       75 d8                   jne    401270 <main+0xa0>

Answer 1

分支预测可以这么有效。正如 Peter Cordes 所建议的，我已经用 perf stat 检查了分支未命中。以下是结果：

N   time          cycles  branch-misses (%)      approx-time
===============================================================
8    2.2   9,084,889,375         34,806 ( 0.00)    2.2
9    2.2   9,212,112,830         39,725 ( 0.00)    2.2
10   2.2   9,264,903,090      2,394,253 ( 0.06)    2.2
11   2.2   9,415,103,000      8,102,360 ( 0.19)    2.2
12   2.3   9,876,827,586     27,169,271 ( 0.63)    2.3
13   4.6  19,572,398,825    486,814,972 (11.33)    4.6
14   9.5  39,813,380,461  1,473,662,853 (34.31)    9.5
15  11.6  49,079,798,916  1,915,930,302 (44.61)   11.7
16  12.7  53,216,900,532  2,113,177,105 (49.20)   12.7
20  12.9  54,317,444,104  2,149,928,923 (50.06)   12.9

Note: branch-misses (%) is calculated for 2^32 branches

如您所见，当N<=12时，分支预测器可以预测大部分分支（令人惊讶：分支预测器可以记住4096个连续随机分支的结果！）。当 N>12 时，分支未命中数开始增加。在 N>=16，它只能正确预测 ~50%，这意味着它与随机抛硬币一样有效。

所花费的时间可以通过查看时间和分支未命中 (%) 列来估算：我添加了最后一列，approx-time。我是这样计算的：2.2+(12.9-2.2)*branch-misses %/100。如您所见，approx-time 等于 time（不考虑舍入误差）。所以这个效果完全可以用分支预测来解释。

最初的目的是计算一个分支未命中的周期数（在这种特殊情况下 - 对于其他情况，这个数字可能不同）：

(54,317,444,104-9,084,889,375)/(2,149,928,923-34,806) = 21.039 = ~21 cycles.

了解分支预测效率

Understanding branch prediction efficiency

performance

x86

x86-64

cpu-architecture

branch-prediction