performance - 了解分支预测效率

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 )，时间或多或少是常数，它在 1.5-1.7 之间变化 N 8..16.

我的问题是:分支预测器能否有效预测如此大量的随机数？如果不是，那么这里发生了什么？

(更多解释:代码执行 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.