C尾呼叫优化

我经常听到有人说C不执行尾呼叫消除。尽管标准没有保证它，但是它在任何体面实施中都不是在实践中执行的吗？假设你只针对成熟，实现良好的编译器，并且不关心针对为不明显平台编写的原始编译器的绝对最大可移植性，那么依靠C中的tail call消除是否合理？C尾呼叫优化

此外，将尾部呼叫优化离开标准的原因是什么？

来源

2010-08-18 dsimcha

相关：http://stackoverflow.com/questions/2250727/regarding-stack-reuse-of-a-function-calling-itself – 2010-08-18 16:28:24

像“C不执行尾呼叫消除”这样的语句没有任何意义。正如你正确地指出自己，这样的事情完全取决于实施。是的，任何体面的实现都可以很容易地将尾递归转化为[相当于]一个循环。当然，C编译器通常不会保证什么优化，哪些优化不会发生在每个特定的代码中。你必须编译它并亲自查看。

来源

2010-08-18 16:27:51 AnT

回答你最后一个问题：标准绝对不应该对优化做任何说明。可能存在实施起来或多或少困难的环境。

来源

2010-08-18 16:28:16 Frank

+11

标准要求while循环运行在常量内存中是否是错误的？（除了while循环中的分配）标准要求尾递归函数在常量内存中运行会是错误的吗？ – Jules 2010-08-18 16:55:12

我认为Scheme需要tail-call优化，但Scheme是一种主要的函数式语言，大量使用递归作为控制结构。 C程序往往递归较少，并且有不断使用的迭代结构。 – 2010-08-18 17:04:25

语言标准定义了语言的行为方式，而不是如何实现编译器。优化不是强制性的，因为它并不总是想要的。编译器提供选项，以便用户可以启用优化，如果他们愿意的话，也可以关闭它们。编译器优化会影响调试代码的能力（将C逐行匹配到程序集中变得更加困难），所以只根据用户的请求执行优化是有意义的。

来源

2010-08-18 16:35:48 bta

只需要满足特定要求的调用模式使用恒定的内存空间就会非常容易。这是语言如何行为的一部分，以及如果您可以在程序中调用数百万次而无需返回（如我编写的一个依赖于编译器TCO的程序那样）的效果。 – 2014-05-30 15:39:40

我认为只有在很多的递归是预期或需要的时候才需要保证尾部呼叫优化;也就是说，鼓励或强化函数式编程风格的语言。（使用这些语言，您可能会发现for或while循环要么强烈地被阻止，要么被认为不雅，要么可能完全不在语言中，所以您会因为所有这些原因而采用递归，可能更多。）

C编程语言（恕我直言）显然是而不是考虑到功能编程的设计。有各种通常用于递归的循环结构：for,do .. while,while。在这样的语言中，在标准中规定tail call优化没有多大意义，因为它不是严格要求保证工作程序。

再次与没有while循环的函数式编程语言进行对比：这意味着您需要需要递归;这又意味着语言必须确保在迭代过程中堆栈溢出不会成为问题;因此官方对这种语言的标准可能会选择开尾通话优化。

P.S：注意，在我的论点为尾调用优化的轻微缺陷。接近尾声时，我提到堆栈溢出。但是谁说函数调用总是需要堆栈？在某些平台上，函数调用可能以完全不同的方式实现，堆栈溢出甚至不会成为问题。这将是另一个反对在标准中规定尾部呼叫优化的论点。（但是不要误解我的意思，我可以看到这种优化的优点，即使没有堆栈！）

来源

2010-08-18 16:46:56 stakx

然而，实现函数调用的一般情况将始终需要保存和恢复某个状态。因此，总会有这样的函数，使得嵌套的函数调用过多以填充可用内存来存储这个状态。传统的数据结构是固定存储器模块中的一个堆栈，但它可以以不同的方式完成。尾部调用消除可以避免对某些函数进行保存和恢复，但调用两次的非平凡函数将需要为第二次调用存储状态。 – jilles 2010-08-18 22:22:26

@jilles：确切地说，无论函数调用如何工作，尾部调用优化都应该有助于保留内存。然而，CPU堆栈的一个特点是它的容量通常相对有限;比例如堆内存。这就是为什么我提到堆栈溢出，但不是更普遍的内存不足的原因;我认为你需要一个几乎难以置信的递归来耗尽例如2 GB的内存。 – stakx 2010-08-19 08:17:09

虽然现代编译器可以在开启优化的情况下进行尾部优化，但是您的调试版本可能会在没有它的情况下运行，这样您就可以获取堆栈跟踪并进入/退出代码以及类似的美妙事物。在这种情况下，尾巴呼叫优化是不希望的。

由于尾调用优化并不总是可取的，因此将其委托给编译器编写者是没有意义的。

来源

2014-05-01 17:34:55

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

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

另外setjmp和longjmp是有问题的，当然，因为这实际上意味着函数可以在实际完成之前多次完成执行。编译时难以或不可能优化！

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

来源

2018-02-17 10:04:27 nondeterministic

C尾呼叫优化

回答

相关问题