Таблица виртуальных методов (MgQlneg fnjmrgl,ud] bymk;kf)

Таблица виртуальных методов (англ. virtual method table, VMT) — координирующая таблица или vtable — механизм, используемый в языках программирования для поддержки динамического соответствия (или метода позднего связывания).

Допустим, программа содержит несколько классов в иерархии наследования: базовый класс Cat и два подкласса DomesticCat и Lion. Класс Cat определяет виртуальную функцию speak, так что его подклассы могут обеспечивать соответствующую реализацию (т.е. «мяу» или «рык»).

Когда программа вызывает метод speak по указателю Cat (который может указывать на класс Cat или любой подкласс Cat), контекстное окружение (среда запуска) должна уметь определять, какая именно реализация вызывается, в зависимости от текущего типа указываемого объекта.

Существует множество различных способов реализации подобного динамического связывания, но решение при помощи виртуальной таблицы весьма распространено в C++ и родственных языках (как например, D и C#). Языки, в которых есть разделение на программный интерфейс объектов и их реализацию, как Visual Basic и Delphi, также склоняются к использованию аналогов виртуальной таблицы, так как это позволяет объектам использовать другую реализацию просто используя другой набор указателей метода.

Реализация

Координирующая таблица объекта содержит адреса динамически связанных методов объекта. Метод вызывается при выборке адреса метода из таблицы. Координирующая таблица будет той же самой для всех объектов, принадлежащих тому же классу, поэтому допускается её совместное использование. Объекты, принадлежащие классам, совместимым по типу (например, стоящие на одной ступени в иерархии наследования), будут иметь схожие координирующие таблицы: адрес данного метода зафиксируется с одним и тем же смещением для всех классов, совместимых по типу. Таким образом, выбирая адрес метода из данной координирующей таблицы смещением, получим метод, связанный с текущим классом объекта.^[1]

В стандартах C++ нет четкого определения как должна реализовываться динамическая координация, но компиляторы зачастую используют некоторые вариации одной и той же базовой модели.

Обычно компилятор создает отдельную виртуальную таблицу для каждого класса. После создания объекта указатель на эту виртуальную таблицу, называемый виртуальный табличный указатель или vpointer (также иногда называется vptr или vfptr), добавляется как скрытый член данного объекта (а зачастую как первый член). Компилятор также генерирует «скрытый» код в конструкторе каждого класса для инициализации 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:
  void d() {}
  void f2() {}  // переопределяем B2::f2()
  int int_in_d;
};

и следующий фрагмент C++ кода:

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

G++ 3.4.6 из набора GCC создает следующую 32-битную схему памяти для объекта b2 (здесь и далее ТВМ - таблица виртуальных методов):^{[nb 1]}

b2:
  +0: указатель на ТВМ B2
  +4: значение int_in_b2

ТВМ B2:
  +0: B2::f2()

а для объекта d схема памяти будет такой :

d:
  +0: указатель на ТВМ D (для B1)
  +4: значение int_in_b1
  +8: указатель на ТВМ D (для B2)
 +12: значение int_in_b2
 +16: значение int_in_d

Общий размер: 20 байтов.

ТВМ D (для B1):
  +0: B1::f1()  // B1::f1() не переопределён

ТВМ D (для B2):
  +0: D::f2()   // B2::f2() замещён D::f2()

Необходимо отметить, что невиртуальные функции (такие как f0) в общем случае не могут появляться в виртуальной таблице, но в некоторых случаях есть исключения (как, например, конструктор по умолчанию).

Переопределение метода f2() в классе D реализуется дублированием ТВМ B2 и заменой указателя на B2::f2() указателем на D::f2().

Множественное наследование

Множественное наследование классов B1 и B2 в класс D, используя две таблицы виртуальных методов, по одной для каждого базового класса. (Есть и другие способы реализации множественного наследования, но данный наиболее распространенный.) Это приводит к потребности в "указателях на адресную запись" (связках) при создании.

Рассмотрим следующий C++ код:

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

В то время как d и b1 указывают на одно место в памяти после выполнения данного кода, b2 будет указывать на участок памяти d+8 (смещение на восемь байт относительно участка d). Таким образом, b2 указывает на область памяти внутри d, что "выглядит" как сущность B2, т.е. имеет ту же схему размещения в памяти, что и сущность B2.

Вызов

Вызов d->f1() происходит при разыменовании vpointer D::B1 из d: просмотр записи о f1 в виртуальной таблице, а затем разыменование этого указателя вызывает код.

В случае одиночного наследования (или в случае языка с поддержкой только одиночного наследования), если vpointer всегда является первым элементом в d (как это происходит у многих компиляторов), то это решается следующим псевдо-C++ кодом:

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

В более общем случае, как упоминалось выше, вызов f1(), D::f2() и B2::f2() на d будет сложнее

*((d->/*указатель ТВМ D (для B1)*/)[0])(d)    // d->f1();
*((d->/*указатель ТВМ D (для B2)*/)[0])(d+8)  // d->f2();
*((/*адрес ТВМ B2 */)[0])(d+8)               // d->B2::f2();

