C++ コンパイル時計算



(2019.6)

テンプレートを使う

C++ では昔から、テンプレートを使えば、コンパイル時計算を行えた。これは Template Meta-Programming (TMP) と呼ばれる。

階乗をコンパイル時計算してみよう (C++11). gcc だと -std=c++11 オプション.

C++
[RAW]
  1. #include <stdio.h>
  3. // C++ の template は, 型名 (typename) 以外も書ける.
  4. // 定数式, 関数のアドレス, 外部リンケージのあるオブジェクト, または静的クラス・メンバのアドレス
  5. template< unsigned n >
  6. struct factorial {
  7. // テンプレート引数で演算する.
  9. // static変数.
  10. //static const unsigned value = n * factorial<n - 1>::value;
  12. // こうすれば value 変数がメモリに生成されない
  13. //enum { value = n * factorial<n - 1>::value };
  15. // メモリに生成されず、型も指定
  16. // const ではなく, constexpr
  17. static constexpr unsigned value = n * factorial<n - 1>::value;
  18. };
  20. // 特殊化
  21. template<>
  22. struct factorial<0> {
  23. static constexpr unsigned value = 1;
  24. };
  27. int main() {
  28. printf("f(10) = %d\n", factorial<10>::value);
  29. return 0;
  30. }

確認のためアセンブラを出力させると, 結果が即値として埋め込まれている。 

	movl	$3628800, %edx
	leaq	.LC0(%rip), %rcx
	call	printf

constexpr

新たに導入された constexprキーワードを使えば、はるかに簡単に書ける。

constexprキーワードのようなヒントがなくても, 原理的にはコンパイル時に読みきれれば, コンパイル時計算は加能だが、ソースコード全体に渡ってそのような判定をするのは現実的でない。constexpr がない箇所では, 最適化によって自動的にコンパイル時計算を行うようにはなっていないようだ。(gcc 7.3)

次のように、普通に関数を書くだけで, コンパイル時計算になる。

C++
[RAW]
  1. #include <stdio.h>
  3. constexpr unsigned factorial(unsigned N)
  4. {
  5. return N == 0 ? 1 : N * factorial(N - 1);
  6. }
  8. int main() {
  9. printf("f(10) = %d\n", factorial(10));
  10. return 0;
  11. }

即値になっている。 

	leaq	.LC0(%rip), %rcx
	movl	$3628800, %edx
	call	printf

constexpr 関数は、それだけではコンパイル時計算を強制できない。実引数として定数式でない値を渡せるし、その場合は、実行時計算になる。

constexpr関数の throw式は, さすがにコンパイルエラーになる。

C++
[RAW]
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. constexpr unsigned factorial(unsigned N)
  5. {
  6. printf("1\n"); // 副作用が書ける. => コンパイル時計算もされなくなる.
  7. //throw 1; //throw式は書けない。(コンパイルエラー)
  8. return N == 0 ? 1 : N * factorial(N - 1);
  9. }
  11. int main( int argc, char* argv[] ) {
  12. unsigned t = factorial(atoi(argv[1])); // 引数が定数式でなくてもOK
  14. printf("f(10) = %d\n", t);
  15. return 0;
  16. }

constexpr関数内で、副作用のある式も書ける。それだけではコンパイルエラーにならない。

コンパイル時計算が強制されて、かつ実行経路上の文に副作用があれば、コンパイルエラーになる。コンパイル時計算が強制されない場合は、実行時計算になる。

コンパイル時計算を強制

コンパイル時計算を強制するには、関数の戻り値をconstexpr変数に代入する。

コンパイル時計算が強制されると、矛盾が生じるため、先ほどの関数内のprintf()もコンパイルエラーになる。

値の検査は、assert()を使うのが簡単。条件を満たさないときは、エラーメッセージの表示という副作用が生じるので、コンパイルエラーになる。

このコードは、C++11 ではコンパイルできない (C++14が必要) が、C++11 のことはもう忘れていい。

C++
[RAW]
  1. #include <stdio.h>
  2. #include <assert.h>
  4. // 1..n を合計.
  5. constexpr int sum(int n) {
  6. assert(n >= 0); // 満たさないときは、コンパイルエラーになる.
  8. int x = 0;
  9. for (int i = 0; i <= n; ++i) {
  10. x += i;
  11. }
  12. return x;
  13. }
  15. int main () {
  16. constexpr int x = sum(100); // 左辺で、右辺のコンパイル時計算を強制.
  17. //constexpr int y = sum(-1); // error: call to non-constexpr function.
  19. printf("%d\n", x);
  20. return 0;
  21. }

ちょっと複雑な計算

たらい回し関数 (竹内関数) を試してみる。C言語による最新アルゴリズム事典 (1991年) では「特に用途はない.」と評されている。

コードの通りに実行すると、かなり時間が掛かる。

C++
[RAW]
  1. #include <stdio.h>
  3. constexpr int tarai(int x, int y, int z) {
  4. if (x <= y) return y; // zを返すのは誤り.
  5. return tarai(tarai(x - 1, y, z),
  6. tarai(y - 1, z, x),
  7. tarai(z - 1, x, y));
  8. }
  10. int main() {
  11. // コンパイル時計算を強制.
  12. constexpr int t = tarai(192, 96, 0);
  13. printf("%d\n", t);
  14. return 0;
  15. }

はい, 即値. 

	leaq	.LC0(%rip), %rcx
	movl	$192, %edx
	call	printf

もっともっと複雑なものでも、コンパイル計算を行える、らしい。

クラスインスタンス

クラス/構造体のインスタンスもconstexpr定数にできる。コンストラクタを constexpr修飾しなければならない。

C++
[RAW]
  1. #include <stdio.h>
  2. #include <math.h>
  4. // 呼び出せる関数は, 明示的に constexpr 修飾されたもののみ.
  5. constexpr int g() {
  6. //printf("1\n");
  7. return 1;
  8. }
  10. struct X {
  11. int y;
  13. // コンストラクタに明示的に constexpr 修飾が必要.
  14. // 暗黙のコンストラクタは、自動的に constexpr.
  15. // メンバ変数は, 関数ブロック内ではなく, メンバ初期化子として書かなければな
  16. // らない. (でないと, コンパイルエラーになる.)
  17. constexpr X(): y(pow(5, 3)) {
  18. g(); // non-constexpr 関数の呼び出しは、コンパイルエラー.
  19. }
  20. };
  22. int main() {
  23. constexpr X x = X(); // 左辺で、右辺の constexpr を強制.
  24. return 0;
  25. }