・ Twitterにて
「CRTPによる多態が適用できる部分は仮想関数で書いても遅くはならない。何故なら型が静的解決できるから。」
僕がTwitterでこのような発言をしたところCryolite氏と議論になりました。
とりあえず検証してみる
コンパイルはg++ 4.3.2で最適化は-O3です。
※x86のアセンブラはop [dest],[src]が普通ですがgccはop [src],[dest]の形式で出力します。
・手始め
まず以下の簡単なソースを見てください。
※このソースはコンパイル＆実行できますが何の面白味もありません
※インスタンスを静的変数にしているのはアセンブラの出力をわかりやすくするためです。
volatile int global_value;
template<class T> class crtp_base {
public:
void method() { static_cast<T&>(*this).sub_method(); }
};
class vf_base {
public:
virtual void method() {}
};
class crtp_derived : public crtp_base<crtp_derived> {
public:
void sub_method() { global_value = 1; }
};
class vf_derived : public vf_base {
public:
void method() { global_value = 2; }
};
static crtp_derived crtp;
static vf_derived vf;
int main()
{
crtp.method();
vf.method();
}
このソースをコンパイルして出力されるmain関数のコンパイル結果は以下の通りです。
※以下アセンブラ出力は要点となる部分のみ抜粋しスタックフレームの生成等は割愛します。
movl $1, global_value
movl $2, global_value
インライン展開されてメソッド呼び出しすら発生しません。流石最近のコンパイラは賢いですね。
※global_valueをvolatileにしないと最適化により2を代入する行のみ出力されます。
・コンパイル単位が分かれたら？
Cryolite氏から
「コンパイル単位が分かれたらCRTPが有利になりませんか？」
との指摘もありました。
C++の場合JavaやC#とは違いクラスの宣言と実装を分離することが出来ます。むしろtemplateクラスで無ければ実装を分離して記述する場合の方が多いのではないかと思います。
実装を分離しメソッド呼出が別のコンパイル単位に対して発生する場合インライン展開ができなくなり前述の例の様な出力は期待できなくなります。そこで
派生クラスのmethod(crtp_derivedはsub_method)の実装を削除し外部に実装があるとみなさせます。
class crtp_derived : public crtp_base<crtp_derived> {
public:
void sub_method();
};
class vf_derived : public vf_base {
public:
void method();
};
このソースをにおけるmain関数のコンパイル結果は以下の通りです。
movl $_ZL4crtp, (%esp) crtp変数のアドレス(暗黙の引数this)
call _ZN12crtp_derived10sub_methodEv crtp_drived::sub_method呼出
movl $_ZL2vf, (%esp) vf変数のアドレス(暗黙の引数this)
call _ZN10vf_derived6methodEv vf_derived::method呼出
変数名・メソッド名共にマングリングされてわかりにくくなっていますがどちらも同等の出力結果が得られます。つまりCRTPと仮想関数の間にパフォーマンスの差は無いことになります。
・実装分離を考える
vf_base/vf_derived各クラスは問題なく全ての実装部分を分離することが可能です。容易にコンパイル単位を分けることが出来ます。
crtp_derivedクラスはtemplateクラスの派生クラスではありますが、crtp_derivedクラス自身はtemplateクラスではありませんし、基底クラスは型解決されたcrtp_baseなのでこちらも実装を分離することが可能です。
しかし、crtp_baseはtemplateクラスである以上exportをサポートしていないコンパイラではcrtp_baseクラスの宣言部に実装も記述する必要があります。つまりcrtp_baseは常にインライン展開される可能性を含んでいることになります。ですからcrtp_baseは今のままでその他のクラスを別コンパイル単位に置き換えた場合はCRTPが有利な場合も当然出てくるでしょう。但しこれでは条件が違ってしまいます。
※exportを使わずに実装分離するテクニックも無いわけじゃないですが割愛
・実装を分離した場合は果たして有利なのか？
ではCRTPにおいて実装を分離した場合を考えます。つまり今回の例であればcrtp_baseクラスの
void method() { static_cast<T&>(*this).sub_method(); }
このmethodの実装が仮にクラス宣言から分離されたとすると、crtp.method()呼出はインライン展開できなくなります。従って該当箇所ではcrtp_base::method()を呼び出すコードが出力されることになります。更にcrtp_base::methodとcrtp_derived::sub_methodの実装が同一コンパイル単位に無ければcrtp_base::mehtodはT::sub_methodを呼び出すコードを出力することになります。
つまりこの場合、２段のjmpもしくはcallが発生することになるわけです。こうなってしまうとヘタをすれば仮想関数呼出よりも遅くなる可能性があります。jmp/jmpならまだしもcall/callになってしまう場合はほぼ間違いなく仮想関数呼び出しより遅くなるでしょう。仮想関数の場合どれだけ派生したクラスの実装を呼び出すことになったとしても
1. thisポインタから仮想関数テーブルのアドレスを取得
2. 呼び出すメソッドのアドレスを取得
3. 仮想関数呼出
の３段階で済みます。
※菱形多重継承した場合アップキャストのコストが発生しますがここでは割愛。
・CRTPの方がパフォーマンスの良くなる場合
CRTPが有利に働くのは以下の様なケースです。
void call_method(crtp_derived& obj) { obj.method(); }
void call_method(vf_derived& obj) { obj.method(); }
上記の各関数をコンパイルした出力結果は以下の通りです。
void call_method(crtp_derived& obj) { obj.method(); }
jmp _ZN12crtp_derived10sub_methodEv
void call_method(vf_derived& obj) { obj.method(); }
movl (%eax), %edx
movl (%edx), %ecx
jmp *%ecx
このような場合は仮想関数による実装の方が遅くなります。
コンパイラはvf_derivedクラスの派生クラスが存在するか否か判断できません。コンパイル単位に全ての派生クラスの宣言が必ずあるという保証はないからです。
従って参照もしくはポインタ経由でメソッドを呼び出す場合は仮想関数テーブルを使わざるを得ません。もっともこの場合は静的型解決出来ない訳ですから前提条件から外れますが^^;
但しJavaのfinalのように派生を禁止することが出来るようになれば最適化可能でしょう。
・結論
コンパイラの最適化が強力であれば（実はこれが前提条件なのです）CRTPを使用した多態も仮想関数を使った多態も大差ない。
但し、CRTPの場合は当然静的型解決が出来ているのでどのような場合でもメソッドを直接呼び出すことが出来るが仮想関数を使った場合は静的型解決できない場合があるので、そのような場合は仮想関数テーブルを使わざるをえず結果としてパフォーマンスが落ちる場合がある。また、templateクラスの実装分離を行った場合は仮想関数よりむしろ速度低下する可能性もある。
しかし
CRTPが適用できる場合って静的型解決できるんだから、その場合って非仮想関数のみのクラスで問題ないんじゃない？という疑問も残った。
・余談
参照もしくはポインタを使用していても、それらの指すインスタンスが明らかな場合は最適化可能です。
vf_derived& vf_ref = vf;
vf_ref.method();
このような場合はvf_refの参照先がvf(vf_derived型の変数)であることがわかっているため仮想関数テーブルを参照せずに直接メソッドを呼び出す事が可能です。
※但しVC8では/Oxでも仮想関数テーブルを参照するコードが出力されました。
上述したcall_method関数の場合でも呼び出し元と実装が同一コンパイル単位に存在し、インライン展開可能である場合は同様です。
更に関数の引数を参照もしくはポインタではなく実体とした場合も最適化可能です。
void call_method(vf_derived obj);
この場合はobjの型がvf_derivedである事が保障されます。
・静的型解決できるはずなのに最適化されない場合
但し一見静的型解決が出来ているように見えてもそこまで最適化に頑張ってもらえない場合も存在します。この例は出水氏に指摘されたものです。
static vf_derived vf1;
static vf_derived vf2;
static vf_derived vf3;
このように同じ型の複数の変数があり、以下の様な実装で仮想関数を呼び出す場合
vf_derived* a;
if(global_value == 1) a = &vf1;
else if(global_value == 2) a = &vf2;
else a = &vf3;
a->method();
g++4.3.2では仮想関数テーブルを使うコードが出力されました。
但しこの例の場合aに代入されるポインタは必ずvf_derived型なのでより強力な最適化機能をもったコンパイラであれば仮想関数テーブルを参照しないコードが出力される可能性はあります。
※勿論aに代入されるポインタは必ずvf_derived型のインスタンスを指しており静的に解決できることが条件です。