第20回 std::tupleの要素を静的に枚挙する

こんにちは。田原です。

std::tupleには複数の要素を保存できます。ならば、それを枚挙したくなりますね。（私だけ？）しかし、これが意外に難しいです。std::get<i>(タプル)の i はコンパイル時に値が決まっている必要があるからです。そこで、まずは基本のstd::tupleの要素を静的に枚挙する方法をご紹介します。

実は元ネタは静的ポリモーフィズムについて調べていて、偶然見つけたQiitaのこのコメントです。
std::tupleは静的なリストであること、および、各要素の型が異なることの２点からstd::tupleの各要素を動的に枚挙することは無理と考えてました。
しかし、このkazatsuyuさんのコメントを見るとstd::tupleの各要素へのアクセスを動的に行えることが分かります。まさかと思いつつ実際に動かしてみたら確かに出来ます！！正直びっくりしました。
つい ご本人にTwitterで聞いてみたところ、ジェネリック・ラムダを使えば枚挙も可能でしょうとのご返事を頂きました。
そう言えば、当講座ではまだラムダ式の解説も行っていませんでしたし、静動変換もテーマとして面白いと思います。そこで、静的枚挙、動的枚挙、ラムダ式について数回に渡って解説してみたいと思います。

１．静的な枚挙、動的な枚挙とは？

まず「枚挙」とは１つ１つ取り上げることです。例えば範囲ベースfor文を使って配列の中身を１つ１つ処理することがありますが、そのような処理を「枚挙」と言います。for文で枚挙することは多いと思いますが、これは「動的な枚挙」です。

そして、「静的な枚挙」はコンパイル時に枚挙してしまうことです。コンパイル時に処理するということは、当たり前ですが実行時に処理しないので枚挙のためのオーバーヘッド（ループ変数のインクリメントや終了判定など）を極限まで減らせる可能性があります。ただしC++の全ての静的処理が性能を上げることを目的に用意されているとは限りません。運が良ければ性能を改善できるという程度にとらえておいた方がよさそうです。

ところですいません。「静的な枚挙」、「動的な枚挙」は私の造語です。他では通用しませんのでここだけの話として下さいね。

さて、一般的な高速化のテクニックの１つとして有名なものに、ループの展開があります。例えば、次のようなプログラムのarrayへ設定しているところを一部分展開するテクニックです。
現代のC++コンパイラの最適化は優秀なので、それほど効果的というわけではないのですが、静的枚挙をイメージするためのサンプルとして説明します。

constexpr std::size_t   n=896;
volatile int array[n];

void set0(int iData)
{
    for (std::size_t i=0; i < n; ++i)
    {
        array[i]=iData;
    }
}

void set1(int iData)
{
    for (std::size_t i=0; i < n; i+=8)
    {
        array[i+ 0]=iData;
        array[i+ 1]=iData;
        array[i+ 2]=iData;
        array[i+ 3]=iData;
        array[i+ 4]=iData;
        array[i+ 5]=iData;
        array[i+ 6]=iData;
        array[i+ 7]=iData;
    }
}

set0(), set1()は同じことをするのですが、（最適化無効でビルドすると）set0()に較べてset1()の方が高速です。これはループの中身を8回展開することでループの回数を1/8にしました。これによりループ処理のオーバーヘッドを1/8に減らしています。ループ内部の処理が非常に軽いので、このループ処理のオーバーヘッドの割合が多く、結果として全体の性能がそこそこ改善しています。

このset0()関数の処理が「動的な枚挙」です。そして、set1()関数でループの一部を展開した16行目～23行名の部分が「静的な枚挙」です。この例ではプログラマが手で静的に枚挙しているためコンパイル時には既に枚挙されています。次節でコンパイラにやらせてみます。

ところで、このコードは最適化ビルドした場合ほとんど差がでません。測定バラツキで結果が逆転することさえあります。これは最近のコンパイラの最適化が非常に優秀ということなのです。つまり、通常は最適化に任せて、なるべくメンテナンスし易いコーディングを心かけた方が好ましいと思います。
しかし、お手軽なコーディングのためにstd::tupleを使うこともあると思います。そのような時std::tupleの各要素を枚挙したいこともあるでしょう。また他のケースでも「静的な枚挙」できると嬉しい場合もあります。

Wandboxで確認する。
左上にある「Optimaization」をチェックして最適化を有効にすると全体に高速になります。その結果、速度が逆転することもあります。

２．コンパイラでループを展開する

上記サンプルを静的枚挙してみるのですが、それに用いるパーツについて説明します。

2-1.そのための重要なパーツstd::index_sequenceとstd::make_index_sequence

C++14でSTLに追加されたものにstd::index_sequenceという謎のクラス・テンプレートがあります。一見何の役に立つのか本当に解らないクラス・テンプレートです。

ポイントだけ抽出すると次のようなものです。（実際の定義はこれとは異なります。）

template<std::size_t... indices>
struct index_sequence
{
};

