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 (ウィキペディアで見つけることができます) であり、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 に答える