c++ - 为什么这个C++函数会产生如此多的分支错误预测？

Question

令A为包含奇数个零和一的数组。如果n是A的大小，则A的构造应使第一个ceil(n/2)元素为0，其余元素为1。

因此，如果n = 9，A看起来像这样:
0,0,0,0,0,1,1,1,1
我们的目标是在数组中找到1s的总和，我们可以通过使用以下函数来实现:

s = 0;
void test1(int curIndex){
    //A is 0,0,0,...,0,1,1,1,1,1...,1

    if(curIndex == ceil(n/2)) return;

    if(A[curIndex] == 1) return;

    test1(curIndex+1);
    test1(size-curIndex-1);

    s += A[curIndex+1] + A[size-curIndex-1];

}

对于给定的问题，此功能相当愚蠢，但它是对另一个功能的模拟，我希望这样看起来并产生相同数量的分支错误预测。

这是实验的完整代码:

#include <iostream>
#include <fstream>

using namespace std;


int size;
int *A;
int half;
int s;

void test1(int curIndex){
    //A is 0,0,0,...,0,1,1,1,1,1...,1

    if(curIndex == half) return;
    if(A[curIndex] == 1) return;

    test1(curIndex+1);
    test1(size - curIndex - 1);

    s += A[curIndex+1] + A[size-curIndex-1];

}


int main(int argc, char* argv[]){

    size = atoi(argv[1]);
    if(argc!=2){
        cout<<"type ./executable size{odd integer}"<<endl;
        return 1;
    }
    if(size%2!=1){
        cout<<"size must be an odd number"<<endl;
        return 1;
    }
    A = new int[size];

    half = size/2;
    int i;
    for(i=0;i<=half;i++){
        A[i] = 0;
    }
    for(i=half+1;i<size;i++){
        A[i] = 1;
    }

    for(i=0;i<100;i++) {
        test1(0);
    }
    cout<<s<<endl;

    return 0;
}

输入 g++ -O3 -std=c++11 file.cpp进行编译，然后输入 ./executable size{odd integer}进行运行。

我使用的是Intel®CoreTM i5-3470 CPU @ 3.20GHz，具有8 GB RAM，L1高速缓存256 KB，L2高速缓存1 MB，L3高速缓存6 MB。

运行 perf stat -B -e branches,branch-misses ./cachetests 111111给我以下内容:

   Performance counter stats for './cachetests 111111':

    32,639,932      branches                                                    
     1,404,836      branch-misses             #    4.30% of all branches        

   0.060349641 seconds time elapsed

如果我删除线

s += A[curIndex+1] + A[size-curIndex-1];

我从perf得到以下输出:

  Performance counter stats for './cachetests 111111':

    24,079,109      branches                                                    
        39,078      branch-misses             #    0.16% of all branches        

   0.027679521 seconds time elapsed

当它甚至不是if语句时，该行与分支预测有什么关系？

我的看法是，在 ceil(n/2) - 1的第一个 test1()调用中，两个if语句都为false。在 ceil(n/2)-th调用中， if(curIndex == ceil(n/2))将为true。在其余的 n-ceil(n/2)调用中，第一个语句为false，第二个语句为true。

为什么英特尔无法预测这种简单的行为？

现在让我们看第二种情况。假设 A现在具有交替的零和一。我们将始终从0开始。因此，如果 n = 9 A看起来像这样:
0,1,0,1,0,1,0,1,0
我们将要使用的功能如下:

void test2(int curIndex){
    //A is 0,1,0,1,0,1,0,1,....
    if(curIndex == size-1) return;
    if(A[curIndex] == 1) return;

    test2(curIndex+1);
    test2(curIndex+2);

    s += A[curIndex+1] + A[curIndex+2];

}

这是实验的完整代码:

#include <iostream>
#include <fstream>

using namespace std;


int size;
int *A;
int s;

void test2(int curIndex){
    //A is 0,1,0,1,0,1,0,1,....
    if(curIndex == size-1) return;
    if(A[curIndex] == 1) return;

    test2(curIndex+1);
    test2(curIndex+2);

    s += A[curIndex+1] + A[curIndex+2];

}

int main(int argc, char* argv[]){

    size = atoi(argv[1]);
    if(argc!=2){
        cout<<"type ./executable size{odd integer}"<<endl;
        return 1;
    }
    if(size%2!=1){
        cout<<"size must be an odd number"<<endl;
        return 1;
    }
    A = new int[size];
    int i;
    for(i=0;i<size;i++){
        if(i%2==0){
            A[i] = false;
        }
        else{
            A[i] = true;
        }
    }

    for(i=0;i<100;i++) {
        test2(0);
    }
    cout<<s<<endl;

    return 0;
}

