仮想関数テーブル

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

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

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

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

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

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

vtable の実装

オブジェクトのディスパッチテーブルはオブジェクトの動的に束縛されるメソッドのアドレスを保持する。メソッドの呼び出しは、メソッドのアドレスをオブジェクトのディスパッチテーブルから取り出すことにより行われる。ディスパッチテーブルは同じクラスに属するオブジェクトでは全て同一であり、通常オブジェクトから共有される。互換性のある型のオブジェクト（継承関係において兄弟のもの）は同じレイアウトのディスパッチテーブルを持ち、あるメソッドのアドレスは、全ての型互換のクラスの中で常に同じオフセットに現れる。それゆえ、メソッドのアドレスをディスパッチテーブルから取り出すことで、オブジェクトの実際のクラスに対応したメソッドが得られる。

(Ellis & Stroustrup 1990, pp. 227–232)

C++ の標準では、動的なディスパッチがどのように実装されるべきかについて規定していないが、一般的にコンパイラは若干の変更を加えて共通の基本的なモデルを用いる。

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

例

下記のクラスの宣言は C++ の文法に従うものとする：

class B1
{
public:
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2
{
public:
  virtual void f2() {}
  int int_in_b2;
};

これらは下記のクラスを派生させる。

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 メモリレイアウトを生成する^{[注釈 1]}^{[注釈 2]}。

b2:
  +0: pointer to virtual method table of B2
  +4: value of int_in_b2

virtual method table of B2:
  +0: B2::f2()   
  +4: B2::~B2()

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

d:
  +0: pointer to virtual method table of D (for B1)
  +4: value of int_in_b1
  +8: pointer to virtual method table of D (for B2)
 +12: value of int_in_b2
 +16: value of int_in_d

virtual method table of D (for B1):
  +0: B1::f1()
  +4: D::~D()
  +8: D::d()
 +12: D::f2()

virtual method table of D (for B2):
  +0: D::d()
  +4: D::f2()   // B2::f2() is overridden by D::f2()
  +8: D::~D()

仮想でない関数（f0）は通常 vtable に現れないが、いくつかの例外もある（デフォルトコンストラクタなど）。

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

多重継承とthunk

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

下記のような C++ コードを考える:

D  *d  = new D();
B1 *b1 = dynamic_cast<B1*>(d);
B2 *b2 = dynamic_cast<B2*>(d);

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

呼び出し

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

単一継承（あるいは、単一継承のみ可能な言語）の場合、vpointer が常に d の最初の要素にあれば（多数のコンパイラでそうなっている）、下記のような擬似 C++ のコードに簡略化できる。

*((*d)[0])(d)

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

*((d->/* Dの(B1用の)仮想関数テーブルへのポインタ*/)[0])(d)
*((d->/* Dの(B1用の)仮想関数テーブルへのポインタ*/)[12])(d)
*((d->/* Dの(B2用の)仮想関数テーブルへのポインタ*/)[0])(d+8)

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

*B1::f0(d)

効率

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

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

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

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

比較、およびその他の方法

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

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

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

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

脚注

注釈

^ g++ の -fdump-class-hierarchy オプションで、仮想関数テーブルを出力して手動でチェックすることができる。
^ AIX の VisualAge XlC コンパイラでは -qdump_class_hierarchy を用いてクラスの階層構造と仮想関数テーブルのレイアウトを出力することができる。

出典

^ Driesen, Karel and Holzle, Urs, "The Direct Cost of Virtual Function Calls in C++", OOPSLA 1996
^ Zendra, Olivier and Driesen, Karel, Stress-testing Control Structures for Dynamic Dispatch in Java", Pp. 105?118, Proceedings of the USENIX 2nd Java Virtual Machine Research and Technology Symposium, 2002 (JVM '02)

参考文献

Margaret A. Ellis and Bjarne Stroustrup (1990) The Annotated C++ Reference Manual. Reading, MA: Addison-Wesley. (ISBN 0-201-51459-1)

[1] ++ の -fdump-class-hierarchy オプションで、仮想関数テーブルを出力して手動でチェックすることができる。

[2] AIX の VisualAge XlC コンパイラでは -qdump_class_hierarchy を用いてクラスの階層構造と仮想関数テーブルのレイアウトを出力することができる。

[3] Driesen, Karel and Holzle, Urs, "The Direct Cost of Virtual Function Calls in C++", OOPSLA 1996

[4] Zendra, Olivier and Driesen, Karel, Stress-testing Control Structures for Dynamic Dispatch in Java", Pp. 105?118, Proceedings of the USENIX 2nd Java Virtual Machine Research and Technology Symposium, 2002 (JVM '02)

[注釈 1]

[注釈 2]

[1]

[2]

vtable の実装

例

多重継承とthunk

呼び出し

効率

比較、およびその他の方法

脚注

注釈

出典

関連項目

参考文献