Branchless性能优化编程
Branchless可以优化多少性能
例子1:
f (bool b, unsigned long x, unsigned long& s) {
if (b) s += x;
}
优化前：130M calls/second
优化后：400M calls/second
例子二：
if (x[i] || y[i]) {
...
}
优化前：150M calls/second
优化后：570M calls/second
理解Branchless前，需要准备一部分体系结构的知识。
体系结构
branchless-opt
体系结构优化包括SSE并行优化/cache优化/pipeline优化/分支预测优化/循环优化等。
这些很多都是由编译器完成了。
但这不代表程序员不需要去关注这些
因为编译器远没有我们想象的聪明。
当程序员理解了这些技术后，可以在一些关键问题上，给出一般人给不出来的解决方案
计算资源问题思考
例子实验
考虑以下程序（code 1.1）：
unsigned long v1[N], v2[N];
unsigned long a = 0;
for (size_t i = 0; i < N; ++i) {
a += v1[i]*v2[i];
}
在CPU中执行过程如下：
执行 a += v1[i]*v2[i];
Init:
register: i ｜
---------------------------------------------------------
register: v1 ｜ memory: v1[i]
register: v2 ｜ memory: v2[i]
register: a1 ｜
CPU ｜ Memory
Step 1: load v1
register: i ｜
---------------------------------------------------------
register: v1 <- read: v1[i]｜ memory: v1[i]
register: v2 ｜ memory: v2[i]
register: a1 ｜
CPU ｜ Memory
Step 2: load v2
register: i ｜
---------------------------------------------------------
register: v1 ｜ memory: v1[i]
register: v2 <- read: v2[i]｜ memory: v2[i]
register: a1 ｜
CPU ｜ Memory
Step 3 mul
register: i ｜
---------------------------------------------------------
register: v1 ------- ｜ memory: v1[i]
register: v2 ------ | ｜ memory: v2[i]
multipy |
register: a1 <- | ｜
CPU ｜ Memory
再考虑以下程序（code 1.2）：
unsigned long v1[N], v2[N];
unsigned long a1 = 0;
unsigned long a2 = 0;
for (size_t i = 0; i < N; ++i) {
a1 += v1[i]*v2[i];
a2 += v1[i]+v2[i];
}
比较代码 code 1.1与code 1.2的benchmark发现
两者并没有明显的差别。
结论
这是因为CPU的寄存器有非常多个
多余的计算资源可以同时完成更多的指令
当计算与计算是各自独立的，那么可以很好的利用多余的计算资源，并行完成多个计算
但实际情况会复杂很多
当前指令的数据可能依赖上一条指令的输出
当前指令的执行可能依赖上一条指令的条件判断
cpu pipeline 的计算过程
例子
code 2.1
for (int i=0; i<N; i++) {
a1 += (v1[i]+v2[i])*(v1[i]-v2[i]);
}
单条语句的执行过程：
------------------------time line---------------------------
exec s[i]:v1[i]+v2[i] | exec s[i]*d[i] (data dependency)
exec d[i]:v1[i]-v2[i] |
语句s[i]*d[i]的执行以来于前两条语句执行的结果，所以这三条语句，只有前两条可以并行执行，最后一条语句则需要等待前两条语句都完成后，才可以执行
循环展开优化
code 2.2
for (int i=0; i<N; i+=4) {
a1 += (v1[i]+v2[i])*(v1[i]-v2[i]);
a1 += (v1[i+1]+v2[i+1])*(v1[i+1]-v2[i+1]);
a1 += (v1[i+2]+v2[i+2])*(v1[i+2]-v2[i+2]);
a1 += (v1[i+3]+v2[i+3])*(v1[i+3]-v2[i+3]);
}
通过展开循环体
就可以通过多pipeline同时执行这四条语句了
过程如下：
------------------------time line---------------------------
exec s[i]:v1[i]+v2[i] | exec s[i]*d[i]
exec d[i]:v1[i]-v2[i] |
exec s[i+1]:v1[i+1]+v2[i+1] | exec s[i+1]*d[i+1]
exec d[i+1]:v1[i+1]-v2[i+1] |
exec s[i+2]:v1[i+2]+v2[i+2] | exec s[i+2]*d[i+2]
exec d[i+2]:v1[i+2]-v2[i+2] |
exec s[i+3]:v1[i+3]+v2[i+3] | exec s[i+3]*d[i+3]
exec d[i+4]:v1[i+4]-v2[i+4] |
条件分支与cpu pipeline
例子
code 3.1
for (int i=0; i<N; i++) {
a+=(v1[i]>v2[i])?v1[i]:v2[i];
}
分析
pipeline对于独立的语句，可以很好的优化执行
但是对于上面这个例子code 3.1
下一条执行的语句，依赖上一条判断语句（v1[i]>v2[i]）的真假来决定
cpu执行一条语句是不能在一个clock内执行完的
一般需要4～5个clock才能执行完一条语句
那么代表一下条语句必须让cpu停顿若干个clock，才能执行下一条语句
对于循环体的 i<N，由于cpu有分支预测功能，只要cpu一直判断 1<N为true，就可以提高并行性
但是对于v1[i] > v2[i]，情况就复杂了。
分支预测
分支预测是CPU的一个单元对条件判断语句的结果进行预测的行为
它通过条件判断语句几次的结果输出，进行模式预测
如果预测对了，那么什么也不会发生
如果预测错了.....
分支预测错误会发生什么
- 所有预测后的计算需要被废弃
- 新的分支的计算需要开始
- 所有因预测错误产生的内存结果需要废弃
- 所有因预测错误产生的异常需要废弃
思考下面的例子
code 4.1
if (p != NULL)
*p = 1; // p is rarely NULL int v[N];
for (size_t i=0; i<N; ++i) {
v[i]=i; // Usually i<N
}
分析
p大部分时间都是非空
cpu所以一直预测p不为空
那么*p=1的执行则会发生异常
但是当cpu执行完条件语句p != NULL，发现输出为false
那么*p=1的执行发生的异常就需要被废弃掉
同样的
对于i<N，cpu一直预测为真
当i=N时， cpu也预测为真
那么v[N] = N就会被执行
当i<N真正输出结果后，发现结果为false
那么就需要回退v[N] = N的写内存的结果
通过例子来思考分支预测
可预测与不可预测性能比较
例子
branchless_predit
上面这两个例子，
左边这个的分支一直输出true，是可以被cpu预测准确的
右边这个的分支输出是随机的，是不可以背哦cpu准确预测的。
下面我们看看他们的性能结果：
不可预测的结果：
branchless_predit_result_1
可以看到分支预测错误占了10%
可预测的结果：
branchless_predit_result_2
可以看到分支miss降低到0.06%
吞吐量也涨了几倍
结论
这代表cpu对于特定模式，是可以做出正确的预判的
分支优化在通常情况下，是不必的
因为cpu的预测可以预测的很好
可预测与不可预测性能比较（更复杂的例子）
例子
branchless_predit_1
左边的代码代表不可预测
右边的代码是true和false交错出现的
相同的，我们来看看性能结果
不可预测的结果：
branchless_predit_result_1
可以看到分支预测错误占了10%
可预测的结果
branchless_predit_result_3
cpu可以正确的识别这种复杂的场景，并正确的预判了程序的行为
结论
不要在一开始就进行分支优化
需要知道等到用perf确认后，才进行必要的分支优化
多分支预测
if (x || y)
do_it();
else
dont_do_it();
从程序员的视觉：如果 x||y是经常是true/false的，那么cpu应该可以预测正确
cpu的视觉：如果x经常是true/false，那么第一个分支是可预测的；如果x为false，y经常为true/false，那么第二个分支是可预测的
那这就有问题了，因为x是不可预测的，y是不可预测的，即使x和y结合后，输出的稳定的，cpu并没有那么强大可以识别出来
例子
branchless_predit_2
结果
branchless_predit_result_4
可以看到，分支预测并不能很好的处理这种情况
优化
if (x || y)
=>
if (bool(x) + bool(y))
通过把bool累加后，转换为单条件语句
有些编译器会做上面的优化，有些不会，所以优化前，需要先确认，再进行优化
优化后的例子
branchless_predit_3
结果
branchless_predit_result_5
cpu成功的做出了预测
branchless优化技巧
技巧1
sum += cond ? expr1 : expr2;
=转化=>
term[2] = { expr2, expr1 };
sum += term[bool(cond)];
例子
branchless_predit_4
左边是一个不可预测的例子
右边是通过去掉分支，优化的例子
结果
branchless_predit_result_6
跟正确预测的版本对比，发现性能稍微下降了一点
但是跟不可预测的版本对比，branchless的性能是提高了几倍
结论
branchless优化是通过让cpu做更多的计算来减少分支代码的
技巧2
if (b) {
s += x;
}
==>
s += b*x;
例子：
branchless_predit_5
结果
branchless_predit_result_7
结论
优化后，性能提高了3倍
总结
分支优化前，先验证，因为编译器和cpu分支预测已经做的很好
确认发生分支miss太多后，才去进行branchless优化
branchless的代价是让cpu做更多的计算来减少分支预测失效
