動的型情報で仮想関数呼び出しを速くできるか

C++は抽象化と高いパフォーマンスを両立させるにはtemplateを使うのがセオリーでした。そのため、標準ライブラリはtemplateを使っています。一方のJavaは、積極的に仮想関数を使っています。しかし、Javaは動的型情報を使った実行時インライン展開ができるため、C++と違って疎結合のまま高いパフォーマンスを出すことが出来ました。しかし、よく考えれば、C++でも実装クラスが限定されるなら、Javaと同様なことをハードコードすることでC++の仮想関数を高速ができるのではと思って試してみました。

結論から言うと、一応速くなりました。でも、インライン展開を抑制しなければいけないほどの効果が出るのは、かなり限定的のようです。




さて、順を追って説明します。

まず、C++では仮想関数を使うと遅くなるというはなし。C++で仮想関数を使うと、仮想関数テーブルが作られます。そして、関数呼び出しが起こると仮想関数テーブルを参照して、そこに書かれた関数を呼ぶことになります。仮想関数テーブルというのは、要は関数ポインタです。そしてこれが遅いため敬遠されます。
何故遅いのか。これは、呼び出す関数が実行時までわからないため、コンパイル時にインライン展開できないというのが問題です。例えばvectorのoperator[]や、greaterなどのように、実質的には1命令ですむような関数を仮想関数にすると、本来数クロックで終わる処理に、レジスタの退避とジャンプ命令が付与されるため、劇的にパフォーマンスが低下する可能性があります。

例えば以下のようなプログラムを書いてみます。

class Parent {
 public:
  virtual ~Parent() {}
  virtual void fun() = 0;
};

class Child : public Parent {
 public:
  void fun() {}
};

int main() {
  Parent* c = new Child();
  for (int i = 0; i < 1000000000; ++i)
    c->fun();
}

この実行時間は1.7sec程度でした。ここで、c->fun()をdynamic_cast<child*>(c)->Child::fun()にすると実行時間が0.0secになりました。呼び出される関数が特定されたためインライン展開されて、結果的にループが消えたようです。これは、-Sでアセンブリを出力させれば、c->fun()ではあった1000000000回のループが消えることで確認できます。ちなみに、Parent* c = ... をChild* c = ...に変えても実行時間は変わりません。cがChildの子クラスである可能性を否定出来ないからだと思います。

さて、C++はこうした問題を回避しながら処理の抽象化を行うために、templateを使って対処しました。有名な例として、CのqsortよりもC++のsortの方が速いという話があります。これは、Cのqsortは比較関数を関数ポインタで渡しますがC++のstd::sortは関数オブジェクトをtemplateで渡します。関数ポインタですと、インライン展開できませんが、templateで関数オブジェクトを渡せばインライン展開されるので高速になるという寸法です。
ここまでは、C++をやっていれば必ず聞く話です。

さて、そうしたわけでパフォーマンスを気にしなければならないシーンで、templateを使うハメになるのですが、templateにするためにはソースを全部ヘッダに書いてコンパイルが遅くなったり、極端に複雑な依存関係に悩むはめになります。一方のJavaは、そもそもtemplateがないのですが、実はそもそも仮想関数がそんなに遅くならない仕組みが入っています。
例えば、Javaで以下のようなソースを書きます。

interface Parent {
  public void fun();
}

class Child implements Parent {
  public void fun() {}
}

class InlineTest {
  public static void main(String[] args) {
    Parent c = new Child();
    for (int i = 0; i < 1000000000; ++i)
      c.fun();
  }
}

このプログラムは非常に高速に実行されて、例えば自分の環境では 0.0ms でした。JavaのJIT最適化コンパイラは、ループの間でcが書き換わらないことを検知したら、下のようなプログラムに（実際はバイトコードレベルですが）に書き換えて実行するということのようです。

if (c instanceof Child) {
  Child c_ = (Child)c;
  for (int i = 0; i < 1000000000; ++i) {
    c_.fun();
  }
} else {
  for (int i = 0; i < 1000000000; ++i) {
    c.fun();
  }
}

c_.fun()がさらに実行時最適化によってインライン展開されて、最終的に大量の関数コールが消える、という寸法です。 さて、そういうわけで仮想関数に関してJavaの方が優れているように感じられます。だからといって、C++でtemplate地獄に陥りたくない・・・。この問題はC++プログラマーを非常に悩ませます。そもそもC++のように面倒なことこの上ない言語を使っているのは、ギリギリのCPU性能を引き出したいからなのに、仮想関数を使ったとたんJavaよりも遅くなるとか・・・。 そこで考えます。実装クラスがある程度事前に分かっていたら、手動で上記のようなif文を挿入すればいいのではないか、と。ようやく本題です。 C++で以下のようなプログラムを書いてみます。

if (typeid(*c) == typeid(Child))
    for (int i = 0; i < 1000000000; ++i)
      dynamic_cast<child*>(c)->Child::fun();
  else
    for (int i = 0; i < 1000000000; ++i)
      c->fun();

これは見事に0.0secでした。インライン展開されたのがわかります。ただし、上記のコードは若干マクロにしにくいので、以下のようにしました。

#define CALL(T, c, f, ...)                          \
  (typeid(*c) == typeid(T) ?                        \
   dynamic_cast<t*>(c)->T::f(__VA_ARGS__)           \
   : c->f(__VA_ARGS__))

...

  for (int i = 0; i < 1000000000; ++i)
    CALL(Child, c, fun);

これを実行すると、0.6secでした。実行時間がもとのおよそ1/3になりました。先程のようなパフォーマンスにならないのは、もちろん分岐命令が入るからです。簡単なマクロを書くことで、事前にある程度実行型が分かっているなら効率を上げることができることがわかります。 ところで、指定した型以外のパフォーマンスはどうでしょう。別名の全く同じクラスを作ってみます。

class Child2 : public Parent {
 public:
  void fun() {}
};

int main() {
  Parent* c = new Child();
  for (int i = 0; i < 1000000000; ++i)
    CALL(Child, c, fun);
}

これが非常に遅いです。5秒以上かかってしまいました。もとの時間の3倍です。何故でしょうか。 この謎を解くためには、typeinfoを覗かないといけません。 typeinfoファイルを覗くと、type_info::operator == で__buildin_strcmpという関数を使って型名の比較を行っているようです。これは残念すぎる。しかし、どうやら__GXX_MERGED_TYPEINFO_NAMESが0でなければ、単なる==演算しかしないようなので、gccに-D__GXX_MERGED_TYPEINFO_NAMES=1を指定して実行してみましょう。すると、実行時間が2.0sec程度になります。元のc->fun()のみに比べて1割増程度で抑えられました。これでようやく満足です。

ところで、実際のところここまで最適化する必要が有るのでしょうか。今回、意図的に差が出やすいように関数の中身を空にしました。実際は、数回のロード命令が挟まるだけで、インライン展開の恩恵は相対的に消えていきます。実際はサイズをいろいろ変えて、アセンブリコードを確認しながら試しましたが、載せるのがしんどくなったので割愛しますｗ　結果として、分岐やロードを数個挟むのであれば、普通に仮想関数にしてしまってもそこまで極端な性能差はでない、ということです。それから、上記の__GXX_MERGED_TYPEINFO_NAMESの問題もあるため、簡単にはパフォーマンスが上がってくれないということのようです。C++、ホントに難しい・・・。