常数优化之循环展开

背景

各位读者可能在兴高采烈要死要活地码完一道题兴奋地交题后也遇到过下面的情况：

或者更OI一点：

大家大概都是一边抱怨毒瘤出题人，一边真香地改代码。如果复杂度是对的，那就要考虑程序的常数是不是太大了，进而考虑怎么优化。啥，你说开O2吸个氧不就完了？yysy，确实问题是正式比赛不知道给不给开，而且编译器优化最重要的是在不改变程序行为的前提下优化，总不能优化错吧，所以如果程序写得实在是很难优化，编译器也无能为力，还是要自己来。考虑到OI选手都是初、高中生巨佬小学生巨佬暂且不考虑，还没有接触大学课程，尤其是深入理解计算机系统这门课，可能对这种方法了解的也比较少，下面就介绍一种不知道常不用的常数优化方法——循环展开就是介绍点深入理解计算机系统(CSAPP)的内容，下文的图片也都出自该书

观前提示：以下内容仅供参考，本大学狗也只是刚学完这门课，有些内容可能有疏漏，为了能将内容讲得更容易理解，说法也不是很严谨

循环展开——CPU友好型代码

原理

流水线

现代CPU采用流水线设计(可以类比汽车生产流水线，分多阶段)，把一条机器指令的执行分成多个阶段，然后每个时钟周期尽可能多地执行不同指令的不同阶段，我们可以从下面两张图看出流水线和不流水线的区别

• \(I1、I2、I3\)表示待三条不同的机器指令，\(A、B、C\)代表指令的阶段(当然不止3个，由CPU设计者决定)

显然流水线只要流起来可以大大提高CPU的工作效率，前提是流起来，如果\(I2\)的\(A\)阶段涉及的数据\(a\)和\(I1\)的一致，且\(I1\)操作又会修改\(a\)，那么就可能出现\(I1\)的\(C\)阶段还没完成对\(a\)的修改就被\(I2\)用了，就会出现错误；到这里读者可以类比编译器的优化，编译器优化不改变程序行为，流水线也不能让程序出错。怎么解决涉及到数据转发等知识，有兴趣的读者可以去看CSAPP原书，这里不做介绍。结论是CPU的设计者设计的硬件能让流水线很好地运作，即使在少数情况下也只牺牲一点效率。为了让流水线更好地流，我们可以在写程序时可以地减少程序相邻行的数据相关。比如

x += a;
tmp = x * b;
// 可以改为
tmp = a * b + x * b;

理解现代处理器——以Intel Core i7 Haswell为例

现代处理器中有许多功能单元，它们有着各自的功能，比如Intel Core i7 Haswell，它有8个功能单元，如下图所示

我们不需要理解加载、分支等的具体意思，我们需要理解的就是，不同功能单元能同时工作，只是它们的“业务”范围不一定相同，理解了这些之后，就开始介绍本文的重点内容——循环展开

循环展开

循环展开是一种程序变换，通过增加每次迭代计算元素的数量，减少循环迭代次数。以求和函数为例：

//非循环展开
for(int i = 1; i <= n; i++)
    sum += a[i];

//2*1循环展开
int i;
for(i = 1; i <= n - 1; i += 2) {
    sum += a[i];
    sum += a[i + 1];
}
for(; i <= n; i++)
    sum += a[i];

//3*1循环展开
int i;
for(i = 1; i <= n - 2; i += 3) {
    sum += a[i];
    sum += a[i + 1];
    sum += a[i + 2];
}
for(; i <= n; i++)
    sum += a[i];

2×1和3×1循环展开中的2和3很好理解，就是步长的意思，至于1是什么意思，恳请众看官耐心看下去。

大家能都很好奇，就简单地改改步长，能让代码变快？？回答这个问题之前，我们先讲讲循环展开如何改进程序的性能。循环展开主要从两个方面改进程序性能：

• 它减少了不直接有助于程序结果的操作数的数量，如2×1展开中，i += 2的执行次数小于i++的次数，i <= n的条件判断次数也是2×1展开少
• 它提供了一些方法，可以进一步变化代码，使其性能更高

对于第二点，我们可以通过一些手段来提高代码的效率：2×2循环展开

先看看代码怎么写的：

//2*2循环展开
int i, sum0, sum1, sum;
for(i = 1; i <= n - 1; i += 2) {
    sum0 = sum0 + a[i];
    sum1 = sum1 + a[i + 1];
}
for(i; i <= n; i++)
    sum0 += a[i];
sum = sum0 + sum1;

对比2×1循环展开，我们发现2×2循坏展开采用了两个变量sum0、sum1来累积和，这就是2×2中的后面的2的含义。为啥要这样呢？在流水线部分，我们提到过代码相邻行的数据相关越小流水线越好流，效率也就更高，普通的2×1循环展开中，数据相关较大，sum += a[i]得到的sum值还要参与sum += a[i + 1]的运算，导致流水线的效率降低，改用两个变量，消除了数据相关，所以代码执行的效率变高了

笔者在数据量为3e6的情况下随机生成了50组测试数据，分别采用上述4种循环方式以及5×5的循环展开跑程序，取平均后的结果如下：(以下结果均是在没开O2的情况下测的，仅供参考)

从数据上来5×5展开的效果最好，比1×1快2倍多(读者可以尝试3×3展开、4×4展开等)，需要注意的是，不是循环展开级数增加了就一定能提高性能，因为常用寄存器就那么几个，超过一定数量后，累积变量就不能存在寄存器里了，需要存在内存里，所以效果并不一定会好，具体可以去看CSAPP原书

题外话

其实CSAPP中还有其他许多的优化方法，如利用局部性原理——编写高速缓存友好型程序以及编写编译器友好型程序，前者优化效果较优，但技巧性教循环展开要强，而且因机而异，后者不知道怎么写能写出来不错了，还要编译器友好？，但是前者涉及到的知识和存储器的结构有较大关联，要想讲清楚可能得把CSAPP中的一、两章都讲掉，如果有空，会考虑再写一篇利用局部性原理的优化方法

说了这么多，最重要的还是程序员友好型——自己咋舒服咋写，对于我这种CE选手常数优化是实在没办法的时候的下下之选。ACM赛场上风云莫测，常数优化也要谨慎，万一压根不是常数的问题不白忙活嘛，还吃罚时；OI的时候也一样，别舍本逐末，别为了贪那一两个数据点打上一些常数优化的骚操作结果爆零

参考文献

深入理解计算机系统 第三版