ボレロ村上 - ENiyGmaA Code

中3女子です。

C++ 標準ライブラリにテンプレート再帰深度のオーダーを定めるべきである

C++ 2013-01 mailing が公開された。
詳細は江添氏のブログを参照されたし。
本の虫: C++ 2013-01 mailingの簡易レビュー


これには、コンパイル時処理において非常に重要なイディオムの標準ライブラリ化が含まれている。
Compile-time integer sequences
いわゆる index_tuple idiom などとして知られているものである。
タプルや配列、型リストなど、インデックスアクセス可能な構造に対して、Variadic Template の中でパック展開式を書くためのイディオムだ。
(Sprout C++ Library では、sprout::index_tuple として提供されている)
Sprout/sprout/index_tuple at master · bolero-MURAKAMI/Sprout · GitHub


この提案では、std::make_integer_seq から、std::integer_seq を導出するようになっている。
想定される実装は、当然、テンプレート再帰によるものだろう。


これの実装について、Twitter で議論が提起された。というか提起した。
テンプレート再帰深度 - Togetterまとめ


問題は、実装のテンプレート再帰の、再帰深度のオーダーである。
もっとも単純な実装では Ο(N) になる。工夫すれば Ο(logN) にすることができる。
自分の主張するところは、「実装のテンプレート再帰深度のオーダーが Ο(logN) である」よう要件として定義すべきということだ。
C++11 がコンパイラに推奨するテンプレートインスタンス化の深度制限が 1024 であるから、例えば

std::make_integer_seq<int, 2048>

としたとき、Ο(N) ならばおそらくコンパイルできないし、Ο(logN) ならばおそらくコンパイルできる。
(じつは index_tuple の実装のこの問題については、以前すでに記事を書いている)
index_tuple イディオムにおける index_range の効率的な実装 - ボレロ村上 - ENiyGmaA Code


では、Ο(logN) を要件に加えることでのデメリットはあるだろうか。

    1. 想定される実装がいくらか複雑になる。
    2. それによりコンパイル時間が僅少長くなる(かもしれない)。

この「僅少」とは、無視できるほどわずかという意味である。
実行時なら3秒で終わるレイトレーシングコンパイル時に処理すると72分もかかるというのと同じようなことは無い。実際無い。
そして、これらはコンパイル時の問題である。完全に型レベルで解決される。


ならばランタイムでのデメリットはあるか。
これは(自分が現在考える限り)無い。本当に無い。
そもそも std::make_integer_seq は、N を入力として 数列 [0..N-1] を得るだけの処理である。重ねて書くがこれは完全に型レベルで解決される。
成果物の std::integer_seq をどのようなデータ構造やアルゴリズムに対して適用するとしても、std::make_integer_seq の処理は完全に終わっているのだから関係しない。
何度も書くが std::make_integer_seq の実装がどうであろうと完全に型レベルで解決されるから、ランタイムあるいは constexpr 関数実行のパフォーマンスには関係ない。


何かの標準アルゴリズムに対して、想定される実装から計算量のオーダーを定義するのは、至極普通のことである。
例えば std::lower_bound は、高々 log2(N)+O(1) 回の比較を行うと定義されている。
このようにほとんどの標準アルゴリズムは、計算量のオーダーが定められている。


問題があるとすれば、テンプレート再帰深度のオーダーというものが、議論の俎上に乗るかということだ。
少なくとも知る限り、再帰深度のオーダーが規格で定められた標準ライブラリは無い。
なぜならば、Boost.MPL のアルゴリズムのような、本当にテンプレート再帰深度が実装の懸案事項になるようなライブラリは未だ標準に無いからだ。


だから、これを「標準に付け加えるべきか」という論拠を自分は持たない。
しかしながら、「ほとんどデメリット無しに機能の使用範囲を広げることができる」ことは実装と実績をもって挙げることができる。
何しろ、この実装無しには、コンパイル時のレイトレーシング音声合成も不可能だったのだから。


さて、どうしたものか。