Cry’s Diary

0100-08-31 関数へのポインタによるコールバックをインライン化する

関数へのポインタによるコールバックをインライン化する

関数ポインタとコールバックとインライン化と

C++,特にSTLではコールバックにファンクタを使用することが推奨されています.コールバックにファンクタを用いることの利点は大きく次の2つだと思われます.

  • コールバックがインライン化される(ただしあくまで「かも知れない」)
  • 各種のアダプタを適用できる

以下では主に前者について,関数ポインタを用いたコールバックをインライン化できないかを考えます.

そもそも,インライン化したい関数というのは短い簡潔な関数のはずで,そういった関数のインライン化のためだけにstructごにょごにょ,operator()うにゃうにゃとやるというのは面倒だなぁ,関数ぺぺっと書きたいな,というモチベーションは十分にありえるかと思われます.

さて,関数ポインタ経由での関数呼び出しは通常インライン化されないと考えられます.これは関数ポインタ経由の場合,実行時まで呼び出す関数のアドレスが決まらないからに他なりません.しかしながら,積極的な最適化を行ういくつかのコンパイラでは,コンパイル時に呼び出す関数が決定しているかを判別し,決定できる場合インライン化を行うものがあるようです.例えば,VC++7.1では以下のような単純な関数ポインタ経由の関数呼び出しはインライン化してくれます.

template<class F>
inline
int invoke(F f)
{
  int n = 3;
  return f(n);
}

inline
int square(int n)
{
  return n * n;
}

int main()
{
  // VC++7.1 with /Oxでsquareの呼び出しがインライン化される
  std::cout << invoke(&square) << std::endl;
}

しかしこのような積極的な最適化を行ってくれるコンパイラばかりではありません.そのようなコンパイラでも関数ポインタによるコールバックをインライン化したい,というのがここでのモチベーションになります.

さらに上のような最適化を行ってくれるコンパイラでも,関数ポインタ関数アダプタでラップするなど,少し複雑な文脈にしただけで(たとえコンパイル時にアドレスが評価できるとしても)インライン化を諦めてしまいます.これはアダプタ内でいったんポインタ変数に代入されるので,コンパイル時決定かどうかを解析し切れないためだと思われます.

template<class F>
inline
int invoke(F f)
{
  int n = 3;
  return f(n);
}

inline
int square(int n)
{
  return n * n;
}

int main()
{
  using namespace boost::lambda;
  // VC++7.1 with /Oxでsquareがinline化されなかった例
  std::cout << invoke(std::ptr_fun(&square)) << std::endl;
  std::cout << invoke(bind(&square, _1)) << std::endl;
}

このような多少複雑な文脈でのインライン化を促進できれば,関数ポインタによるコールバックのインライン化というテーマはさらに意義を持つと考えられます.

上のような,関数ポインタをアダプタでラップする状況として最たるものと考えられるのがメンバ関数へのコールバックです.このメンバ変数へのコールバックをインライン化したいというのは,恐らくここでの最大のモチベーションになるかと思います.特に単純なsetter/getterでは必要性が大きいでしょう.

また,メンバ関数はファンクタに出来ないという事情もさらなる動機付けになります(より正確には,ネストしたファンクタを定義してそのオブジェクトをメンバ関数とみなす手法も存在しますが,この手法はthisポインタを明示的に引き渡さないとならないという欠点を抱えます).

さて,コンパイラによる積極的な最適化を前提とすることなく,関数ポインタによるコールバックのインライン化を期待することは出来るでしょうか?

基本的アイデア

コンパイラが関数ポインタ経由での関数呼び出しをインライン化するためには,そのポインタがコンパイル時に評価できるということを解析できれば良いわけで,プログラマである我々がそれを何らかの形でコンパイラに伝えられれば良いわけです.そのための非常に巧みな手法として,インライン化して欲しい関数ポインタをコールバックする関数テンプレート引数にしてしまうというものがあります.

このアイデアはTodd Veldhuizen氏の以下のarticleからお借りしたものです.

http://www.osl.iu.edu/~tveldhui/papers/techniques/techniques01.html#index00030

template<int (*pf)(int)>
int invoke()
{
  int n = 3;
  // このpfはコンパイル時に決定しているので,
  // これによる関数呼び出しはインライン化可能であると
  // コンパイラが容易に判定できる.
  return pf(n);
}

int square(int n)
{
  n * n;
}

