为什么这个 C++ 函数会产生如此多的分支预测错误？
Why does this C++ function produce so many branch mispredictions?
设A 为包含奇数个0 和1 的数组。如果 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，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 语句，该行与分支预测有什么关系？
在我看来，在 test1() 的第一个 ceil(n/2) - 1 调用中，两个 if 语句都是假的。在 ceil(n/2)-th 调用中，if(curIndex == ceil(n/2)) 将为真。在剩下的 n-ceil(n/2) 次调用中，第一个语句为假，第二个语句为真。
为什么英特尔未能预测到如此简单的行为？
现在我们来看第二种情况。假设 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) 将是 false n-1 次，并且 if(A[curIndex] == 1) 将从 true 到 false 交替。
在我看来，这两个函数应该很容易预测，但是第一个函数并非如此。同时，我不确定那条线发生了什么，以及为什么它在改善分支行为方面发挥作用。
删除行 s += A[curIndex+1] + A[size-curIndex-1]; 启用 尾递归优化。
只有当递归调用在函数的最后一行时才会发生这种优化。
有趣的是，在第一次执行中，您的分支比第二次执行多了大约 30%（32M 分支对 24M 分支）。
我已经使用 gcc 4.8.5 和相同的标志（加上 -S）为您的应用程序生成了汇编代码，这些程序集之间存在显着差异。带有冲突语句的代码大约有 572 行，而没有相同语句的代码只有 409 行。关注符号 _Z5test1i —— test1) 的修饰 C++ 名称），该例程长 367 行，而第二种情况仅占用 202 行。从所有这些行来看，第一种情况包含 36 个分支（加上 15 个调用指令），第二种情况包含 34 个分支（加上 1 个调用指令）。
同样有趣的是，使用 -O1 编译应用程序不会暴露两个版本之间的这种差异（尽管分支预测错误更高，大约 12%）。使用 -O2 显示两个版本之间的差异（12% 对 3% 的分支预测错误）。
我不是编译器专家，无法理解编译器使用的控制流和逻辑，但看起来编译器能够实现更智能的优化（可能包括 user1850903 在他的回答中指出的尾递归优化）当那部分代码不存在时。
问题是这样的：
if(A[curIndex] == 1) return;
测试函数的每次调用都是交替比较的结果，由于一些优化，因为数组是，例如 0,0,0,0,0,1,1,1,1
换句话说：
- curIndex = 0 -> A[0] = 0
- test1(curIndex + 1) -> curIndex = 1 -> A[1] = 0
但是，处理器架构 MIGHT（一个很大的可能，因为它取决于；对我来说，优化被禁用 - i5-6400）有一个名为 runahead（沿分支预测执行），在进入分支之前执行流水线中剩余的指令；所以它将在有问题的 if 语句之前执行 test1(size - curIndex -1)。
去除归属地，然后进入另一个优化，如user1850903所说。
下面的代码是尾递归的：函数的最后一行不需要调用，只是一个分支到函数开始使用第一个参数的地方：
void f(int i) {
if (i == size) break;
s += a[i];
f(i + 1);
}
但是，如果我们打破它并使其成为非尾递归：
void f(int i) {
if (i == size) break;
f(i + 1);
s += a[i];
}
编译器无法将后者推断为尾递归的原因有很多，但在您给出的示例中，
test(A[N]);
test(A[M]);
s += a[N] + a[M];
适用相同的规则。编译器无法确定这是尾递归，但由于这两个调用（请参阅 before and after）。
您似乎希望编译器对此执行的是一个函数，该函数执行几个简单的条件分支、两个调用和一些 load/add/stores。
相反，编译器正在展开这个循环并生成具有很多分支点的代码。这样做的部分原因是编译器认为这样会更有效（涉及 less 分支），但部分原因是它减少了运行时递归深度。
int size;
int* A;
int half;
int s;
void test1(int curIndex){
if(curIndex == half || A[curIndex] == 1) return;
test1(curIndex+1);
test1(size-curIndex-1);
s += A[curIndex+1] + A[size-curIndex-1];
}
产生：
test1(int):
movl half(%rip), %edx
cmpl %edi, %edx
je .L36
pushq %r15
pushq %r14
movslq %edi, %rcx
pushq %r13
pushq %r12
leaq 0(,%rcx,4), %r12
pushq %rbp
pushq %rbx
subq , %rsp
movq A(%rip), %rax
cmpl , (%rax,%rcx,4)
je .L1
leal 1(%rdi), %r13d
movl %edi, %ebp
cmpl %r13d, %edx
je .L42
cmpl , 4(%rax,%r12)
je .L42
leal 2(%rdi), %ebx
cmpl %ebx, %edx
je .L39
cmpl , 8(%rax,%r12)
je .L39
leal 3(%rdi), %r14d
cmpl %r14d, %edx
je .L37
cmpl , 12(%rax,%r12)
je .L37
leal 4(%rdi), %edi
call test1(int)
movl %r14d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %esi
movl 16(%rax,%r12), %edx
subl %r14d, %esi
movslq %esi, %rsi
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L10:
movl %ecx, %edi
subl %ebx, %edi
leal -1(%rdi), %r14d
cmpl %edx, %r14d
je .L38
movslq %r14d, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L38
call test1(int)
movl %r14d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %edx
movl 4(%rax,%r15), %esi
movl %ecx, %edi
subl %r14d, %edx
subl %ebx, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, s(%rip)
.L13:
movslq %edi, %rdi
movl 12(%rax,%r12), %r8d
addl -4(%rax,%rdi,4), %r8d
addl %r8d, %esi
movl %esi, s(%rip)
.L7:
movl %ecx, %ebx
subl %r13d, %ebx
leal -1(%rbx), %r14d
cmpl %edx, %r14d
je .L41
movslq %r14d, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L41
cmpl %edx, %ebx
je .L18
movslq %ebx, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r8
movq %r8, (%rsp)
je .L18
leal 1(%rbx), %edi
call test1(int)
movl %ebx, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movq (%rsp), %r8
movl %ecx, %esi
subl %ebx, %esi
movl 4(%rax,%r8), %edx
movslq %esi, %rsi
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L18:
movl %ecx, %edi
subl %r14d, %edi
leal -1(%rdi), %ebx
cmpl %edx, %ebx
je .L40
movslq %ebx, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r8
je .L40
movq %r8, (%rsp)
call test1(int)
movl %ebx, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movq (%rsp), %r8
movl %ecx, %edx
movl %ecx, %edi
subl %ebx, %edx
movl 4(%rax,%r8), %esi
subl %r14d, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, %r8d
movl %esi, s(%rip)
.L20:
movslq %edi, %rdi
movl 4(%rax,%r15), %esi
movl %ecx, %ebx
addl -4(%rax,%rdi,4), %esi
subl %r13d, %ebx
addl %r8d, %esi
movl %esi, s(%rip)
.L16:
movslq %ebx, %rbx
movl 8(%rax,%r12), %edi
addl -4(%rax,%rbx,4), %edi
addl %edi, %esi
movl %esi, s(%rip)
jmp .L4
.L45:
movl s(%rip), %edx
.L23:
movslq %ebx, %rbx
movl 4(%rax,%r12), %ecx
addl -4(%rax,%rbx,4), %ecx
addl %ecx, %edx
movl %edx, s(%rip)
.L1:
addq , %rsp
popq %rbx
popq %rbp
popq %r12
popq %r13
popq %r14
popq %r15
.L36:
rep ret
.L42:
movl size(%rip), %ecx
.L4:
movl %ecx, %ebx
subl %ebp, %ebx
leal -1(%rbx), %r14d
cmpl %edx, %r14d
je .L45
movslq %r14d, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L45
cmpl %edx, %ebx
je .L25
movslq %ebx, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r13
je .L25
leal 1(%rbx), %esi
cmpl %edx, %esi
movl %esi, (%rsp)
je .L26
cmpl , 8(%rax,%r15)
je .L26
leal 2(%rbx), %edi
call test1(int)
movl (%rsp), %esi
movl %esi, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movl (%rsp), %esi
movq A(%rip), %rax
movl %ecx, %edx
subl %esi, %edx
movslq %edx, %rsi
movl 12(%rax,%r15), %edx
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L26:
movl %ecx, %edi
subl %ebx, %edi
leal -1(%rdi), %esi
cmpl %edx, %esi
je .L43
movslq %esi, %r8
cmpl , (%rax,%r8,4)
leaq 0(,%r8,4), %r9
je .L43
movq %r9, 8(%rsp)
movl %esi, (%rsp)
call test1(int)
movl (%rsp), %esi
movl %esi, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movl (%rsp), %esi
movq A(%rip), %rax
movq 8(%rsp), %r9
movl %ecx, %edx
movl %ecx, %edi
subl %esi, %edx
movl 4(%rax,%r9), %esi
subl %ebx, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, s(%rip)
.L28:
movslq %edi, %rdi
movl 4(%rax,%r13), %r8d
addl -4(%rax,%rdi,4), %r8d
addl %r8d, %esi
movl %esi, s(%rip)
.L25:
movl %ecx, %r13d
subl %r14d, %r13d
leal -1(%r13), %ebx
cmpl %edx, %ebx
je .L44
movslq %ebx, %rdi
cmpl , (%rax,%rdi,4)
leaq 0(,%rdi,4), %rsi
movq %rsi, (%rsp)
je .L44
cmpl %edx, %r13d
je .L33
movslq %r13d, %rdx
cmpl , (%rax,%rdx,4)
leaq 0(,%rdx,4), %r8
movq %r8, 8(%rsp)
je .L33
leal 1(%r13), %edi
call test1(int)
movl %r13d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rdi
movq 8(%rsp), %r8
movl %ecx, %edx
subl %r13d, %edx
movl 4(%rdi,%r8), %eax
movslq %edx, %rdx
addl -4(%rdi,%rdx,4), %eax
addl %eax, s(%rip)
.L33:
subl %ebx, %ecx
leal -1(%rcx), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %esi
movl %ecx, %r13d
subl %ebx, %esi
movq (%rsp), %rbx
subl %r14d, %r13d
movslq %esi, %rsi
movl 4(%rax,%rbx), %edx
addl -4(%rax,%rsi,4), %edx
movl s(%rip), %esi
addl %edx, %esi
movl %esi, s(%rip)
.L31:
movslq %r13d, %r13
movl 4(%rax,%r15), %edx
subl %ebp, %ecx
addl -4(%rax,%r13,4), %edx
movl %ecx, %ebx
addl %esi, %edx
movl %edx, s(%rip)
jmp .L23
.L44:
movl s(%rip), %esi
jmp .L31
.L39:
movl size(%rip), %ecx
jmp .L7
.L41:
movl s(%rip), %esi
jmp .L16
.L43:
movl s(%rip), %esi
jmp .L28
.L38:
movl s(%rip), %esi
jmp .L13
.L37:
movl size(%rip), %ecx
jmp .L10
.L40:
movl s(%rip), %r8d
jmp .L20
s:
half:
.zero 4
A:
.zero 8
size:
.zero 4
对于交替值的情况，假设大小 == 7：
test1(curIndex = 0)
{
if (curIndex == size - 1) return; // false x1
if (A[curIndex] == 1) return; // false x1
test1(curIndex + 1 => 1) {
if (curIndex == size - 1) return; // false x2
if (A[curIndex] == 1) return; // false x1 -mispred-> returns
}
test1(curIndex + 2 => 2) {
if (curIndex == size - 1) return; // false x 3
if (A[curIndex] == 1) return; // false x2
test1(curIndex + 1 => 3) {
if (curIndex == size - 1) return; // false x3
if (A[curIndex] == 1) return; // false x2 -mispred-> returns
}
test1(curIndex + 2 => 4) {
if (curIndex == size - 1) return; // false x4
if (A[curIndex] == 1) return; // false x3
test1(curIndex + 1 => 5) {
if (curIndex == size - 1) return; // false x5
if (A[curIndex] == 1) return; // false x3 -mispred-> returns
}
test1(curIndex + 2 => 6) {
if (curIndex == size - 1) return; // false x5 -mispred-> returns
}
s += A[5] + A[6];
}
s += A[3] + A[4];
}
s += A[1] + A[2];
}
让我们想象一下
size = 11;
A[11] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 };
test1(0)
-> test1(1)
-> test1(2)
-> test1(3) -> returns because 1
-> test1(4)
-> test1(5)
-> test1(6)
-> test1(7) -- returns because 1
-> test1(8)
-> test1(9) -- returns because 1
-> test1(10) -- returns because size-1
-> test1(7) -- returns because 1
-> test1(6)
-> test1(7)
-> test1(8)
-> test1(9) -- 1
-> test1(10) -- size-1
-> test1(3) -> returns
-> test1(2)
... as above
或
size = 5;
A[5] = { 0, 0, 0, 0, 1 };
test1(0)
-> test1(1)
-> test1(2)
-> test1(3)
-> test1(4) -- size
-> test1(5) -- UB
-> test1(4)
-> test1(3)
-> test1(4) -- size
-> test1(5) -- UB
-> test1(2)
..
您挑出的两种情况（交替和半模式）是最优的极端情况，编译器选择了一些中间情况，它会尽力处理。
这是我盯着它看了一会儿后的想法。首先，
使用 -O2 很容易重现该问题，因此最好将其用作
参考，因为它生成简单的非展开代码，很容易
分析。 -O3 的问题本质上是一样的，只是不太明显。
因此，对于第一种情况（半零和半一模式），编译器
生成此代码：
0000000000400a80 <_Z5test1i>:
400a80: 55 push %rbp
400a81: 53 push %rbx
400a82: 89 fb mov %edi,%ebx
400a84: 48 83 ec 08 sub [=10=]x8,%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 [=10=]x1,(%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 [=10=]x8,%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 和酷睿 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 您将获得相同的 "bad" 结果。那么让我们
看看我们在尾调用优化的汇编中有什么：
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 [=14=]x1,(%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 [=14=]x1,(%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 [=14=]x1,%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 次）或 returns（就像它在递归调用之后所做的那样）。所以这是每 11M 调用 4 条分支指令，正是我们看到的数字。在这些大约 550 万个分支中遗漏了，这表明这些遗漏全部来自一个错误预测的指令，要么是被评估了 1100 万次但遗漏了大约 50% 的时间，要么是被评估了一半但总是遗漏的东西。
我们在尾调用优化版本中有什么？我们有一个函数叫做
大约 550 万次，但现在每次调用都会产生一个 call，最初有两个分支（第一个在所有情况下都是正确的，除了一个，第二个总是错误，因为我们的数据），然后是 jmp ，然后是一个调用（但我们已经计算出我们有 550 万次调用），然后是 400ae8 的分支和 400ab6 的分支（由于我们的数据总是正确的），然后是 return.因此，平均而言，有四个条件分支、一个无条件跳转、一个调用和一个间接分支（来自函数的 return），550 万乘以 7 得到大约 3900 万个分支的总数，正如我们在 perf 中看到的输出。
我们所知道的是，处理器在使用一个函数调用预测流程中的事物时完全没有问题（即使这个版本有更多的条件分支）并且它在使用两个函数调用时存在问题。所以这表明问题出在函数的 return 中。
不幸的是，我们对分支的细节知之甚少
我们现代处理器工作的预测器。我能找到的最好的分析
is this 并且它表明处理器具有大约 16 个条目的 return 堆栈缓冲区。如果我们根据手头的这一发现再次 return 我们的数据，事情就会开始变得清晰起来。
当你有半零和半一模式时，你在递归 非常
深入 test1(curIndex+1)，但随后你开始 return 回头
呼叫 test1(size-curIndex-1)。该递归 永远不会 比一个更深
调用，因此可以完美地预测 return。但请记住，我们是
现在有 55555 次调用深度，处理器只记得最后 16 次，所以它是
毫不奇怪，它无法从 55539 级深度开始猜测我们的 returns，
更令人惊讶的是它可以使用尾调用优化版本。
实际上，尾调用优化版本的行为表明缺少
关于 returns 的任何其他信息，处理器只是假设正确
一个是最后一个看到的。也被以下的行为所证明
非尾调用优化版本，因为它深入到 55555 个调用
test1(curIndex+1) 然后在 return 它总是深入到一个层次
test1(size-curIndex-1)，所以当我们从 55555 深上升到 55539 深（或
无论你的处理器 return 缓冲区是什么）它调用
test1(size-curIndex-1), returns 从那开始，它绝对没有
关于下一个 return 的信息，所以它假设我们要 return
最后看到的地址（这是 return 从
test1(size-curIndex-1)) 这显然是错误的。错了55539次。和
函数的 100 个循环，正好是 5.5M 分支预测未命中
我们看到了。
现在让我们来看看交替模式及其代码。这段代码是
实际上非常不同，如果你要分析它是如何进入
深度。在这里你有你的 test2(curIndex+1) always return 立即和
你的 test2(curIndex+2) 到 总是 更深入。所以 returns 来自
test2(curIndex+1) 总是被完美预测（他们只是不深入
够了），当我们完成对 test2(curIndex+2) 的递归时，它
总是returns到同一个点，都是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
正如预期的那样，现在我们的第一次调用总是立即 returns，第二次调用进入 55555-deep，然后仅 returns 到达同一点。
现在解决了这个问题，让我展示一下我的袖子。在一个系统上，和
这是 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 可以轻松处理这种模式，return让我们
我们对我们的分支预测逻辑了解多少的问题
现代处理器。
设A 为包含奇数个0 和1 的数组。如果 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，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 语句，该行与分支预测有什么关系？
在我看来，在 test1() 的第一个 ceil(n/2) - 1 调用中，两个 if 语句都是假的。在 ceil(n/2)-th 调用中，if(curIndex == ceil(n/2)) 将为真。在剩下的 n-ceil(n/2) 次调用中，第一个语句为假，第二个语句为真。
为什么英特尔未能预测到如此简单的行为？
现在我们来看第二种情况。假设 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) 将是 false n-1 次，并且 if(A[curIndex] == 1) 将从 true 到 false 交替。
在我看来，这两个函数应该很容易预测，但是第一个函数并非如此。同时，我不确定那条线发生了什么，以及为什么它在改善分支行为方面发挥作用。
删除行 s += A[curIndex+1] + A[size-curIndex-1]; 启用 尾递归优化。
只有当递归调用在函数的最后一行时才会发生这种优化。
有趣的是，在第一次执行中，您的分支比第二次执行多了大约 30%（32M 分支对 24M 分支）。
我已经使用 gcc 4.8.5 和相同的标志（加上 -S）为您的应用程序生成了汇编代码，这些程序集之间存在显着差异。带有冲突语句的代码大约有 572 行，而没有相同语句的代码只有 409 行。关注符号 _Z5test1i —— test1) 的修饰 C++ 名称），该例程长 367 行，而第二种情况仅占用 202 行。从所有这些行来看，第一种情况包含 36 个分支（加上 15 个调用指令），第二种情况包含 34 个分支（加上 1 个调用指令）。
同样有趣的是，使用 -O1 编译应用程序不会暴露两个版本之间的这种差异（尽管分支预测错误更高，大约 12%）。使用 -O2 显示两个版本之间的差异（12% 对 3% 的分支预测错误）。
我不是编译器专家，无法理解编译器使用的控制流和逻辑，但看起来编译器能够实现更智能的优化（可能包括 user1850903 在他的回答中指出的尾递归优化）当那部分代码不存在时。
问题是这样的：
if(A[curIndex] == 1) return;
测试函数的每次调用都是交替比较的结果，由于一些优化，因为数组是，例如 0,0,0,0,0,1,1,1,1
换句话说：
- curIndex = 0 -> A[0] = 0
- test1(curIndex + 1) -> curIndex = 1 -> A[1] = 0
但是，处理器架构 MIGHT（一个很大的可能，因为它取决于；对我来说，优化被禁用 - i5-6400）有一个名为 runahead（沿分支预测执行），在进入分支之前执行流水线中剩余的指令；所以它将在有问题的 if 语句之前执行 test1(size - curIndex -1)。
去除归属地，然后进入另一个优化，如user1850903所说。
下面的代码是尾递归的：函数的最后一行不需要调用，只是一个分支到函数开始使用第一个参数的地方：
void f(int i) {
if (i == size) break;
s += a[i];
f(i + 1);
}
但是，如果我们打破它并使其成为非尾递归：
void f(int i) {
if (i == size) break;
f(i + 1);
s += a[i];
}
编译器无法将后者推断为尾递归的原因有很多，但在您给出的示例中，
test(A[N]);
test(A[M]);
s += a[N] + a[M];
适用相同的规则。编译器无法确定这是尾递归，但由于这两个调用（请参阅 before and after）。
您似乎希望编译器对此执行的是一个函数，该函数执行几个简单的条件分支、两个调用和一些 load/add/stores。
相反，编译器正在展开这个循环并生成具有很多分支点的代码。这样做的部分原因是编译器认为这样会更有效（涉及 less 分支），但部分原因是它减少了运行时递归深度。
int size;
int* A;
int half;
int s;
void test1(int curIndex){
if(curIndex == half || A[curIndex] == 1) return;
test1(curIndex+1);
test1(size-curIndex-1);
s += A[curIndex+1] + A[size-curIndex-1];
}
产生：
test1(int):
movl half(%rip), %edx
cmpl %edi, %edx
je .L36
pushq %r15
pushq %r14
movslq %edi, %rcx
pushq %r13
pushq %r12
leaq 0(,%rcx,4), %r12
pushq %rbp
pushq %rbx
subq , %rsp
movq A(%rip), %rax
cmpl , (%rax,%rcx,4)
je .L1
leal 1(%rdi), %r13d
movl %edi, %ebp
cmpl %r13d, %edx
je .L42
cmpl , 4(%rax,%r12)
je .L42
leal 2(%rdi), %ebx
cmpl %ebx, %edx
je .L39
cmpl , 8(%rax,%r12)
je .L39
leal 3(%rdi), %r14d
cmpl %r14d, %edx
je .L37
cmpl , 12(%rax,%r12)
je .L37
leal 4(%rdi), %edi
call test1(int)
movl %r14d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %esi
movl 16(%rax,%r12), %edx
subl %r14d, %esi
movslq %esi, %rsi
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L10:
movl %ecx, %edi
subl %ebx, %edi
leal -1(%rdi), %r14d
cmpl %edx, %r14d
je .L38
movslq %r14d, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L38
call test1(int)
movl %r14d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %edx
movl 4(%rax,%r15), %esi
movl %ecx, %edi
subl %r14d, %edx
subl %ebx, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, s(%rip)
.L13:
movslq %edi, %rdi
movl 12(%rax,%r12), %r8d
addl -4(%rax,%rdi,4), %r8d
addl %r8d, %esi
movl %esi, s(%rip)
.L7:
movl %ecx, %ebx
subl %r13d, %ebx
leal -1(%rbx), %r14d
cmpl %edx, %r14d
je .L41
movslq %r14d, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L41
cmpl %edx, %ebx
je .L18
movslq %ebx, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r8
movq %r8, (%rsp)
je .L18
leal 1(%rbx), %edi
call test1(int)
movl %ebx, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movq (%rsp), %r8
movl %ecx, %esi
subl %ebx, %esi
movl 4(%rax,%r8), %edx
movslq %esi, %rsi
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L18:
movl %ecx, %edi
subl %r14d, %edi
leal -1(%rdi), %ebx
cmpl %edx, %ebx
je .L40
movslq %ebx, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r8
je .L40
movq %r8, (%rsp)
call test1(int)
movl %ebx, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movq (%rsp), %r8
movl %ecx, %edx
movl %ecx, %edi
subl %ebx, %edx
movl 4(%rax,%r8), %esi
subl %r14d, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, %r8d
movl %esi, s(%rip)
.L20:
movslq %edi, %rdi
movl 4(%rax,%r15), %esi
movl %ecx, %ebx
addl -4(%rax,%rdi,4), %esi
subl %r13d, %ebx
addl %r8d, %esi
movl %esi, s(%rip)
.L16:
movslq %ebx, %rbx
movl 8(%rax,%r12), %edi
addl -4(%rax,%rbx,4), %edi
addl %edi, %esi
movl %esi, s(%rip)
jmp .L4
.L45:
movl s(%rip), %edx
.L23:
movslq %ebx, %rbx
movl 4(%rax,%r12), %ecx
addl -4(%rax,%rbx,4), %ecx
addl %ecx, %edx
movl %edx, s(%rip)
.L1:
addq , %rsp
popq %rbx
popq %rbp
popq %r12
popq %r13
popq %r14
popq %r15
.L36:
rep ret
.L42:
movl size(%rip), %ecx
.L4:
movl %ecx, %ebx
subl %ebp, %ebx
leal -1(%rbx), %r14d
cmpl %edx, %r14d
je .L45
movslq %r14d, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r15
je .L45
cmpl %edx, %ebx
je .L25
movslq %ebx, %rsi
cmpl , (%rax,%rsi,4)
leaq 0(,%rsi,4), %r13
je .L25
leal 1(%rbx), %esi
cmpl %edx, %esi
movl %esi, (%rsp)
je .L26
cmpl , 8(%rax,%r15)
je .L26
leal 2(%rbx), %edi
call test1(int)
movl (%rsp), %esi
movl %esi, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movl (%rsp), %esi
movq A(%rip), %rax
movl %ecx, %edx
subl %esi, %edx
movslq %edx, %rsi
movl 12(%rax,%r15), %edx
addl -4(%rax,%rsi,4), %edx
addl %edx, s(%rip)
movl half(%rip), %edx
.L26:
movl %ecx, %edi
subl %ebx, %edi
leal -1(%rdi), %esi
cmpl %edx, %esi
je .L43
movslq %esi, %r8
cmpl , (%rax,%r8,4)
leaq 0(,%r8,4), %r9
je .L43
movq %r9, 8(%rsp)
movl %esi, (%rsp)
call test1(int)
movl (%rsp), %esi
movl %esi, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movl (%rsp), %esi
movq A(%rip), %rax
movq 8(%rsp), %r9
movl %ecx, %edx
movl %ecx, %edi
subl %esi, %edx
movl 4(%rax,%r9), %esi
subl %ebx, %edi
movslq %edx, %rdx
addl -4(%rax,%rdx,4), %esi
movl half(%rip), %edx
addl s(%rip), %esi
movl %esi, s(%rip)
.L28:
movslq %edi, %rdi
movl 4(%rax,%r13), %r8d
addl -4(%rax,%rdi,4), %r8d
addl %r8d, %esi
movl %esi, s(%rip)
.L25:
movl %ecx, %r13d
subl %r14d, %r13d
leal -1(%r13), %ebx
cmpl %edx, %ebx
je .L44
movslq %ebx, %rdi
cmpl , (%rax,%rdi,4)
leaq 0(,%rdi,4), %rsi
movq %rsi, (%rsp)
je .L44
cmpl %edx, %r13d
je .L33
movslq %r13d, %rdx
cmpl , (%rax,%rdx,4)
leaq 0(,%rdx,4), %r8
movq %r8, 8(%rsp)
je .L33
leal 1(%r13), %edi
call test1(int)
movl %r13d, %edi
notl %edi
addl size(%rip), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rdi
movq 8(%rsp), %r8
movl %ecx, %edx
subl %r13d, %edx
movl 4(%rdi,%r8), %eax
movslq %edx, %rdx
addl -4(%rdi,%rdx,4), %eax
addl %eax, s(%rip)
.L33:
subl %ebx, %ecx
leal -1(%rcx), %edi
call test1(int)
movl size(%rip), %ecx
movq A(%rip), %rax
movl %ecx, %esi
movl %ecx, %r13d
subl %ebx, %esi
movq (%rsp), %rbx
subl %r14d, %r13d
movslq %esi, %rsi
movl 4(%rax,%rbx), %edx
addl -4(%rax,%rsi,4), %edx
movl s(%rip), %esi
addl %edx, %esi
movl %esi, s(%rip)
.L31:
movslq %r13d, %r13
movl 4(%rax,%r15), %edx
subl %ebp, %ecx
addl -4(%rax,%r13,4), %edx
movl %ecx, %ebx
addl %esi, %edx
movl %edx, s(%rip)
jmp .L23
.L44:
movl s(%rip), %esi
jmp .L31
.L39:
movl size(%rip), %ecx
jmp .L7
.L41:
movl s(%rip), %esi
jmp .L16
.L43:
movl s(%rip), %esi
jmp .L28
.L38:
movl s(%rip), %esi
jmp .L13
.L37:
movl size(%rip), %ecx
jmp .L10
.L40:
movl s(%rip), %r8d
jmp .L20
s:
half:
.zero 4
A:
.zero 8
size:
.zero 4
对于交替值的情况，假设大小 == 7：
test1(curIndex = 0)
{
if (curIndex == size - 1) return; // false x1
if (A[curIndex] == 1) return; // false x1
test1(curIndex + 1 => 1) {
if (curIndex == size - 1) return; // false x2
if (A[curIndex] == 1) return; // false x1 -mispred-> returns
}
test1(curIndex + 2 => 2) {
if (curIndex == size - 1) return; // false x 3
if (A[curIndex] == 1) return; // false x2
test1(curIndex + 1 => 3) {
if (curIndex == size - 1) return; // false x3
if (A[curIndex] == 1) return; // false x2 -mispred-> returns
}
test1(curIndex + 2 => 4) {
if (curIndex == size - 1) return; // false x4
if (A[curIndex] == 1) return; // false x3
test1(curIndex + 1 => 5) {
if (curIndex == size - 1) return; // false x5
if (A[curIndex] == 1) return; // false x3 -mispred-> returns
}
test1(curIndex + 2 => 6) {
if (curIndex == size - 1) return; // false x5 -mispred-> returns
}
s += A[5] + A[6];
}
s += A[3] + A[4];
}
s += A[1] + A[2];
}
让我们想象一下
size = 11;
A[11] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 };
test1(0)
-> test1(1)
-> test1(2)
-> test1(3) -> returns because 1
-> test1(4)
-> test1(5)
-> test1(6)
-> test1(7) -- returns because 1
-> test1(8)
-> test1(9) -- returns because 1
-> test1(10) -- returns because size-1
-> test1(7) -- returns because 1
-> test1(6)
-> test1(7)
-> test1(8)
-> test1(9) -- 1
-> test1(10) -- size-1
-> test1(3) -> returns
-> test1(2)
... as above
或
size = 5;
A[5] = { 0, 0, 0, 0, 1 };
test1(0)
-> test1(1)
-> test1(2)
-> test1(3)
-> test1(4) -- size
-> test1(5) -- UB
-> test1(4)
-> test1(3)
-> test1(4) -- size
-> test1(5) -- UB
-> test1(2)
..
您挑出的两种情况（交替和半模式）是最优的极端情况，编译器选择了一些中间情况，它会尽力处理。
这是我盯着它看了一会儿后的想法。首先，
使用 -O2 很容易重现该问题，因此最好将其用作
参考，因为它生成简单的非展开代码，很容易
分析。 -O3 的问题本质上是一样的，只是不太明显。
因此，对于第一种情况（半零和半一模式），编译器 生成此代码：
0000000000400a80 <_Z5test1i>:
400a80: 55 push %rbp
400a81: 53 push %rbx
400a82: 89 fb mov %edi,%ebx
400a84: 48 83 ec 08 sub [=10=]x8,%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 [=10=]x1,(%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 [=10=]x8,%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 和酷睿 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 您将获得相同的 "bad" 结果。那么让我们
看看我们在尾调用优化的汇编中有什么：
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 [=14=]x1,(%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 [=14=]x1,(%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 [=14=]x1,%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 次）或 returns（就像它在递归调用之后所做的那样）。所以这是每 11M 调用 4 条分支指令，正是我们看到的数字。在这些大约 550 万个分支中遗漏了，这表明这些遗漏全部来自一个错误预测的指令，要么是被评估了 1100 万次但遗漏了大约 50% 的时间，要么是被评估了一半但总是遗漏的东西。
我们在尾调用优化版本中有什么？我们有一个函数叫做
大约 550 万次，但现在每次调用都会产生一个 call，最初有两个分支（第一个在所有情况下都是正确的，除了一个，第二个总是错误，因为我们的数据），然后是 jmp ，然后是一个调用（但我们已经计算出我们有 550 万次调用），然后是 400ae8 的分支和 400ab6 的分支（由于我们的数据总是正确的），然后是 return.因此，平均而言，有四个条件分支、一个无条件跳转、一个调用和一个间接分支（来自函数的 return），550 万乘以 7 得到大约 3900 万个分支的总数，正如我们在 perf 中看到的输出。
我们所知道的是，处理器在使用一个函数调用预测流程中的事物时完全没有问题（即使这个版本有更多的条件分支）并且它在使用两个函数调用时存在问题。所以这表明问题出在函数的 return 中。
不幸的是，我们对分支的细节知之甚少 我们现代处理器工作的预测器。我能找到的最好的分析 is this 并且它表明处理器具有大约 16 个条目的 return 堆栈缓冲区。如果我们根据手头的这一发现再次 return 我们的数据，事情就会开始变得清晰起来。
当你有半零和半一模式时，你在递归 非常
深入 test1(curIndex+1)，但随后你开始 return 回头
呼叫 test1(size-curIndex-1)。该递归 永远不会 比一个更深
调用，因此可以完美地预测 return。但请记住，我们是
现在有 55555 次调用深度，处理器只记得最后 16 次，所以它是
毫不奇怪，它无法从 55539 级深度开始猜测我们的 returns，
更令人惊讶的是它可以使用尾调用优化版本。
实际上，尾调用优化版本的行为表明缺少
关于 returns 的任何其他信息，处理器只是假设正确
一个是最后一个看到的。也被以下的行为所证明
非尾调用优化版本，因为它深入到 55555 个调用
test1(curIndex+1) 然后在 return 它总是深入到一个层次
test1(size-curIndex-1)，所以当我们从 55555 深上升到 55539 深（或
无论你的处理器 return 缓冲区是什么）它调用
test1(size-curIndex-1), returns 从那开始，它绝对没有
关于下一个 return 的信息，所以它假设我们要 return
最后看到的地址（这是 return 从
test1(size-curIndex-1)) 这显然是错误的。错了55539次。和
函数的 100 个循环，正好是 5.5M 分支预测未命中
我们看到了。
现在让我们来看看交替模式及其代码。这段代码是
实际上非常不同，如果你要分析它是如何进入
深度。在这里你有你的 test2(curIndex+1) always return 立即和
你的 test2(curIndex+2) 到 总是 更深入。所以 returns 来自
test2(curIndex+1) 总是被完美预测（他们只是不深入
够了），当我们完成对 test2(curIndex+2) 的递归时，它
总是returns到同一个点，都是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
正如预期的那样，现在我们的第一次调用总是立即 returns，第二次调用进入 55555-deep，然后仅 returns 到达同一点。
现在解决了这个问题，让我展示一下我的袖子。在一个系统上，和 这是 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 可以轻松处理这种模式，return让我们 我们对我们的分支预测逻辑了解多少的问题 现代处理器。