大家好，我是江南一散人，本文是程序性能调优系列专题第四篇。
本专题除讲解常见性能问题以及分析、调优手段外，还会重点讲解一些对系统性能至关重要，却又经常被忽视的高级话题，如Cache、指令流水线、Superscalar、SIMD、分支预测、内存屏障等。此外，还会涉及到编译器、操作系统等话题。
一资深程序员，应聘系统调优专家。有这么一段代码：
面试官：这段代码很简单，不需要解释了吧？
答：是的。功能是统计数组中，值大于500的元素个数，和小于等于500的元素个数的差值。
面试官：是的。你觉得这段代码的运行时间受哪些因素影响？
答：系统负载，CPU使用率很高的话，运行速度会变慢。
面试官：嗯，不考虑负载呢？
答：那运行时间不会有太大变化。
面试官：数组array里的数据，会影响calc()的性能吗？比如，一个无序的数组，和一个有序的数组，calc()的处理时间一样吗？
答：一样！不管数组元素是什么，是否有序，只会影响返回值a-b。不管元素值是多少，要么执行a++，要么执行b++，最终执行的指令总数是一样的，所以运行时间不会变化！
面试官：确定吗？
答：确定！
面试官：好了，感谢来参加面试，回去等通知吧！
思考一下，如果是你的话，会怎么回答呢？
下面，来深入讲解一下，隐藏在这道题背后的深层次知识！
本文较长，且涉及到CPU内部很底层的知识，请耐心看完，一定会有收获！
测试程序
测试程序test1.c非常简单，把数组array的元素初始化为0~999之间的随机值，调用面试题中的calc()函数，并测量它的运行时间。代码如下：
编译运行一下：
然后，只改一行代码，把array初始化为有序数组，命名为test2.c：
重新编译运行：
calc()运行耗时从3.251秒降到了0.722秒。有序数组的处理速度，居然是无序数组的4.5倍！
是否觉得不可思议？原因稍后详解！
看到这里，有人会有疑问，上面代码编译时，连优化选项都没加，这样对比性能差异有什么意义呢？
-O3，一定能消除差异吗？
首先，说明一下，上面之所以没加-O3，是因为代码逻辑太过简单，加了-O3之后，编译器会用SIMD指令集进行优化，就无法当做示例来讲解本文的重点内容了。
下面换个例子，来验证加了-O3之后，能不能消除这个性能差异。
代码也很简单：
代码如下，test3.c：
注意：为了演示数组元素顺序对遍历性能的影响，这里只测量calc()的运行时间，无需纠结排序本身的耗时！
编译test3.c，先不加优化选项：
无优化选项时，有序数组的处理速度是无序数组的3.8倍！
然后加上-O3优化选项，重新编译运行：
加了-O3后，有序数组的处理速度仍然是无序数组的近4倍!
可见，加了-O3之后，编译器确实做了很不错的优化，但是，对calc()函数而言，无论是否加-O3，处理有序数组的速度，都是无序数组的4倍！
接下来，正式开始解释性能差异的原因。
重要说明
为讲解清楚，必须先补充一些CPU相关的基础知识。这会涉及到CPU内部实现细节，相对比较底层，而且对绝大多数程序员是透明的，因此很多人可能都没听说过这些概念。不过，也不用担心，跟之前一样，我会尽量用通俗易懂的语言来解释这些概念。
注：指令流水线部分概念虽然在之前文章介绍过，但为了文章的独立和完整性，本文会再次简单介绍，但侧重点与之前不同，因此，无论是否看过之前文章，都请仔细阅读！
背景知识：指令流水线(pipeline)
在CPU内部，一条指令的执行过程被分为多个阶段，每个阶段使用CPU内部不同的硬件资源来完成，就像是工厂里的流水线一样，因此被称为指令流水线(pipeline)。
以经典的5级流水线为例，一条指令在CPU内的执行，被分为5个阶段：
在时钟信号的驱动下，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，情况会更糟。(上篇《》中，对指令流水线、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，很明显存在这样的规律：
True True True True True ...而i % 2 == 0则存在这样的规律：
True False True False True False ...因此，对于这段代码，CPU动态分支预测的准确率可以接近100%！
当然，我们这里讲的只是动态预测技术的一般性原理，具体实现方式有很多种，不同CPU可能采用不同的动态预测算法，这不是本文的重点，而且从软件开发的角度，也不需要过多关心内部实现细节，不再展开讨论。
了解了CPU内部指令分支预测和推测执行的原理后，就很好理解上文test1.c、test2.c中calc()函数性能差异的真正原因了。
test1和test2性能差异的原因
test1.c和test2.c逻辑一模一样，唯一的区别是：test1.c中数组元素是随机无序的，而test2.c中是有序的。
test1.c中calc()性能差的原因
前面讲过，CPU遇到一条分支指令时，需要根据这条分支指令的历史执行规律，来预测当前这次分支条件是True还是False，然后根据预测结果来提前执行后面的指令，以此来提高流水线的运行效率。
但是在test1.c中，数组中所有的元素都是随机生成的，无序的，也就是说对于array[i] > 500这个条件是否成立，没有任何规律可言，而这对CPU来说，是最糟糕的情况！
因为，在这种情况下，这条指令的历史执行数据，几乎无法对CPU分支预测部件提供任何有用的信息，此时分支预测部件基本上处于一种最低效的状态，能否预测成功，全凭运气，就像抛硬币一样！
而一旦分支预测失败，将面临严重的性能惩罚，之前根据预测结果提前进入流水线的所有操作，全部都是无用功，需要全部撤销，CPU必须从正确的路径重新执行。
test2.c中calc()性能好的原因
test2.c中，array被初始化成有序的数组，这样一来，前面500个元素都都小于500，后面的元素都大于500。因此，CPU很容易从array[i] > 500的历史执行数据中找到规律，从而使得分支预测的准确率非常高，接近100%，每次都能准确地把分支条件之后正确的指令序列提前送入指令流水线进行推测执行，使得指令流水线性能优势得到充分发挥！
同样的，test3.c中，无论是否用-O3优化，处理有序的数组的速度都是无序数组的4倍左右，都是因为无序数组的分支预测准确率只有50%左右，而有序数组的分支预测率则接近100%。
上面只是单纯的理论分析，为了验证我们的结论，下面，我们借助perf工具来测算一下，test3.c中，处理无序数组和有序数组时，calc()中的if语句的分支预测率分别是多少。
perf测算test3中calc()分支预测准确率
perf是Linux提供的一个非常强大且实用的性能调优工具，它可以用来观测几乎所有CPU相关的性能指标，但perf工具本身，不是本文重点，以后会有专门文章详细介绍perf的使用，感兴趣的朋友可以关注一下。
无序数组分支预测准确率
先用test3处理无序数组，用perf record进行统计，这里我们只关心用户态的branches和branch-misses的数据：
perf record -e branches:u,branch-misses:u ./test3然后用perf report查看结果，先看总的branches数：
perf统计到用户态branches总数是4780173621，其中函数calc()占比10.65%，也就是4780173621 * 10.65% = 509088491次。
函数calc()中分支指令有两条：
这两条分支指令的执行次数一样，各占50%。因此，被统计到的if(array[i] > 500)的次数应该是：509088491 * 50% = 254544246次。
再看branch-misses(即分支预测失败)的数据：
perf统计到的branch-misses总数是135754744，其中函数calc()占比93.94%，也就是135754744 * 93.94% = 127528007次。
对于branch-misses事件来说，虽然calc()中分支指令有两条，但根据上面对动态分支预测原理的理解，不难想到，对于for循环的结束条件i 500)触发的。
所以，我们得到if(array[i] > 500)分支预测的失败率：127528007 / 254544246 = 50.1%，看来真的和抛硬币一样，分支预测准确率只有50%左右！
有序数组的分支预测准确率
同样，先用perf record来统计test3处理有序数组时，在用户态的branches和branch-misses的数据：
perf record -e branches:u,branch-misses:u ./test3 sort然后用perf report查看结果，这次我们直接看branch-misses(即分支预测失败)的数据：
可以看到，calc()的branch-misses的占比是0.00%，也就是说，此时calc()中if语句的分支预测准确率是100%！
小结
分支预测的准确率，对提高CPU指令流水线的效率至关重要，一旦分支预测失败，会造成指令流水线的延迟，遭受严重的性能惩罚。尤其在对性能敏感的热点路径中，如果分支预测准确率太低，会严重降低程序性能。我们应该尽可能地合理组织数据和代码结构，使得分支代码的执行有规律可循，帮助CPU提高分支预测准确率。同时，也应该尽量避免在热点路径(如循环体中)进行不必要的分支判断。
不过，现代的CPU的分支预测准确率是非常高的，据统计，一般可以达到90%以上。因此，在对性能没有严格要求的场景中，往往编译器就可以帮我们很好地进行代码优化。
如果系统真的遇到性能问题，除了架构、算法等方面的考量外，不妨从CPU的角度思考一下，如何通过调整代码结构和数据组织方式，来提高指令流水线的运行效率，或许会有事半功倍的效果。通常，可以借助perf等工具，找到真正的性能瓶颈，然后进行针对性优化。
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： lzxmw777
