大家好啊，我是董董灿。
这篇文章，会从软件的角度来介绍一个常用的AI加速方法。
循环展开
如果要我说一个最简单，最有效的，并且人人都能学会的程序优化方法，我估计会投票给Unrooling（译为：循环展开）。
循环展开，从名字就能看出来是什么意思：就是把一段循环代码展开来写。
听着简单，但具体怎么做呢？先举个简单的例子——
高斯年轻的时候，老师曾问他：从1加到100，结果是多少？高斯思考片刻后，给出了5050的答案，让老师大吃一惊。
这里也用这个例子，计算1到100的所有数的和。用C语言很容易写出下面的代码：
#include "stdio.h"
int main() {
int sum = 0;
for (int i = 1; i <= 100; ++i) {
sum = sum + i;
}
printf("sum = %d\n", sum);
return 0;
}这个写法很容易想出来：100个数相加，循环100次，每次累加一个数字，最终输出结果 sum = 5050。
那么，这段代码，如果用循环展开会怎么写呢？
#include "stdio.h"
int main() {
int sum = 0;
for (int i = 1; i <= 100; i+=4) {
sum = sum + i;
sum = sum + (i + 1);
sum = sum + (i + 2);
sum = sum + (i + 3);
}
printf("sum = %d\n", sum);
return 0;
}如上是循环展开的写法，我们把原来循环100次，每次循环加1个数的写法，写成了循环25次，每次循环加4个数。
从结果上看肯定是一致的，最终结果都是5050。但是两者的性能会有较大的差别。
性能验证
下面实际验证一下两种写法的性能。
为了更准确的获取到程序中数字累加的耗时，把100个数字的相加改为10000个数字相加。因为100个数字对于计算机来说太少了，两者的性能差别不大，不容易看出差别。
在我的笔记本上进行如下的测试，有以下代码，其中 gettimeofday函数用来获取时间戳。
#include "stdio.h"
#include <sys/time.h>
int main() {
int sum = 0;
struct timeval tv0, tv1;
#if 0
printf("do not use unrooling\n");
gettimeofday(&tv0, NULL);
for (int i = 1; i <= 10000; ++i) {
sum = sum + i;
}
#else
printf("use unrooling\n");
gettimeofday(&tv0, NULL);
for (int i = 1; i <= 10000; i+=4) {
sum = sum + i;
sum = sum + (i + 1);
sum = sum + (i + 2);
sum = sum + (i + 3);
}
#endif
gettimeofday(&tv1, NULL);
printf("time = %ld\n", (tv1.tv_usec) - (tv0.tv_usec));
printf("sum = %d\n", sum);
return 0;
}测试结果如下：
可以看到，使用循环展开后，10000个数的累加耗时为14微秒；不使用循环展开，10000个数的累加耗时为24微秒。
两者相差10us的耗时，大约相差40%的耗时！
这是很夸张的，要知道，在做程序性能优化时，如果能一次优化掉40%的耗时，几乎就算是一个很棒的优化手段了。（感兴趣的同学可以复制上面的代码实际测试一下）
为什么循环展开会有效呢
这和计算机的取指令以及缓存机制有关。
其性能加速的思想是：减少CPU读取指令的失败次数，也就是降低指令的Cache Miss。
可能不太好理解，没关系，先看一个实际例子就懂了。
双11刚刚过去，你肯定买了不少的快递。假设你买了100件快递，并且这些快递已经放在了快递柜中一个个的小格子里了。
现在要去取快递，100件快递至少要开100次的快递柜门，才能把所有的快递取出来。
为什么这里说至少100次呢？因为很有可能因为某些原因一次不能成功开启快递柜的门，这些原因可能包括：
- 走错快递柜
- 输错取件码
- 脑袋发蒙，快递没取出来又给关上了
连着取100个快递，谁能说得准会发生什么事情呢？
但不管怎样，在这个场景下，你需要一件一件地将快递拿出来，但由于上面几个原因，如果运气不好，就会出现好几次打不开快递柜门的情况。
那有没有办法优化一下这个问题呢？
当然有，那就是让快递员把多个快递放在同一个快递格子里。
如上图，比如每4个快递放在一个快递格子里，这样打开一个格子，就一定能取出4个快递。那至少开25次的快递柜门，就能把所有的快递取出来。这很显然，比100次的效率要高不少。
说回循环展开，100个快递就需要做100次循环，每个快递的取出就是循环里的一条加法指令。
如果不做循环展开，那就需要一个快递一个快递的取（相当于从指令内存iCache中一条指令一条指令的取），并且很有可能取完这一条指令后，并不能成功的取到下一条指令，从而发生Cache Miss现象。
但如果我们做了循环展开，相当于把相邻的4条指令绑定了，CPU做一次循环，看到里面一定有四条相邻的指令，就像我们打开快递柜门，里面一定有四个快递一样。
CPU取完第一条指令后，能很快地取到第二条指令，从而很快地取到第三条第四条指令。
在取完4条指令后，才会有可能发生Cache Miss 现象。连着取四个快递之后Miss一次，和每取一个快递，就Miss一次，浪费的时间肯定是不一样的。
循环展开能有效地降低指令的Cache Miss 。这个方法对于程序加速很有效，并且实施起来也很简单，如果你有兴趣，不防在自己的项目中试一试。
但是需要说明的是：现在的编译器可能会对你的代码自动做循环展开优化，因此，如果你想试试效果，建议编译的时候不要打开任何优化选项。
好啦，循环展开就写到这，欢迎持续关注本系列。
欢迎关注@董董灿是个攻城狮 和同名微信公众号
本文作者原创，转载请联系作者，请勿随意转载