int main()
{
  // squareへのコールバックはinline化されうる
  std::cout << invoke<&square>() << std::endl; // 9
}

しかし,この手法はそのままでは汎用性に欠けますし,またSTL等のコールバックの形態と合いません(STLの各アルゴリズムテンプレート引数関数ポインタを渡せるようには出来ていません).

実装の汎用化

さて上のアイデアを元に,STLなどのコールバックに使え,なおかつインライン化可能な関数ポインタのラッパを実装してみることにします.コンパイル時に評価される関数ポインタテンプレート引数として保持しつつ,関数呼び出しの構文を備えた以下のようなファンクタを実装します.

template<int (*pf)(int)>
struct inline_ptr_fun
{
  int operator(int n) const
  {
    return (*pf)(n);
  }
};

この関数オブジェクトに対する関数呼び出しがインライン化され,pfに対する関数呼び出しがインライン化されれば,結果的に関数ポインタによるコールバックがインライン化されるという寸法です.この関数オブジェクトは以下のように使えるでしょう.

template<class F>
int invoke(F f)
{
  int n = 3;
  return f(n);
}

int square(int n)
{
  n * n;
}

int main()
{
  std::cout << invoke(inline_ptr_fun<&square>()) << std::endl; // 9
}

見ての通り,これはSTLで採用されているコールバックの形態と同じです.すなわち,STLの各アルゴリズムに何の問題も無く引き渡せます.

  std::transform(v.begin(), v.end(), v.begin(), inline_ptr_fun<&square>());

しかも,このsquareへのコールバックはインライン化が期待できるというわけです.

しかしこのままでは様々な関数ポインタ型に対して逐一関数オブジェクトを書かねばならず未だ汎用性に欠けます.そこで以下ではこれをテンプレートの部分特殊化を用いて汎用化した実装を行っていきます.引数の個数と型・戻り値の型などによって特殊化したラッパを個別に作成していけばよいわけです.

以下具体的な実装を追っていきます.

まずプライマリテンプレート

// F : ラップする関数ポインタの型
// f : ラップする関数ポインタ
template<class F, F f>
struct il_ptr_fun;

として(これ自体は宣言のみで定義を提供しません),これを引数の個数によって特殊化します.

まず,引数が0の関数ポインタの場合の部分特殊化.

template<class R, R (*pf)()>
struct il_ptr_fun<R (*)(), pf>
{
  R operator()() const
  { return (*pf)(); }
};

引数が1個の場合.

template<class R, class A0, R (*pf)(A0)>
struct il_ptr_fun<R (*)(A0), pf>
{
  R operator()(A0 a0) const
  { return (*pf)(a0); }
};

引数が2個の場合.

template<class R, class A0, class A1, R (*pf)(A0, A1)>
struct il_ptr_fun<R (*)(A0, A1), pf>
{
  R operator()(A0 a0, A1 a1) const
  { return (*pf)(a0, a1); }
};

以下,希望する引数の個数の特殊化を繰り返し作っていけば良いだけです.そして,例えば

int f(int, int);

という関数があれば

il_ptr_fun<int (*)(int, int), &f>();

というのがil_ptr_fun<R (*)(A0, A1), pf>の特殊化に一致するわけです(R = int, A0 = int, A1 = int, pf = f).

実装自体は似たようなコードの繰り返しになるため,Boost.Preprocessorで機械的に生成していけば良いだけです.

後は同様の特殊化を関数への参照,メンバ関数へのポインタについて実装すれば万事OKという寸法です.

細かい問題として,返り値がvoidの場合returnが出来ないので返り値がvoidの場合だけ別に特殊化しなければならないというものがあります(より正確に言うと,このvoid returnは標準規格では可能であると明記していますが,実装しているコンパイラが未だ少ないらしいのであえてそうしています).

プロトタイプですが一応実装全体を公開しておきます.

http://park7.wakwak.com/~cryolite/hatena/cpp/il_ptr_fun.zip

好きに持っていって,好きに使ってもらって構いません.むしろ,使ってみてのダメだしを強く希望します.使うにはboost1.32.0以降が必要です.

使い方

テンプレートの第1引数はラップする関数ポインタの型,第2引数はラップする関数ポインタを指定します.

int square(int);

il_ptr_fun<int (*)(int), &square>();

関数へのポインタの他に関数への参照,メンバ関数へのポインタをラップ出来ます.

