Таблица виртуальных методов

В компьютерном программировании таблица виртуальных методов ( VMT ), таблица виртуальных функций , таблица виртуальных вызовов , таблица диспетчеризации , vtable или vftable — это механизм, используемый в языке программирования для поддержки динамической диспетчеризации (или во время выполнения метода привязки ).

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

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

Предположим, программа содержит три класса в иерархии наследования: суперкласс , Кот , и два подкласса , ДомКот и Лев . Сорт Cat определяет виртуальную функцию с именем talk , поэтому его подклассы могут предоставить соответствующую реализацию (например, либо мяу или рев ). Когда программа вызывает разговора на функция Ссылка на Cat (которая может ссылаться на экземпляр Cat или экземпляр Домовой Кот или Lion ), код должен иметь возможность определять, в какую реализацию функции должен быть отправлен вызов . Это зависит от фактического класса объекта, а не от класса ссылки на него ( Кот ). Класс обычно не может быть определен статически (то есть во время компиляции ), поэтому компилятор также не может решить, какую функцию вызывать в этот момент. Вместо этого вызов должен быть перенаправлен на нужную функцию динамически (то есть во время выполнения ).

Выполнение

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

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

Обычно компилятор создает отдельную таблицу виртуальных методов для каждого класса. При создании объекта указатель на эту таблицу, называемый указателем виртуальной таблицы , vpointer или VPTR , добавляется в качестве скрытого члена этого объекта. Таким образом, компилятор также должен генерировать «скрытый» код в конструкторах каждого класса, чтобы инициализировать указатель виртуальной таблицы нового объекта по адресу таблицы виртуальных методов его класса.

Многие компиляторы помещают указатель виртуальной таблицы в качестве последнего члена объекта; другие составители ставят его первым; переносимый исходный код работает в любом случае. ^[3] Например, g++ ранее помещал указатель в конец объекта. ^[4]

Пример

Рассмотрим следующие объявления классов в синтаксисе C++ :

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

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

используется для получения следующего класса:

class D : public B1, public B2 {
public:
  void d() {}
  void f2() override {}
  int int_in_d;
};

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

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

g++ 3.4.6 из GCC создает следующую 32-битную структуру памяти для объекта. b2: ^{[номер 1]}

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()
                // The location of B2::f2 is not in the virtual method table for D

Обратите внимание, что эти функции не содержат ключевого слова virtual в своей декларации (например, fnonvirtual() и d()) обычно не отображаются в таблице виртуальных методов. Существуют исключения для особых случаев, заданных конструктором по умолчанию .

Также обратите внимание на виртуальные деструкторы в базовых классах. B1 и B2. Они необходимы для обеспечения delete d может освободить память не только для D, но и для B1 и B2, если d является указателем или ссылкой на типы B1 или B2. Они были исключены из макетов памяти, чтобы упростить пример. ^{[номер 2]}

Переопределение метода f2() в классе D реализуется путем дублирования таблицы виртуальных методов B2 и заменив указатель на B2::f2() с указателем на D::f2().

Множественное наследование и переходы

Компилятор g++ реализует множественное наследование классов. B1 и B2 в классе D используя две таблицы виртуальных методов, по одной для каждого базового класса. (Есть и другие способы реализации множественного наследования, но это наиболее распространенный.) Это приводит к необходимости «исправления указателя», также называемого thunks , при приведении типов .

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

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

Пока d и b1 будет указывать на ту же ячейку памяти после выполнения этого кода, b2 укажет на место d+8 (восемь байтов за пределами ячейки памяти d). Таким образом, b2 указывает на регион внутри d это "выглядит как" экземпляр B2, т. е. имеет ту же структуру памяти, что и экземпляр B2. ^{[ нужны разъяснения ]}

Призыв

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

Единое наследование

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

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

Где *d ссылается на таблицу виртуальных методов D и [0] ссылается на первый метод в таблице виртуальных методов. Параметр 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 указатель в качестве параметра. Этот второй вызов требует исправления для создания правильного указателя. Расположение B2::f2 отсутствует в таблице виртуальных методов для D.

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

(*B1::fnonvirtual)(d)

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

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

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

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

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

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

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

