[閒聊] g++ 8.2.1 把 O(n) code 轉成 O(1)

看板C_and_CPP作者johnjohnlin時間5年前 (2019/02/16 00:50)推噓21(21推 0噓 26→)

留言47則, 13人參與討論串1/2 (看更多)

最近有個熱門的討論話題就是計算費氏數列的複雜度到底是 O(1) 還是 O(n) 剛好我前幾天在看 wiki 嘗試 compiler 的一些東西的時候 https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8 也遇到一些有趣的 O(1) 還是 O(n) 的問題覺得很有趣所以就分享上來我也有把問題丟在 stackoverflow 上面問沒想到上面的反應也蠻熱烈的 https://stackoverflow.com/questions/54686395 讓我不小心賺到了一些 reputation，大概比我回答十個問題還多 --- 不管複雜度是 O(1) 或是 O(n)，也不管 lookup table 到底要不要存在月球上費氏數列遞迴的形式都是這條：F(x) = F(x-1) + F(x-2), F(1) = F(2) = 1 不過今天要討論的是一個更簡單的問題 F(x) = F(x-1)+1, F(0) = 0 學過中學以上歸納法的人類都能知道 F(x) = x 而學過 C++ 的人都可以把這個式子轉換變成程式碼 int Identity(int i) { if (i == 1) return 1; else return Identity(i-1)+1; } 上面的 wiki 說明了這個並不是有效的 tail recursion 形式理論上應該不會變成 for loop 會產生 O(n) memory, O(n) runtime 的程式（PS: 如果是 for loop，應該是 O(1), memory O(n) runtime）為了驗證，我用了 gcc 8.2.1 編譯看看，結果大出意外 % g++ a.cpp -c -O2 && objdump -d a.o Disassembly of section .text: 0000000000000000 <_Z8Identityi>: 0: 89 f8 mov %edi,%eax 2: c3 ret Linux 下 x64 的第一個整數是 %edi，回傳值放在 %eax 等等，所以我以為 O(n) 的問題，真的可以在 O(1) 解出來嗎（誤）難道 compiler 做了一些數學計算，推出 F(x) = x 了嗎該不會在這個大 AI 時代，compiler 也要內建高中生等級的 super AI 了吧該不會我下次升級到 gcc 9 的時候，我的 compiler 就會跑去當 Youtuber 了吧？！ --- Sorry 扯遠了，回歸正題我一開始的想法是 1. gcc 知道了 negative i 會撞到 UB，因此可以隨便回傳任何值（PS: negative i 不會變成 infinite loop 的 UB，而是 overflow） 2. positive i 的情形 gcc 經過了某些數學推導算出 F(x) = x 但是怎麼看都覺得太神奇，感覺不會有人實做這種東西總之經過 stackoverflow 一番討論之後看起來的結論如下首先，當代的 gcc 不只可以化簡基本的 tail recursion 就連上面那個形式都可以（可以去看 stackoverflow 的一些討論）雖然詳細上原理我不太明白，但是應該、大約、好像會變成這樣子 int Identity(int i) { int ans = 0; for (; i != 0; i--, ans++); return ans; } 接著我猜測這個形式對 compiler 來說應該比較好化簡了因為這種 for loop 非常常見，應該有機會做某種化簡得到 F(x) = x 順帶一題，直接寫這個程式的話，gcc 是可以化簡 O(n) -> O(1) 的如果 i != 0 改成 i >= 0 的話，gcc 會變成 return i > 0 ? i : 0; 真的很厲害 --- 另外 stackoverflow 裡面有人直接挖出 gcc code 來解釋但是其實我不是 compiler 專家所以我這篇主要還是單純分享一些我的觀察啦如果這個版有人能做出更淺顯易懂，又更完整的解釋的話就太好了謝謝大家～ -- Time waits for no one. ↑ (。Ａ。)ハァ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.89.176 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1550249453.A.382.html

推