C++のSTLアルゴリズムには関数ポインタよりも関数オブジェクトを渡そうという話

C++のalgorithmヘッダーで宣言されているSTLのアルゴリズム関数テンプレートには，引数に関数ポインタや関数オブジェクト(ファンクタ)を取るものが多い．

例えば，引数が一つの関数を受け取るstd::transformは以下のコードと等価である．

template <class InputIterator, class OutputIterator, class UnaryOperator>
OutputIterator transform (InputIterator first1, InputIterator last1,
                          OutputIterator result, UnaryOperator op) {
  while (first1 != last1)
    *result++ = op(*first1++);
  return result;
}

transformの引数opには関数ポインタ，もしくはoperator()が定義されたclassやstruct(つまり関数オブジェクト)のインスタンスを渡すことができる．

vector<int> v;

// 関数ポインタの場合
int inc(int n) {
  return n + 1;
}

transform(v.begin(), v.end(), v.begin(), inc);

// 関数オブジェクトの場合
struct Inc : public unary_function<int, int> {
  int operator ()(int n) {
    return n + 1;
  }
};

transform(v.begin(), v.end(), v.begin(), Inc());

関数ポインタよりも関数オブジェクトを使った方がいいという話

記事のタイトルにもある通り，STLアルゴリズムには関数ポインタよりも関数オブジェクトを渡すようにした方がよい．その理由は関数呼び出しのインライン化と関係がある．

関数ポインタの場合は関数の呼び出しがインライン化できない

STLアルゴリズムに関数ポインタを渡した場合，その関数の呼び出しには関数のアドレス値が必要である．~~関数のアドレス値はプログラム実行時に決まる~~<追記 2011/02/21 11:13>関数のアドレス値はコンパイル時に決まるそうです．~~そのため，~~たとえ呼び出し先の関数がinline指定されていたとしても，その関数をポインタ経由で呼び出した場合は(ほとんどのコンパイラでは)インライン化されない．

関数オブジェクトの場合はoperator()の呼び出しがインライン化できる

STLアルゴリズムに関数オブジェクトを渡した場合，コンパイラはそのoperator()の呼び出しを静的に解決することができる．そのため，operator()がinline指定されていた場合，コンパイラはその呼び出しをインライン化して高速化することが可能である．
また，関数オブジェクトをSTLアルゴリズムに渡す場合は関数オブジェクトのインスタンスを生成する必要があるが，その際のオーバーヘッドは大抵コンパイル時の最適化で吸収されるため問題にはならない．

速度比較

STLアルゴリズムに関数ポインタを渡した場合と関数オブジェクトを渡した場合でどれくらい速度に差が出るかを簡単な実験で調べてみる．

関数ポインタの場合

以下のように，int型の値をインクリメントする関数incを定義し，std::transformにその関数ポインタを渡すプログラムを書き，実行時間を測った．

#include <algorithm>
#include <vector>
using namespace std;

// inline指定あり
inline int inc(int n) {
  return n + 1;
}

int main(int argc, const char *argv[]) {
  vector<int> v(10000000, 1); 
  for (int i = 0; i < 100; ++i) {
    transform(v.begin(), v.end(), v.begin(), inc);
  }
  return 0;
}

$ g++ -O2 test_functor_speed.cc
$ time ./a.out
./a.out  3.22s user 0.06s system 98% cpu 3.335 total

要素数10Mのvectorに対するtransformを100回繰り返して3秒程かかった．計測は10回ほど行ったが，傾向は変わらなかった．

関数オブジェクトの場合

次に，先程のincの関数オブジェクト版を書き，std::transformに渡して同様に実行時間を測った．

#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

struct Inc : public unary_function<int, int> {
  // クラス定義の中にメンバ関数の定義を直接記述しているため，
  // 暗黙にインライン化される
  int operator ()(int n) {
    return n + 1;
  }
};

int main(int argc, const char *argv[]) {
  vector<int> v(10000000, 1); 
  for (int i = 0; i < 100; ++i) {
    transform(v.begin(), v.end(), v.begin(), Inc());
  }
  return 0;
}

$ g++ -O2 test_functor_speed.cc
$ time ./a.out
./a.out  2.07s user 0.06s system 99% cpu 2.142 total

2秒程度．関数ポインタの場合と比べて約1.5倍高速だった．こちらも計測は10回ほど行ったが傾向は同じだった．

結論

STLアルゴリズムには関数ポインタよりも関数オブジェクトを渡すようにしよう．何故ならば，後者は関数呼び出しのインライン化によって高速化される場合があるからだ．

こういう些細なことの積み重ねがプログラムの大幅な速度低下(向上)に繋がると思うと非常にアレなので気をつけたい．

追記 (2011/02/21 11:13)

上述の実験ではgcc 4.2.1で行った．同じ実験ををgcc 4.6で行ってみたところ，関数ポインタ版と関数オブジェクト版の速度がほぼ等しくなった．また，gccに-Sオプションを付けてアセンブリコードを生成させたところ，gcc 4.6では両者のアセンブリコードが一致した(gcc 4.2.1だと一致しなかった)．

最近のコンパイラだと関数ポインタ経由の関数呼び出しでもちゃんとインライン化されるケースが増えたようだ．それでも全ての環境のコンパイラが関数ポインタの場合の最適化をしてくれるわけではないので，可能ならば関数オブジェクトを優先的に使うべきだろう．