jsg*_*guy 33 c++ performance branch-prediction
让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(R)Core(TM)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语句都是假的.在ceil(n/2)-th通话中,if(curIndex == ceil(n/2))将是真的.在剩余的n-ceil(n/2)调用中,第一个语句将为false,第二个语句将为true.
为什么英特尔无法预测这么简单的行为？
现在让我们看看第二种情况.假设A现在有交替的零和1.我们总是从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.
在我看来,两个函数都应该很容易预测,但第一个函数不是这种情况.与此同时,我不确定该行发生了什么,以及为什么它在改善分支行为方面发挥作用.
Rom*_*mov 26
在盯着它看了一会儿之后,我对此有了一些看法.首先,这个问题很容易重现-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次,每个元素一个,大约是11M.在非尾部调用优化版本中,我们看到大约45M分支,main()中的初始化仅为111K,所有其他东西都是次要的,因此对此数字的主要贡献来自我们的函数.我们的函数是call-ed,它计算第一个je,除了一个之外在所有情况下都是真的,然后它计算第二个je,这是真正的一半时间,然后它递归地调用它自己(但我们已经计算了函数被调用11M次)或返回(就像它在递归调用之后那样.因此,每11M调用就有4个分支指令,正好是我们看到的数量.这些错过了大约5.5M的分支,这表明这些错误都来自一个错误的预测指令,要么被评估了11M次并且错过了大约50%的时间,要么被评估了一半的时间并且总是错过了.
我们在尾部调用优化版本中有什么作用？我们有大约5.5M次调用的函数,但现在每个调用call最初都会产生一个,两个分支(第一个在所有情况下都是真的,除了一个,第二个因为我们的数据总是假的),然后是a jmp,然后是一个调用(但是我们已经计算过我们有5.5M的调用),然后是一个分支at 400ae8和一个分支400ab6(由于我们的数据总是如此),然后返回.因此,平均而言,四个条件分支,一个无条件跳转,一个调用和一个间接分支(从函数返回),5.5M乘以7给出了大约39M分支的总计数,正如我们在perf输出中看到的那样.
我们所知道的是,处理器在使用一个函数调用来预测流中的事物没有任何问题(即使这个版本有更多的条件分支),并且它有两个函数调用的问题.所以它表明问题在于函数的回报.
不幸的是,我们对现代处理器的分支预测器的工作原理的细节知之甚少.我能找到的最好的分析 就是这个,它表明处理器有一个大约16个条目的返回堆栈缓冲区.如果我们再次使用这一发现再次回到我们的数据,事情就会开始澄清一点.
如果你有半个半零的模式,那么你会非常
深入地进行复制test1(curIndex+1),但是你会开始返回并调用test1(size-curIndex-1).该递归永远不会比一次调用更深,因此可以完美地预测回报.但请记住,我们现在已经进行了55555次深度调用,处理器只记得16级,因此它无法从55539级深度猜测我们的回报也就不足为奇了,更令人惊讶的是它可以通过尾部调用来实现 - 优化版.
实际上,尾部调用优化版本的行为表明缺少有关返回的任何其他信息,处理器只是假设正确的一个是最后看到的.非尾部调用优化版本的行为也证明了这一点,因为它深入55555次调用
test1(curIndex+1),然后返回时它总是深入到一级
test1(size-curIndex-1),所以当我们从55555深度到55539深度时(或者你的处理器返回缓冲区是什么)它调用
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深,然后只返回到同一个点.
现在解决了这个让我展示一些东西.在一个系统上,即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可以轻松处理这种模式,这使我们回到了我们对现代处理器的分支预测逻辑了解多少的问题.