我使用与以前相同的命令来运行perf:

    Performance counter stats for './cachetests2 111111':

    28,560,183      branches                                                    
        54,204      branch-misses             #    0.19% of all branches        

   0.037134196 seconds time elapsed

再次删除该行可以使事情有所改善:

   Performance counter stats for './cachetests2 111111':

    28,419,557      branches                                                    
        16,636      branch-misses             #    0.06% of all branches        

   0.009977772 seconds time elapsed

现在，如果我们分析函数， if(curIndex == size-1)将是错误的 n-1倍， if(A[curIndex] == 1)将从true变为false。

如我所见，这两个函数应该易于预测，但是第一个函数却并非如此。同时，我不确定该行发生了什么，以及为什么它在改善分支行为方面起着作用。

Answer 1

凝视了一段时间后，这是我对此的想法。首先，
这个问题可以通过-O2轻松重现，因此最好将其用作
引用，因为它会生成简单的非展开代码，易于执行
分析。 -O3的问题本质上是相同的，只是不那么明显。

因此，对于第一种情况(半零模式的半零模式)，编译器
生成此代码:

 0000000000400a80 <_Z5test1i>:
   400a80:       55                      push   %rbp
   400a81:       53                      push   %rbx
   400a82:       89 fb                   mov    %edi,%ebx
   400a84:       48 83 ec 08             sub    $0x8,%rsp
   400a88:       3b 3d 0e 07 20 00       cmp    0x20070e(%rip),%edi        #
   60119c <half>
   400a8e:       74 4f                   je     400adf <_Z5test1i+0x5f>
   400a90:       48 8b 15 09 07 20 00    mov    0x200709(%rip),%rdx        #
   6011a0 <A>
   400a97:       48 63 c7                movslq %edi,%rax
   400a9a:       48 8d 2c 85 00 00 00    lea    0x0(,%rax,4),%rbp
   400aa1:       00 
   400aa2:       83 3c 82 01             cmpl   $0x1,(%rdx,%rax,4)
   400aa6:       74 37                   je     400adf <_Z5test1i+0x5f>
   400aa8:       8d 7f 01                lea    0x1(%rdi),%edi
   400aab:       e8 d0 ff ff ff          callq  400a80 <_Z5test1i>
   400ab0:       89 df                   mov    %ebx,%edi
   400ab2:       f7 d7                   not    %edi
   400ab4:       03 3d ee 06 20 00       add    0x2006ee(%rip),%edi        #
   6011a8 <size>
   400aba:       e8 c1 ff ff ff          callq  400a80 <_Z5test1i>
   400abf:       8b 05 e3 06 20 00       mov    0x2006e3(%rip),%eax        #
   6011a8 <size>
   400ac5:       48 8b 15 d4 06 20 00    mov    0x2006d4(%rip),%rdx        #
   6011a0 <A>
   400acc:       29 d8                   sub    %ebx,%eax
   400ace:       48 63 c8                movslq %eax,%rcx
   400ad1:       8b 44 2a 04             mov    0x4(%rdx,%rbp,1),%eax
   400ad5:       03 44 8a fc             add    -0x4(%rdx,%rcx,4),%eax
   400ad9:       01 05 b9 06 20 00       add    %eax,0x2006b9(%rip)        #
   601198 <s>
   400adf:       48 83 c4 08             add    $0x8,%rsp
   400ae3:       5b                      pop    %rbx
   400ae4:       5d                      pop    %rbp
   400ae5:       c3                      retq   
   400ae6:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
   400aed:       00 00 00 

非常简单，有点您所期望的-两个条件分支，两个
电话。它为我们提供了有关Core 2 Duo T6570，AMD的此(或类似数据)统计信息
Phenom II X4 925和Core i7-4770:

$ perf stat -B -e branches,branch-misses ./a.out 111111
5555500

 Performance counter stats for './a.out 111111':

        45,216,754      branches                                                    
         5,588,484      branch-misses             #   12.36% of all branches        

       0.098535791 seconds time elapsed

