std::make_integer_seqをO(LogN)にしろという議論

Jonathan Wakelyの書いた論文、N3493: Compile-time integer sequencesで、Variadic TemplatesとTupleを組み合わせた場合に、Tupleの各要素にパック展開でアクセスできるようにする技法のためのライブラリを、標準ライブラリで提供しようという提案がなされた。この論文は、本の虫: C++ 2013-01 mailingの簡易レビューで要約している。

これに我らが縄文土器陶芸家でメタプログラマーのボレロ村上氏が、std::make_integer_seqはO(LogN)の再帰深度を保証しろと注文をつけた。

ISO C++ Standard - Future Proposals に投稿した - ボレロ村上 - ENiyGmaA Code

私の簡易レビューでも、make_integer_seqの実装例を書いているが、これはO(N)な実装であり、氏のメタプログラミングでレイトレやPCM生成といった処理に使うには適していない。

O(LogN)の実装は、私の理解が正しければ、バイナリサーチ的な手法でインスタンス化の低減をしているようだ。

その議論の結果だが、氏がまとめる気配がないので、とりあえず紹介しておこうと思う。

O(LogN)な実装にするというのは、論文筆者を始めて、名だたるC++プログラマー達から賛同を得た。その中で、R. Martinho Fernandesが言うには、

そんな保証の要求に同意するなら、なんでユーザーコードじゃ実現不可能な保証にしないんだよ。なんでO(1)インスタンス化保証にしないんだ？

これは当然の話で、コンパイラーの支援を受ければ、O(1)は造作もないことだ。標準ライブラリに入る以上、コンパイラーの支援を受けた実装になっていても何の問題もない。

Jonathan Wakelyの回答としては、「提案は既存の手法に裏打ちされたものであるべきで、何でもかんでも袖を広げすぎると、宇宙の熱的死が訪れるまで採用されない」と答えている。それも当然の話で、じゃあライブラリじゃなくてコア言語で提供しろよとか、そもそもテンプレートじゃなくて、もっとメタプログラミング前提の機能で提供しろよとか、キリがない。

O(1)に反対しているわけではないし、この提案を議論する際にはもちろん言及するつもりだが、コンパイラーマジックを要求する前に、標準化委員会の反応をみたいのだ。この機能が受け入れられて、ユーザーに重要視されたなれば、コンパイラー側としても、より良い実装のために、O(1)実装のmake_integer_seqを提供するかもしれない。

正直なところ、汎用的すぎるgeneric integer_seq<T, T...>なんかいらないだろ、int_seq<int...>かuint_seq<unsigned...>で十分だろという反応を予想していたので、そういうことには触れず、「こいつァいい、もっと高速化しろ！」という反応には喜ばしい限りだ。

と答えている。

ところで、ISO/IEC JTC1/SC22/WG21 - Papers 2013が公開された。今回の論文は90本以上あるので、恒例の簡易レビューは時間がかかりそうだ。