Non-type template parametersの威力

数年ぶりにC++関連のまとまった記事を書こうという気になった。最近の私はというと研究で毎日C++を書いていたので記事にできそうなネタはたくさんあるのだが、それを公開するのは若干面倒なので出し渋っていたところがある。加えて、C++嫌いな人々の根も葉もない批判によって、毎日強烈なストレスを受けてきたのも制約の一つだったかもしれない。まあここで愚痴愚痴言う気もあまりないのだが、プログラマが落ち着いて物事を考えるには周りの環境はとても大事ってわけだ。

この記事では、直近1年ぐらいで私が重要だと感じるようになった、 Non-type template parameters (型ではないテンプレート引数)を使ったイディオムをいくつか紹介しようと思う。面白いことに、今回紹介する抽象化手法には実行時オーバーヘッドが全く無いため、上手く組み合わせることで安全で生産的かつ高速なコードを記述することができる。

C++03までは、Non-type template parametersの重要な用途としてコンパイル時計算があったが、そういった用途はC++11以降ではconstexprでほとんど置き換えられている。今回紹介するのはコンパイル時計算とは異なった用途の例である。

アダプタ関数の生成

よくあるケースで、次のようなコールバック関数を要求するAPIがあるとしよう。

void set_callback(void (*func)(int, void*), void* data);

この例のfuncは引数にユーザ定義のvoid*を取ることができるようだ。例えば、ユーザは以下のように任意の型を定義して、それに対応したコールバック関数を定義する。

// ユーザ定義型
struct my_data
{
    int val;
};

// コールバック関数
void my_handler(int info, void* ptr)
{
    my_data* data = static_cast<my_data*>(ptr); // キャストが要る
    data->val = info; // イベントのデータを自分で用意した領域にコピー
}

my_data g_data; // コールバックに書き込んでもらうデータ

void g()
{
    set_callback(my_handler, &g_data); // コールバックを設定
}

上のコードには特に問題はない。しかし、このset_callbackという関数はvoid*を受け取っており、タイプチェックが行われないので、以下のような危険なコードを簡単に書けてしまう。

double x;
set_callback(my_handler, &x); // ptrはmy_data*型だったはずだが・・・

本題と少し逸れるが、static_castというのは（Cの"包容力の高い"キャストよりは大分マシとはいえ）実際のところ大して安全ではないということも分かる。

T* -> (暗黙のキャスト) -> void* -> (static_cast) -> U*

というように2段階にキャストすると、 reinterpret_cast相当のことが簡単にできてしまう。 (実際にこの罠に嵌っている人を見たことがある。)

T* t = /*...*/;
void* v = t; // 暗黙のキャスト
U* u = static_cast<U*>(v); // reinterpret_cast<U*>(t)と同じ

どうすればこのようなミスを防げるだろうか？コールバックを登録する際には、関数の型とデータの型を比較できるはずだから、本来はset_callbackの呼び出し時点で静的タイプチェックができるはずなのである。やりたいこととしては、テンプレートを使ってこんなラッパー関数を書くことである。

// タイプセーフなラッパー関数
template <typename T>
inline void set_callback_typesafe(void (*func)(int, T*), T* ptr)
{
     set_callback(func, ptr); // ←タイプエラー
}

void my_handler(int info, my_data* ptr);

void g()
{
    set_callback(my_handler, &g_data);
}

しかし、実際には矢印の場所でタイプエラーが起きる。 funcの型が、元の関数だとvoid (*)(int, void*)だったのに、ラッパー関数ではvoid (*)(int, my_data*)になってしまっており、シグネチャが合っていない。

いい加減な解決方法としては、無理やりvoid (*)(int, void*)にキャストしてしまうという方法がある。

template <typename T>
inline void set_callback_typesafe(void (*func)(int, T*), T* ptr)
{
     set_callback(reinterpret_cast<void (*)(int, void*)>(func), ptr); // 危うい
}

型に無頓着なC言語プログラマがいかにも好きそうな方法だ。ほとんど全てのアーキテクチャにおいて、ポインタはその指す先の型に関わらずただのアドレスだから、実際に実行しても多分何もエラーは出ないだろう。しかし、複雑なコードになればなるほど、こういうキャストをばらまいたコードは信頼出来ない品質になっていくだろう。

ランタイムの性能を犠牲にできるのなら解決は容易である。例えばこんな風にする。

template <typename T>
struct Temp
{
    void (*func)();
    T* ptr;
};

template <typename T>
void transfer(int data, void* ptr)
{
    Temp<T>* temp = static_cast< Temp<T>* >(ptr);
    temp->func(temp->ptr);
}

template <typename T>
inline void set_callback_typesafe(void (*func)(int, T*), T* ptr)
{
    Temp<T> p = new Temp<T>;
    p->func = func;
    p->ptr = ptr;
    set_callback(&transfer<T>, p);
}

このコードは安全だし、実際正しく動く保証がある。しかし、実行時性能は（無理やりキャストする案と比べて）ひどく悪くなった。 funcは関数ポインタとして一時的に格納されるから、インライン化は事実上不可能になり、 2段階の関数コールが走る。関数ポインタを一時的に格納するために動的メモリ確保が必要だし、しかもポインタ2個分のメモリを余計に食っていることになる。実際には機械語として出力されないはずのキャストを省略するためのコストとしては、あまりに大きすぎる。

ではどうするか。我々は無念にもvoid*に屈し、キャストをばらまいた型安全でないコードを書くしかないのか？いや、そんなことはない。 Non-type template parametersを使えば、次のようなラッパ関数を書くだけでよいのだ。

template <typename T, void (*Func)(int, T*)>
void transfer(int data, void* ptr)
{
    Func(data, static_cast<T*>(ptr));
}

template <typename T, void (*Func)(int, T*)>
inline void set_callback_typesafe(T* ptr)
{
    void (*func)(int, void*) = &transfer<T, Func>;
    set_callback(func, ptr);
}

そしてこれをこんな風に使う。

void my_handler(int, my_data*);

my_data g_data;

void g()
{
    set_callback_typesafe<my_data, &my_handler>(&g_data);
}

Funcはテンプレートパラメータだから、コンパイル時に決定される。そのため、transferにはコンパイル時に関数が渡る。 set_callback_typesafeの利用者は、全くキャストを使わずに静的タイプチェックをしながら、型のない世界にコールバックを渡せるのである。

関数をコンパイル時に渡すことで何が嬉しいかというと、コンパイル時に呼び出す関数が決まるからコード中（要するにアセンブリ中のテキスト領域）に関数を埋め込めることである。さらに、インライン化できる場合はそもそも関数呼び出しが消滅し、ラッパ関数のみが残る。結果的に、インライン化が行われればオーバーヘッドがゼロ、ということが実現できる。 2個の関数呼び出しをコンパイル時に1個に融合させた、ともいえる。

「なんだ、キャストがなくなっただけじゃないか」と思う人もいるだろうが、この手法は別にキャストに限った話ではなく、応用範囲は広い。例えばこんな風に

// 指定したコールバックを10回呼び出す謎のアダプタ関数
template <typename T, void (*Func)(int, T*)>
void transfer_10(int data, void* ptr)
{
    for (int i = 0; i < 10; ++i)
        Func(data + i, static_cast<T*>(ptr));
}

template <typename T, void (*Func)(int, T*)>
void set_callback_10(T* ptr)
{
    void (*func)(int, void*) = &transfer_10<T, Func>;
    set_callback(func, ptr);
}

void h()
{
    set_callback_10<my_data, &my_handler>(&g_data);
}

関数の前処理/後処理を入れたり、複数の関数を合成したり、呼び出し回数や条件を変えたりなど、要するに関数をラップする色んな転送関数がオーバーヘッドなしに作れる。この特長は、コールバック関数に典型的なパターンを共通化して、ジェネリックかつ高速なライブラリを作る際に特に役に立つだろう。

インライン化の促進

コールバック関数のインライン化に重点をおいた話として、Cryolite先生が興味深いコードを載せていた。

http://d.hatena.ne.jp/Cryolite/01000831

STLのアルゴリズム等に述語として関数ポインタを渡した際に、コンパイル時に呼び出す関数が決定されるにも関わらず、関数ポインタの指す関数のインライン化が行われないことがある。最近のGCCやClangは賢いのでそのような問題はないが、古めのコンパイラを使った場合に、関数ポインタが引き回された際の解析を途中で諦めてしまうのである。

そこで、関数ポインタをNon-type template parametersとした関数オブジェクトを作るという手法がある。すると、関数ポインタが型にエンコードされるので、手で関数オブジェクトを書いた時と同様の状況となり、インライン化が促進される。

元の記事のコードは後方互換性のために若干複雑なので、C++11で簡略化したコードを載せておく。 C++03ではVariadic Templatesが使えないので引数を並べる必要があるが、依然として実装は至って単純である。

template <typename Sig, Sig Func>
struct inline_function;

template <typename R, typename... As, R (*Func)(As...)>
struct inline_function<R (*)(As...), Func>
{
    template <typename... Args>
    R operator () (Args&&... args) const {
        return Func(std::forward<Args>(args)...);
    }
};

// マクロにせずにfを2度書かなくて済む方法があったら教えてほしい
#define MAKE_INLINE_FUNCTION(f) (inline_function<decltype(f), (f)>())

ちなみに、今となっては過去のイディオムだが、 MAKE_INLINE_FUNCTIONは、decltypeのないC++03においても実装できる。初めて見た時はなかなかマジカルな手法だと思った。

// C++03

template <typename Sig>
struct deducer {
    template <Sig Func>
    inline_function<Sig, Func> make() {
        return inline_function<Sig, Func>();
    }
};

template <typename Sig>
inline deducer<Sig> make_deducer(Sig /*ignored*/) {
    return deducer<Sig>(); // 実行時の関数ポインタを捨てるのがミソ
}

#define MAKE_INLINE_FUNCTION(f) (make_deducer(f).make<f>())

こうして定義したinline_functionは、こんな風に使う。

// 与えられた関数を10回呼び出すジェネリックな関数
template <typename Func>
void f(Func func)
{
    for (int i = 0; i < 10; ++i)
        func(i);
}

void g(int x)
{
    std::cout << x << std::endl;
}

// ...

f(&g); // 古いコンパイラだとインライン化されないかも
f(MAKE_INLINE_FUNCTION(&g)); // ほぼインライン化される

近年のコンパイラは賢いので、このテクニックによるインライン化の促進自体はさほど重要ではないだろう。しかし、依然として静的解析の弱いコンパイラは存在するので覚えておいて損はない。

なお、最初のコールバックを登録する話題の中で、利用側で毎回シグネチャを渡していたが、この話と混ぜると少しだけ短くできる。関数を型にエンコードする部分は分離したほうが分かりやすい気がする。

template <typename T, void (*Func)(int, T*)>
inline void set_callback_typesafe(inline_function<void (*)(int, T*), Func> /*ignored*/, T* ptr)
{
    void (*func)(int, void*) = &transfer<T, Func>;
    set_callback(func, ptr);
}

void f(int, my_data*);

my_data g_data;

void g()
{
    set_callback_typesafe(MAKE_INLINE_FUNCTION(&f), &g_data);
}

グローバル変数へのポインタ

グローバル変数は、スコープを飛び越えてありとあらゆる関数に副作用をもたらす邪悪な存在である。一方で、C++プログラマはしばしば忘れがちであるが、構造体メンバにポインタ経由でアクセスするよりも、グローバル変数に直接アクセスする方が高速になる場合が多い。グローバル変数だと、構造体メンバのアドレスをコンパイル時に決定できるので、ポインタの値をメモリからロードしたり、オフセットを足しこんだりする命令が不要になるためである。

単純化した例として、次のようにクラスfooをクラスbarに集約して、 barに転送関数を記述したコードを考える。

class foo
{
public:
    void set(int val) { val_ = val; }

private:
    int val_;
};

class bar
{
public:
    bar(foo* f) : f_(f) { }
    
    void set(int val) const {
        f_->set(val);
    }

private:
    foo* f_;
};

foo g_foo;
bar g_bar(&g_foo);

void set_value_1(int val) {
    g_foo.set(val);
}
void set_value_2(int val) {
    g_bar.set(val);
}

これをClangでコンパイルすると、次のようなアセンブリが吐かれる。

__Z11set_value_1i:
        # ...
        movl    %edi, _g_foo(%rip)  # 直接g_foo.val_に代入
        # ...

__Z11set_value_2i:
        # ...
        movq    _g_bar(%rip), %rax  # g_bar.f_の値をロード
        movl    %edi, (%rax)        # 間接的にg_foo.val_に代入
        # ...

