[C++]テンプレート再帰回数の限界、再帰回数を減らす実装方法。

　テンプレートメタプログラミングなどをしていると多用することになる、テンプレートの再帰。実はこの再帰回数には制限がある。C++11ではこの再帰回数は1024回が推奨されており十分に大きい。実際の回数制限はコンパイラによって異なるが、それなりに大きな数字になっている。そのため小さな利用に留まる限りは問題ではない。ただし、私のようにメタプログラミングを使い倒していると稀にこの制限に引っかかることがある。

　例えばstd::tuple_elementのように、可変長引数テンプレートで与えられた型のリストからN番目の型を取得するようなクラステンプレートを考えてみる。

#include <iostream>
#include <vector>

template <size_t N, class ...Types>
class GetType;
template <size_t N, class TypeHead, class ...TypeBody>
class GetType<N, TypeHead, TypeBody...> : public GetType<N - 1, TypeBody...>
{};
template <class TypeHead, class ...TypeBody>
class GetType<0, TypeHead, TypeBody...>
{
public:
    using Type = TypeHead;
};
int main()
{
    std::cout << typeid(GetType<3, int, double, float, char, std::vector<double>>::Type).name() << std::endl;
    return 0;
}

　非常に素直な実装だ。再帰するごとに可変長引数テンプレートを一個ずつ剥がしていくだけの簡単なお仕事。環境によるかもしれないが、Visual Studioのstd::tuple_elementはこれとほぼ同様の実装である。
　ただしもしGetTypeに与える型リストが制限を超えていて、かつNに制限以上の数字を与えてしまった場合、その時点でコンパイルエラーとなる。この単純な実装では再帰回数がO(N)なので、制限超過を招きやすいのだ。普通はそんな事は起きないのだろうが、私はやらかしてしまった。

　ではこのO(N)をもっと減らす方法はないのだろうか？　……ある。私の思いつく限りでは、O(log(N))に削減することが可能だ。

#include <iostream>
#include <vector>

template <class...>
struct TypeList {};
namespace detail
{
template <size_t Index, class Type>
struct GetType_impl_s
{
    friend Type Get(const GetType_impl_s&, std::integral_constant<size_t, Index>);
};
template <class, class>
struct GetType_impl;
template <size_t ...Indices, class ...Types>
struct GetType_impl<std::index_sequence<Indices...>, TypeList<Types...>>
    : public GetType_impl_s<Indices, Types>...
{};
}
template <size_t Index, class ...Types>
struct GetType
{
    using Type = decltype(Get(detail::GetType_impl<
                                std::make_index_sequence<sizeof...(Types)>,
                                TypeList<Types...>>(),
                              std::integral_constant<size_t, Index>()));
};
int main()
{
    std::cout << typeid(GetType<3, int, double, float, char, std::vector<double>>::Type).name() << std::endl;
    return 0;
}

　意外と短く纏まった。
　上の実装の肝は、Get関数のオーバーロードを解決させることで要求された型を判定しているところだ。GetTypeに与えられたTypes...一つ一つにIndexを割り当て、ある特定のIndexを用いて呼び出すことのできるGet関数を探し、その戻り値の型を取得している。関数オーバーロードの解決に長大な再帰は必要ないので、std::make_index_sequenceのみが制限を受けている状態。従って、std::make_index_sequenceの再帰回数が制限を超過しない限り問題とはならない。std::make_index_sequenceは実装に依存するが、原理的にO(log(N))である。したがって、改良型GetTypeもO(log(N))となる。
　ただし、もし利用しているコンパイラがstd::make_index_sequenceを上のGetTypeのようにO(N)の単純な再帰を用いて実装している場合、まずこちらの改良版を自ら作成しなければならないだろう。MSVC2015以上では問題ないようだったが。まあ別に、これは特に難しくない。

　これを少し応用すると可変長引数テンプレートのリストの中から特定の型のindexを検索するクラステンプレートなども設計できる。実装は割愛。上のGetTypeをちょっとこねくり回すだけで十分だ。

Visual Studioで64bitコンパイラツールセットを使う方法。C1060への対処。

　msvcでテンプレートを大量に使うなど非常に重たいコードをコンパイルしていると、

　fatal error C1060: ヒープの領域を使い果たしました。

　というエラーが出ることがある。