Однако таблицы виртуальных методов допускают только однократную отправку по специальному параметру «this», в отличие от множественной отправки (как в CLOS , Dylan или Julia ), где типы всех параметров могут быть приняты во внимание при диспетчеризации.

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

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

См. также

Примечания

^ G++ -fdump-class-hierarchy (начиная с версии 8: -fdump-lang-class) Аргумент можно использовать для вывода таблиц виртуальных методов для проверки вручную. Для компилятора AIX VisualAge XlC используйте -qdump_class_hierarchy для дампа иерархии классов и макета таблицы виртуальных функций.
^ «C++ — почему в виртуальной таблице два виртуальных деструктора и где находится адрес невиртуальной функции (gcc4.6.3)» .

Ссылки

Маргарет А. Эллис и Бьерн Страуструп (1990) Аннотированное справочное руководство по C++. Ридинг, Массачусетс: Аддисон-Уэсли. ( ISBN 0-201-51459-1 )

^ Перейти обратно: ^а ^б Зендра, Оливье; Колнет, Доминик; Коллин, Сюзанна (1997). Эффективная динамическая диспетчеризация без таблиц виртуальных функций: компилятор SmallEiffel - 12-я ежегодная конференция ACM SIGPLAN по системам, языкам и приложениям объектно-ориентированного программирования (OOPSLA'97), ACM SIGPLAN, октябрь 1997 г., Атланта, США. стр.125-141. инрия-00565627 . Центр компьютерных исследований научного кампуса Нэнси, здание ЛОРИЯ. п. 16.
^ Эллис и Страуструп 1990, стр. 227–232.
^ Дэнни Калев. «Справочное руководство по C++: Объектная модель II» . 2003. Рубрики «Наследование и полиморфизм» и «Множественное наследование».
^ «Закрытые проблемы C++ ABI» . Архивировано из оригинала 25 июля 2011 года . Проверено 17 июня 2011 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
^ Дрисен, Карел и Хёльцле, Урс, «Прямая стоимость вызовов виртуальных функций в C++» , OOPSLA, 1996 г.
^ Зендра, Оливье и Дрисен, Карел, «Структуры управления стресс-тестированием для динамического диспетчеризации в Java» , стр. 105–118, Материалы 2-го симпозиума USENIX по исследованиям и технологиям виртуальных машин Java, 2002 г. (JVM '02)

[5] G++ -fdump-class-hierarchy (начиная с версии 8: -fdump-lang-class) Аргумент можно использовать для вывода таблиц виртуальных методов для проверки вручную. Для компилятора AIX VisualAge XlC используйте -qdump_class_hierarchy для дампа иерархии классов и макета таблицы виртуальных функций.

[6] «C++ — почему в виртуальной таблице два виртуальных деструктора и где находится адрес невиртуальной функции (gcc4.6.3)» .

[inria-00565627-1] Перейти обратно: ^а ^б Зендра, Оливье; Колнет, Доминик; Коллин, Сюзанна (1997). Эффективная динамическая диспетчеризация без таблиц виртуальных функций: компилятор SmallEiffel - 12-я ежегодная конференция ACM SIGPLAN по системам, языкам и приложениям объектно-ориентированного программирования (OOPSLA'97), ACM SIGPLAN, октябрь 1997 г., Атланта, США. стр.125-141. инрия-00565627 . Центр компьютерных исследований научного кампуса Нэнси, здание ЛОРИЯ. п. 16.

[2] Эллис и Страуструп 1990, стр. 227–232.

[3] Дэнни Калев. «Справочное руководство по C++: Объектная модель II» . 2003. Рубрики «Наследование и полиморфизм» и «Множественное наследование».

[4] «Закрытые проблемы C++ ABI» . Архивировано из оригинала 25 июля 2011 года . Проверено 17 июня 2011 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[7] Дрисен, Карел и Хёльцле, Урс, «Прямая стоимость вызовов виртуальных функций в C++» , OOPSLA, 1996 г.

[8] Зендра, Оливье и Дрисен, Карел, «Структуры управления стресс-тестированием для динамического диспетчеризации в Java» , стр. 105–118, Материалы 2-го симпозиума USENIX по исследованиям и технологиям виртуальных машин Java, 2002 г. (JVM '02)

[1]

[2]

[3]

[4]

[номер 1]

[номер 2]

[5]

[6]