如果要进行此更改，请在递归调用之前移动分配:

 --- file.cpp.orig  2016-09-22 22:59:20.744678438 +0300
 +++ file.cpp   2016-09-22 22:59:36.492583925 +0300
 @@ -15,10 +15,10 @@
      if(curIndex == half) return;
      if(A[curIndex] == 1) return;

 +    s += A[curIndex+1] + A[size-curIndex-1];
      test1(curIndex+1);
      test1(size - curIndex - 1);

 -    s += A[curIndex+1] + A[size-curIndex-1];

  }

画面变化:

 $ perf stat -B -e branches,branch-misses ./a.out 111111
 5555500

  Performance counter stats for './a.out 111111':

         39,495,804      branches                                                    
             54,430      branch-misses             #    0.14% of all branches        

        0.039522259 seconds time elapsed

是的，正如已经提到的，它与尾递归直接相关
优化，因为如果您要使用 -fno-optimize-sibling-calls您将获得相同的“不良”结果。让我们
看看我们在使用尾调用优化的汇编中有什么:

 0000000000400a80 <_Z5test1i>:
   400a80:       3b 3d 16 07 20 00       cmp    0x200716(%rip),%edi        #
   60119c <half>
   400a86:       53                      push   %rbx
   400a87:       89 fb                   mov    %edi,%ebx
   400a89:       74 5f                   je     400aea <_Z5test1i+0x6a>
   400a8b:       48 8b 05 0e 07 20 00    mov    0x20070e(%rip),%rax        #
   6011a0 <A>
   400a92:       48 63 d7                movslq %edi,%rdx
   400a95:       83 3c 90 01             cmpl   $0x1,(%rax,%rdx,4)
   400a99:       74 4f                   je     400aea <_Z5test1i+0x6a>
   400a9b:       8b 0d 07 07 20 00       mov    0x200707(%rip),%ecx        #
   6011a8 <size>
   400aa1:       eb 15                   jmp    400ab8 <_Z5test1i+0x38>
   400aa3:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
   400aa8:       48 8b 05 f1 06 20 00    mov    0x2006f1(%rip),%rax        #
   6011a0 <A>
   400aaf:       48 63 d3                movslq %ebx,%rdx
   400ab2:       83 3c 90 01             cmpl   $0x1,(%rax,%rdx,4)
   400ab6:       74 32                   je     400aea <_Z5test1i+0x6a>
   400ab8:       29 d9                   sub    %ebx,%ecx
   400aba:       8d 7b 01                lea    0x1(%rbx),%edi
   400abd:       8b 54 90 04             mov    0x4(%rax,%rdx,4),%edx
   400ac1:       48 63 c9                movslq %ecx,%rcx
   400ac4:       03 54 88 fc             add    -0x4(%rax,%rcx,4),%edx
   400ac8:       01 15 ca 06 20 00       add    %edx,0x2006ca(%rip)        #
   601198 <s>
   400ace:       e8 ad ff ff ff          callq  400a80 <_Z5test1i>
   400ad3:       8b 0d cf 06 20 00       mov    0x2006cf(%rip),%ecx        #
   6011a8 <size>
   400ad9:       89 c8                   mov    %ecx,%eax
   400adb:       29 d8                   sub    %ebx,%eax
   400add:       89 c3                   mov    %eax,%ebx
   400adf:       83 eb 01                sub    $0x1,%ebx
   400ae2:       39 1d b4 06 20 00       cmp    %ebx,0x2006b4(%rip)        #
   60119c <half>
   400ae8:       75 be                   jne    400aa8 <_Z5test1i+0x28>
   400aea:       5b                      pop    %rbx
   400aeb:       c3                      retq   
   400aec:       0f 1f 40 00             nopl   0x0(%rax)

它有四个条件分支，一个调用。因此，让我们分析数据
我们到目前为止。

首先，从处理器的角度来看，什么是分支指令？它可以是 call， ret， j*(包括直接 jmp)和 loop中的任何一个。 call和 jmp有点不直观，但是它们对于正确计数是至关重要的。

总体而言，我们希望此函数被调用11111100次，每次
元素，大约是1100万。在非尾部 call 优化的版本中，我们看到
分支为45M，main()中的初始化仅为111K，其他所有事情都是次要的，因此对该数字的主要贡献来自于我们的函数。我们的函数是 call -ed，它计算第一个 je，在所有情况下都为true，然后计算第二个 je，一半时间为true，然后递归调用自身(但是我们已经计算了该函数被调用11M次)或返回(如在递归调用之后一样)。因此，每11M调用有4条分支指令，恰好是我们看到的数量。在大约5.5M个分支中，有10个未命中，这表明这些未命中都来了一条错误预测的指令，要么评估了1100万次，却错失了大约50％的时间，要么就评估了一半的时间，总错失了。

