Reload Original PagePrint PageEmail Page

编译之尾调用优化(tail call elimination)_李小红_新浪博客

许多问题适合于用递归的算法来描述与解决,而从理论上讲,都可以换成迭代的方法。

下面是阶乘的递归描述方法(C语言)

unsigned long fact(int n)
{
   if (n == 1) return 1;

    return n * fact(n-1);
}

再换成迭代的版本(同样是C语言):

unsigned long fact(unsigned long cur, int n)
{
   if (n == 1) return cur;

    return fact(cur*n, n-1);
}

假设n为3,计算3的阶重,迭代的调用及返回序列如下图:

fact(1, 3)                     1
fact(3, 2)                   2
   fact(6,1)                  3
   return 6                   3
return 6                     2
return 6                       1

从上面的序列可以看出,第3次调用fact(6,1),它直接返回6,返回第二次和第1次调用的后,也是直接返回6。也就是说,第3次调用可以直接返回给main函数。

这其实是尾递归,是尾调用的一种特殊形式。对应语言在实现时,如果能识别这种尾调用并优化成jmp(跳转指令),而不是函数调用的方式,将提升运行性能和降低对内存的使用(包括stack和heap)。

GCC加上-O2或O3的优化参数就可以识别尾调用。下面测试一下。

下加优化参数:
[xiaohong@localhost c]$ gcc -o fact fact.c
[xiaohong@localhost c]$ ./fact 800000
Segmentation fault

报段错误,很明显调用自身的次数太多,导致堆栈不够了。

再试着加上优化参数:
[xiaohong@localhost c]$ gcc -O2 -o fact fact.c
[xiaohong@localhost c]$ ./fact 800000
ret: 0l

这样已经识别并对尾调用进行了优化,所以不会再出现堆栈不够的情况了。

那么在内部实际上是如何进行尾调用的优化的呢?

正常情况下函数调用序列如下:
1、按一定顺序(从左之右,或从右之左)所参数压入堆栈中
2、把函数执行完后的返回地址压入堆栈,控制转到被调用函数(比如运行call指令)
3、被调用者把返回值存入到寄存器或堆栈中(一般是寄存器)
4、被调用者根椐堆栈中保存的返回地址,返回控制给调用者(可选清除参数)
5、调用者清除参数(可选,如果4步中被调者清除参数)

如果换成尾调用优化成jmp方式:
f -> g -> h  返回时,直接回到f

这时候,f就不知道堆栈中还有多个参数了,因而它来清除堆栈参数就不合适了,这种情况下,由被调用者来清除堆栈中的参数(ret + ::...


免责声明:
当前网页内容, 由 大妈 ZoomQuiet 使用工具: ScrapBook :: Firefox Extension 人工从互联网中收集并分享;
内容版权归原作者所有;
本人对内容的有效性/合法性不承担任何强制性责任.
若有不妥, 欢迎评注提醒:

或是邮件反馈可也:
askdama[AT]googlegroups.com


点击注册~> 获得 100$ 体验券: DigitalOcean Referral Badge

订阅 substack 体验古早写作:


关注公众号, 持续获得相关各种嗯哼:
zoomquiet


自怼圈/年度番新

DU22.4
关于 ~ DebugUself with DAMA ;-)
粤ICP备18025058号-1
公安备案号: 44049002000656 ...::