そう、中身が空っぽなのです。サンプルだからではありません。ほぼ完全に空でよいのです。実に不思議な存在です。

この目的は、型推論によりstd::size_t...と言うテンプレート・パラメータ・パックを生成することです。別名テンプレートstd::make_index_sequence<N>を実体化することによりstd::index_sequence<0, 1, 2, ..., N-1>クラスが実体化されます。

#include <iostream>
#include <utility>

template<std::size_t... indices>
void foo(std::index_sequence<indices...>)
{
    using swallow = int[];
    (void)swallow
    {
        (std::cout << indices << "\n", 0)...
    };
}

int main()
{
    foo(std::make_index_sequence<5>());
}

1. クラス・テンプレートを実体化する（16行目）
   std::make_index_sequenceを明示的に実体化したstd::make_index_sequence<5>はstd::index_sequence<0, 1, 2, 3, 4>クラスとなります。

2. 実体化により作られたクラスのインスタンスをコンストラクトする（16行目）
   その後ろに()を付けて`std::index_sequence<0, 1, 2, 3, 4>’のデフォルト・コンストラクタを呼び出してインスタンスを生成しています。このクラスの中身は空ですからインスタンスのサイズは最小です。（多くの処理系で1バイトです。）

3. 型推論によりテンプレート・パラメータ・パックを生成する（4行目）
   foo関数テンプレートへ2.で生成したインスタンスを与えて呼び出しています。その結果、型推論によりテンプレート・パラメータが決定されます。与えたものはstd::index_sequence<0, 1, 2, 3, 4>ですから、これに適合するテンプレート・パラメータは<0, 1, 2, 3, 4>です。つまり、<indices ...>は<0, 1, 2, 3, 4>に展開されます。

4. 最後にswallowテクニックでindicesを展開し表示する（10行目）
   見ての通りの結果となります。

0
1
2
3
4

2-2.std::index_sequenceを使って静的枚挙へ変更する

目的は性能改善ではなく「静的な枚挙」の学習ですので、このままswallowテクニックを用います。（これは使用しない配列を生成しますので性能的にはいまいちですが汎用性は高いです。）
2-1.で使ったパターンをほぼそのまま使います。

constexpr std::size_t   n=896;
volatile int array[n];

template<std::size_t... indices>
void set2(int iData, std::index_sequence<indices...>)
{
    using swallow=int[];
    (void)swallow
    {
        (array[indices]=iData, 0)...
    };
}

int main()
{
    set2(789, std::make_index_sequence<n>{});
}

Wandboxで確認する。

ところで、n=896と定義しています。実はmake_index_sequenceに与えることができるnの値はあまり大きくありません。gcc 5.4.0では900程度でしたので900を越えない16の倍数となる最も大きな896を与えています。
この数値はコンパイラが処理するので、あまり大きいとコンパイラがオーバーフローしてしまうようです。

３．そしてstd::tupleを静的に枚挙する

ここまで来るとほぼ見当が付くと思いますが、次のプログラムはstd::tupleの各要素を静的に枚挙して表示します。

#include <iostream>
#include <tuple>
#include <string>
#include <utility>

template<class tTuple, std::size_t... indices>
void print(tTuple const& iTuple, std::index_sequence<indices...>)
{
    using swallow=int[];
    (void)swallow
    {
        (std::cout << std::get<indices>(iTuple) << "\n", 0)...
    };
}

template<class tTuple>
void forTuple(tTuple const& iTuple)
{
    constexpr std::size_t n = std::tuple_size<tTuple>::value;
    print(iTuple, std::make_index_sequence<n>{});
}

int main()
{
    std::tuple<int, std::string, long>  aTuple(123, "abc", 789);
    forTuple(aTuple);
}

std::tuple_size<tTuple>::valueはそのタプルの要素数を静的に（コンパイル時定数として）返却します。ですので、これをmake_index_sequenceの非型テンプレート・パラメータとして渡すことができます。

Wandboxで確認する。

４．まとめ

昔、高速化のテクニックとしてループ展開を良く使っていました。アセンブラでは間違いなくその方が高速になります。しかし、C++では意外にそうでもないのです。下手に展開すると却って遅くなりますし、VC++とgccでは振る舞いが異なるため、片方で速くなってももう一方では遅くなることもありました。最適化の技術はそれぞれの処理系で独自に発展しているからだろうと思います。
結局、記事中でも書きましたが、高速化は通常はコンパイラの最適化に任せておくのが良さそうです。

さて、今回は静的に枚挙してみました。これはこれで使えることもあると思いますが、私は２点の不満があります。

1. 全部枚挙するしかない
   一部分だけ表示したいとか、動的に指定した要素だけを取り出したいとかできないです。

2. 処理内容がswallowの中に埋め込まれている
   取り出した要素に対して異なる処理をしたい時は、また異なるforTupleとprintを作るしかありません。枚挙処理とその中で行いたい処理は別物ですからできれば切り離したいものです。

次回はこの辺を改善してみたいと思います。お楽しみに。