寫完《費氏數列 O(LogN) 的解法》後，發現一個奇怪的事: clang++ -O2 編出來的程式，執行效率明顯的比 g++ -O2 好。這裡有完整的程式碼，以下是執行結果:
$ g++ -std=c++11 -O2 fib2.cpp -o fib2O2_gcc
$ clang++ -std=c++11 -O2 fib2.cpp -o fib2O2_clang$ ./fib2O2_gcc 70 10000000
fib (loop) 308061521170129 0.358412
fib by matrix (loop) 308061521170129 0.331294
fib by matrix (log(N) recursion) 308061521170129 0.299235
fib by matrix (log(N) loop) 308061521170129 0.11102$ ./fib2O2_clang 70 10000000
fib (loop) 308061521170129 0.124882
fib by matrix (loop) 308061521170129 0.12926
fib by matrix (log(N) recursion) 308061521170129 0.262108
fib by matrix (log(N) loop) 308061521170129 0.110683
- 上面都是求 fib(70) 的解，然後計算執行 10,000,000 次的秒數。次數太少的話，每次的執行時間會有些變動。
- fib (loop) 是迴圈版的解法。
- fib by matrix (loop) 是用矩陣求解，一樣用迴圈求矩陣的 n 次方。
- fib by matrix (log(N) recursion) 同上，但用 divide-and-conquer 的方式，減少乘的次數。有興趣了解細節，可以參考上篇說明。
- fib by matrix (log(N) loop) 是這篇新加的方法，一樣是 O(LogN) 的解，但沒有用遞迴，理論上會更快。
問題
從上面的數據得知幾件有趣的事:
- n = 70 的情況，
g++ -O2的迴圈版比 O(LogN) 的遞迴版慢; 但clang++ -O2較快。 - fib by matrix (loop) 版和 fib (loop) 執行時間差不多。
- fib by matrix (log(N)) 的迴圈版確實比遞迴版快。
第一點頗詭異的，這表示若真實的使用情境剛好是要算 f(70) 的話，用基本的迴圈版配合 clang++ -O2 編出來的程式，執行結果和精心設計並實作的版差不多快; 但若用 g++ -O2 編，精心設計的版本會顯著快很多。
雖然這和真實使用情境八竿子打不著，還是值得研究一下。
觀察組語
於是我查看 clang++ -O2 編出 fib(int n) 的組語，看看有無線索。產生組語的的指令如下:
$ clang++ -std=c++11 -O2 -g fib2.cpp -o fib2
$ objdump -d -S fib2 > fib2.s( 注意要編譯時要用 -g 帶入 debug symbol，objdump 才能將程式碼對回組語的位置 。關於 debug symbol 的其它有趣應用，可以參考《如何從 C/C++ 函式名稱找出來源檔案和行數？》 )
fib2.s 和 fib(int n) 相關的內容如下:
原以為是很簡單的東西，結果看了好久才看懂大概。
若你和我一樣完全不熟組語的話，這裡有一些需要知道的基本知識:
objdump預設產生 AT&T 的語法，參考《X86 Assembly/GAS Syntax》了解基本語法。- 依 x86 -4 calling convention 的定義，
%edi存函式的第一個參數，也就是 fib(n) 的 n。 - 回傳值存在
%eax。 - lea 的意思: ref0、 ref1、ref2。
組語碼裡有些 magic number，像是:
lea 0x7(%rdi),%r9d的意思是r9 = n — 7，為什麼要 -7？- 38 行為什麼要用
%r9d作 branch？ - 51 ~ 58 行有串重覆的
add %rax,$rcx和add %rcx,%rax，然後在 64 行作n -= 8。
看到最後才有些想法，推測是在作 loop unrolling，減少迴圈的計算次數。
驗證 loop unrolling 的影響
為驗證這個想法，從 man g++ 找到相關的參數 unroll-loops，然後 clang++ 編譯的時候，加上 -f-no-unroll-loops 關閉這項最佳化:
$ clang++ -std=c++11 -O2 -g fib2.cpp -o fib2 -fno-unroll-loops然後一樣用 objdump 產生組語，編出的組語果然精簡許多，程式輪廓和我預期的一樣:
long long fib(int n) {
400fa0: b8 01 00 00 00 mov $0x1,%eax
if (n <= 1)
400fa5: 83 ff 02 cmp $0x2,%edi
400fa8: 7c 26 jl 400fd0 <_Z3fibi+0x30>long long a = 1;
long long b = 1;
long long c;
for (int i = 2; i <= n; i++) {
c = a + b;
400faa: ff cf dec %edi
400fac: b8 01 00 00 00 mov $0x1,%eax
400fb1: b9 01 00 00 00 mov $0x1,%ecx
400fb6: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
400fbd: 00 00 00
400fc0: 48 89 c2 mov %rax,%rdx
400fc3: 48 89 c8 mov %rcx,%rax
400fc6: 48 01 d0 add %rdx,%rax
return 1;long long a = 1;
long long b = 1;
long long c;
for (int i = 2; i <= n; i++) {
400fc9: ff cf dec %edi
400fcb: 48 89 d1 mov %rdx,%rcx
400fce: 75 f0 jne 400fc0 <_Z3fibi+0x20>
c = a + b;
a = b;
b = c;
}
return c;
}
400fd0: c3 retq
400fd1: 66 66 66 66 66 66 2e data16 data16 data16 data16 data16 nopw %cs:0x0(%rax,%rax,1)
400fd8: 0f 1f 84 00 00 00 00
400fdf: 00
另外，關於執行速度:
clang++ -O2 -fno-unroll-loops和g++ -O2一樣慢。g++ -O2 -funroll-loops和clang++ -O2一樣快。
綜合以上，確認是 loop unrolling 造成的差異。
雜談
附帶一提，用 -O0 的時候 ，即使 N = 70 (N 不大)，在我測試的機器上 O(LogN) 遞迴版會比 O(N) 迴圈版快一倍; 但開啟編譯器最佳化後，反而是 O(N) 迴圈版快一倍多。
這個小例子可以說明在調校效能的時候，永遠都要用 release build (有開啟編譯器最佳化參數) 的版本，而不要用 debug build 。畢竟，編譯器的參數對效能有巨大影響，針對實際使用的環境來調校能，才能確保調整真的有效。
還有也可以看出編譯器最佳化後，為什麼有時 debugger 單步執行會亂跳: 最佳化的過程編譯器可能將原本的程式轉換成不同的寫法，debugger 要對回原始碼，自然就對不準了。
