13

g++ (4.7.2) 和类似版本似乎在编译时评估 constexpr 的速度出奇地快。在我的机器上实际上比运行时编译的程序快得多。

这种行为有合理的解释吗？是否涉及仅适用于编译时的优化技术，可以比实际编译的代码更快地执行？如果是这样，是哪个？

这是我的测试程序和观察到的结果。

#include <iostream>

constexpr int mc91(int n)
 {

     return (n > 100)? n-10 : mc91(mc91(n+11));

 }

constexpr double foo(double n)
{
   return (n>2)? (0.9999)*((unsigned int)(foo(n-1)+foo(n-2))%100):1;
}

constexpr unsigned ack( unsigned m, unsigned n )
{
    return m == 0
        ? n + 1
        : n == 0
        ? ack( m - 1, 1 )
        : ack( m - 1, ack( m, n - 1 ) );
}

constexpr unsigned slow91(int n) {
   return mc91(mc91(foo(n))%100);
}

int main(void)
{
   constexpr unsigned int compiletime_ack=ack(3,14);
   constexpr int compiletime_91=slow91(49);
   static_assert( compiletime_ack == 131069, "Must be evaluated at compile-time" );
   static_assert( compiletime_91  == 91,     "Must be evaluated at compile-time" );
   std::cout << compiletime_ack << std::endl;
   std::cout << compiletime_91  << std::endl;
   std::cout << ack(3,14) << std::endl;
   std::cout << slow91(49) << std::endl;
   return 0;
}

编译时间：

time g++ constexpr.cpp -std=c++11 -fconstexpr-depth=10000000 -O3 

real    0m0.645s
user    0m0.600s
sys     0m0.032s

运行：

time ./a.out 

131069
91
131069
91

real    0m43.708s
user    0m43.567s
sys     0m0.008s

这里 mc91 是通常的 mac carthy f91（可以在 wikipedia 上找到），而 foo 只是一个返回大约 1 到 100 之间的实际值的无用函数，具有 fib 运行时复杂性。

91 的慢速计算和 ackermann 函数都由编译器和编译程序使用相同的参数进行评估。

令人惊讶的是，该程序甚至会运行得更快，只需生成代码并通过编译器运行它，而不是执行代码本身。

4

2 回答 2

14

在编译时，constexpr可以记忆冗余（相同）调用，而运行时递归行为不提供这一点。

如果您更改每个递归函数，例如...

constexpr unsigned slow91(int n) {
   return mc91(mc91(foo(n))%100);
}

... 到一个不是constexpr，但在运行时记得过去计算的形式：

std::unordered_map< int, boost::optional<unsigned> > results4;
//     parameter(s) ^^^           result ^^^^^^^^

unsigned slow91(int n) {
     boost::optional<unsigned> &ret = results4[n];
     if ( !ret )
     {
         ret = mc91(mc91(foo(n))%100);
     }
     return *ret;
}

你会得到不那么令人惊讶的结果。

编译时间：

time g++ test.cpp -std=c++11 -O3

real    0m1.708s
user    0m1.496s
sys     0m0.176s

运行：

time ./a.out

131069
91
131069
91

real    0m0.097s
user    0m0.064s
sys     0m0.032s
于 2013-04-25T18:29:25.577 回答
10

记忆

这是一个非常有趣的“发现”，但答案可能比你想象的要简单。

如果所有涉及的值在编译constexpr时都已知（并且如果值应该结束的变量也被声明为constexpr ），则可以在声明时评估某些东西，假设以下伪代码：

f(x)   = g(x)
g(x)   = x + h(x,x)
h(x,y) = x + y

由于每个值在编译时都是已知的，编译器可以将上面的内容重写为下面的等价物：

f(x) = x + x + x

简而言之，每个函数调用都已被删除并替换为表达式本身的调用。同样适用的是一种称为memoization的方法，其中传递的计算表达式的结果被存储起来，因此您只需要进行一次艰苦的工作。

如果你知道g(5) = 15为什么还要计算呢？而是在每次需要时替换g(5)为15，这是可能的，因为声明为的函数constexpr不允许有副作用。

运行

在运行时这不会发生（因为我们没有告诉代码以这种方式运行）。运行您的代码的小家伙将需要从fto跳到gto h，然后在它从to跳到 all之前跳回 from g，同时他存储每个函数的返回值并将其传递给下一个函数。hgf

就算这家伙很小很小，也不需要跳得很远，他也不喜欢一直来回跳，他做这个做那个要花很多功夫；这需要时间。

但是在 OPs 示例中，它真的计算了编译时间吗？

是的，对于那些不相信编译器实际计算并把它作为常量放入完成的二进制文件的人，我将从下面的 OPs 代码中提供相关的汇编指令（输出g++ -S -Wall -pedantic -fconstexpr-depth=1000000 -std=c++11）

main:
.LFB1200:
  .cfi_startproc
  pushq %rbp
  .cfi_def_cfa_offset 16
  .cfi_offset 6, -16
  movq  %rsp, %rbp
  .cfi_def_cfa_register 6
  subq  $16, %rsp
  movl  $131069, -4(%rbp)
  movl  $91, -8(%rbp)
  movl  $131069, %esi               # one of the values from constexpr
  movl  $_ZSt4cout, %edi
  call  _ZNSolsEj
  movl  $_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_, %esi
  movq  %rax, %rdi
  call  _ZNSolsEPFRSoS_E
  movl  $91, %esi                   # the other value from our constexpr
  movl  $_ZSt4cout, %edi
  call  _ZNSolsEi
  movl  $_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_, %esi
  movq  %rax, %rdi

  # ...
  # a lot of jumping is taking place down here
  # see the full output at http://codepad.org/Q8D7c41y
于 2013-04-25T18:49:29.863 回答