GCCがconstexpr関数のメモ化をやめたっぽい

はじめに

　なんかGCC9.3とGCC10.1でconstexpr関数の挙動が変わったようです。最近発見したのでちょっとした小ネタとして記事にします。大した記事ではありませんが。

constexprとは

　constexpr関数とはコンパイル時に評価可能な関数のことです。実行時に評価することも可能です。

constexpr int func(int x, int y) {
  return x + y;
}

int main() {
  constexpr int i = func(20, 22);  // コンパイル時に計算される (実行時コストが減って高速)
  int j = func(20, 22);   // 実行時に計算される (最適化によってはコンパイル時に計算される)
  return 0; 
}

constexprのメモ化

　constexpr関数は、C++17までは与える引数に対して戻り値が一意に決まります。そのため、引数と戻り値のペアを保存しておけば、たとえ実行時に呼び出されたとしても保存しておいた値を取り出すだけで良いので速いわけですね。それがメモ化というものです。ClangやMSVCはこの機能を取り入れていませんでしたが、GCCでは9.3までこのメモ化が実装されていました。
　しかし、C++20でnew式とdelete式がconstexprになったため、戻り値が一意ではなくなりました (newの返すポインタはいつも同じではありませんよね？)。なので必ずしもメモ化できるというわけではなくなったのですが、その影響もあってか、GCC10.1以降メモ化できるできないにかかわらず、メモ化するのをやめたようです。-std=c++2aだけでなく-std=c++17でもこの変更が適用されています。正直このメモ化は高速な代わりに、少しコードの規模が大きくなるとメモリをえげつなく食らいつくすので無い方が有難かったりしますが。
　メモ化をやめたことは以下のコードで確認できます。

constexpr long long fib(int i) {
  if (i == 0) {
    return 0;
  }
  if (i == 1) {
    return 1;
  }
  return fib(i - 1) + fib(i - 2);
}

int main() {
  constexpr long long j = fib(50);
  return static_cast<int>(j);
}

　実行結果は下のリンクから。

　関数fibは入力の引数$ N $に対して計算量$ O(2^N) $かかり、最大ステップ数制限をオーバーしてコンパイルエラーになりますが、メモ化されていれば計算量$ O(N) $で済み、普通はステップ数オーバーしません。GCC9.3ではコンパイルできていますが、GCC10.1ではコンパイルエラーになっていますね。

おしまい