C尾调用优化

问题描述 投票:30回答:8

我经常听到人们说C不执行尾部呼叫消除。虽然标准不能保证,但是无论如何,它是否在实践中通过任何体面的实现来执行?假设你只针对成熟的,实现良好的编译器而不关心为模糊平台编写的原始编译器的绝对最大可移植性,那么在C中依赖尾调用是否合理呢?

此外,将尾部呼叫优化留在标准之外的理由是什么?

c standards tail-recursion tail-call-optimization
8个回答
27
投票

像“C不执行尾部调用消除”这样的语句没有任何意义。正如你自己正确地指出的那样,这样的事情完全取决于实现。是的,任何体面的实现都可以轻松地将尾递归转换为[相当于]一个循环。当然,C编译器通常不会对优化程序以及每个特定代码段中不会发生的优化提供任何保证。你必须编译它并亲自看看。


6
投票

虽然现代编译器可以在启用优化时进行尾部调用优化,但是调试版本可能会在没有它的情况下运行,因此您可以获得堆栈跟踪和进入/退出代码以及类似的奇妙事情。在这种情况下,不希望尾调用优化。

由于尾调用优化并不总是令人满意,因此将其强制命令编译器编写器是没有意义的。


5
投票

我认为只有在预期或需要大量递归的情况下才需要保证尾调用优化;也就是说,在鼓励或强制执行函数式编程风格的语言中。 (使用这些类型的语言,你可能会发现forwhile循环要么强烈劝阻,被认为是不优雅的,或者甚至可能完全不在语言中,所以你会因为所有这些原因而诉诸递归,而且可能更多。)

C编程语言(恕我直言)显然没有考虑到函数式编程。有各种各样的循环结构通常用于支持递归:fordo .. whilewhile。在这种语言中,在标准中规定尾部呼叫优化没有多大意义,因为并不是严格要求保证工作程序。

将此与具有while循环的函数式编程语言进行对比:这意味着您将需要递归;这反过来意味着语言必须确保,经过多次迭代,堆栈溢出不会成为问题;因此,这种语言的官方标准可能会选择规定尾部呼叫优化。


P.S。:注意我的尾部调用优化论点中的一个小缺陷。接近尾声,我提到了堆栈溢出。但谁说函数调用总是需要堆栈?在某些平台上,函数调用可能以完全不同的方式实现,堆栈溢出甚至不会成为问题。这将是另一个反对在标准中规定尾调用优化的论据。 (但不要误解我的意思,即使没有堆叠,我也可以看到这种优化的优点!)


3
投票

为了回答你的上一个问题:标准绝对不应该做任何关于优化的陈述。可能存在或多或少难以实施的环境。


1
投票

语言标准定义了语言的行为方式,而不是如何实现编译器。优化不是强制性的,因为并不总是需要。编译器提供选项,以便用户可以根据需要启用优化,并且同样可以将其关闭。编译器优化会影响调试代码的能力(以逐行方式将C与汇编匹配变得更加困难),因此仅根据用户的请求执行优化是有意义的。


1
投票

在某些情况下,尾调用优化可能会破坏ABI,或者至少很难以语义保留的方式实现。例如,可以考虑共享库中与位置无关的代码:某些平台允许程序动态链接到库,以便在各种不同的应用程序都依赖于相同的功能时保存主内存。在这种情况下,库被加载一次并映射到程序的每个虚拟内存中,就好像它是系统上的唯一应用程序一样。在UNIX以及其他一些系统上,这是通过对库使用位置无关代码来实现的,因此寻址是相对于偏移而不是绝对的固定地址空间。但是,在许多平台上,位置无关代码不能进行尾调用优化。所涉及的问题是导航程序的偏移量必须保存在寄存器中;在Intel 32位上,使用%ebx,这是被调用者保存的寄存器;其他平台遵循这一概念。与使用普通调用的函数不同,那些部署尾调用的函数必须在分支到子例程之前恢复被调用者保存的寄存器,而不是在它们自行返回时。通常,这没有问题,因为此时,最顶层的调用函数不关心存储在%ebx中的值,但是位置无关代码依赖于每个跳转,调用或分支命令的该值。

其他问题可能是等待面向对象语言(C ++)中的清理,这意味着函数中的最后一次调用实际上并不是最后一次调用 - 清理工作。因此,在这种情况下,编译器通常不会进行优化。

当然,setjmplongjmp也存在问题,因为这实际上意味着函数可以在实际完成之前多次完成执行。在编译时很难或不可能优化!

人们可以想到的技术原因可能更多。这些只是一些考虑因素。


0
投票

对于那些喜欢通过构造证明的人来说,这里是Godbolt做一个漂亮的尾部调用优化和内联:https://godbolt.org/z/DMleUN

但是,如果您将优化调整为-O3(或者如果您等待几年或使用不同的编译器,则毫无疑问),优化将完全消除循环/递归。

下面是一个示例,即使使用-O2:https://godbolt.org/z/CNzWex也可以优化为单个指令


0
投票

编译器通常会在调用另一个函数后识别函数不需要执行任何操作的情况,并用跳转替换该调用。许多可以安全地进行安全检查的案例很容易识别,而且这类案件有资格成为“安全低悬的果实”。然而,即使在可以执行此类优化的编译器上,它应该或将要执行时也可能并不总是显而易见的。各种因素可能使尾部呼叫的成本大于正常呼叫的成本,并且这些因素可能并不总是可预测的。例如,如果函数以return foo(1,2,3,a,b,c,4,5,6);结尾,将a,b和c复制到寄存器中,清理堆栈然后准备传递参数可能是切实可行的,但可能没有足够的寄存器来处理foo(a,b,c,d,e,f,g,h,i);

如果一种语言有一个特殊的“尾调用”语法,要求给出的编译器尽可能进行尾调用,否则拒绝编译,代码可以安全地假设这些函数可以任意嵌套。然而,当使用普通的调用语法时,没有一般的方法来知道编译器是否能够比“普通”调制器更便宜地执行尾调用。

© www.soinside.com 2019 - 2024. All rights reserved.