Neaural Networkのプログラムを書いてる時に気づいたのでメモ。

仮想関数呼び出しのコスト

C++でクラスの継承を用いたプログラムを記述する際、仮想関数を利用することがあります。仮想関数を利用するメリットは、「動的なポリモーフィズム」を実現できるところにあります。
一方で、仮想関数の呼び出しは通常の関数の呼び出しに比べてかなりオーバーヘッドが大きくなります。これは、仮想関数を呼び出すごとに仮想関数テーブルを参照していることに起因します(仮想関数テーブルが何なのか分からない方は、下の記事を参考にしてください)。

「ｃ＋＋」プログラミング/第3章-ｃ＋＋プログラミングの裏側/3-4-仮想関数の裏側

しかし、予めすべての子クラスが決まっていて、それらを配列にしたい時ってありますよね。その時には仮想関数を用いるのではなく、以下に示す方法のほうが高速です。

タグ識別による条件分岐

仮想関数を用いない「動的なポリモーフィズム」を実現するために、タグによる識別を用います。
まず、子クラスのオブジェクト作成時に、そのオブジェクトにタグ(番号)をつけておきます。そして親クラスのポインタに格納され、メソッドを呼び出すときに、そのタグを参照して識別します。

例えば、親クラスAを継承する子クラスB,Cがあるとします。また、B,Cは同名のメンバ関数GetProperty()を持つとします。Aクラスのポインタに代入された後にGetProperty()関数を呼び出すには、以下のようにします。

A *a[] = {new B(), new C()};

for(int i = 0; i < 2; ++i){
    if(a[i]->tag == 'B'){
        static_cast<B*>(a[i])->GetProperty();
    } else {
        static_cast<C*>(a[i])->GetProperty();
    }
}

これは明らかに型安全なキャストなので、dynamic_castする必要はありません。

タグ識別のメリット

高速化

この方法のメリットとしては、まず高速化が挙げられます。
まずは仮想関数を使ったプログラム(virtual.cpp)とタグ識別を利用したプログラム(nonvirtual.cpp)で実行性能を比較しました(ソースコードはココにあります)。

環境

CPU: Intel(R) Core(TM) i3-4025U (1.9GHz, 4コア, 64bit)
コンパイラ: g++(GNU GCC 5.4.0)
OS: Ubuntu 16.04 LTS

	virtual.cpp	non-virtual.cpp
最適化オプションなし	1854 [ms]	1795 [ms]
〃　(関数本体のみ)	140 [ms]	100 [ms]
最適化オプションあり(-O3)	462 [ms]	451 [ms]
※関数本体のみとは、サブ関数(mt)を含まない関数本体の処理の累計時間を指します。

templateの使用

他のメリットとして、テンプレートが使えることが挙げられます。
仮想関数ではテンプレートを使用することが出来ません。そんな時、このタグ識別による方法を使えば、関数テンプレートを使用することが可能となります。これは、可変長引数やユニヴァーサル参照の関数を利用できることを意味します。

タグ識別が使えない場面

開発者が継承クラスの名前を知らない時ってありますよね。例えば、あるライブラリの設計者が、ユーザに対し、特定の関数をオーバーライドしたクラスの作成を要求することがあります。そんな時、仮想関数を利用すれば、ユーザはクラスの名前を自由に設定できますし、それを複数個作ることだって出来ます。
しかし、タグ識別による方法では、関数を呼び出す部分を実装するのに、あらかじめ子クラスの種類数、及びすべての子クラスのタグが定まっていなければなりません。従って、ユーザは決められた名前の子クラスしか作成できない上、呼びだされうるすべてのコンストラクタにおいてタグを設定する処理を書かなければなりません(暗黙に生成されるものも含めて)。

例えば、上で使用したnonvirtual.cppにおける子クラスSub1, Sub2の実装は以下のようになっています。

nonvirtual.cpp

class Sub1 : public Base {
  public:
    Sub1() : Base('1') {} // タグを設定

    void test() {
        for (int i = 0; i < 10; ++i) {
            val += mt() % 10; // 0から9までの乱数を加える
        }
    }
};  //! class Sub1

class Sub2 : public Base {
  public:
    Sub2() : Base('2') {} // タグを設定

    void test() {
        for (int i = 0; i < 10; ++i) {
            val -= mt() % 10; // 0から9までの乱数を引く
        }
    }
};  //! class Sub1

今回は性能の比較が目的だったのでコンストラクタは一つしか実装していませんが、実際の場面ではもっと多くのコンストラクタが呼び出されます。そのため、ユーザはそれらのすべてにタグを設定する処理を書かざるを得なくなり、腱鞘炎になるリスクは飛躍的に向上するでしょう(?)。

だからといって、ライブラリ開発者がタグ識別を拒む必要はありません。コードが長いなら、コードを生成してしまえばいいのです。
つまり、プログラムをビルドする際、コンパイル前に予めソースコードを改変して、タグを設定する処理、及び関数の呼び出し処理を自動的に追加します。

C++のメタ機能がより進化すれば、コンパイラだけですべて生成できるのかもしれませんが、今の段階では無理がありそうです。。。