为什么C++模板计算速度如此之快？

Question

我想了解下面的代码。

#include <iostream>
using std::cout;
template<int N> struct Fib {
    enum { v = Fib<N - 1>::v + Fib<N - 2>::v };
};
template<> struct Fib<0> {
    enum { v = 0 };
};
template<> struct Fib<1> {
    enum { v = 1 };
};
int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main() {
    cout << Fib<46>::v << '\n';
//    cout << fib(46) << '\n';
    return 0;
}

它在编译时计算结果，没有任何明显的延迟。这是怎么做到的呢？如果我们调用fib(46)，即使使用最快的PC也需要等待几秒钟。模板使用相同的计算方案，并使其瞬间完成。我还惊讶于使用模板生成的可执行文件大小几乎与不使用模板相同。我使用了GCC。

- vollitwr

---

“without any noticeable delay.” - 你是如何衡量的？ - Joseph D.

时间 g++ fib.cpp -o fib - vollitwr

我对你的测量结果非常怀疑。如果你在运行时需要等待几秒钟才能得到结果，那么你要么没有打开优化，要么做错了其他事情。此外，在进行编译时计算时“没有明显的延迟”是相当不寻常的。 - 463035818_is_not_a_number

模板在编译时进行评估，而不是运行时。基本上将计算移动到编译中，因此编译时间会更长，执行时间会更短。此外，朴素递归方法与模板一起使用效果还可以（每个值仅评估一次），但在运行时效率非常低，因为必须多次重新评估每个值。 - Yksisarvinen

time ./fib 我可以保证我的测量是准确的。 @Yksisarvinen 谢谢，但编译时间几乎没有改变。因此我可以假设GCC使用一些技巧来计算模板。 - vollitwr

这不是很多计算。它生成了45个类，每个类只有一个枚举。对于现代编译器来说，这是一个简单的任务。在运行时（如果编译器没有应用优化 - 我对此一无所知），您必须计算每个斐波那契值2^(n-i)（其中i是该值）。而对于fib(2)，需要进行2^44次计算，这是相当糟糕的前景。 - Yksisarvinen

Answer 1

这是由于模板解决方案中固有的记忆化 (memoization) 机制所致。

编译期间，每个实例，如 Fib<1>，Fib<2> 等，只被编译器执行一次并被记住。

然而当你运行 fib(n) 时，fib(1)，fib(2) 等则被多次计算。解决方法是将其 记忆化，即在映射或数组中记住每个 fib 调用的结果，并在已存在结果的情况下返回它。

- rustyx

---

可以说这里的记忆化是由编译器而不是生成的程序完成的。每个Fib<N>只被实例化一次。 - Swift - Friday Pie

@rustyx，在编译期间进行计算时，先前计算出的值存储在哪里？ - Joseph D.

@codekaizer - 值存储在 Fib 模板的生成实例（枚举 Fib<N>::v）中的内存中。 - rustyx

Answer 2

他们不是快速的，他们已经在那里了。 如果您成功编写了这样一个模板程序，那么在程序开始之前，您使用的值将已经存在。
这也可以通过constexpr实现。
然而，需要在编译时获取所有信息的事实使其适用于非常少量的用例。

我重新设计了您的示例以向您展示(示例链接)。

main:
.LFB0:
  .file 1 "/tmp/compiler-explorer-compiler118417-63-1cf1gj5.e1tp/example.cpp"
  .loc 1 12 0
  .cfi_startproc
  .loc 1 14 0
  mov eax, 1836311903
  ret

eax被填充为数字1836311903，恰好是第46个斐波那契数。

- Petar Velev

---

不回答提问者的问题。提问者写道：“它在编译时计算结果，没有任何明显的延迟。”问题是：“为什么编译需要的时间不会更长？”，而不是“为什么执行需要的时间不会更长？” - gflegar

@GoranFlegar 说实话，问题的表述并不清晰。我也会对此提出疑问，因为在单线程模板和constexpr变量的情况下，编译时间几乎达到了10秒。我猜想模板实例生成和constexpr解析是并行化的。 - Swift - Friday Pie

Answer 3

fib()是一个递归函数，在这种情况下性能较差，因为需要多次迭代函数调用和堆栈创建。

模板值应该在编译时静态计算，因为N在编译时已知。也可以尝试：

constexpr int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

这将使它成为模板解决方案的等效物，如果可能的话，函数值将在编译时计算。使用 -O2 标志 :P

- Swift - Friday Pie

---

我正在使用GCC版本6.3.0，“-O2”对于这种情况没有影响，程序在计算fib(46)时需要几秒钟。 - vollitwr

@vollitwr使用constexpr？我怀疑，尽管我在v.7上测试过了。 - Swift - Friday Pie

谢谢！constexpr改变了很多东西。 - vollitwr

使用模板时，fib(1)在编译时会被“计算”多少次？我知道只有一次。对于constexpr，我会说取决于使用次数。 - Jarod42

clang在使用constexpr函数时存在困难演示，但对于模板结构则无此问题演示。(gcc两者都能很好地处理)。 - Jarod42