仮想関数テーブル

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

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

実用的なオブジェクトのインターフェイス実装と分離する言語(Visual BasicDelphi など)でも、オブジェクトが異なる関数ポインタのセットを用いるだけで異なる実装を用いることができるため、vtable による方法を用いる傾向にある。

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

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

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

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

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

呼び出し[編集]

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

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

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

より一般的なケースでは、上記のようなdf1()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 のみ保持しており、Df1 をオーバーライドしないことをコンパイラが判断できるため、vtable の検索は必要なくなる可能性がある。コンパイラ(あるいは最適化プログラム)はプログラム内に f1 をオーバーライドする B1 のサブクラスがないことを検出することができるかもしれない。実装が明示的に指定されているため(this ポインタの fixup が必要ではあるが) B1::f1 ないし B2::f2 はおそらく vtable の検索を必要とすることはない。

比較、およびその他の方法[編集]

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

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

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

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

関連項目[編集]

参考文献[編集]

  1. ^ Driesen, Karel and Holzle, Urs, "The Direct Cost of Virtual Function Calls in C++", OOPSLA 1996
  2. ^ 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)