优化学习笔记(1):Loop unrolling
迫于生计，最近要学习halide
先去学习/复习一下常见的编译优化技巧。
loop unrolling，也就是循环展开，顾名思义，就是把循环展开来写。
1normal loop:
2int x;
3 for (x = 0; x < 100; x++)
4 {
5 delete(x);
6 }
1after loop unrolling:
2int x;
3 for (x = 0; x < 100; x += 5 )
4 {
5 delete(x);
6 delete(x + 1);
7 delete(x + 2);
8 delete(x + 3);
9 delete(x + 4);
10 }
循环展开是一种优化，可以手动实现也可以编译器自动实现。
为什么要将循环展开？
* 循环每次都需要判断终止条件，展开后可以消除这部分开销。
* 减少[分支预测](https://en.wikipedia.org/wiki/Branch_predictor)开销。循环里的分支是指“跳出循环”还是“进行下一次迭代”
* [vectorization](https://en.wikipedia.org/wiki/Automatic_vectorization)
1for (int y = 0; y < 4; y++) {
2 for (int x_outer = 0; x_outer < 2; x_outer++) {
3 // The loop over x_inner has gone away, and has been
4 // replaced by a vectorized version of the
5 // expression. On x86 processors, Halide generates SSE
6 // for all of this.
7 int x_vec[] = {x_outer * 4 + 0,
8 x_outer * 4 + 1,
9 x_outer * 4 + 2,
10 x_outer * 4 + 3};
11 int val[] = {x_vec[0] + y,
12 x_vec[1] + y,
13 x_vec[2] + y,
14 x_vec[3] + y};
15 printf("Evaluating at <%d, %d, %d, %d>, <%d, %d, %d, %d>:"
16 " <%d, %d, %d, %d>\n",
17 x_vec[0], x_vec[1], x_vec[2], x_vec[3],
18 y, y, y, y,
19 val[0], val[1], val[2], val[3]);
20 }
21 }zhichi
可以看到最里面一层循环被展开以实现向量化.向量化是一种优化计算的手段。该优化的实现基于SIMD 和Advanced_Vector_Extensions(AVX)指令集架构的支持。 * 消除和loop counter(i)有关的除法计算。
1 for (int fused = 0; fused < 4*4; fused++) {
2 int y = fused / 4;
3 int x = fused % 4;
4 printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);
5 }
* 消除循环内部的分支。比如loop counter奇数和偶数时会进入不同的分支，那么将循环展开后，就消除了该分支。
有什么缺点？
* 代码体积增加了。这对于嵌入式设备等往往是不可接受的。
* 代码可读性变差了。
* 单一指令可能会使用更多的寄存器，导致性能下降。
* 如果循环内部包含函数调用，那么和函数的内联(inline)优化会有冲突。原因是，循环展开＋函数展开...代码的体积会爆炸。
参考资料
* [Optimizing subroutines in assembly language An optimization guide for x86 platforms(chapter 12.12)](https://www.agner.org/optimize/optimizing_assembly.pdf)
* [Loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling)