最初に

本記事はvtableについての知見をC++ベースで解説するものとなります。vtable自体はオブジェクト指向プログラミング言語においてポリモフィズムを実現するために必要な機能となっているので、ここで解説するものはJavaやC#などの初学者にも有用な知識かと思います。

また対象読者のスキル想定としては以下のようになります。

基本的なC++の構文を読むことができる。
基本的な継承の概念が理解できている。
動的ポリモフィズムが理解できている。
オフセットとは何かを理解している。

できるだけ初心者の方にもわかりやすいように書こうと思いますので、テーマとしてポイントとならないnullチェック等のコードは含みません。ご不明な点や理解が難しかった点、記事と事実が異なる点があれば下記連絡先までご一報ください。または単にこの記事に対してコメントをして頂く形でも構いません。どうぞ宜しくお願いします。

Twitter:@4_mio_11
Gmail :mio041100505@gmail.com

非ポリモーフィズムなクラスの継承

基本的なメモリレイアウト

仮想関数がないクラス又は構造体は、非staticメンバ変数が定義順にメモリに配置されます。
(アクセス指定子によってはコード上の見た目とメモリレイアウト順序が一致しないことがあります。)

class A { public: int a; int b; int c; };

上記の場合は、以下のようなメモリレイアウトとなります。

intメンバだけの多重継承例

非仮想且つ単純なintメンバだけを持つクラスで多重継承を行なった場合どうなるのか探っていきましょう。

では、以下のコードを見てください。

class A { public: int a; };
class B : public A { public: int b; };

class C : public B
{
    public:
        int c;
};

このようなクラス定義があったとして、C* cptr = new C;を行なった場合には、どのようなメモリの割り当てが行われるでしょうか。

実は、C++では継承したメンバ変数等におけるメモリ割り当ての順序は特に規定していません。

そのため、クラスCのオブジェクト構成が以下のようになることもあるかもしれません。

ただ、説明するのにちょっと面倒なので、定義順で表記を行います。

複雑なクラス表現を行うコンパイラでは、A, B, Cクラスの様に宣言されたクラスは、それぞれ自身のメンバ用の**「先頭アドレスからのオフセットテーブル」**を持っています。

つまり、Aにはint aのオフセットが入った表、Bにはint aとint bのオフセットが入った表、Cなら...

となります。

このため、cptrは、上記のオフセットテーブルへのポインタ＆クラスCのインスタンスへのポインタで構成されています。

関数を含む単純な多重継承例

単なる関数の場合は、コンパイラはコンパイル時とリンク時にその関数のアドレスを計算し、実行時にはその関数のアドレス(固定アドレス)を用いて関数を呼び出します。

以下のサンプルコードを見てみましょう。