在尾部 call 优化版本中我​​们有什么？我们有一个叫做
大约5.5百万次，但现在每次调用都会产生一个 call，最初是两个分支(在所有情况下，第一个分支为true，除了一个分支，第二个分支由于我们的数据始终为false)，然后是 jmp，然后是调用(但是我们ve已经计算出我们有5.5M个调用)，然后在 400ae8上创建一个分支，然后在 400ab6上创建一个分支(由于我们的数据始终为true)，然后返回。因此，平均而言，这是四个条件分支，一个无条件跳转，一个调用和一个间接分支(从函数返回)，5.5M乘以7得到的总数约为39M，这与我们在perf输出中看到的完全一样。

我们知道的是，通过一个函数调用(即使该版本具有更多的条件分支)，处理器完全不会在流中预测事物，而通过两个函数调用则具有问题。因此，这表明问题出在函数的返回中。

不幸的是，我们对如何精确分支的细节知之甚少
现代处理器工作的预测指标。我能找到的最佳分析
is this，它建议处理器具有大约16个条目的返回堆栈缓冲区。如果我们要借助这一发现再次返回我们的数据，那么事情就会开始澄清。

当您具有带有半个半个模式的半个零时，您将非常递归
深入到 test1(curIndex+1)中，但随后您开始返回并
调用 test1(size-curIndex-1)。递归从来都不比一个深
调用，因此可以很好地预测 yield 。但是请记住，我们
现在深度55555调用，处理器仅记住最后16个，因此
不足为奇的是，我们无法猜测我们从55539水平开始的返回，
更令人惊讶的是，它可以通过尾部 call 优化版本来实现。

实际上，尾部 call 优化版本的行为表明缺少
有关退货的任何其他信息，处理器仅假设该权利是正确的
一个是最后一个。它的行为也证明了这一点
非尾部 call 最佳化版本，因为它将55555个 call 深入到 test1(curIndex+1)，然后在返回时总会深入一层 test1(size-curIndex-1)，所以当我们从55555-deep升至55539-deep(或
无论您的处理器返回缓冲区是什么)，它都会调用 test1(size-curIndex-1)，从那里返回，它绝对没有
有关下一次返回的信息，因此假设我们要返回到
上次看到的地址(这是从其返回的地址 test1(size-curIndex-1))，这显然是错误的。 55539次错。用
该函数的100个周期，恰好是5.5M分支预测未命中
我们看。

现在，让我们进入您的交替模式和代码。该代码是
如果您要分析它如何进入
深度。在这里，您的 test2(curIndex+1)总是立即返回，
您的 test2(curIndex+2)总是更深入。所以从 test2(curIndex+1)总是被完美预测的(它们只是不深入
足够)，当我们完成对 test2(curIndex+2)的递归时，它
始终返回同一点，共55555次，因此处理器没有
问题。

这可以通过对半个半编码的原始半个零变化进行进一步证明:

--- file.cpp.orig       2016-09-23 11:00:26.917977032 +0300
+++ file.cpp    2016-09-23 11:00:31.946027451 +0300
@@ -15,8 +15,8 @@
   if(curIndex == half) return;
   if(A[curIndex] == 1) return;

-  test1(curIndex+1);
   test1(size - curIndex - 1);
+  test1(curIndex+1);

   s += A[curIndex+1] + A[size-curIndex-1];

因此，现在生成的代码仍未进行尾调用优化(在汇编方面，它与原始代码非常相似)，但是在perf输出中会得到如下所示的代码:

$ perf stat -B -e branches,branch-misses ./a.out 111111 
5555500

 Performance counter stats for './a.out 111111':

        45 308 579      branches                                                    
            75 927      branch-misses             #    0,17% of all branches        

       0,026271402 seconds time elapsed

不出所料，现在我们的第一个调用总是立即返回，第二个调用变为55555-deep，然后仅返回相同的点。

现在解决了，让我袖手旁观。在一个系统上，以及
这是Core i5-5200U(具有尾部半音版本的未经尾部调用优化的原始半数零)显示了以下结果:

 $ perf stat -B -e branches,branch-misses ./a.out 111111
 5555500

  Performance counter stats for './a.out 111111':

         45 331 670      branches                                                    
             16 349      branch-misses             #    0,04% of all branches        

        0,043351547 seconds time elapsed

因此，显然，Broadwell可以轻松处理此模式，这使我们回到了
我们对分支预测逻辑了解多少的问题
现代处理器。