　Visual Studioのデフォルトのコンパイラは未だに32bitである。出力するバイナリが32bit用か64bit用かに関わらず、コンパイラそれ自体は32bitなのだ。とはいえ、ほとんどの場合32bitコンパイラで特に問題ない。
　ただ上述のC1060のエラーが出る場合、この32bitが足枷になっている場合がある。メモリを2GBまでしか使えないので、巨大なコードのコンパイルにはメモリが足りない場合があるのだ。こんなとき、64bit用のコンパイラツールセットを使うことで解消される可能性がある。

設定方法

　ネット上で調べてみると色々な方法が散らかっていてどの設定方法が適切なのかよく分からないが、とりあえず以下の方法が簡単だった。

　64bitコンパイラツールセットを使いたいプロジェクトに対して、.vcxprojファイルを直接書き換える。
　.vcxprojファイルを開くと、次のようなブロックがある。

  <PropertyGroup Label="Globals">
    ...
  </PropertyGroup>

　この中に次のように一行書き加えればよい。

  <PropertyGroup Label="Globals">
    ...
    <PreferredToolArchitecture>x64</PreferredToolArchitecture>
  </PropertyGroup>

　<PropertyGroup Label="Globals">はプロジェクトのプロパティにおける"すべての構成"に相当する設定だと思われる。Release、Debugなどの構成やプラットフォームごとに切り替えたい場合は、"Globals"ではなく各構成ごとのブロックに書き加えればいい。

根本的な対処

　64bitコンパイラツールセットといえどもPCに搭載されているメモリ容量という限界はあるため、コードそのものがあまりに汚い場合は無駄である。
　コンパイラは基本的に.cppなどのファイルを1つずつコンパイルする。この一つの.cppファイルの中で大量のクラステンプレート、関数テンプレートのインスタンス化が発生することが、上記のC1060エラーのよくある原因である。何でもかんでもヘッダーに書いてその全てを一つの.cppファイル中にincludeしたりすると、しばしばこのような事態になる。
　クラステンプレート、関数テンプレートのインスタンス化を小さな.cppファイルに分割するという手は有効だ。明示的インスタンス化を活用したり、テンプレートでない関数の中に押し込んだりして分割コンパイルするよう工夫すれば、上のエラーは回避できる。……かもしれない。

[C++]std::bindはnon-copyableな引数を束縛できない。

　タイトルのとおりである。std::bindはnon-copyableな引数を束縛できないので、rvalue referenceを引数に取るような関数の扱いには注意を要する。

　std::bindは、何らかの関数に事前に引数を与えた関数オブジェクトを生成する機能である。事前に引数を与えておくことで、後ほど複数回呼び出す際にいちいち引数を与えなくても良くなる便利機能。ただしC++14以上の環境だったらラムダ式で事足りるのであんまり出番はない。敢えて言えば、ラムダ式と違いオーバーロードされた関数オブジェクトに対応しやすいこと、コードが比較的綺麗であることがメリットと言えるが、関数ポインタを与えた場合に実行時オーバーヘッドが増してしまうことはデメリットだ。

　そして困ったことに、std::bindもやはりムーブセマンティクスにまつわる致命的な欠点がある。std::functionと並びマジうぜえ。
　std::bindの特徴の一つは、束縛した関数を何度でも呼び出せるというところだ。何度でも呼び出せるということは、最初に束縛した引数が後に何度も利用されるということである。そう、std::bindは、関数を何度呼び出そうと束縛した引数が有効であり続けることを要求してくるのだ。……さて、ここからが本記事タイトルの話だ。ちょっと考えてみてほしい。std::bindに束縛した関数が引数にrvalue referenceを持っていたとしたら。そしてもし、std::bindに束縛した引数が、ただ一度の関数呼び出しで破壊されてしまうとしたら。
　次のコードを見てほしい。単純な足し算を行う関数Funcをstd::bindによって束縛している。

double Func(std::unique_ptr<double>&& x, std::unique_ptr<double>&& y)
{
    //意図的にxとyの中身をmoveし破壊している。
    auto xtmp = std::move(x);
    auto ytmp = std::move(y);
    return *xtmp + *ytmp;
}
int main()
{
    auto x = std::make_unique<double>(3);
    auto y = std::make_unique<double>(5);
    auto func = std::bind(&Func, std::move(x), std::move(y));
    std::cout << func() << std::endl;//これが仮に動いたとしても、
    std::cout << func() << std::endl;//この時点で束縛したxとyが空なのでエラー。
    return 0;
}