il_ptr_fun<int (&)(int), *square>();

class C{
public:
  int f(int);
};

il_ptr_fun<int (C::*)(int), &C::f>();

メンバ関数へのポインタをラップした場合,第1引数クラスのオブジェクトへのポインタまたは参照を取る関数オブジェクトとして扱えます.これはstd::mem_fun, std::mem_fun_refでラップした場合,あるいはメンバ関数へのポインタBoost.Lambdaのbindでバインドした場合と同じです.

il_ptr_fun<int (C::*)(int), &C::f> cf;

C c;
cf(c, 3); // c.f(3)の呼び出し
C *pc = &c;
cf(pc, 3); // pc->f(3)の呼び出し

他の特徴として,内部にsigクラステンプレートを持っているのでそのままBoost.Lambdaと一緒に使えます.

int square(int);

transform(v.begin(), v.end(), v.begin(),
	  bind(il_ptr_fun<int (*)(int), square>(), _1 + 1));

オブジェクトジェネレータ

上のようにil_ptr_funのテンプレート引数の型の部分をいちいち指定するのは非常に面倒なので,関数ポインタを渡しただけで型パラメータを自動推論してくれるオブジェクトジェネレータも用意しています.ただし実装の都合上マクロで提供しています.

transform(v.begin(), v.end(), v.begin(), CRY_AS_FUNCTOR(square));

実はこのマクロの実装がこのライブラリの心臓部だったりします.特にVC++7.1だとコンパイラのバグ(ただし非常に特殊な状況下でのバグ)があるために,これを回避するためのwork-aroundに凶悪なテクニックを連発しなければならず相当苦労したという・・・.

比較

以下はVC++7.1 with /Oxでインライン化されているかどうかを確認した簡単なコードとその結果です.

#include "il_ptr_fun.hpp"

#include <iostream>
#include <functional>

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

class C
{
public:
  void set(int n){ n_ = n; }
  int get() const{ return n_; }
private:
  int n_;
};

inline int square(int n){ return n * n; }

template<class F>
inline
void print_ptr_fun(F f, int n)
{
  std::cout << f(n) << std::endl;
}

template<class T, class F>
inline
void my_mem_fun1(F f, T *p, int n)
{
  f(p, n);
}

template<class T, class F>
inline
void print_mem_fun(F f, T const *p)
{ std::cout << f(p) << std::endl; }

int main()
{
  using namespace cry;
  using namespace std;
  using namespace boost::lambda;

                                                                   // inlined? (@VC++7.1 with /Ox)
  print_ptr_fun(&square, 1);                                       // yes
  print_ptr_fun(ptr_fun(&square), 2);                              // no
  print_ptr_fun(bind(&square, _1), 3);                             // no
  print_ptr_fun(il_ptr_fun<int (*)(int), &square>(), 4);           // yes
  print_ptr_fun(bind(il_ptr_fun<int (*)(int), &square>(), _1), 5); // yes
  print_ptr_fun(CRY_AS_FUNCTOR(&square), 6);                       // yes
  print_ptr_fun(CRY_AS_FUNCTOR(&square), 7);                       // yes

  C c;                                                           // inlined? (@VC++7.1 with /Ox)
  my_mem_fun1(mem_fun(&C::set), &c, 1);                          // no
  print_mem_fun(mem_fun(&C::get), &c);                           // no
  my_mem_fun1(il_ptr_fun<void (C::*)(int), &C::set>(), &c, 2);   // yes
  print_mem_fun(il_ptr_fun<int (C::*)() const, &C::get>(), &c);  // yes
  my_mem_fun1(CRY_AS_FUNCTOR(&C::set), &c, 3);                   // yes
  print_mem_fun(CRY_AS_FUNCTOR(&C::get), &c);                    // yes
}

動作を確認したコンパイラ

  • Microsoft Visual C++ 7.1
  • GCC 3.3.3

おわりに

関数ポインタによるコールバックをinline化するという目的のためだけにしては,実装が肥大化しすぎた気がする・・・.ま,テンプレートだから使わないものはインスタンス化されないしいっか・・・いいのか?


おわり.

kumagikumagi 2010/10/08 16:49 zipのソースコードですが、il_ptr_fun_preprocessed.hppにおいて
s/X &x/X &p/
s/X const &x/X const &p/
の2つの置換が必要でした。