g_bar.f_の値は実行中に書き換わるかもしれないから、コンパイラとしては必ずf_を一度ロードして、その結果得られたアドレスを使わなければいけない。しかし、f_の指す先が特定のグローバル変数だと決まっているのなら、このような間接参照は無意味であるし、コンパイル時に取り除くべきである。

この例だと、g_bar.f_が定数であることを明示すれば、コンパイラは冗長なポインタのロードを除去できる。

const bar g_bar(&g_foo); // g_bar.f_をconstにした

void set_value_2(int val) {
    g_bar.set(val);
}

__Z11set_value_2i:
        # ...
        movl    %edi, _g_foo(%rip)
        # ...

というわけでconstをたくさん付けましょうで話が済めばいいのだが、実際のところそう簡単ではない。少なくともClangでは、デストラクタを加えて少し複雑にしただけで、再び不要なポインタのロードが発生してしまうのである。

class bar
{
public:
    bar(foo* f) : f_(f) { }
    
    // デストラクタを加える (実際のところ空でも同様)
    ~bar() { std::cout << "~bar()" << std::endl; }
    
    void set(int val) const {
        f_->set(val);
    }

private:
    foo* f_;
};

foo g_foo;
const bar g_bar(&g_foo);

void set_value_2(int val) {
    g_bar.set(val); // g_bar.f_をロードしてしまう
}

デストラクタを加えたところで、f_がコンパイル時に決定されることに変わりはないから、コンパイラは依然としてg_bar.f_のロードを取り除けるはずなのだが、そうはならない。この現象については私も正確な理由が分からないのだが、可能性としては次のように考えられる。プログラム終了時にグローバル変数のデストラクタを呼ぶためには、事前に__cxa_atexitを使ってデストラクタを登録する必要がある。デストラクタの登録作業もコンストラクタの仕事の一部と考えれば、 barは定数で初期化できないということになる。しかし、この理屈だと、デストラクタが空でも同じ理由が説明できていない。

いずれにせよ、我々がコンパイラに伝えたいことは、グローバル変数を指して初期化したので間接参照を省いてほしいということである。クラスの利用側の状況によって、コンパイル時にポインタの値が決定できる場合もあるし、実行時にしかわからない場合もありうるが、コンパイル時に決定できるなら必ず間接参照を省いてほしいということになる。

一つの解決策として紹介したいのが、やはりNon-type template parametersを使った手法である。まず、グローバル変数を表すテンプレートを作り、それにポインタ的なインターフェイスを付ける。

template <typename T, T* Obj>
struct global_object
{
    T& operator * () const { return *Obj; }
    
    T* operator -> () const { return Obj; }
};

そして、これの利用を意図したクラスを次のようにテンプレートで定義する。

template <typename Foo>
class bar
{
public:
    bar(Foo f) : f_(f) { }
    
    ~bar() { std::cout << "~bar()" << std::endl; }
    
    void set(int val) const {
        f_->set(val);
    }

private:
    Foo f_;
};

テンプレート引数であるFooには、グローバル変数を紐付けたい場合global_objectを入れ、実行時にアドレスを変更したいならポインタ型を入れればよい。

// グローバル変数なら型として埋め込む
const bar< global_object<foo, &g_foo> > g_bar( (global_object<foo, &g_foo>()) );
    // Most vexing parseの一例になってしまっている

void set_value_2(int val) {
    g_bar.set(val);
}

void set_to(foo* f)
{
    bar<foo*> b(f); // 実行時に決定することもできる
    b.set(123);
}

ポインタを持った全てのクラスをこのように定義するのは若干面倒だが、グローバル変数を直接触るコードよりは遥かに柔軟性が高いし、その一方でコンパイラの最適化能力に関わらずオーバーヘッドは確実にゼロにできるので、手段の一つとしてありなのではないかと思う。

まとめ

Non-type template parametersを使うことで、関数や変数、定数などを型にエンコードし、コンパイル時の色んな最適化を促進することができる。性能要件の厳しい状況下において、 C++が備えているゼロオーバーヘッドの抽象化能力は特に役立つ。

meryngii.neta

今日も新たな"ネタ"を求めて。

Non-type template parametersの威力

アダプタ関数の生成

インライン化の促進

グローバル変数へのポインタ

まとめ