constexpr メタプログラミング:「速度が欲しいか… ならばくれてやる!」
source: http://cpptruths.blogspot.com/2011/07/want-speed-use-constexpr-meta.html
公的にC++11は二種のメタプログラミング方法を備えている。ひとつはtemplateベースで、もうひとつはconstexprである。(訳註：CPPどこいった…!) templateはC++03では広くメタプログラミングに用いられている。C++11ではもうひとつ選択肢が加わる。constexprを用いたコンパイルタイムメタプログラミングである。だが、これらは機能性・可用性の点で相違がある。
templateを利用したメタプログラミングはまったくの偶然から発見され、以来、種々多様なテクニックが発明されつづけてきた。これは、整数リテラルと型のコンパイル時操作が可能な一方で、浮動小数点数リテラルを扱えない純粋関数型言語として機能した。templateメタプログラミングの構文は、メタ関数を構造体、もしくは入れ子のtypedefで実装しなければならず、非常に見苦しいと感じる者が多かった。
汎化された定数式(以下 constexpr)はC++11に対応したコンパイラが、関数の(さらにはクラスの)実装を調べて、もし関数(とクラス)が定数(リテラル)のみを使っている場合に最適化できるようにする機能である。この場合、定数は整数リテラルでも浮動小数点数リテラルでも文字列リテラルでもよい。constexprがついた関数は普通のC++関数と同じように見えるが、関数本文は単一のreturn文しか許可されないという制限がある。それにしても、constexpr関数の構文はtemplateベースのメタ関数よりはるかにとっつきやすい。templateが導入されたときとは対照的に、汎化された定数式の設計者はそもそもそのメタプログラミング能力を十分理解していた。
思うに、constexprの瞠目すべき性質はその速度にある。constexpr関数はコンパイル時に電光石火のごとき速度で計算を行なう。パフォーマンスを比較するために、筆者はis_prime アルゴリズムを3種の方法で実装した。まず以下は通常のC++で実装したものである：
static bool IsPrime(size_t number) { if (number <= 1) return false; for (size_t i = 2; i*i <= number; ++i) if (number % i == 0) return false; return true; }
つぎに、同じアルゴリズムをtemplateで実装したものを示す。言うまでもなく、構造体を基本としたメタ関数のあつまりとして実装した。
struct false_type { typedef false_type type; enum { value = 0 }; }; struct true_type { typedef true_type type; enum { value = 1 }; }; template<bool condition, class T, class U> struct if_ { typedef U type; }; template <class T, class U> struct if_<true, T, U> { typedef T type; }; template<size_t N, size_t c> struct is_prime_impl { typedef typename if_<(c*c > N), true_type, typename if_<(N % c == 0), false_type, is_prime_impl<N, c+1> >::type >::type type; enum { value = type::value }; }; template<size_t N> struct is_prime { enum { value = is_prime_impl<N, 2>::type::value }; }; template <> struct is_prime<0> { enum { value = 0 }; }; template <> struct is_prime<1> { enum { value = 0 }; };
このメタプログラムは純粋関数型言語に則って再帰的実装を取っている。この is_prime_impleメタ関数が重要な仕事をすべてやっつけている。無限再帰を防ぐために、"怠惰なインスタンス化(lazy instatiation)"テクニックを用いている。思うに、きっと今読者はコードを凝視して理解に努めていることだろう。
…そう、それこそが狙いだ。要はC++03のメタプログラムはだいたい読みづらく、理解しづらいのだ。…時は来たれり! 以下は同じアルゴリズムをconstexprで実装したものである。
constexpr bool is_prime_recursive(size_t number, size_t c) { return (c*c > number) ? true : (number % c == 0) ? false : is_prime_recursive(number, c+1); } constexpr bool is_prime_func(size_t number) { return (number <= 1) ? false : is_prime_recursive(number, 2); }
えぇ。まぁ言いたいことは分かる。このヴァージョンでもまだそれほど読みやすいとは言えない。template版と同様、こちらも再帰を使っている。そこはあきらめて馴れましょう! C++のメタプログラミングにおいては、再帰は切っても切れない関係にあるので仕方ない。また、全ての関数は単一のreturn文しか持っておらず、素数を検出する際の条件分岐に条件演算子(訳註：原文ternary operatorェ…)が多用されている。
実引数が整数定数ならば、constexpr版は(もちろんC++11対応のコンパイラならば)コンパイル時に結果がでる。また、実引数がランタイムに決定される場合でも、同じ関数を使って実行時に計算し問題なく結果を出すことができる。つまり、コンパイルタイムとランタイム用に二つ同じことをするプログラムを書く必要がない。これひとつで全てが叶うのだ!
int main(void) { int i = is_prime_func(7); // Computed at compile-time int j = is_prime_func(i); // Computed at run-time }
さて、実装が終わったところで、パフォーマンスの話に移ろう。4256233を例として挙げよう。これは三万番目の素数だ。これが素数かどうか確認するのに、template版だとどのくらい掛るだろうか。…だがダメっ…! それ以前の問題で、g++4.7ではis_prime<4256233>::valueをコンパイルできない。というのは、再帰テンプレートインスタンス化の上限がデフォルトでは900回に縛られているからだ。気をとりなおして -ftemplate-depth-2100 を使って2100回まで再帰できるようにしてみよう。…イケるか…？ イケた! さぁどのくらい時間が掛っただろうか。…だいたい一秒だ! …まぁ悪くないね、と読者は思うかもしれない。ではconstexprではどうか。なんと脅威の0.154秒だ!
これだとそれほどtemplate版が遅いようには見えないかもしれない。大間違いだ。五千万個目の素数について考えてみよう。982451653だ。g++4.7では動作させることすらできなかった。8000回目あたりのテンプレートインスタンス化でg++はセグフォを吐いた。そりゃアンフェアだ! と思うかもしれない。8000+回の再帰テンプレートインスタンス化が？もっとマシな方法があるに違いない。
さて、ではconstexpr版で五千万個目の素数を判定してみよう… なんと0.154秒だった! 間違いない。typoもしていない! この巨大な素数を以ってすらコンパイル時間に与える影響はほとんどないも同然だった。いったいどういう訳だろう。まず、constexpr版にはテンプレートのインスタンス化が伴なわない。C++コンパイラはできる限りコンパイル時計算をやろうとする。constexprはユーザー定義の抽象化(user-defined abstractions)の機会を与え、関数の後ろに計算を隠しつつ、コンパイラから見通せるようになる。もうひとつこの電光石火のパフォーマンスがでそうな理由は、is_prime_funcは末尾再帰関数だという点だ。これは、優れたコンパイラならコンパイルタイムに再帰を完全に省いて単純なループに平板化できるという事を意味する。
この簡単なサンプルで、リテラル(整数、浮動小数点数、文字列)を処理する限りにおいて、constexprはC++の静的メタプログラミングの進むべき道を示していると確信していただければ幸いである。constexpr関数で複雑なメタプログラム可能な型、例えばmpl::contains、mpl::push_backなどをうまく扱えるかどうかまだよく分からない。もし興味が沸いて、上記のサンプルコードで遊んでみたい場合は、こちら(is_prime.cpp prime-test.sh)に置いてある。