class A { public: void HogeA(); // その他... };
class B { public: void HogeB(); // その他... };
class C : public A, public B { public: void HogeC(); };

C* cptr = new C;
cptr->HogeB();

この場合のC* cptr = new C;によるメモリ割り当て構成は以下のようになります。

もちろん先ほど記載した通り、継承した場合のメモリ割り当ては順序が決まっていないので、上の図の通りにはならないかもしれません。ただ、説明のために一旦上記の順番で構成されていると仮定します。

thisポインタはC* cptr時点では先頭にあります(図の矢印)。

さて、cptrからBクラスが実装しているHogeBを呼び出すためにはどのような処理が行われるのでしょうか。

クラスBが実装している関数を呼び出すためには、thisポインタをBのオブジェクト部分へ移動させて、クラスBのポインタを得る必要があります。そのためにクラスCが持つBのオフセットをcptrに足してあげましょう。このBのオフセットのことを**delta(B)**と呼びます。delta(B)はコンパイル時の定数として存在しています。

コンパイラはcptr->HogeB();を

((B*)((char*)pc+delta(B)))->HogeB();

という等価な呼び出しへと変換します。

この呼び出しコードからもわかるかもしれませんが、クラスCのポインタからクラスBのポインタへキャストする場合も同様にdelta(B)の加算を行います。逆にクラスBのポインタをクラスCにキャストする場合はthisポインタに対してdelta(B)を減算を行なって同オブジェクトのB部分を指します。つまり、キャストはオブジェクトの適切なオブジェクトを参照するポインタを呼び出すということです。

vtableとは

いよいよ本題です。

以下のサンプルコードをご覧ください。

class A { public: virtual void HogeA(); virtual void HogeB(); virtual HogeC(); };
class B : public A { public: void HogeB(); void HogeA(); int a; int b; };
class C : public A { public: void HogeC(); void HogeA(); };

void CallHogeA(A* aptr)
{
    aptr->HogeA();
}

クラスBとCはどちらもクラスAを継承していますね。

CallHogeAではクラスAのポインタを受け取り、そのポインタからHogeA()を呼んでいます。このHogeA()は仮想関数のため、aptrの指すオブジェクトがB型なのかC型なのかで異なる処理を行います。つまりオブジェクトの型に依存しているということです。

通常、この型に依存した関数の呼び出しを**「仮想関数テーブル(vtable)」**を使って解決しています。

C++では該当クラスに関連する仮想関数を関数ポインタとして実装し、それらのポインタをまとめたテーブルがvtableとなります。仮想関数の呼び出しはvtableを介した間接的な関数呼び出しとなります。

vtableは、1つ以上仮想関数を持っているクラスであれば必ずvtableも1つ持っています。また、そのクラスの全てのオブジェクトは、そのクラスのvtableを指すポインタ(vpointer,vptr)が先頭に暗黙で追加されます。

例として上記サンプルコードにおけるクラスBのオブジェクトを見てみましょう。

vtable内に関数ポインタが設定されてあるのがわかると思います。ここから、コンパイラによって間接呼び出しへ変換され、テーブル上の正しいスロットをindexで参照するコードになることで、実行時にどの関数を呼び出すかが決まります。

わかりやすい図を見つけたので引用の引用()させて貰います。更にvtableの構成の理解が深まるかと思います。
引用元：C++ の vptr, vtable

例えばaptr->HogeA();はコンパイラによって以下のように変換されます。

(*(aptr->vtpr[1]))(aptr);

仮想関数を持つクラスの多重継承

仮想関数をもつクラスを多重継承した場合は、もう少し複雑になります。

サンプルコードを見てみましょう。

class A { public: virtual void f(); };
class B { public: virtual void f(); virtual void g() };
class C : public A, public B { public void f(); };

C* cptr = new C;
A* aptr = cptr;
B* bptr = cptr;

cptr->f();
aptr->f();
bptr->f();

上記で呼び出されているf()は全てC::f()を起動します。つまり上記のオブジェクトが持つthisポインタはCオブジェクトの先頭を指しているはずです。

しかし以下のコードを見てみましょう。

void Hoge(B* pb)
{
    pb->f();
}

上記コードでは渡されているBのポインタが実際にはCオブジェクトなのか、それともBを継承した別のオブジェクトが渡されてくるのかはわかりません。このためdelta(B)は定数とすることができず、実行時にどのオブジェクトなのか判明した時点でdelta(B)を格納します。

このオフセットは仮想関数の呼び出し時にのみ使用されるので理論的に最良の格納位置はvtableの中となります。

struct vtbl_entry {
   void (*fct)();
   int delta;
};

ちなみにオフセットの型にintを使うとオブジェクトのサイズを制限することになりますが、多数のマシンではintは合理的サイズのあらゆるオブジェクトのオフセットを保持するのに十分な大きさを持っているため問題視されていません。

それでは、渡されたBのポインタからf()を実装するオブジェクトの先頭を見つけるためにはどうするべきでしょうか。例えば上記の例だとbptrから、Cのオブジェクト中に存在している、Bに関するvtblにて格納されているオフセットを、Bオブジェクトを指すthisポインタ(bptr)から減算してCの開始位置を発見しています。そこからメソッドを実装するオブジェクトの先頭へthisポインタを更に計算して移動させる必要がありますが、今回の場合では必要はありません。

クラスCのオブジェクト中の**「Bに関するvtable」と「Bが独自にもつvtable」**は異なっています。派生クラスのオブジェクトは派生クラスが第一基底クラスのvtableを共有できる場合以外は各基底クラスに対するvtableに加えて、基底クラスに対するvtableを必要とします。

そのため上の例だと、Cのオブジェクト中にはAと共有するvtableとBオブジェクト用のvtableの二つを含んでいることになります。これによって、CのオブジェクトはクラスA、クラスBどちらにもキャストが可能となります。

仮想関数のデメリット

ここまでで一通りの仕組みは学びました。これらを踏まえた上で、仮想関数を使用したデメリットを確認しましょう。

仮想関数保持クラスのインスタンスは自クラスのvtableへアクセスする用ポインタが暗黙で先頭に追加され、その分サイズも大きくなります（基本は4byteまたは8byte(処理系に依存)）。メモリに大きな制限があるプラットフォームで開発するなら注意が必要です。
vtableは仮想関数へのポインタのみを保持しています。仮想関数は非仮想関数と違い、仮想関数ごとに数byteのコストと僅かなパフォーマンスロスがあります。もちろん現代のハードウェアでの仮想関数のオーバーヘッドは非常に小さいため、普段は気にしなくても構いません。ただ、1フレームに何千回も呼び出されるような関数を仮想化するとすぐにオーバーヘッドが積み重なるので、その場合は普通の関数に置き換えが必要となります。
最適化を行う際に仮想関数の使用がボトルネックになっているかは、プロファイラの出力にホットスポットとして表れないため判定が難しいです。なので、最初からリスクを念頭に置いて設計しましょう。また仮想関数はインラインでの使用を想定をしてないためインラインで使うとパフォーマンスに大きな影響がでます。
vtableの影響はデータキャッシュにも及びます。1フレームの中で数多くのvtableのエントリを参照することになると、他のデータをキャッシュから弾き出したり、参照に必要なvtableがキャッシュに残らなくなる可能性があります。

デメリットをまとめてみましたが、最近のコンパイラは賢いので可能な限り高速に実行できるように都度検知と最適化をしてくれます。例えば以下のように、ポインタの型と実際のオブジェクトの型が一致している場合は最適化されます。

Enemy *enemy1 = new Boss;
// 仮想関数コスト発生
enemy1->Execute();

Boss *enemy2 = new Boss;
// 最適化されて非仮想関数と同様、関数を直接呼び出すためコストは発生しない
enemy2->Execute();

他言語での状況

C#、Javaでは、仮想メソッドが一つもなくても型情報を取得するためにvtable相当のものが生成されます。Javaではこのコストを避ける方法はありませんが、C#ではclassではなくstructを使用することでvtable分(4byte程度)をメモリ節約可能です。

最後に

いかがだったでしょうか。なかなかメモリレイアウト周りは情報が少なかったり、難しくてつまずいたりすることが多いと思いますが知っておくといざとなった時に幸せになれるかもしれません。静的ポリモフィズムに関してもいつか書きたいなぁと思いますがそれはいずれ…。とりあえずC++アドカレ遅刻してすいませんでした。

参考

C++リファレンスマニュアル(文献)
C++の設計と進化(文献)
ゲームプログラマのためのC++(文献)
[雑記] 仮想関数テーブル ++C++