가상 메소드 테이블

가상 메소드 테이블(virtual method table, virtual function table, virtual call table, 디스패치 테이블, vtable, 또는 vftable)은 동적 디스패치(또는 런타임 메소드 바인딩)를 지원하기 위해 프로그래밍 언어에서 사용되는 메커니즘이다.
클래스가 가상 함수(또는 가상 메소드)을 정의할 때마다, 대부분의 컴파일러들은 클래스에 숨겨진 멤버 변수를 추가하는데, 이것은 (가상) 함수들에 대한 포인터들의 배열들(가상 메소드 테이블(VMT 또는 Vtable)라고 불리는)을 가리킨다. 이 포인터들은 실행 기간 도중에 정확한 함수를 가리키게 되는데, 왜냐하면 컴파일 타임에는 베이스 함수가 호출될 것인지 또는 베이스 클래스를 상속한 클래스에 의해서 구현될 지 알려져 있지 않기 때문이다.
프로그램이 상속 계층 구조의 여러 클래스들을 포함한다고 가정해보자. superclass인 Cat, 그리고 두 개의 하위 클래스인 HouseCat 그리고 Lion이 그것이다. Cat 클래스는 가상 함수의 이름을 speak로 정의하고, 이것의 하위 클래스들은 적절한 구현을 제공할 것이다. (예를 들면 meow 나 roar).
프로그램이 Cat 포인터의 speak 메소드를 호출한 경우 (이것은 Cat 클래스나 또는 Cat 하위 클래스를 가리킬 수 있다.), 호출하는 코드는 반드시 어떤 것을 구현할지를 결정해야 한다. (이것은 가리켜지는 객체의 실제 타입에 달려있다.) Cat 포인터에 의해 가리켜지는 객체의 타입이 컴파일 타임에 결정되지 않기 때문에, 어떤 것을 세팅할지는 컴파일 타임에 결정될 수 없다.
이러한 동적 디스패치를 구현하는 여러 다른 방법들이 있지만, vtable (virtual table) 솔루션은 특히 C++과 관련된 언어들에서 흔하다. 비주얼 베이직 또는 델파이처럼 구현 시 객체들의 프로그래매틱 인터페이스를 분리하는 언어들은 또한 vtable 접근을 사용하는 경향이 있다. 왜냐하면 이것은 단순히 다른 메소드 포인터들의 집합을 사용함으로써 객체들에게 다른 구현을 사용할 수 있게 하기 때문이다. 

구현

객체의 디스패치 테이블은 객체의 동적으로 바인딩된 메소드들의 주소들을 포함할 수 있다. 메소드 호출들은 객체의 디스패치 테이블에서 메소드의 주소를 꺼냄으로써 수행된다. 이 디스패치 테이블은 같은 클래스에 속한 모든 객체들에서 같으며, 그러므로 보통 그들 끼리는 공유된다. 타입 호환이 되는 클래스에 속한 객체들은 같은 레이아웃의 디스패치 테이블을 가질 것이다. 주어진 메소드의 주소는 모든 타입 호환이 되는 클래스의 같은 오프셋에 나타난다. 그래서 주어진 디스패치 테이블 오프셋에서 메소드의 주소를 꺼내오는 것은 객체의 실제 클래스와 상응하는 메소드를 갖게 되는 것이다.
C++ 표준은 꼭 구현되어야 할 동적 디스패치를 어떻게 할 것인지를 정확히 위임하지 않는다. 그러나 컴파일러들은 보통 같은 기본 모델에서 마이너 변수를 사용한다.
일반적으로, 컴파일러는 각 클래스에 분리된 vtable을 생성한다. 객체가 생성되면, 이 vtable에 대한 포인터 (virtual table pointer, vpointer 또는 VPTR)는 이 객체의 숨겨진 멤버로써 더해진다. 컴파일러는 또한 이 객체의 vpointer들을 vtable의 상응하는 주소로 초기화하기 위해 각 클래스의 생성자 안에 숨겨진 코드를 생성한다.
많은 컴파일러들은 vpointer를 객체의 마지막 멤버에 위치시킨다. 다른 컴파일러들은 객체의 첫 번째 멤버에 위치시키기도 한다. portable 소스 코드는 둘 중 한 방식으로 일한다. 예를 들면, g++은 미리 vpointer를 객체의 마지막에 위치시킨다.

예시

아래의 클래스 선언은 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:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;};
아래는 C++ 코드이다.
B2 *b2 = new B2();D  *d  = new D();
GCC의 g++ 3.4.6은 객체 b2를 위해 아래의 32비트 메모리 레이아웃을 생성한다.

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

virtual method table of B2:
  +0: B2::f2()   
그리고 아래는 객체  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

Total size: 20 Bytes.

virtual method table of D (for B1):
  +0: B1::f1()  // B1::f1() is not overridden

