'聰明'是GCC的尾巴呼叫優化？

我只是在那裏正在討論的C代碼以下兩個peices討論：'聰明'是GCC的尾巴呼叫優化？

for循環：

#include <stdio.h> 
#define n (196607) 

int main() { 
    long loop; 
    int count=0; 
    for (loop=0;loop<n;loop++) { 
    count++; 
    } 
    printf("Result = %d\n",count); 

    return 0; 
}

遞歸：

#include <stdio.h> 
#define n (196607) 

long recursive(long loop) { 
    return (loop>0) ? recursive(loop-1)+1: 0; 
} 

int main() { 
    long result; 
    result = recursive(n); 
    printf("Result = %d\n",result); 
    return 0; 
}

在看到這個代碼，我看到了recursive(loop-1)+1並認爲「啊，這不是尾遞歸調用」，因爲它有工作在調用recursive後做的是完整的;它需要增加返回值。

果然，沒有優化，遞歸碼觸發棧溢出，如你所願。

與-O2標誌然而，沒有遇到堆棧溢出，我認爲堆棧被重用，而不是越來越多地推入堆棧 - 這是tco。

GCC可以明顯發現這個簡單的例子（+1返回值），並優化它，但多遠它去？

什麼都可以用TCO優化什麼GCC的限制，當遞歸調用是不被執行的最後一個操作？

附錄：我寫了一個完全尾遞歸的return function();版本的代碼。包裝紙上面與9999999個迭代循環，我想出了以下時序：

$ for f in *.exe; do time ./$f > results; done 
+ for f in '*.exe' 
+ ./forLoop.c.exe 

real 0m3.650s 
user 0m3.588s 
sys  0m0.061s 
+ for f in '*.exe' 
+ ./recursive.c.exe 

real 0m3.682s 
user 0m3.588s 
sys  0m0.093s 
+ for f in '*.exe' 
+ ./tail_recursive.c.exe 

real 0m3.697s 
user 0m3.588s 
sys  0m0.077s

所以（當然簡單，並沒有很嚴格）基準測試表明，它確實似乎是在相同的順序所用的時間。

來源

2017-02-10 Baldrickk

編譯器可能只是內聯函數而不是使用尾遞歸。使用'-S'標誌編譯程序並查看彙編代碼的外觀。 –

我同意@squeamishossifrage。不要啓用優化，然後假設編譯器做了什麼。你可能會感到驚訝，這是毫無意義的。 – unwind

只需拆卸代碼，看看發生了什麼。如果沒有優化，我得到這個：

0x0040150B cmpl $0x0,0x10(%rbp) 
0x0040150F jle 0x401523 <recursive+35> 
0x00401511 mov 0x10(%rbp),%eax 
0x00401514 sub $0x1,%eax 
0x00401517 mov %eax,%ecx 
0x00401519 callq 0x401500 <recursive>

但隨着-O1，-O2或-O3我得到這個：

0x00402D09 mov $0x2ffff,%edx

這不會有任何與尾部的優化，但更激進的優化。編譯器簡單地將整個函數內聯並預先計算出結果。

爲什麼你最終得到相同的結果在基準的所有不同的情況下，這是可能的。

來源

2017-02-10 14:03:45 Lundin

'聰明'是GCC的尾巴呼叫優化？

回答

相關問題