for循环展开浅析

改几行代码，for循环耗时从3.2秒降到0.3秒！真正看懂的都是牛人！

测试程序

测试程序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. 1. 循环展开为什么能提高程序性能，其背后的深层次原理是什么？

2. 2. 循环随便怎么展开都一定可以提高性能吗？

3. 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内部实现细节的知识，相对比较底层，而且对绝大多数程序员是透明的，因此很多人甚至都没听说过这些概念。不过，也不用担心，跟之前一样，我会尽量用通俗易懂的语言来解释这些概念。

test1.c

__attribute__((noinline)) int calc(int n) {
  int fact = 1;
  for (int i = 1; i < n; i++) {
    fact *= i;
  }
  return fact;
}

int main() { return calc(1000000000); }

test2.c

__attribute__((noinline)) int calc(int n) {
  int fact0 = 1,fact1=1,fact2=1,fact3=1;
  for (int i = 1; i < n; i += 4) {
    fact0 *= i;
    fact1 *= i + 1;
    fact2 *= i + 2;
    fact3 *= i + 3;
  }
  return fact0*fact1*fact2*fact3;
}

int main() { return calc(1000000000); }

test3.c

__attribute__((noinline)) int calc(int n) {
  int fact;
  for (int i = 1; i < n; i += 4) {
    fact *= i;
    fact *= i + 1;
    fact *= i + 2;
    fact *= i + 3;
  }
  return fact;
}

int main() { return calc(1000000000); }

背景知识：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. 1. 热点路径上，也就是循环体内无用指令占比是3/7 = 42%！即便在不考虑其他因素的情况下，CPU单单用来执行这些无用的指令，也是一笔不小的开销！

2. 2. 整个阶乘计算过程中，循环体内需要执行1000000000次条件跳转指令！条件跳转又会造成控制冲突，使得流水线无法全速运行，从而造成巨大的性能损失。

3. 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. 1. 循环次数减少75%，无用指令减少了，相应的CPU执行这些指令本身的开销也少了。

2. 2. 计算过程中，热点路径的条件跳转指令少了75%，这样就减少了由于控制相关引起的流水线冲突，提升了流水线执行的效率。

3. 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产生影响，因此使用时候，要仔细权衡。