virtual method table of D (for B2):
  +0: D::f2()   // B2::f2() is overridden by D::f2()
그들의 선언에서 virtual 키워드를 갖지 않는 (f0()와 d() 같은) 이러한 함수들은 보통 vtable 안에 없다. 기본 생성자에 의한 생성 같은 특별한 경우를 위한 예외가 존재한다.
클래스 D에서 메소드 f2() 를 오버라이딩하는 것은 B2의 가상 메소드 테이블을 복사하고 포인터를 D::f2()에서 B2::fe()로 바꿈으로써 수행된다.

다중 상속과 thunks

g++ 컴파일러는 클래스 D에서 클래스 B1과 B2의 다중 상속을 두 가상 메소드 테이블을 사용함으로써 구현한다. (여러 다른 방법들이 있지만 이것이 가장 보통 방식이다.) 형 변환시 이것은 thunk의 필요성을 야기한다.
D  *d  = new D();B1 *b1 = static_cast<B1*>(d);B2 *b2 = static_cast<B2*>(d);
이 코드의 실행 이후 d 와 b1 이 같은 메모리 위치를 가리키는 동안, b2 는 d+8 (d 메모리 위치의 8바이트 너머) 위치를 가리킨다. 그래서 b2는 d 내부의 영역을 가리키며(이것은 B2의 인스턴스처럼 보인다.), B2의 인스턴스로서 같은 메모리 레이아웃을 가지게 된다.

호출

d->f1() 호출은 d의 D::B1 vpointer의 역참조에 의해 다루어지는데, vtable에서 f1 를 찾고, 코드를 호출하는 포인터를 역참조한다. 
단일 상속의 경우 (또는 오직 단일 상속만 있는 언어의 경우), 만약 vpointer가 항상 d의 첫 번째 요소라면(많은 컴파일러들 처럼), 이것은 아래의 pseudo-C++ 처럼 감소한다.
(*((*d)[0]))(d)
가상 메소드 테이블 D와 [0]을 나타내는 *d의 위치는 vtable 안의 첫 번째 메소드를 나타낸다. 파라미터 d는 이 객체의 This 포인터가 된다. 더 일반적인 경우, B1::f1() 또는 D::f2() 를 호출하는 것은 더 복잡하다.
(*(*(d[+0]/*pointer to virtual method table of D (for B1)*/)[0]))(d)   /* Call d->f1() */(*(*(d[+8]/*pointer to virtual method table of D (for B2)*/)[0]))(d+8) /* Call d->f2() */
d->f1() 호출은 B1 포인터를 파라미터로 패스한다. d->f2() 호출은 B2 포인터를 파라미터로 패스한다. 이 두 번째 호출은 정확한 포인터를 만들기 위해 fixup을 요구한다. D의 구현 당시 오버라이드되었기 때문에 B2::f2를 호출하는 것은 불가능하다. B2::f2의 위치는 D를 위한 vtable 안에 없다. 비교를 위해서, d->f0() 호출은 훨씬 간단하다.
(*B1::f0)(d)

효율성

가상 호출은 단순하게 컴파일된 포인터로 점프하는 일반 호출과 비교해서, 최소한 추가적인 색인화된 역참조와, 가끔은 "fixup" 추가를 필요로 한다. 그러므로 가상 함수를 호출하는 것은 본질적으로 일반 호출 함수보다 느리다. 
게다가 JIT 컴파일이 사용되지 않은 환경에서, 가상 함수 호출은 보통 인라인화될 수 없다. 
이런 오버헤드를 피하기 위해서, 컴파일러는 보통 vtable 사용을 피한다. 
그러므로 위의 f1 호출은 vtable 검사를 필요로 하지 않을 것이다. 왜냐하면 컴파일러는 이 시점에서  d가 오직  D를 가지고, D는 f1을 오버라이드하지 않는다는 것을 말할 수 있기 때문이다. 또는 컴파일러는 이 프로그램에서 f1을 오버라이드하는 B1의 하위 클래스는 없다고 탐지할 수 있다. 구현이 구체적으로 명시되기 때문에 B1::f1 또는 B2::f2 호출은 아마 vtable 검색을 요구하지 않을 것이다. (비록 아직도 'this'-pointer fixup을 요구하지만).
그러나 숙지해야 할 점은 가상 호출은 조건부 표현이라는 것이다. 만약 가상 호출이 상속 구조를 제거하면서 제거된다면, 그때는 코드 내에서 진단되기 위하여 어떤 함수를 호출해야 하는지를 결정하는 것이 요구된다. 이것은 코드의 각 위치에서 코드 진단을 요구한다.

대안과의 비교

vtable은 일반적으로 좋은 성능과 동적 디스패치 구현과의 트레이드오프이다. 그러나 대안들이 존재하는데, 더 높은 성능과 낮은 비용을 가진 바이너리 트리 디스패치가 그것이다.