constexpr はもはや C++ になくてはならないものになったが constexpr 関数には様々な制約があり、特に C++11 では普通の関数とはまるで違う書き方を必要とする。特にループを書けないという制約が厳しい。再帰で代用することになるのだが、再帰の深さにも上限があるので、どうにかして再帰の深さを減らすかというのが重要なテクニックになる。再帰の深さは規格では最小でも 512 以上であることが要求されているようだが、ループの替わりにするならいかにも少ない数値だ。

さて、 constexpr 関数を書いたときに実際に再帰の深さがどの程度になっているのか雑に計測する方法として、私はコンパイラのオプションで限界値を減らしてみるという方法をとろうとした。 GCC や Clang なら -fconstexpr-depth というオプションである。が、 GCC と Clang で結果が異なるという知見を得た。

処理系

ここで使う Clang と GCC は MSYS2 上のパッケージとして提供されているもので、それぞれのバージョンは以下の通りです。

GCC 7.3.0
Clang 7.0.0

アッカーマン関数での例

サンプルとしてアッカーマン関数で示す。

sample.cpp

#include <iostream>

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

int main(void) {
  constexpr auto bar = ack(3,1);
  std::cout << bar <<std::endl;
  return 0;
}

Clang では

clang++ sample.cpp -fconstexpr-depth=15

GCC では

g++ sample.cpp -fconstexpr-depth=8

が限界値の最小となる。

実際はどうなのか、少しプログラムを変形して確認してみると……

#include <iostream>

int max_depth=0;

int ack(int m, int n, int depth) {
  if(max_depth < depth) max_depth = depth;

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

int main(void) {
  auto bar = ack(3, 1, 1);
  std::cout << "depth=" << max_depth << std::endl;
  return 0;
}

Clang での限界値に一致する。

depth=15

フィボナッチ数での例

フィボナッチ数を計算する関数ならどうだろうか。

#include <iostream>

constexpr int fib(int n) {
 return n < 2 ? 1 : fib(n-1) + fib(n-2);
}

int main(void) {
  auto bar = fib(10);
  std::cout << bar << std::endl;
  return 0;
}

clang++ sample.cpp -fconstexpr-depth=1

g++ sample.cpp -fconstexpr-depth=0

Clang と GCC のどちらとも、実際の再帰の深さよりもかなり小さい値を指定してもコンパイルが通ってしまった。

まとめ

このようなざっとした確認に過ぎないが、上手く最適化して再帰の深さを抑えるような仕組みでもあるのか、見かけ上の再帰の深さよりも少ない値を指定しても通ってしまうようだ。

再帰の深さを計測するために使うという当初の目的には使えなさそう。

constexpr での再帰の深さ

処理系

アッカーマン関数での例

フィボナッチ数での例

まとめ