GCC的尾部呼叫优化有多“聪明”?
我刚刚讨论了以下两个C代码的讨论:
for循环:
#include #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 #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返回值)并对其进行优化,但它会走多远?
当递归调用不是最后要执行的操作时,gcc可以用tco优化的限制是什么?
附录:我写了一个完全尾递归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
所以一个(不可否认的简单而不是非常严格)的基准测试表明,它确实看起来确实处于相同的时间顺序。
只需反汇编代码,看看发生了什么。 没有优化,我得到这个:
0x0040150B cmpl $0x0,0x10(%rbp) 0x0040150F jle 0x401523 0x00401511 mov 0x10(%rbp),%eax 0x00401514 sub $0x1,%eax 0x00401517 mov %eax,%ecx 0x00401519 callq 0x401500
但是使用-O1,-O2或-O3我得到这个:
0x00402D09 mov $0x2ffff,%edx
这与尾部优化没有任何关系,而是更激进的优化。 编译器只是简单地内联整个函数并预先计算结果。
这可能是您在所有不同的基准测试案例中得出相同结果的原因。