多少if语句算多
本文是 Branch predictor: How many "if"s are too many? Including x86 and M1 benchmarks! 的思考、阅读笔记。
本文提出了一个问题：不执行的if语句，影响性能吗？
if (debug) {
log(...);
}
1 了解分支的耗时
对于现代CPU，一条分支指令大概需要1-20个cycle。分支可以分为：1. 无条件分支（x86的jmp）; 2. call/return; 3. 执行的条件分支; 4. 没执行的条件分支。 其中1、2、3都是执行的分支（taken branch）。
CPU的分支预测单元（BPU），可以在分支执行前，确定分支的目标（branch target）。BPU使用BTB（Branch Target Buffer）存放分支目标（和其它信息），显然它的大小很关键。
2 为什么需要分支预测
简单说，这是CPU性能要求的必然。没有分支预测，CPU的流水线、多发射、乱序执行就没法高效运转。
BR label_a;
X1
X2
label_a:
Y1
CPU执行上面代码的逻辑，大概是这样的：
| CPU cycle | 前端 | 后端 | 说明 |
|---|---|---|---|
| 1 | 读取BR指令 | 此时BR还没有解码 | |
| 2 | 对BR解码，读取X1指令 | 此时前端可以等待BR的执行结果（branch target）或者取下一条指令 | |
| 3 | 对X1解码，读取X2指令 | 执行BR指令 | |
| 4 | 读取Y1指令 | CPU发现前端错了，根据BR的结果，重新取指令 |
在这个过程中，前端浪费了2个cycles（2和3）。分支越复杂，前端浪费的cycles越多。所以需要分支预测。
3 BTB
可以写代码探测BTB的大小。在AMD EPYC 7642上得到一些结论（适用于无条件分支）。
- 成功的分支预测节约了7个cycles（预测成功，执行分支花费~3.4个cycles）;
- 在代码小于2k时，可能有uop缓存（uop是指令解码后的形式），预测成功的分支只要 ~1.5 cycles;
- hot loop中的分支小于4096时，无论代码大小，成功预测的分支要 ~3.4个cycles;
- hot loop中的分支大于4096时，分支要 ~10.5个cycles;
- 根据1、3、4推测BTB的大小是4096，大于4096时，分支预测总是失败;
- 热点代码函数调用不要多于2000（循环中的函数算一个，这里2000应该是指令地址），函数调用对应call/return两次分支，2000约是4096的一半;
- 没执行的条件分支几乎没有花销。
4 总结
- x86上BTB只有4096个entries（应该和CPU的型号有关）;
- 热点代码小于16K（应该小于L1i就行，避免L1缓存miss）;
- 没执行的条件分支没有花销（但是条件的执行需要花销，例如：debug的值可能需要从内存load进缓存，这个花销可能不小）。