※ 引述《c3035281 (:::::>_<:::::)》之铭言：
: 如题
: 今天小妹带来比较知识性的问题
: 我最近在写作业啦 用g++编译
: 有个参数拉吼 叫做 -O3 (也有O2 O1 等等)
: 不知道是干了什么事
: 跑起来整个快很多 从3分钟变成3秒钟
: 究竟4发生了什么事ㄋ
: 有没有修过compiler的人来解释一下
: 有没有八卦
刚接触编译器的最佳化时真的会让人很震撼，
大学的时候还有很多人在用 Dev C++ 之类的开发工具，也没有去调整编译参数
当时同学之间还喜欢比较程式速度，
后来才知道都是没有最佳化，甚至还带着除错资讯的菜鸡互啄XD
第一次在 CLI 下了 gcc -O2 瞬间把原本跑 100 秒的程式变 1 秒时差点升天了
之后开始对编译器的技术有些兴趣，也就稍微学了一些相关的东西。
在这里分享一些常见易懂的编译最佳化功能。
GCC/G++ 有非常多最佳化的参数可以使用，
'-O2', '-O3' 这些则是帮你一次性的开启大量最佳化功能。
详细到底会开启哪些最佳化，可以在 GCC 的官方文件中查看: https://is.gd/gcc_oo
-O (-O1): 开启一些基本的最佳化，对编译速度的影响较小。
-O2: 包含 -O 所有的最佳化选项再加上更多选项。
-O3: 则包含 -O2 的选项，又再加上更多。
O1 -> O2 -> O3 会编译的比前一个选项比较久，产生的程式效能通常也更高。
我自己已经一段时间没有用 GCC 了，根据以前的经验 -O3 和 -O2 的效能差距不多。
有时候 -O3 效果未必 -O2 好。
原 PO 所问“从3分钟变成3秒钟”的问题属于 O2 & O3 都可能会发生的事情，
就不特别区分说明了。
其实要了解编译器的最佳化结果，有一个很简单的方式可以实验验证，大家无聊的时候都
可以玩玩
只要在编译时加上参数 -S 就会产生组合语言程式，我们可以借由观察组合语言来知道
做了什么最佳化。
我们用简单的程式码来示范一些基本的最佳化:
char foo(char x, char y) {
return x + y;
}
int main() {
return foo(1, 2);
}
我们分别使用 g++ -S 和 g++ -S -O2 来进行编译
(我另外加了一些参数来去除 cfi 让程式看起来比较单纯)
编译出的的完整结果 可以看 gist 连结:
未做最佳化 : https://is.gd/eWQBni
最佳化(O2): https://is.gd/NLJ5q2
(gcc version 8.2.0)
先来看未最佳化的 main:
main:
.LFB1:
pushq %rbp
.LCFI3:
movq %rsp, %rbp
.LCFI4:
movl $2, %esi
movl $1, %edi
call _Z3foocc
movsbl %al, %eax
popq %rbp
.LCFI5:
ret
需要把 RBP 暂存器做 push & pop，需要为 call 做准备，需要呼叫 foo
最佳化之后的 main:
main:
.LFB1:
movl $3, %eax
ret
直接把 EAX 内容设成 3 后 return... 咦，就没了？
原来编译器会把简短的函式 inline，
例如上面的 C++ 程式码中的 foo 在 main 中可以直接被省略
int main() { return foo(1, 2); }
就变成
int main() { retrn 1 + 2: }
这样就节省了一次呼叫的成本。
包含暂存器的 push/pop、配置内存、运算移动 pointer 暂存器等等。
而在这个范例中，编译器又可以做 constant folding，
更进一步地判断像 '1 + 2' 这种运算由于不受和其他外部因素影响，
可以在编译时就确定其结果，就干脆帮你直接把它改成算好的结果 (常数 3) 了。
编译器也可以删除一些永远不会进入的 branch， 例如编译下面这个简单的程式
if (n == 1) {
return 0;
} else {
return n == 1 ? n * 5566 : 1;
}
会发现原本有“imull $5566, %eax, %eax”的指令，在 -O2 时完全消失。
因为在 else block 中不会再有 n == 1 的情况，所以“n * 5566”就直接被省略。
另外像这样的函式:
int main() {
for (int i = 0; i < 1000; ++i);
return 0;
}
进行编译之后会发现只剩下:
xorl %eax, %eax
ret
也就是直接不管那个不会影响执行结果的循环，直接 return 0
再提一个和 function 最佳化有关的例子。
大学相关科系应该都学过，递回和循环的写法可以互相置换达到相同的运算结果。
但使用递回的写法会产生 function call 的开销，
也可能会遇到 stack overflow 的问题。
后来我接触了 LISP 才知道许多 LISP 家族的语言是没有循环语法的。
但他们可以借由对 tail recursion 的最佳化，来避免前述的问题。
以求阶乘的函式为例:
int factorial(int x) {
if (x == 1) {
return 1;
} else {
return x * factorial(x - 1);
}
}
许多 functional programming 相关的书籍都会提到，
上面的函式可以被改写成 tail call 的形式:
int factorial(int x) {
return fac_iter(x, 1, 1);
}
int fac_iter(int x, int i, int prod) {
if (i > x) {
return prod;
} else {
return fac_iter(x, i + 1, prod * i);
}
}
这种形式的函式，可以被编译器最佳化成循环的形式，
以避免递回对效能和内存造成影响。
如果实际拿上面的两个写法用 GCC 去编译，
会发现产生出来的程式都帮你省略了递回呼叫变成如下形式:
_Z9factoriali:
.LFB0:
.cfi_startproc
movl $1, %eax
cmpl $1, %edi
je .L1
.p2align 4,,10
.p2align 3
.L2:
imull %edi, %eax
subl $1, %edi
cmpl $1, %edi
jne .L2
.L1:
ret
.cfi_endproc
这个选项在 GCC 为 optimize-sibling-calls，
包含但不仅限于对 tail recursion 的最佳化。
以上是一些简单的编译器最佳化内容，
除了这些比较直觉易懂的程式逻辑与步骤简化以外，
还有许多更复杂的，或是针对各个不同平台(例如 x86, amd64, arm)的最佳化，
例如在可以达到相同执行结果的指令中，选择速度较快的指令、
针对暂存器大小和提供的指令，把变量和函式做内存对齐、
把原本 if(a)-else 的 branch 改成 if(a) - if(!a)
这种可能做 predication 的形式...，等等
除了执行速度以外，
也有以“节省内存”用量、“程式大小”或是“省电”为目标的最佳化，
族繁不及备载。
如果只是一般使用的话其实不用知道太多，直接下 -O2 基本上就够用了。
想知道 GCC or CLANG 有哪些最佳化的细项可用的话，可以从官方文件起手。
编译器因为相对其他领域已算成熟，研究能再取得过相较少，
似乎是目前比较不被重视的一块。
据我所知国内的资工大学部编译器课程能深入探讨编译最佳化的并不多，
依教科书顺序进行的话，大致教完编译器前端的原理也过一个学期了。
如果对这方面很有兴趣，可以自行阅读龙书一类的书籍，
虽然这类书都蛮古老了，但内容大多还是现在编译器中的重要技术，
还蛮推荐拿来当休闲读物的。