了解分支机构预测效率

Question

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

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

现在，我预计，如果 1

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

代码如下:

#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";
}

（代码也包含非缓冲版本，如果0＜/code＞，请使用＜code＞#。它的运行速度与缓冲版本相同，＜code＞N＝16＜/code>）

以下是内部循环反汇编（用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）所建议的那样，我已经用性能统计信息检查了分支未命中。以下是结果：

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

如您所见，当< code>N

通过查看时间和分支失误(%)列，可以估计所用的时间:我添加了最后一列< code>approx-time。我是这样算的:< code > 2.2(12.9-2.2)*分支失误%/100。如您所见，< code>approx-time等于< code>time(不考虑舍入误差)。所以这种效应可以用分支预测来完美解释。

最初的目的是计算分支未命中的周期数(在这种特殊情况下——对于其他情况，这个数字可以不同):

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