如果递归深度很深，TMP 真的更快吗？

Question

我使用 TMP 制作了一个简单的 sqrt 结构。它是这样的：

template <int N, int i>
struct sqrt {
    static const int val = (i*i <= N && (i + 1)*(i + 1) > N) ? i : sqrt<N, i - 1 >::val;
};

但是因为它没有退出条件而导致错误，所以我添加了这个：

template <int N>
struct sqrtM<N, 0> {
    static const int val = 0;
};

据我了解，如果我们使用 TMP，编译器会进入递归循环，直到它们满足退出条件（根据 sqrt，通常是 i = 0 或 i = 1 时）

但是如果我们创建一个递归sqrt函数，编译器不必跳到满足i = 0，因为在某些时候，递归函数在条件[=16]的确切位置结束=]满足。

所以假设我们将非常大的值放入我们的 sqrt，那么与 sqrt 函数的递归版本相比，我们的 TMP 应该对 sqrt<N, sqrt<N-1>::val> 进行额外的计算，看起来浪费我。

我理解错了吗？或者即使在这种情况下，TMP 真的值得吗？

Answer 1

问题是，在 TMP 中，默认情况下您不能深入。深度是有限的，但可以更改限制（请参阅 this）。另一件事是你用递归编写你的 TMP 代码，但它可以编译成非递归代码，因此它没有额外的成本来保存状态和进行更深入的函数调用。所以它是编译时间、可执行文件大小和运行时性能之间的权衡。如果你的 N 在编译时不知道，那么你就不能使用 TMP。

Answer 2

评估和实例化之间存在差异。

在

template <int N, int i>
struct sqrt {
    static const int val = (i*i <= N && (i + 1)*(i + 1) > N) ? i : sqrt<N, i - 1 >::val;
};

它应该实例化 sqrt<N, i - 1 > 以检索关联的 val，即使最后不会采用该值。

您可以编写不同的代码来延迟 sqrt<N, i - 1 >

的实例化

template <int N> struct val_identity { static const int val = N; };

template <int N, int i>
struct sqrt {
    static const int val =
        std::conditional_t<i * i <= N && N < (i + 1) * (i + 1),
                           val_identity<i>,
                           sqrt<N, i - 1 >
                          >::val;
};

Demo

如果递归深度很深，TMP 真的更快吗？

Is TMP really faster if the recusion depth is very deep?

c++

template-meta-programming