仮想関数テーブル

仮想関数テーブルあるいはvtableは、プログラミング言語の実装において動的なポリモーフィズム、すなわち実行時のメソッドの束縛を実現するために用いられる機構である。

あるプログラムが、継承関係にある複数のクラスを持っているとする。たとえばスーパークラス Cat と二つのサブクラス HouseCat と Lion において、クラス Cat が speak という仮想関数を定義しており、サブクラスは適切な実装を行うものとする。

プログラムがspeakメソッドをCatへのポインタpに対して呼び出すと、実行環境は、pが指す実際のオブジェクトの種類に応じてどの実装を呼び出すかを決定しなければならない。

このような動的な割り当てを実現するには様々な方法があるが、C++および関連するプログラミング言語では、vtableによる方法が一般的である。

オブジェクトのインターフェイスを実装から分離する言語でも、異なるメソッドポインタの集合を用いるだけで、異なる実装をオブジェクトが使用できるため、vtable による方法を採用する傾向にある。

C言語はオブジェクト指向プログラミングの機能を言語仕様としてサポートしないが、関数ポインタを利用することで仮想関数を模倣することができる。

1. vtable の実装
-------------

オブジェクトのディスパッチテーブルはオブジェクトの動的に束縛されるメソッドのアドレスを保持する。メソッドの呼び出しは、メソッドのアドレスをオブジェクトのディスパッチテーブルから取り出すことにより行われる。ディスパッチテーブルは同じクラスに属するオブジェクトでは全て同一であり、通常オブジェクトから共有される。互換性のある型のオブジェクトは同じレイアウトのディスパッチテーブルを持ち、あるメソッドのアドレスは、全ての型互換のクラスの中で常に同じオフセットに現れる。それゆえ、メソッドのアドレスをディスパッチテーブルから取り出すことで、オブジェクトの実際のクラスに対応したメソッドが得られる。C++ の標準では、動的なディスパッチがどのように実装されるべきかについて規定していないが、一般的にコンパイラは若干の変更を加えて共通の基本的なモデルを用いる。

典型的には、コンパイラは個々のクラスごとに別の vtable を作成する。オブジェクトが生成される際、vtable へのポインタがオブジェクトの不可視のメンバーとして追加される。コンパイラはコンストラクタ内に"隠れた"コードを生成し、クラスのオブジェクトの vpointer が、対応する vtable のアドレスで初期化されるようにする。

2. 例
----

下記のクラスの宣言は C++ の文法に従うものとする： class B1 { public: void f0 {} virtual void f1 {} int int_in_b1; };

class B2 { public: virtual void f2 {} int int_in_b2; };<WtXmlEndTag /> これらは下記のクラスを派生させる。 class D : public B1, public B2 { public: virtual void d {} virtual void f2 {} // B2::f2 をオーバーライド int int_in_d; };

B2 *b2 = new B2; D *d = new D;

GNUコンパイラコレクション の g++ 3.4.6 は、オブジェクト b2 に対して下記の 32bit メモリレイアウトを生成するg++ の -fdump-class-hierarchy オプションで、仮想関数テーブルを出力して手動でチェックすることができる。}}AIX の VisualAge XlC コンパイラでは -qdump_class_hierarchy を用いてクラスの階層構造と仮想関数テーブルのレイアウトを出力することができる。}}。

オブジェクト d のメモリレイアウト:

仮想でない関数は通常 vtable に現れないが、いくつかの例外もある。

クラス D でメソッド f2 をオーバーライドしているが、これは B2の仮想関数テーブルを複製し、B2::f2 へのポインタを D::f2 へのポインタで置き換えることで実現されている。

3. 多重継承とthunk
-------------

g++ コンパイラはクラス D の B1 と B2 からの多重継承を、基底クラスごとに一つずつの、二つの仮想関数テーブルを用いて実現する。これにより、キャストの際 "pointer fixups"  が必要になる。

下記のような C++ コードを考える: D *d = new D; B1 *b1 = dynamic_cast<B1*>; B2 *b2 = dynamic_cast<B2*>;

d と b1 が実行時に同じメモリ位置を参照するが、b2 は d+8を示す。 そのため、b2 は d 内の B2 らしく見える領域、 すなわち B2 のインスタンスと同じメモリレイアウトを持つ部分を示す。

4. 呼び出し
-------

呼び出しの際には、d->f1 の呼び出しの際は、d の D::B1 vpointer をたどり、vtable から f1 のエントリーを調べ、ポインタを取り出してコードを呼び出す。

単一継承の場合、vpointer が常に d の最初の要素にあれば、下記のような擬似 C++ のコードに簡略化できる。

[0])<WtXmlEndTag />

より一般的なケースでは、上記のようなdの f1、D::f2、B2::f2 呼び出しはより複雑なものとなる。

仮想関数テーブルへのポインタ*/)[0])
仮想関数テーブルへのポインタ*/)[12])
仮想関数テーブルへのポインタ*/)[0])<WtXmlEndTag />

これに対して、d->f0 の呼び出しはもっと単純である：

B1::f0<WtXmlEndTag />

5. 効率
-----

単なるコンパイルされたポインタへのジャンプである非仮想関数の呼び出しに対して、仮想関数の呼び出しは最低一度以上、余分にポインタをたどる操作や"fixup" が必要である。そのため、仮想関数の呼び出しは原理的に非仮想の関数呼び出しに対して低速である。実験によれば 6-13% の実行時間が単なる関数のディスパッチに用いられ、オーバーヘッドは場合によって 50% に達する。

さらに、 JIT コンパイルが使用できない環境では、仮想関数は通常インライン展開できない。テーブルの参照を行う部分を、たとえばインライン化された本体部分を条件文で実行させることも可能ではあるが、そうした最適化は一般的ではない。

オーバーヘッドを避けるため、コンパイラはコンパイル時に呼び出しが解決できる場合には vtable の生成を行わない。

従って、上記の f1 の呼び出しは、 d が現時点で D のみ保持しており、D が f1 をオーバーライドしないことをコンパイラが判断できるため、vtable の検索は必要なくなる可能性がある。コンパイラはプログラム内に f1 をオーバーライドする B1 のサブクラスがないことを検出することができるかもしれない。実装が明示的に指定されているためB1::f1 または B2::f2 はおそらく vtable の検索を必要とすることはない。

6. 比較、およびその他の方法
---------------

vtable は一般的に動的なディスパッチを実現するための、性能上のよいトレードオフであるが、たとえば二分木ディスパッチといった代替の方法も存在する。

しかし、vtable は特殊な "this" パラメータでは single dispatch のみ考慮しており、ディスパッチの際全てのパラメータの型が考慮される多重ディスパッチとは異なる。

vtables はまた、コンパイル時に単一の配列にメソッドを配置するため、ディスパッチが既知のメソッドのセットに限定されている場合のみうまく動作する。これはダック・タイピング言語とは対照的である。

上記の一つまたは両方をサポートする言語は、ディスパッチをハッシュテーブルの文字列検索や同等の手段で行うことが多い。ディスパッチを高速化する様々な方法があり、ディスパッチの時間は全体的な処理時間にそれほどの影響を与えない。それでもなお、vtable の検索の方が明らかに高速である。また vtable は実装やデバッグが簡単で、文字列のハッシュテーブルよりも"Cの精神"に近い。

7. 脚注
-----

7.1. 注釈
-------

7.2. 出典
-------

8. 関連項目
-------

仮想継承

9. 参考文献
-------

Margaret A. Ellis and Bjarne Stroustrup  The Annotated C++ Reference Manual. Reading, MA: Addison-Wesley.