4

我今天发现了一个关于 gcc 的有趣测验http://ridiculousfish.com/blog/posts/will-it-optimize.html

这个代码怎么来的

int factorial(int x) {
   if (x > 1) return x * factorial(x-1);
   else return 1;
}

可以被编译器翻译成

int factorial(int x) {
   int result = 1;
   while (x > 1) result *= x--;
   return result;
}

这是真的？gcc是怎么做到的？

4

2 回答 2

5

您已经知道 gcc 可以将尾递归函数优化为循环。gcc 可以做的另一件事（并且在您的链接中提到）是尝试将非尾递归函数优化为尾递归函数。

您的阶乘函数在这里：

int factorial(int x) {
   if (x > 1) return x * factorial(x-1);
   else return 1;
}

现在我将尝试进行尽可能少的更改并将其重写为尾递归。首先，我将翻转 if 测试：

int factorial(int x) {
   if (!(x > 1)) return 1;
   else return x * factorial(x-1);
}

接下来，我将删除不需要的else：

int factorial(int x) {
   if (!(x > 1)) return 1;
   return x * factorial(x-1);
}

这几乎是尾递归的，但它正在返回x * factorial()，而不仅仅是factorial(). 使这个尾递归的典型方法是包含第二个参数，它是一个累加器。

int factorial(int x, int accumulator = 1) {
   if (!(x > 1)) return accumulator;
   return factorial(x - 1, x * accumulator);
}

现在这是一个尾递归函数，可以优化成一个循环。

于 2013-04-07T14:46:52.780 回答
4

通过将乘法放在递归函数调用之前，编译器可以将该代码转换为可优化的尾部调用：

int factorial(int x) {
    return factorial_tail_call(x, 1);
}

int factorial_tail_call(int x, int result) {
    if (x > 1) return factorial_tail_call(x-1, result*x);
    return result;
}

通过递归调用result*xbefore的评估factorial_tail_call，编译器可以确定x并且result不再需要。因此，它可以将它们从堆栈中弹出。这证明了堆栈不需要增长。

你能看到转换后的代码之间有什么相似之处吗？在1同一个地方，条件x > 1在同一个地方，return result;在同一个地方。提供编译器实现尾调用优化，这只是表达相同算法的不同方式。通过将乘法表达式移动到一个参数中并将您的帖子中的代码放在注释中，您可能会看到一些功能相似之处，以及编译器如何设法进行其余的转换：

int factorial(int x) {
    return factorial_tail_call(x, 1);                     // int result = 1;
}

int factorial_tail_call(int x, int result) {
    if (x > 1) return factorial_tail_call(x-1, result*x); // while (x > 1) result *= x--;
    return result;                                        // return result;
}

n1570.pdf 的§5.1.2.3p4

在抽象机中，所有表达式都按照语义的规定进行评估。如果一个实际的实现可以推断出它的值没有被使用并且没有产生所需的副作用（包括调用函数或访问易失性对象引起的任何副作用），则它不需要评估表达式的一部分。

编译器是聪明的东西，由比我们大多数人优秀得多的程序员编写。如果编译器可以确定两段代码是等价的，那么它可以选择它希望的两者中的任何一个（有一些限制，在下面的引用中描述）。例如，它可以用一个printf表达式替换一个计算和打印前一千个素数的循环。

n1570.pdf 的§5.1.2.3p6

对一致性实现的最低要求是：

— 对 volatile 对象的访问严格按照抽象机的规则进行评估。

— 在程序终止时，写入文件的所有数据应与根据抽象语义执行程序所产生的结果相同。

— 交互设备的输入和输出动态应按照 7.21.3 的规定进行。这些要求的目的是尽快出现无缓冲或行缓冲的输出，以确保在程序等待输入之前实际出现提示消息。

这是程序的可观察行为。

这就是为什么微优化是徒劳的原因之一。

如果另一个线程修改了 strlen 正在处理的字符串，那就是竞争条件。竞争条件是未定义的行为。您需要使用互斥锁保护字符串以确保不会发生这种情况，或者学习更好的多线程范例。你在看哪本书？

n1570.pdf 的§5.1.2.4p25

如果程序的执行包含不同线程中的两个冲突操作，则该程序的执行包含数据竞争，其中至少一个不是原子的，并且两者都不会在另一个之前发生。任何此类数据竞争都会导致未定义的行为。

于 2013-04-07T14:31:26.697 回答