constexpr问题：为什么使用g++编译时这两个不同的程序运行时间差异如此大？

Question

我正在使用 gcc 4.6.1 编译器，并且在调用一个 constexpr 函数时遇到了一些有趣的行为。这个程序可以顺利运行，直接输出了 12200160415121876738。

#include <iostream>

extern const unsigned long joe;

constexpr unsigned long fib(unsigned long int x)
{
   return (x <= 1) ? 1 : (fib(x - 1) + fib(x - 2));
}

const unsigned long joe = fib(92);

int main()
{
   ::std::cout << "Here I am!\n";
   ::std::cout << joe << '\n';
   return 0;
}

这个程序运行起来需要很长时间，我从来没有耐心等待它打印出一个值：

#include <iostream>

constexpr unsigned long fib(unsigned long int x)
{
   return (x <= 1) ? 1 : (fib(x - 1) + fib(x - 2));
}

int main()
{
   ::std::cout << "Here I am!\n";
   ::std::cout << fib(92) << '\n';
   return 0;
}

为什么会有这样巨大的差异？我在第二个程序中做错了什么吗？

编辑：我正在64位平台上使用g++ -std=c++0x -O3进行编译。

- Omnifarious

---

另外，为什么Intel icc不支持“constexpr”呢？;-) - Martin Kristiansen

Answer 1

joe是一个整数常量表达式；它必须可用于数组边界。因此，合理的编译器会在编译时对其进行评估。

在您的第二个程序中，即使编译器可以在编译时计算它，也没有必要这样做。

- MSalters

---

也许第一个程序编译需要更长时间？ :) - Torp

如果启用优化，看编译器是否会在编译时计算它会很有趣。 - Kerrek SB

@Torp：如果编译器在编译时计算函数并进行记忆化处理，则可能不会注意到这一点。这是我能想到的关于为什么运行第二个程序比Omnifarious愿意等待更长时间，但编译第一个程序可能要快得多的所有原因。 - Steve Jessop

@Torp - 编译第一个程序所需的时间与编译第二个程序所需的时间没有明显的区别。我相信 Steve Jessop 的猜测很可能是正确的。 - Omnifarious

那么我想这意味着，即使 constexpr 有所帮助，但当你想要确保某些东西 将 在编译时计算时，你仍需要强制它。 - Matthieu M.

Answer 2

我的最佳猜测是，第一个程序在编译时计算了fib(92)，有很多表格等供编译器跟踪已经计算出的值...使运行程序几乎是轻而易举的。而第二个版本实际上是在运行时计算的，没有经过已计算出的常量表达式查找，这意味着计算fib(92)需要进行类似于2**92递归调用的操作。换句话说，编译器并没有优化fib（92）是一个常量表达式这一事实。

- Martin Kristiansen

---

实际上我认为它会产生 fib(92) 个递归调用，所以不像 2**92 那样多，但仍然太长而无法在任何情况下使用。 - visitor

@visitor - 查看汇编输出（对于第二个程序来说，代码量惊人地大），看起来实际上会少得多，因为fib(1)到fib(6)的情况都被特殊处理了。 - Omnifarious

@访客：你差点让我以为我错了 :-) 如果您查看执行的递归树，您将看到有fib(92)个叶子节点，这意味着如果树平衡，则必须在fib(92)个节点的顺序中有某些内容，它不是平衡的，但是考虑到一个因素，近似是正确的，因此不是2 ** 92，但也不是fib（92）。 :-) - Martin Kristiansen

@Martin：微笑 他/她错过了调用树的所有内部节点。 :-) - Omnifarious

Answer 3

我也想看看gcc如何优化这个新的constexpr关键字的代码，实际上这是因为你将fib(92)作为ofstream::operator<<的参数调用。

::std::cout << fib(92) << '\n';

如果您试图将其作为另一个函数的参数之外的调用，那么它不会在编译时进行评估（就像您在中所做的那样）。

const unsigned long joe = fib(92);

它在编译时进行评估，如果您想了解更多信息，请参阅我的博客文章。我不知道是否应该向gcc开发人员提及此事。

- b3nj1

---

我确实提到了它，这是一个有趣且棘手的优化问题。对于这些情况，有两条非常不同的代码路径，因为其中一条必须在编译时进行评估，而另一条则不需要。 - Omnifarious

Answer 4

编译器有一定的余地来决定是否在编译时进行评估，如果认为某些东西“过于复杂”，则可以选择不进行评估。这是在不一定需要强制进行评估以生成确实可运行的正确程序的情况下（正如@MSalters所指出的那样）。

我曾经认为影响编译时惰性的决策是递归深度限制（规范中建议为512），但你可以使用命令行标志 -fconstexpr-depth 将其提高到更高。但实际上，这将控制它在任何情况下放弃...即使必须在编译时进行常量计算才能运行程序。 因此对您的情况没有影响。

看起来如果您想要代码中的一个保证，它会执行优化，那么您已经找到了一种技术。 但是，如果 constexpr-depth 无法帮助您，则我不确定是否还有任何相关的编译器标志...

- HostileFork says dont trust SE

---

在这种情况下，深度为91就足够了。而且编译器编译第一个程序并不需要很长时间。无论如何，与第二个程序相比，编译时间几乎没有明显的延迟。-fconstexpr-depth 用于配置编译器放弃之前的最大深度，而不是在确定是否要优化调用的存在时使用的深度。 - Omnifarious

啊，我没有注意到。不过在这个话题里提一下 constexpr-depth 可能还是有帮助的...更正过来了。 - HostileFork says dont trust SE

你的回答是第二好的，因为虽然最佳答案非常简洁明了，但它缺少细节和建议。 - Omnifarious

谢谢！对于我大多数的回答，我都会尽力做到这一点。解决问题并不仅仅是在特定情况下以精确的细节水平帮助提问者克服障碍。更重要的是考虑到答案的普遍适用性，因为未来可能有其他人通过Google搜索找到它，他们的知识和问题可能与提问者不同。毕竟，只有一个最初的提问者，而未来的页面浏览者数量却无从得知！ - HostileFork says dont trust SE