改几行代码，for 循环耗时从 3.2 秒降到 0.3 秒！真正看懂的都是牛人！
一切都要从一个面试题说起！
一道面试题
有朋友私信给我，聊了下自己的一段面试经历，有这么一段代码：
免责声明：这个面试官真的不是我！！！
面试官：这段求阶乘的代码怎么样？
答：挺简洁的，简单易懂。不过如果参数n值比较大的话，会导致fact溢出，结果是错的。
面试官：嗯，是的。不过，咱们先不考虑溢出的问题，你觉得这段代码的性能怎么样？
答：时间复杂度是O(n)，而且代码比较精炼，性能应该还挺不错的吧？(心虚ing...)
面试官：你能想办法把它优化一下，让性能更好吗？
思考ing...
答：在多CPU系统上，如果n的值比较大的话，可以考虑用多线程来实现。
面试官：嗯，这是一个思路。如果是单CPU呢？
再次思考ing...
答：用GCC编译的话，可以加上优化选项-O3，应该能提高性能。
面试官：嗯，还有吗？
答：没了。
面试官：好了，感谢来参加面试，回去等通知吧！
思考一下，如果是你的话，会怎么回答呢？
下面，来深入讲解一下，隐藏在这道题背后的深层次知识！
本文较长，且涉及到CPU内部很底层的知识，请耐心看完，一定会有收获！
测试程序
测试程序test.c非常简单，计算1000000000的阶乘：
为方便分析，函数calc()前面加上__attribute__((noinline))，禁止GCC把calc内联在main()中。此外，calc()中，fact类型是int，main()中调用calc(1000000000)，会导致fact溢出，但不影响测试，不用管它。
编译一下，然后用time命令测量下运行耗时：
然后，把程序稍微改一下，命名为test_2.c：
注意：这里为方便讲解，假设n总是4的倍数。如果要处理n不是4的倍数的情况，只需要在主循环体外，增加一个小的循环单独处理最后的n%4个数，也就是最多3个数即可，对整体性能影响几乎为0.
编译，并用time命令测量下运行耗时：
运行耗时从原来的3.29秒降到了1秒，性能提升了200%！你以为这就完了？
这还不是最终的结果，因为我们还有一个优化技巧还没加上，最终优化后的结果是0.3秒！文末会讲！先不着急，咱们一个一个来讲！
关于循环展开：你真的理解吗？
看到这里，有人会说，不就是循环展开嘛，很简单的，没什么好研究的，而且加了优化选项之后，编译器会自动进行循环展开的，没必要手动去展开，也就没有研究的价值了！
真的是这样吗？先尝试回答下面几个问题：
- 1. 循环展开为什么能提高程序性能，其背后的深层次原理是什么？
- 2. 循环随便怎么展开都一定可以提高性能吗？
- 3. 用了优化选项，编译器一定会帮我们自动进行循环展开优化吗？
第一个问题后面会详细讲解，我们先用实例回答下第2个和第3个问题。
先看第2个问题。
循环随便展开都能提高性能吗？
我们把test_2.c稍微改一下，命令为test_3.c：
仍然是循环展开，只不过把循环展开的方式稍微改了一下。再编译一下，用time命令测量下运行耗时：
和test.c相比运行耗时只减少了0.2秒！为什么同样是循环展开，test_2.c只需要1.6秒，而test_3.c却要3秒，为什么性能差异这么大呢？别着急，后面细讲。
再看第三个问题，加了优化选项，编译器一定会帮我们自动进行循环展开优化吗？一试便知！
-O3，编译器一定会循环展开吗？
重新编译下test.c, test_2.c, 和test_3.c，只不过，这次我们加上-O3优化选项，然后分别用time命令再测量下运行时间。
先是test.c：
加了-O3优化后，程序耗时从原来的3.29秒降到了1.07秒，性能提升确实非常明显！是否好奇，-O3选项对test.c做了什么样的优化，能够把程序耗时降到三分之一？这个后面再讲。
现在，我们先试下test_2.c：
同样，加了-O3后，程序耗时从原来的1秒降到了0.368秒！此外，在同样加了-O3的情况下，使用了循环展开的test_2.c，程序耗时仍然是test.c的三分之一！可见，编译器确实优化了一些东西，但是，无论是否加-O3优化选项，进行手动循环展开的test.c仍然是性能最好的！
最后，再试下test_3.c:
看到了吧？同样加了-O3优化选项的前提下，性能仍然与test_2.c相差甚远！
小结一下我们现在得到的几组测试结果：
在解释这些性能差异的原因之前，必须要先补充一些CPU相关的基础知识，否则无法真正理解这背后的原因！所以，请务必认真看完！
这会涉及到CPU内部实现细节的知识，相对比较底层，而且对绝大多数程序员是透明的，因此很多人甚至都没听说过这些概念。不过，也不用担心，跟之前一样，我会尽量用通俗易懂的语言来解释这些概念。
背景知识：CPU内部架构
指令流水线(pipeline)
所谓流水线，是把指令的执行过程分成多个阶段，每个阶段使用CPU内部不同的硬件资源来完成。以经典的5级流水线为例，一条指令的执行被分为5个阶段：
- • 取指(IF)：从内存中取出一条指令。
- • 译码(ID)：对指令进行解码，确定该指令要执行的操作。
- • 执行(EX)：执行该指令要执行的操作。
- • 访存(MEM)：进行内存访问操作。
- • 写回(WB)：把执行的结果写回寄存器或内存。
在时钟信号的驱动下，CPU依次来执行这些步骤，这就构成了指令流水线(pipeline)。如下图所示：
在CPU内部，执行每个阶段使用不同的硬件资源，从而可以让多条指令的执行时间相互重叠。当第一条指令完成取指，进入译码阶段时，第二条指令就可以进入取指阶段了。以此类推，在一个5级流水线中，理想情况下，可以有5条不同的指令的不同阶段在同时执行，因此每个时钟周期都会有一条指令完成执行，从而大大提高了CPU执行指令的吞吐率，从而提高CPU整体性能。这就叫做ILP - 指令级并行（Instruction Level Parallelism）。如下图所示：
通过把指令执行分为多个阶段，CPU每个时钟周期只处理一个阶段的工作，这样大大简化了CPU内部负责每个阶段的功能单元，每个时钟周期要做的事情少了，提高时钟频率也变得简单了。
前面说过，有了流水线技术，理想情况下，每个时钟周期，CPU可以完成一条指令的执行。那有没有什么方法，可以让CPU在每个时钟周期，完成多条指令的执行呢，这岂不是会大大提高CPU整体性能吗？
当然有！这就是Superscalar技术！（除此之外还有VLIW，不是本文重点，不再展开讨论。）
超标量(Superscalar)
Superscalar，通过在CPU内部实现多条指令流水线，可以真正实现多条命令并行执行，也被称为多发射数据通路技术。以双发射流水线为例，每个时钟周期，CPU可以同时读取两条指令，然后同时对这两条指令进行译码，同时执行，然后同时写回。如下图所示：
目前为止，这一切看起来都很完美，对吧？然而，现实往往没有理想那么丰满！接着往下看吧。
流水线冲突
大家可能注意到了，前面多次强调过，“在理想状态下”，为什么呢？
现实中程序的指令序列之间往往存在各种各样的依赖和相关性，而CPU为了解决这种指令间的依赖和相关性，有时候不得不“停顿”下来，直到这些依赖得到解决，这就导致CPU指令流水线无法总是保持“全速运行”。
这种现象被称之为Pipeline Hazard，很多资料翻译为“流水线冒险”，我觉得“流水线冲突”更为贴切易懂。
归结起来，有三种情况：
- • 数据冲突(Data Hazard)
- • 控制冲突(Control Hazard)
- • 结构冲突(Structure Hazard)
下面分别举例解释这三种类型的冲突。
数据冲突
所谓数据冲突，简单讲，就是两条在流水线中并行执行的指令，第二条指令需要用到第一条指令的执行结果，因此第二条指令的执行不得不暂停，一直到可以获取到第一条指令的执行结果为止。
比如，用伪代码举例：
x = 1;
y = x;要对y进行赋值，必须要先得到x的值，因此这两条语句无法完全并行执行。
这只是其中的一种典型情况，其他情况不再赘述。
控制冲突
所谓控制冲突，简单讲，就是在CPU在执行分支跳转时，无法预知下一条要执行的指令。
比如：
if(a > 100) {
x = 1;
} else {
y = 2;
}在CPU计算出a > 100这个条件是否成立之前，无法确定接下来是应该执行x = 1 还是执行 y = 2。
为了解决这个问题，CPU可以简单的让流水线停顿一直到确定下一条要执行的指令，也可以采取如分支预测(branch prediction)和推测执行(speculation execution)等手段，但是，预测失败的话，流水线往往会受到比较严重的性能惩罚。之后会有专门的文章分析这个问题，感兴趣的话，可以右上角关注一下！
结构冲突
结构冲突，简单来说，就是多条指令同时竞争同一个硬件资源，由于硬件资源短缺，无法同时满足所有指令的执行请求。如两条并行执行的命令需要同时访问内存，而内存地址译码单元可能只有一个，这就产生了结构冲突。
有了上面这些基础知识做铺垫，接下来就可以开始真正分析这个问题了。
test.c为什么性能最差？
对于计算阶乘，test.c可能是最简单直观、可读性最强的算法。不过可惜的是，它也是性能最差的。
我们再看一下test.c的源码：
说它性能最差，主要有三点原因：
- 1. 热点路径无用指令太多。
- 2. 热点路径跳转指令太多。
- 3. 热点路径内存访问太多。
注意，这里说的无用指令，是指对计算阶乘本身不产生直接影响的指令，但是它们对整个算法的正确性仍然是必不可少的！
为例方便理解，我们来分别看下test.c不加优化选项和加了-O3编译之后的汇编代码。
test.c不加优化选项时
先是不加优化选项的：
绿色方框标注出来的8 ~ 14行是for循环，也就是主循环体。其中，蓝色方框标注出来的8 ~ 11行是真正计算阶乘的代码，12 ~ 14行是循环控制代码，对计算阶乘来说，则是无用代码。
不难看出：
- 1. 热点路径上，也就是循环体内无用指令占比是3/7 = 42%！即便在不考虑其他因素的情况下，CPU单单用来执行这些无用的指令，也是一笔不小的开销！
- 2. 整个阶乘计算过程中，循环体内需要执行1000000000次条件跳转指令！条件跳转又会造成控制冲突，使得流水线无法全速运行，从而造成巨大的性能损失。
- 3. 整个函数一共有10个内存访问操作，而循环体内就有6个内存操作！尽管很多时候可以通过Cache来缓解，但相对于CPU计算速度来说，内存操作仍然是非常慢的，而且容易造成流水线冲突！
那加了-O3优化选项之后，编译器能不能帮我们解决这些问题呢？
test.c加了-O3优化选项后
现在我们看下加了-O3之后的汇编代码：
首先，不得不感叹，现在的编译器的优化真的是太强大了！直接把整个for循环优化成了4条指令！
不难看出，对于test.c而言，加了-O3之后，GCC做的最大的优化是把所有变量存放在寄存器中，消除了所有的内存访问操作！
可以回过头去看下优化之前的汇编代码，整个函数一共有10个内存访问操作，其中6个是在循环体内，而加了-O3之后，整个函数没有任何内存访问操作！难怪-O3编译后性能提升那么多！由此可见，内存访问相对寄存器访问的开销实在是太大了！当然，即便不使用-O3，也有优化内存操作的办法，这个后面再讲。
但是，也不难看出，对于其他两个问题，GCC并没有帮我们解决：现在无用指令占比是 2/4 = 50%! 整个阶乘计算过程，仍然需要执行1000000000次条件跳转指令，仍然无法充分发挥流水线和superscalar的指令并行执行能力！
知道了test.c性能差的原因之后，现在我们来看看，通过手动循环展开，test_2.c又帮我们解决什么问题呢？
test_2.c性能提升原因
再看下test_2.c的源码：
通过对循环进行4次展开，之前每次循环执行1次乘法，现在每次循环执行4次，这就带来了三点很重要的变化：
- 1. 循环次数减少75%，无用指令减少了，相应的CPU执行这些指令本身的开销也少了。
- 2. 计算过程中，热点路径的条件跳转指令少了75%，这样就减少了由于控制相关引起的流水线冲突，提升了流水线执行的效率。
- 3. 提升了指令的并行度，使得CPU superscalar的技术得到更充分的发挥，提高了每个时钟周期并行执行指令的条数。
这也就是为什么在使用同样的编译选项时，test_2.c比test.c的性能提升了200%！不过，热点路径上内存访问操作太多的问题仍然存在。其实，这个其实很好解决，我会在下文给出解决方法。我们先把注意力放在这里所说的三点变化上。
对于第1点和第2点，有了前面介绍的指令流水线的背景知识，即便从C语言的角度也很好理解，不需要过多解释。
至于第3点，为了便于理解，我们和test_3.c对比来看。
test_3.c性能差的原因
再看下test_3.c的代码:
test_3.c虽然也把循环进行了4次展开，但是展开的方式和test_2.c是不一样的。
test_2.c是这样展开的：
fact0 *= i;
fact1 *= i + 1;
fact2 *= i + 2;
fact3 *= i + 3;而test_3.c则是这样做的：
fact *= i;
fact *= i + 1;
fact *= i + 2;
fact *= i + 3;很明显，后面一条指令执行前，必须要先知道前面一条语句计算的结果。还记得前面讲过的造成流水线冲突的三个原因吗？这就是典型的数据依赖，会造成流水线冲突！
可见，虽然test_3.c也通过循环展开，减少了无用指令，也减少了热点路径上分支跳转引起的流水线控制冲突，但它同时引入了数据依赖，进而导致流水线冲突，仍然无法发挥流水线和superscalar的指令级并行执行的能力！
这就是为什么，用同样的选项编译时，test_3.c虽然比未经过循环展开的test.c性能稍微提升了一点点，但相比同样循环展开且没有引入数据相关性的test_2.c来说，性能仍然是非常差的！
讲到这里，本想演示下用perf测量出来的性能指标的，但由于篇幅过长，就不再展开讨论了，以后会专门更新文章介绍perf相关工具的使用！
最后，来看一下前面遗留的那个问题：不加优化选项的情况下，怎么解决热点路径内存访问过多的问题。
杀手锏：优化热点路径内存访问
其实很简单，只需要把test_2.c中定义局部变量的时候加上register关键字就可以了：
C语言中，register关键字的作用是建议编译器，尽可能地把变量存放在寄存器中，以加快其访问速度。
我们现在看下，加了register关键字后，test_2.c的性能如何呢？
为方便对比，我们再看下添加register之前，test_2.c的耗时：
然后是加了register关键字之后的耗时：
看到差异了吧，相差3倍！加了register后，几乎达到了和加-O3优化选项一样的性能！
当然，register的使用还有很多限制，而且它只是给编译器的一种建议，不是强制要求，编译器只能尽量满足，当变量太多，寄存器不够用的时候，还是不得不把变量放到栈中，这和-O3的行为是一样的。
register不是本文重点，限于篇幅，不再赘述。
小结
循环展开是一种非常重要的优化方法，也是编译器后端中常用的一种优化方式，它可以通过减少热点路径上的“无用指令”以及分支指令的个数，来更好地发挥CPU指令流水线的指令并行执行能力，从而提高程序整体性能。
很多时候，我们可以借助编译器来帮我们实现这种优化，但编译器也有失效的时候，比如文中这个例子。这时，我们就不得不手动来进行循环展开来优化程序性能。循环展开时，必须尽量减少语句间的相互依赖。
此外，循环展开的次数并没有一个固定的公式，需要根据具体代码和CPU来决定，通常需要多次尝试来找到一个最优值。
不过，手动循环展开往往是以牺牲代码可读性为代价的，因此使用时也做好取舍。此外，循环展开还会在一定程度上增加程序代码段的大小，还可能会影响到程序局部性，对cache产生影响，因此使用时候，要仔细权衡。
- EOF -
关注「程序员的那些事」加星标，不错过圈内事
点赞和在看就是最大的支持❤️
阅读原文 关键词
代码
问题
条指令
结果
流水线
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明：以上内容为用户推荐收藏至CareerEngine平台，其内容（含文字、图片、视频、音频等）及知识版权均属用户或用户转发自的第三方网站，如涉嫌侵权，请通知[email protected]进行信息删除。如需查看信息来源，请点击“查看原文”。如需洽谈其它事宜，请联系[email protected]。
版权声明：以上内容为用户推荐收藏至CareerEngine平台，其内容（含文字、图片、视频、音频等）及知识版权均属用户或用户转发自的第三方网站，如涉嫌侵权，请通知[email protected]进行信息删除。如需查看信息来源，请点击“查看原文”。如需洽谈其它事宜，请联系[email protected]。