　上記のコードは、実際にはfuncのoperator()の呼び出しができずコンパイルエラーとなるのだが、仮にコンパイルが通り意図したように動作したと考えてみよう。最初のfunc()の時点で、std::bindに束縛したstd::unique_ptrはFuncの中で所有権を移譲され、funcに束縛されている方のstd::unique_ptrは空となる。この状態でもう一度funcを呼び出すと、当然空のポインタにアクセスしているためエラーになるだろう。

　このようなエラーを避けるため、std::bindはrvalue referenceの引数をそもそも束縛できないように設計されている。らしい（海外の掲示板でそのように解説しているレスを見たことがあるだけであるので、信頼性は不明。そのスレッドを改めて探してみるも、見つけられなかった）。何故そんな仕様にしたのか正直理解に苦しむが、そうなっているのだから仕方がない。

　解決方法は複数考えられる。

1. 引数をlvalue referenceに変更する。

　もし関数を変更もしくはラップできるのなら、引数をrvalue referenceからlvalue referenceへと変えてしまうのが手っ取り早い。

double Func(std::unique_ptr<double>& x, std::unique_ptr<double>& y)
{
    //lvalue referenceをmoveしてはいけない、なんてルールは存在しない。
    auto xtmp = std::move(x);
    auto ytmp = std::move(y);
    return *xtmp + *ytmp;
}

　ただこの方法は正直馬鹿げていると思う。引数がrvalue referenceであるからこそ二度目の呼び出しが危険であることが一見して推察されるためプログラマーが注意深く使用できるというのに、lvalue referenceでは関数の処理を熟読しなければ分からない。std::bindはプログラマーに対して危険な使い方をさせないために、より一層危険な回避策へ走らせている。本末転倒ではないか。

2. ラムダ式を使う。

　C++14以上の環境であれば、最も適切な方法はこれだろう。正直、std::bindはラムダ式に比べてデメリットが大きすぎて使う気になれない。ラムダ式はコードが長たらしく汚らしくなるが圧倒的に汎用度が高いので、モダンな環境で開発しているのなら是が非でもマスターすべきである。

//C++14以上なら
auto func = [xtmp = std::move(x), ytmp = std::move(y)]() mutable

　C++11では残念ながら変数をmoveしつつラムダ式にキャプチャさせることができないので、もし変数x、yの寿命がfunc2の呼び出しまで尽きないことが確かであるのなら参照キャプチャを、そうでないならstd::shared_ptrに押し込むか、それも嫌なら次のようなヘルパーを使おう。

//x、yの寿命が尽きない場合はこうするのが手っ取り早い。
auto func = [&x, &y]() mutable
{
    return Func(std::move(x), std::move(y));
};

//もしくはこのようなクラスを用意する。
template <class T>
struct MoveCaptureHelper
{
    MoveCaptureHelper(T&& t)
        : t(std::move(t))
    {}
    //コピーの際、tをコピーではなく強制的にムーブさせる。
    //ムーブキャプチャできないラムダ式に対して、コピーキャプチャに偽装してムーブするわけである。
    MoveCaptureHelper(const MoveCaptureHelper<T>& m)
        : t(std::move(m.t))
    {}
    MoveCaptureHelper<T> operator=(const MoveCaptureHelper<T>& m)
    {
        t = std::move(m.t);
    }
    mutable T t;
};
template <class T>
MoveCaptureHelper<std::decay_t<T>> MoveCapture(T&& t) { return MoveCaptureHelper<std::decay_t<T>>(std::forward<T>(t)); }

//こんな感じに使う。
auto xtmp = MoveCapture(std::move(x));
auto ytmp = MoveCapture(std::move(y));
auto func = [xtmp, ytmp]() mutable
{
    return Func(std::move(xtmp.t), std::move(ytmp.t));
};

3. rvalue reference対応のバインドクラスを自作する。

　標準ライブラリに近い機能を設計する自信のある人は、この方法を取ってみてもいいだろう。ちょっと試しに作ってここに載せてやろうかとも思ったが、やめた。束縛した引数の取り扱いがとても面倒くさいのだ。placeholderまで再現するとかなりの手間になるだろう。本気で実装し始めたら丸一日くらい消費してしまう気がする。

　前回のstd::functionの話と今記事はムーブセマンティクス対応のThreadPoolを公開するための下準備である。このあたりの話が、何故GitHubなどで転がっているThreadPoolの大半が残念な出来であるのかを説明するために重要なのだ。……こんな話をいちいちしなくて済むように、標準ライブラリくらいきちんと制定してほしいものである。ねえ、C++標準化委員会さん？