Для сравнения, вызов d->f0() гораздо проще:

*B1::f0(d)

Эффективность

Виртуальный вызов требует как минимум дополнительно индексированного разыменования, а иногда дополнительной «адресной привязки» (fixup), схожей с невиртуальным вызовом, который является простым переходом к скомпилированному указателю. Поэтому вызов виртуальных функций по сути медленнее, чем вызов невиртуальных. Эксперимент, проведённый в 1996 году, показал, что примерно 6-13% времени выполнения тратится просто на поиск соответствующей функции, в то время как общий рост времени выполнения может достичь 50%^[2]. Стоимость использования виртуальных функций на современных архитектурах процессоров может быть не столь высока из-за наличия значительно больших кэшей и лучшего предсказания переходов.

В среде где JIT-компиляция не используется, вызовы виртуальных функций обычно не могут быть внутренними. В то время как компилятор может заменить просмотр и непрямой вызов, например, условным выполнением каждого внутреннего тела, подобная оптимизация не распространена.

Для избежания подобных потерь компиляторы обычно избегают использования виртуальных таблиц всегда, когда вызов может быть выполнен во время компиляции.

Таким образом, вышеприведеный вызов f1 может и не требовать просмотра виртуальной таблицы, так как компилятор может сообщить о том, что d может иметь в этой точке только D, а D не переопределяет f1. Или компилятор (как вариант, оптимизатор) может обнаружить отсутствие подклассов B1 в программе, переопределяющей f1. Вызов B1::f1 или B2::f2 вероятно не потребует просмотра виртуальной таблицы благодаря реализации, определенной явным образом (хотя все еще требуется привязка по указателю 'this').

Сравнение с альтернативами

Виртуальная таблица в общем случае жертвует производительностью для достижения динамического выбора, но существует множество альтернатив ей, как например, выбор по двоичному дереву, обладающий более высокой производительностью, но различной скоростью исполнения^[3].

Тем не менее, виртуальная таблица предусмотрена только для единичной диспетчеризации (single dispatch) по специальному параметру "this", в отличие от множественной диспетчеризации (multiple dispatch) (как в CLOS или Dylan), где типы всех параметров могут быть присвоены в ходе диспетчеризации.

Виртуальная таблица также работает только если диспетчеризация ограничена известным набором методов, поэтому множество виртуальных таблиц могут быть помещены в простой массив во время компиляции, в отличие от языков с поддержкой утиной типизации (например, Smalltalk, Python или JavaScript).

Языки, поддерживающие один или оба этих варианта, часто осуществляют диспетчеризацию при помощи поиска строки в хеш-таблице или другого эквивалентного метода. Существует довольно большое число уловок повысить скорость (например, токенизация имен методов, применение кэширования, JIT-компиляции), а время диспетчеризации часто не производит значимого влияния на общее время обработки, но несмотря на это, просмотр виртуальной таблицы заметно быстрее ^{ссылка?}. Виртуальную таблицу также проще реализовывать и отлаживать, а кроме того еще и ближе к "философии языка Си" нежели хеш-таблицы строк^{ссылка?}.

См. также

Примечания

↑ Аргумент G++ -fdump-class-hierarchy может быть использован для показа ТВМ (для "ручной" проверки. Для компилятора AIX VisualAge XlC используется -qdump_class_hierarchy для показа иерархии классов и схемы ТВФ.

Источники

↑ Ellis & Stroustrup 1990, pp. 227–232
↑ Driesen, Karel and Hölzle, Urs, "The Direct Cost of Virtual Function Calls in C++" Архивная копия от 10 августа 2017 на Wayback Machine, OOPSLA 1996
↑ Zendra, Olivier and Driesen, Karel, "Stress-testing Control Structures for Dynamic Dispatch in Java" Архивная копия от 27 сентября 2007 на Wayback Machine, 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) (англ.)
Лекция. Виртуальные функции и полиморфизм / Конспекты курса по C++ 2010/11, Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН
5.4.4. Таблица виртуальных функций (стр 43) / Объектно-ориентированное программирование (Учебное пособие). Шахгельдян К.И., ред. Александрова Л.И. Владивостокский государственный университет экономики и сервиса

[2] Аргумент G++ -fdump-class-hierarchy может быть использован для показа ТВМ (для "ручной" проверки. Для компилятора AIX VisualAge XlC используется -qdump_class_hierarchy для показа иерархии классов и схемы ТВФ.

[1] Ellis & Stroustrup 1990, pp. 227–232

[3] Driesen, Karel and Hölzle, Urs, "The Direct Cost of Virtual Function Calls in C++" Архивная копия от 10 августа 2017 на Wayback Machine, OOPSLA 1996

[4] Zendra, Olivier and Driesen, Karel, "Stress-testing Control Structures for Dynamic Dispatch in Java" Архивная копия от 27 сентября 2007 на Wayback Machine, Pp. 105–118, Proceedings of the USENIX 2nd Java Virtual Machine Research and Technology Symposium, 2002 (JVM '02)

[1]

[nb 1]

[2]

[3]