index_tuple イディオムにおける index_range の効率的な実装
コードをコミットしたのはだいぶ以前だけど言及していなかったので書きます。
Github - Sprout/sprout/index_tuple https://github.com/bolero-MURAKAMI/Sprout/tree/master/sprout/index_tuple
index_tuple Idiom そのものについては、ググればそれっぽい情報もいろいろ出てくるので解説は省きます。
ようは C++11 の Pack expansion expression で使えるインデックス列を生成するための技法です。
index_tuple
(Indexes を使った式)... と書けば Indexes がそれぞれの値の場合を列挙した式に展開されます。
index_range
[First .. Last) の範囲の index_tuple を生成するユーティリティです。
-
- index_range (単純な再帰による実装)
namespace sprout { // // index_range // template< sprout::index_t First, sprout::index_t Last, sprout::index_t Step = 1, typename Acc = sprout::index_tuple<>, bool Break = (First >= Last) > struct index_range { typedef Acc type; }; template< sprout::index_t First, sprout::index_t Last, sprout::index_t Step, sprout::index_t... Indexes > struct index_range<First, Last, Step, sprout::index_tuple<Indexes...>, false> : public sprout::index_range<First + Step, Last, Step, sprout::index_tuple<Indexes..., First> > {}; } // namespace sprout
単純なテンプレート再帰による実装では上記のようになります。
F(n+1) = F(n) + s
という漸化式を素直に回しているわけですね。
これでもちろん正しく動くわけですが、あまり要素数が多いと問題になります。
というのも、要素 N 個の index_tuple を求めるのに N 回のテンプレートの再帰的インスタンス化が必要です。
テンプレートの再帰的インスタンス化は、C++11 においてはコンパイラは「少なくとも」深さ 1024 を許容すべきであるとされています。
C++03 では 17 だったことを考えれば大分廃人メタプログラマに優しい仕様になっていますが、
例えば要素数千とか数万の配列をコンパイル時に走査したいときは厳しいです。
よくあることですよね。
なので実装を改良します。
-
- index_range (二分法的な実装)
namespace sprout { // // index_range // namespace detail { template<typename IndexTuple, sprout::index_t Next> struct index_range_next; template<sprout::index_t... Indexes, sprout::index_t Next> struct index_range_next<sprout::index_tuple<Indexes...>, Next> { public: typedef sprout::index_tuple<Indexes..., (Indexes + Next)...> type; }; template<typename IndexTuple, sprout::index_t Next, sprout::index_t Tail> struct index_range_next2; template<sprout::index_t... Indexes, sprout::index_t Next, sprout::index_t Tail> struct index_range_next2<sprout::index_tuple<Indexes...>, Next, Tail> { public: typedef sprout::index_tuple<Indexes..., (Indexes + Next)..., Tail> type; }; template<sprout::index_t First, sprout::index_t Step, std::size_t N, typename Enable = void> struct index_range_impl; template<sprout::index_t First, sprout::index_t Step, std::size_t N> struct index_range_impl< First, Step, N, typename std::enable_if<(N == 0)>::type > { public: typedef sprout::index_tuple<> type; }; template<sprout::index_t First, sprout::index_t Step, std::size_t N> struct index_range_impl< First, Step, N, typename std::enable_if<(N == 1)>::type > { public: typedef sprout::index_tuple<First> type; }; template<sprout::index_t First, sprout::index_t Step, std::size_t N> struct index_range_impl< First, Step, N, typename std::enable_if<(N > 1 && N % 2 == 0)>::type > : public sprout::detail::index_range_next< typename sprout::detail::index_range_impl<First, Step, N / 2>::type, First + N / 2 * Step > {}; template<sprout::index_t First, sprout::index_t Step, std::size_t N> struct index_range_impl< First, Step, N, typename std::enable_if<(N > 1 && N % 2 == 1)>::type > : public sprout::detail::index_range_next2< typename sprout::detail::index_range_impl<First, Step, N / 2>::type, First + N / 2 * Step, First + (N - 1) * Step > {}; } // namespace detail template<sprout::index_t First, sprout::index_t Last, sprout::index_t Step = 1> struct index_range : public sprout::detail::make_indexes_helper< sprout::detail::index_range_impl< First, Step, ((Last - First) + (Step - 1)) / Step > > {}; } // namespace sprout
わりと簡単ですね。
何をやっているかといえば、ポイントはこのあたりです。
typedef sprout::index_tuple<Indexes..., (Indexes + Next)...> type;
「次のインデックス列」を求めるのに、前のインデックス列を利用して展開しています。
こうすることで、n 個のインデックス列から n*2 個のインデックス列を求めるのが 1 回の再帰でできます。
単純計算で、要素 N 個の index_tuple を求めるのに log2(N) 回のテンプレートの再帰的インスタンス化で済みます。
きっとコンパイラにも優しいでしょう。
C++11 時代のメタプログラマは、仕様による制限が C++03 時代に対して緩められ、コンパイラをより酷使することも出来る今だからこそ
あまりコンパイラを虐めずにコンパイラに優しいコードを書いてやるべきだと思います。
ともあれ、これで心おきなく要素数千とか数万の配列をコンパイル時に走査することが出来るわけですね。
Sprout で constexpr DTF のアルゴリズムを書いてみたはいいが放置していたので、
そろそろサンプルでも書いてみようと思います。
