为什么代码在 constexpr 计算中比在 g++ 运行时更快？

问题描述 投票：0回答：2

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() {
   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（可以在维基百科上找到），而 foo 只是一个无用的函数，返回大约 1 到 100 之间的实际值，具有 fib 运行时复杂性。

编译器和编译后的程序都使用相同的参数来计算 91 的缓慢计算和 ackermann 函数。

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

c++ c++11 constexpr
2个回答
14
投票

在编译时，冗余（相同）

constexpr
调用可以被memoized，而运行时递归行为不提供此功能。

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

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
10
投票

记忆

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

如果在编译时已知所有涉及的值（并且如果该值应该最终所在的变量也被声明为constexpr），则在声明时

constexpr
可以对某些内容进行评估编译时，想象一下以下伪代码：

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

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

f(x) = x + x + x

用语言来说，每个函数调用都已被删除并替换为表达式本身的调用。同样适用的是一种称为“记忆化”的方法，其中传递的计算表达式的结果被存储起来，因此您只需要做一次艰苦的工作。 如果你知道

g(5) = 15

为什么还要再计算呢？相反，只需在每次需要时将 

g(5)
替换为 
15
，这是可能的，因为声明为 
constexpr
的函数不允许有 
side-effects
。

运行时

在运行时这不会发生（因为我们没有告诉代码以这种方式运行）。运行代码的小家伙需要从

f

跳转到 

g
再到 
h
，然后从 
g
跳回到 
h
，然后再从 
g
跳到 
f
，同时他存储每个函数的返回值并将其传递给下一个函数。
即使这家伙很小很小，不需要跳很远，但他仍然不喜欢一直跳来跳去，他要花很多时间做这做那；这需要时间。

但是在OPs的例子中，真的是计算了
compile-time

吗？ 是的，对于那些不相信编译器实际上计算了这个并将其作为常量放入完成的二进制文件中的人，我将提供下面OP代码中的相关汇编指令（

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 


      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.