我很好奇就编译时评估而言,我可以将 gcc 推到多远,所以我让它计算Ackermann函数,特别是输入值为 4 和 1(任何高于此值都是不切实际的):
consteval unsigned int A(unsigned int x, unsigned int y)
{
if(x == 0)
return y+1;
else if(y == 0)
return A(x-1, 1);
else
return A(x-1, A(x, y-1));
}
unsigned int result = A(4, 1);
(我认为递归深度限制在~16K,但为了安全起见,我用它编译了这个-std=c++20 -fconstexpr-depth=100000 -fconstexpr-ops-limit=12800000000
)
毫不奇怪,这会占用大量的堆栈空间(事实上,如果以 8mb 的默认进程堆栈大小运行,它会导致编译器崩溃)并且需要几分钟的时间来计算。然而,它最终会到达那里,所以编译器可以处理它。
之后,我决定尝试使用模板、元函数和部分特化模式匹配来实现 Ackermann 函数。令人惊讶的是,以下实现只需要几秒钟即可评估:
template<unsigned int x, unsigned int y>
struct A {
static constexpr unsigned int value = A<x-1, A<x, y-1>::value>::value;
};
template<unsigned int y>
struct A<0, y> {
static constexpr unsigned int value = y+1;
};
template<unsigned int x>
struct A<x, 0> {
static constexpr unsigned int value = A<x-1, 1>::value;
};
unsigned int result = A<4,1>::value;
(用 编译-ftemplate-depth=17000
)
为什么评估时间会有如此巨大的差异?这些本质上不是等效的吗?我想我可以理解consteval
需要更多内存和评估时间的解决方案,因为它在语义上由一堆函数调用组成,但这并不能解释为什么在运行时计算的这个完全相同的(非 consteval)函数只需要比元函数版本(编译时没有优化)。
为什么consteval
这么慢?我几乎很想得出结论,它正在由 GIMPLE 解释器或类似的东西进行评估。还有,元功能版怎么会这么快?它实际上并不比优化的机器代码慢多少。