本文主要讲解一个非常重要的性能调优方法，会涉及CPU内部一些实现细节，为讲解清楚，篇幅较长，请耐心看完，一定会有收获！
一切都要从两个程序员的一次PK说起！
引子 - 两个程序员的PK老大布置一个紧急任务：统计一个随机数组中，值大于50的元素个数，谁代码性能最好，年终奖翻倍，带薪休假一个月！
张三一听，这么简单，跃跃欲试：“我先来！”。只用了几秒钟，代码好了：
“你这代码，性能太差！”，李四一看，有点不屑。
张三不服：“你行你上啊！Show me your code!”。
“来，哥教你！”，李四很是淡定！
“你这什么玩意儿？就把if改成三元表达式，不是跟我的一样嘛！”，张三一看，不屑，觉得李四就是个大忽悠！
“跟你的一样？”，李四微微一笑，“我的代码至少比你的快3倍！”
张三急了：“你可别扯了，怎么可能！”
“要不咱们跑一下看看？”，李四挑衅道。
“看看就看看！”，张三明显不服！
于是，两人各自把代码整理了一下，准备PK。
首先是张三的代码，逻辑很简单，定义了一个全局数组array，在main()中把数组元素初始化为0 ~ 99之间的随机值，然后调用calc()并统计它的运行耗时。保存为test1.c：
李四把张三的test1.c拿过来，把calc()中的if语句改成了三元表达式，其余代码一模一样，然后保存为test2.c:
准备就绪，开始PK！直接编译运行：
test1的calc()耗时3.2秒，test2耗时只有0.76秒！
张三有点怀疑人生了！
看到张三目瞪口呆的样子，李四很是得意，“怎么样，服了吧！”
“其实吧，你这段代码，在有些情况下，可以和我的代码跑的一样快！”，看到张三无语的样子，李四继续得瑟。
“哪些情况？”，张三终于回过神了。
“来，看哥略施小计！”，李四更加得意了！
李四把张三的test1.c拿过来，只添加了几行代码：在调用calc()之前，先用qsort()对数组进行了排序，然后保存为test3.c：
注：红框内为新增代码。这里只测量calc()的运行时间，不要纠结为什么不包含qsort的时间！因为只有这样，才能体现出来数组是否有序对程序运行速度的影响，对于calc()来说，无论数组是否有序，它遍历的元素个数是一样的！
张三不解：“你只是把原来无序的数组，变成了有序的数组，这对calc()遍历数组有什么影响？遍历的元素个数没变啊！”
“先别急，有没有用，跑一下不就知道了！”，李四很是自信，把test3.c编译一下，把三个程序都运行了一下做对比：
test3.c中calc()的耗时居然只有0.698秒，真的只有test1.c的四分之一！甚至比test2.c还稍微快了一点！
“太神奇了！请大神赐教！”，张三彻底服了！
“想知道啊？”，李四稍显猥琐的笑道。
“想！”
“等哥拿着双倍年终奖，度完一个月假期回来再告诉你！”
“噗！”，张三一口老血喷出，卒！
小故事到此结束，现在进入正题！
注：如果，你真的认为加了-O3优化选项之后，数组是否有序就不会影响calc()性能，先去看下文末最后一个例子！
待解答的三个问题- 同样大小的数组，为什么遍历无序数组要3.2秒，而遍历有序数组只需0.7秒？
- 为什么把if语句换成三元表达式，函数calc()性能提升那么多？
- 如果加上编译优化选项，test1.c、test2.c和test3.c中calc()的性能，还有那么大差异吗？（文末解释）
为了讲解清楚，必须先补充一些背景知识。涉及CPU内部实现细节，为了避免枯燥的理论堆积，我会尽量用最通俗直白的语言来介绍这些概念。
注：指令流水线概念虽然在之前文章介绍过，但为了文章的独立和完整性，本文会再次简单介绍，但侧重点与之前不同，因此，无论是否看过之前文章，都建议仔细阅读！
背景知识：指令流水线(pipeline)在CPU内部，一条指令的执行过程被分为多个阶段，每个阶段使用CPU内部不同的硬件资源来完成，就像是工厂里的流水线一样，因此被称为指令流水线(pipeline)。
以经典的5级流水线为例，一条指令在CPU内的执行，被分为5个步骤：
- 取指(IF)：从内存中取出一条指令。
- 译码(ID)：对指令进行解码，确定该指令要执行的操作。
- 执行(EX)：执行该指令要执行的操作。
- 访存(MEM)：进行内存访问操作。
- 写回(WB)：把执行的结果写回寄存器或内存。
在时钟信号的驱动下，CPU依次来执行这些步骤，这就构成了指令流水线(pipeline)。如下图所示：
在CPU内部，执行每个阶段使用不同的硬件资源，从而可以让多条指令的执行时间相互重叠。
当第一条指令完成取指，进入译码阶段时，第二条指令就可以进入取指阶段了。以此类推，在一个5级流水线中，理论上，可以有5条不同的指令的不同阶段在同时执行，因此每个时钟周期都会有一条指令完成执行，从而大大提高了CPU执行指令的吞吐率，从而提高CPU整体性能。这就叫做ILP - 指令级并行（Instruction Level Parallelism）。如下图所示：
如下两句代码：
x = 1;
y = 2;
当第一条指令 x = 1 完成取指，进入译码阶段时，第二条指令 y = 2 就可以进入译码阶段了，如此一来，执行完这两条指令，只需要6个时钟周期。如下图所示：
类似这样的代码序列，对于CPU指令流水线来说，是最友好的，因为它们之间没有任何依赖，能够让指令流水线的性能最大化。
但是，现实中，程序指令序列之间往往存在各种各样的依赖和相关性，而CPU为了解决这种指令间的依赖和相关性，有时候不得不“停顿”下来，直到这些依赖得到解决，这就导致CPU指令流水线无法总是保持“全速运行”。
其中，条件分支指令，是最容易导致流水线停顿的原因之一，也是本文的重点。
条件分支：指令流水线的性能*手程序正常执行过程中，难免会遇到条件分支指令（例如if/else语句、循环等），即需要根据某个条件来选择不同的执行路径。如这样一段代码：
if(a > b){
x = 1;
} else {
y = 2;
}
CPU执行到if(a > b)这一句时，无法确定接下来应该执行x = 1 还是 y = 2，于是CPU指令流水线不得不停顿下来，空闲在那里，一直等到a > b的结果计算出来之后，才能继续执行：如果为true，则执行x = 1, 为false则执行y = 2。如下图所示：
从程序员的角度来看，这似乎是很自然的事情，但是在CPU看来，这却是极大地浪费了宝贵的计算资源。
因为，无论执行哪个分支，都需要 5 5 = 10个时钟周期才能完成，而对比前面没有条件分支时，同样是两条指令，只需要6个时钟周期就可以完成。可见，由于条件跳转的存在，CPU不得不白白浪费了4个时钟周期。
而且，这只是五级流水线的情况，实际上，现代CPU内部指令流水线的级数要大的多，而在这种场景中，流水线级数越多，浪费的时钟周期数就越多，如果再考虑Superscalar，情况会更糟。
那么，该如何解决这个问题呢？难道要完全避免if/else等语句的使用吗？这显然是不现实的。
因此，CPU为了解决这个问题，引入了新的功能单元 - 分支预测(Branch Prediction)和推测执行(Speculative Execution，有资料翻译为“投机执行”).
分支预测和推测执行简单来说，就是CPU在遇到分支指令时，会先预测分支条件的结果，并根据预测的结果，提前去执行分支后面的指令序列。
比如，还是这段代码：
if(a > b){
x = 1;
} else {
y = 2;
}
CPU遇到a > b这条指令时，先猜一下这个条件是true还是false，这里我们假设猜true，那么CPU就会在执行a > b这条指令的同时去执行x = 1，或者更准确地说，是a > b完成取指阶段，进入译码阶段时，x = 1这条指令就可以进入取指阶段了，无需等待a > b的执行结果。如下图所示：
可以简单理解为：CPU猜测a > b是否成立的这个动作，叫做分支预测，而在a > b结果计算出来之前就开始提前执行x = 1的这个动作，叫做推测执行。当然， 严格来讲，这个定义并不是十分准确，但是对于理解本文所要讲的问题，足够了。
分支预测和推测执行可以大大减少甚至避免由分支指令引起的指令流水线的停顿(也就是控制冲突)，使指令流水线尽可能地全速运行，从而大大提高CPU的性能。尤其在程序中存在大量分支，且分支预测准确率很高的情况下，对程序的整体性能会有显著的提升。
看到这里，我们自然会问，既然是预测，总会出错，对吧？那如果CPU分支预测错了，怎么办？
分支预测失败 = 严重的性能惩罚还以这段代码为例：
if(a > b){
x = 1;
} else {
y = 2;
}
假设CPU预测a > b是True，于是推测执行 x = 1, 但等a > b这条指令执行结束，发现结果是False，该怎么办呢？
答案很简单，如果猜错了，就把之前推测执行的x = 1这条指令丢弃掉，从正确的分支，也就是y = 2，重新执行就好了。如下图所示：
如果分支预测失败，CPU必须flush指令流水线，丢弃之前推测执行的指令，并从正确的分支路径重新开始执行。此外，还要做一些清理工作，比如把推测执行过程中使用到的寄存器等硬件资源恢复到原始的状态。因此，一旦CPU分支预测失败，会对指令流水线的正常运行造成延迟，程序遭受严重的性能惩罚。
那么，CPU究竟是如何进行分支预测的呢？
分支预测的实现原理分支预测的实现方式，一般分为两类：静态预测和动态预测。
静态预测静态预测，是最简单的分支预测技术，因为它不依赖于代码执行的历史信息，而是根据代码的静态特征（比如指令的位置、模式、分支指令的类型等）来预测分支的结果。比如，CPU可以采用一种最简单的预测算法：预测分支条件总是为True，或者总是为False。
此外，熟悉Linux内核的童鞋可能知道，Linux内核中有likely和unlikely宏，也可以理解为是一种广义的静态预测。但其本质上只是给编译器的一种优化提示，在大多数较新的CPU上，它只会影响到编译器对两个分支代码的布局顺序，这对提高程序i-Cache的局部性有一定帮助，但并不会真正影响到分支预测准确率。这不是本文重点，不再展开。
对于CPU来说，静态预测最大的优点是实现简单，几乎不需要增加太多额外的功能逻辑就可以实现。但它最大的缺点，是预测准确率太低。因此，主流CPU很少单纯依赖静态的方式来进行分支预测。
动态预测在介绍动态预测之前，大家不妨想一下，平时我们是如何预测天气的呢？如果天气一连好几天都是晴天，我们会预测明天大概率也是晴天，而如果一连好几天都是阴雨天气，我们预测明天大概率也是阴雨天气，毕竟天气连续晴雨交替的情况不多见。
以史为镜，可以知兴替。历史是最好的老师，这句话放到计算机领域，同样适用。
所谓动态预测，本质上就是CPU遇到一条分支指令时，根据这条分支指令历史的执行规律，来预测当前这次分支条件是True还是False。
比如下面这段代码：
这个代码中存在两个条件分支：i < 10000 和 i % 2 == 0，幸运的是CPU在执行这段代码时，根据它们的历史执行轨迹，很容易找到规律：
对于i < 10000，很明显存在这样的规律：
False False False False False ...
而i % 2 == 0则存在这样的规律：
True False False True False False True False False ...
因此，对于这段代码，CPU动态分支预测的准确率可以接近100%！
当然，我们这里讲的只是动态预测技术的一般性原理，具体实现方式有很多种，不同CPU可能采用不同的动态预测算法，这不是本文的重点，而且从软件开发的角度，我们也不需要过多关心内部实现细节，不再展开讨论。
了解了CPU内部指令分支预测和推测执行的原理后，就很好理解上文test1.c、test2.c和test3.c中calc()函数性能差异的真正原因了。
接下来先解释test1.c和test3.c中calc()性能差异的原因，然后再解释test2.c中calc()性能好的原因。
test1.c和test3.c中calc()性能差异的真正原因test1.c和test3.c代码逻辑是一模一样的，唯一的区别是：在调用calc()之前，test1.c中数组元素是随机无序的，而test3.c中是有序的。
test1.c中calc()性能差的原因前面讲过，CPU遇到一条分支指令时，需要根据这条分支指令的历史执行规律，来预测当前这次分支条件是True还是False，然后根据预测结果来提前执行后面的指令，以此来提高流水线的运行效率。
但是在test1.c中，数组中所有的元素都是随机生成的，无序的，也就是说对于array[i] > 50这个条件是否成立，没有任何规律可言，而这对于CPU来说，是最糟糕的情况！
因为，在这种情况下，这条指令的历史执行数据，几乎无法对CPU分支预测部件提供任何有用的信息，此时分支预测部件基本上处于一种最低效的状态，能否预测成功，全凭运气，就像抛硬币一样！
而一旦分支预测失败，将面临严重的性能惩罚，之前根据预测结果提前进入流水线的所有操作，全部都是无用功，需要全部撤销，CPU必须从正确的路径重新执行。
test3.c中calc()性能好的原因test3.c中，在执行calc()之前，先调用qsort()对数组元素进行了从小到大的排序，这样一来，前面约50%的元素都小于50，后面50%的元素都大于50。
因此，CPU很容易从array[i] > 50的历史执行数据中找到规律，从而使得分支预测的准确率非常高，接近100%，每次都能准确地把分支条件之后正确的指令序列提前送入指令流水线进行推测执行，使得指令流水线性能优势得到充分发挥！
上面这些只是单纯的理论分析，为了验证我们的结论，下面，我们借助perf工具来测算一下，CPU在执行test1.c和test3.c中的calc()函数时，if语句的分支预测准确率究竟是多少。
用perf测算calc()中if的分支预测准确率perf是Linux提供的一个非常强大且实用的性能调优工具，它可以用来观测几乎所有CPU相关的性能指标，但perf工具本身，不是本文重点，以后会有专门文章详细介绍perf的使用，感兴趣的小伙伴可以关注一下。
测算test1中calc()的分支预测准确率先看test1的，先用perf record进行统计，这里我们只关心用户态的branches和branch-misses的数据：
perf record -e branches:u,branch-misses:u ./test1
然后用perf report查看结果，先看总的branch数：
perf统计到用户态branches总数是4784245987，其中函数calc()占比10.76%，也就是4784245987 * 10.76% = 514784868次。
函数calc()中分支指令有两条：
- i < SIZE，这个是for循环的结束条件
- if(array[i] > 50)
这两条分支指令的执行次数一样，各占50%。因此，被统计到的if(array[i] > 50)的次数应该是：514784868 * 50% = 257392434次。
接下来看branch-misses(即分支预测失败)的数据：
perf统计到的branch-misses总数是135894569，其中函数calc()占比93.95%，也就是135894569 * 93.95% = 127672948次。
对于branch-misses事件来说，虽然calc()中分支指令有两条，但根据上面对动态分支预测原理的理解，不难想到，对于for循环的结束条件i < SIZE这个分支的预测准确率，可以认为是100%。因此，这里perf统计到的calc()中的branch-misses事件，全部都是if(array[i] > 50)触发的。
所以，我们得到if(array[i] > 50)分支预测的失败率：127672948 / 257392434 = 49.6%，看来真的和抛硬币一样，分支预测准确率只有50%左右！
测算test3中calc()的分支预测准确率同样，先用perf record来统计test3在用户态的branches和branch-misses的数据：
perf record -e branches:u,branch-misses:u ./test3
然后用perf report查看结果，这次我们直接看branch-misses(即分支预测失败)的数据：
出乎意料的是，在"Symbol"这一列居然看不到calc()函数了，这说明，perf已经统计不到在calc()函数中的branch-misses事件了，也就意味着，此时，calc()函数中分支预测准确率是100%(因为失败率为0)！
这也就是test3.c的calc()比test1.c快了4倍多的根本原因！
看到这里，自然会有疑问，既然test1.c和test3.c中calc()函数的性能差异是由于分支预测的准确率导致的，那又该怎么解释test2.c中calc()的性能呢？同样是随机且无序的数组，为什么test2.c比test1.c的性能好那么多呢？
test2.c性能为什么好？test1.c和test2.c中，数组元素都是随机且无序的，唯一的区别是，test1.c的calc()是这样的：
test2.c的calc()把for循环中的if语句替换成了三元表达式：
就是这样一个看似无关紧要的改动，使得test2.c的运行速度是test1.c的4.2倍！
上文解释了，test1.c中calc()函数性能差，是因为随机无序的数组元素导致CPU分支预测准确率非常低，只有50%，指令流水线无法充分发挥其性能优势。
而test2.c虽然把if替换成了三元表达式，从C语言的角度看，其本质上也是和if语句一样的语义，同样存在分支条件，为什么它的性能那么好呢？
原因其实很简单，对比下它们的汇编代码就清楚了！这里，我们只关心两个calc()函数中的if语句和三元表达式对应的汇编代码。
先看test1.c中calc()的汇编：
很明显，里面有一条条件跳转指令jle，CPU需要根据第一条cmp指令的结果，来决定是继续执行jle下面的第三条指令，还是要跳转到0x11c1地址执行。
再来看test2.c中calc()三元表达式对应的汇编：
原来，GCC在生成三元表达式时，没有使用条件跳转指令！
没了条件跳转指令，自然也就不需要分支预测了，直接顺序执行指令就行了，这也就是为什么test2.c性能比test1.c好那么多的根本原因！
CPU在执行第一条cmp指令时，很明确接下来要执行的一定是第二条setg指令，因此在cmp指令完成取指，开始译码的时候，setg指令就可以开始进入取指阶段了，同样setg开始译码时，movzbl就可以开始取指了，这样能够很好地发挥指令流水线的性能了。如下图所示：
不过，setg最终还是要根据cmp指令的结果来设置al寄存器的值，所以在setg执行的过程中，有可能还会让流水线产生短暂的停顿来等待cmp的结果，但这相对于分支预测失败给流水线带来的性能惩罚，是很小的，因此，test2.c会比test1.c的性能好的多。
但是，在分支预测准确率非常高时，由于几乎不会遭受预测失败的性能惩罚，条件跳转的性能反而会更好些，比如test3.c中calc()的性能就稍优于test2.c。
不同的编译器，可能会用不同的指令来处理三元表达式，如果换成别的编译器可能会产生不同的指令，如cmov，但其本质是一样的，都是消除了条件跳转指令。
另外，由于消除了分支指令，不再需要分支预测的参与，calc()的性能也就不再依赖数组元素是否有序了。
简单验证一下，把上面的test2.c简单修改一下，在调用calc()之前，先对数组进行排序，然后重命名为test4.c:
然后对比下test2.c和test4.c中calc()的耗时：
可以看到，无论数组元素是否有序，此时calc()函数的性能是一样的。
值得一提的是，如果编译test1.c时加了-O2优化选项，test1.c和test2.c会生成一模一样的代码，就不存在性能差异了。关于优化选项的问题，稍后再讲。
三元表达式的局限性- 不是所有的if-else语句都能替换成三元表达式。这个很好理解，不再赘述。
- 不是所有的三元表达式都可以用setg或cmov等条件指令来处理。
- setg、cmov等条件指令本质上是通过把结构依赖转化成数据依赖来消除条件分支指令，这在分支预测准确率非常高的场景下，其性能表现反而不如条件分支指令，比如test3.c中calc()的性能就稍优于test2.c。
因此，一般不建议手动去做这种优化，交给编译器去做更为合适。但如果必须要手写汇编时，可以考虑使用。
加了-O3优化选项后，性能差异还存在吗？最后，还有一个疑问需要解决：如果加上优化选项，test1， test2， test3的性能差异还会这么大吗？
直接给出答案吧：对于文中三个简单的示例代码来说，加了-O3优化选项后，三者的性能几乎一样：
这是因为，加了-O3后，GCC利用SIMD指令集对calc()做了向量化处理，几乎消除了分支预测带来的影响。
那么，为什么还要讲文中这些东西呢？
直接看一个例子吧！
把文中的test3.c稍微改一下，保存为test5.c：
逻辑很简单：
- 定义两个全局数组array和copy，把array中大于50的元素拷贝到copy中。
- main中把数组array的所有元素初始化为0~99之间的随机值。
- 默认不对array进行排序，只有当参数传入"sort"时，才对array进行排序。
编译test5.c，先不加优化选项：
无优化选项时，有序数组的运行速度是无序数组的3.8倍！
然后加上-O3优化选项，重新编译运行：
加了-O3后，有序数组的运行速度仍然是无序数组的4.2倍!
可见，编译器的优化并不是万能的！况且，现实的代码中，分支跳转指令是不可避免的，尤其在一些热点路径中，尤其需要考虑分支预测的准确率，有时，这会对系统整体性能产生非常大的影响！
大多数时候，编译器的优化工作确实做的足够出色，比我们手工进行优化要简单高效的多，在绝大多数没有很高性能要求的场景中，这确实已经足够了。
但是，在对性能有着非常严苛要求的场景中，仅仅依赖编译器所做的优化，是远远不够的，这时候我们不得不手动优化，去尽力榨取硬件的每一点性能。尤其对于性能热点路径上的代码，有时，牺牲一点代码的可读性来换取更好的性能，也是值得的，当然，需要根据实际的应用场景来仔细评估。
推荐阅读本专题除讲解常见性能问题以及分析、调优手段外，还会重点讲解一些对系统性能至关重要，却又经常被忽视的高级话题，如Cache、指令流水线、Superscalar、SIMD、分支预测、内存屏障等。此外，还会涉及到编译器、操作系统等话题。
原创不易，别忘了留言点赞！右上角关注！欢迎留言讨论！
原创文章，未经允许，禁止转载！
