※ 引述《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 有哪些最佳化的細項可用的話，可以從官方文件起手。
編譯器因為相對其他領域已算成熟，研究能再取得過相較少，
似乎是目前比較不被重視的一塊。
據我所知國內的資工大學部編譯器課程能深入探討編譯最佳化的並不多，
依教科書順序進行的話，大致教完編譯器前端的原理也過一個學期了。
如果對這方面很有興趣，可以自行閱讀龍書一類的書籍，
雖然這類書都蠻古老了，但內容大多還是現在編譯器中的重要技術，
還蠻推薦拿來當休閒讀物的。