Віртуальна таблиця функцій віртуальна таблиця методів англ virtual method table VMT vtable механізм що використовується

Віртуальна таблиця функцій, віртуальна таблиця методів (англ. virtual method table, VMT, vtable) — механізм, що використовується реалізаціями мов програмування для підтримки динамічної диспетчеризації (або зв'язування методів під час виконання).

Припустимо, програма містить декілька класів в ієрархії спадкування: суперклас, Кіт, і два підкласи, ДомашнійКіт і Лев. Нехай клас Кіт визначає віртуальний метод з назвою звучати, тоді вже його підкласи можуть забезпечити підходящу реалізацію (нявкання або ревіння).

Коли програма викликає метод звучати у вказівника на Кіт (що вказує на об'єкт класу Кіт, або будь-якого його підкласу Кіт), середовище виконання має бути в змозі через дійсний тип об'єкта, на який вказує вказівник, визначити, яку саме реалізацію він має викликати.

Існує багато шляхів здійснення такої динамічної диспетчеризації, але рішення за допомогою віртуальної таблиці особливо вживане серед і споріднених мов (таких як D і C#). Мови, в яких відділяють програмний інтерфейс об'єкта від реалізації, такі як Visual Basic і Delphi, також тяжіють до використання аналогів віртуальних таблиць.

Реалізація

Віртуальна таблиця об'єкта буде містити адреси динамічно зв'язаних методів. Виклики методів здійснюються шляхом вибирання адреси методу з віртуальної таблиці об'єкта. Віртуальна таблиця одна й та сама для всіх об'єктів одного класу, і через це зазвичай спільно використовується ними. Об'єкти, що належать до класів, сумісних за типом (наприклад, що знаходяться на одній сходинці в ієрархії спадкування), будуть мати віртуальні таблиці з однаковим розміщенням: адреса даного віртуального методу буде знаходитись з одним і тим самим зсувом для всіх класів, сумісних за типом. Таким чином, при вибиранні адреси методу з даного зсуву віртуальної таблиці поверне метод відповідний дійсному класу об'єкта

Як правило компілятор створює окрему віртуальну таблицю для кожного класу. Коли об'єкт уже створений, вказівник на його віртуальну таблицю, який зветься вказівник віртуальної таблиці (англ. virtual table pointer або англ. vpointer), додається як прихований член цього об'єкта (зазвичай як перший член ). Компілятор також генерує «прихований» код в конструкторі кожного класу для ініціалізації цього вказівника свого об'єкта адресою відповідної віртуальної таблиці.

Приклади

Припустимо наступні визначення класів в синтаксисі С++:

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; };

і наступний шматок коду:

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

G++ 3.4.6 від GCC продукує наступне 32-бітове розміщення для об'єкта b2:

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()

Зауважте, що функції не позначені ключовим словом virtual в своїх визначеннях (так як f0() і d()) зазвичай не з'являються в віртуальній таблиці методів. Хоча бувають винятки для особливих випадків, наприклад, для конструктора за замовченням.

Заміщення методу f2() в класі D реалізовано повторенням віртуальної таблиці методів B2 і заміною вказівника на B2::f2() вказівником на D::f2().

Множинна спадковість і перехідники

Компілятор C++ здійснює множинну спадковість класів B1 і B2 в клас D із використанням двох таблиць віртуальних методів, одної для кожного базового класу. (Загалом багато способів забезпечення множинної спадковості, але це найпоширеніший.) Це призводить до необхідності коригування вказівників перехідниками при приведені типів.

Припустимо наступний C++ код:

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

Після виконання цього коду d і b1 будуть вказувати на одну адресу в пам'яті, а b2 буде вказувати на адресу d+8. Таким чином, b2 вказує на область пам'яті всередині d, яка виглядає як'` екземпляр B2, тобто, має таке саме роміщення в пам'яті як зразок B2.

Викликання

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

У випадку одинарного спадкування, якщо вказівник завжди перший елемент в d (як це і є в більшості компіляторів), то це згортається до наступного псевдо-C++:

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

Де *d посилається на таблицю віртуальних функцій D і [0] посилається на перший метод в таблиці. Параметр d стає вказівником «this» для об'єкта.

В загальнішому випадку, викликання B1::f1() і D::f2() складніше:

(*(*(d[+0]/*вказівник на таблицю віртуальних методів D (для B1)*/)[0]))(d) /* Call d->f1() */ (*(*(d[+8]/*вказівник на таблицю віртуальних методів D (для B2)*/)[0]))(d+8) /* Call d->f2() */

виклик d->f1() передає вказівник B1 як параметр. Виклик d->f2() передає вказівник B2 як параметр. Другий виклик вимагає коригування вказівника. Вказівник на B2::f2 знаходиться поза межами віртуальної таблиці для D.

Для порівняння, виклик d->f0() значно простіший:

(*B1::f0)(d)

Ефективність

Віртуальний виклик вимагає щонайменше додаткового індексованого розіменування та, іноді, коригування вказівника, порівняно з невіртуальним викликом, який є простим переходом за скомпільованим вказівником. Через це, виклик віртуальних функцій значно повільніший за виклик невіртуальних. Експерименти показують, що близько 6-13% часу виконання припадає на перехід до коректної функції, хоча верхня межа досягає 50%. Виклик віртуальних функцій може бути не таким дорогим на процесорах із сучасною архітектурою завдяки значно більшому кешу і кращому передбаченню переходів.

У середовищах де не використовується JIT-компіляція, виклики віртуальних функцій не можуть бути (англ. inline). Компілятор може замінити пошук і непрямий виклик на, наприклад, умовне виконання кожного тіла функції, але така оптимізація нерозповсюджена.

Для уникнення додаткових дій, компілятори зазвичай уникають використання таблиці віртуальних функцій коли виклик може бути розв'язаним під час компіляції.

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

Порівняння з альтернативами

Віртуальна таблиця зазвичай є компромісом з досить хорошою виробністю для досягнення динамічної диспетчеризації, але існують альтернативи, такі як диспетчеризація за двійковим деревом, з більшою виробністю, але різною швидкістю виконання.

Однак, віртуальні таблиці дозволяють одиничну диспетчеризацію (англ. single dispatch), за спеціальним параметром this, на відміну від множинної диспетчеризації (як в CLOS або Dylan), де тип параметра береться до уваги під час диспетчеризації.

Віртуальні таблиці працюють тільки коли диспетчеризація обмежена відомим набором методів, тобто вони можуть бути розміщені в простих масивах створених під час компіляції, на відміну від мов з качиною типізацією (англ. Duck typing), таких як Smalltalk, Python або JavaScript.

Мови, що підтримують один або обидва цих методи часто здійснюють диспетчеризацію через пошук рядка в хеш-таблиці, або іншим подібним методом. Існує багато вивертів, які дозволяють пришвидшити це (наприклад, токенізація імен методів, кешування результатів пошуку, JIT компіляція), і час диспетчеризації немає значного впливу на загальний час виконання, проте використання віртуальних таблиць вочевидь швидше. Їх також легше реалізовувати і зневаджувати, також вони ближче до «C стилю» ніж хеш-таблиці рядків

Зауважимо, що Objective-C 2.1 підтримує диспетчеризації за допомогою віртуальних таблиць під 64-бітовою Mac OS X 10.6+.

Примітки

Ellis & Stroustrup 1990, pp. 227—232
Heading "Multiple Inheritance". Архів оригіналу за 27 листопада 2012. Процитовано 11 вересня 2010.
Driesen, Karel and Hölzle, Urs, "The Direct Cost of Virtual Function Calls in C++" [Архівовано 2017-08-10 у Wayback Machine.], OOPSLA 1996
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)
http://arstechnica.com/apple/reviews/2009/08/mac-os-x-10-6.ars/5

G++'s -fdump-class-hierarchy аргумент може бути використаний з метою вивантаження таблиці віртуальних методів для ручної перевірки. У випадку компілятора AIX VisualAge XlC, використовуйте -qdump_class_hierarchy для вивантаження ієрархії класів і розміщення віртуальної таблиці.

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

[2] Heading "Multiple Inheritance". Архів оригіналу за 27 листопада 2012. Процитовано 11 вересня 2010.

[4] Driesen, Karel and Hölzle, Urs, "The Direct Cost of Virtual Function Calls in C++" [Архівовано 2017-08-10 у Wayback Machine.], OOPSLA 1996

[5] 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)

[6] ttp://arstechnica.com/apple/reviews/2009/08/mac-os-x-10-6.ars/5

[3] G++'s -fdump-class-hierarchy аргумент може бути використаний з метою вивантаження таблиці віртуальних методів для ручної перевірки. У випадку компілятора AIX VisualAge XlC, використовуйте -qdump_class_hierarchy для вивантаження ієрархії класів і розміщення віртуальної таблиці.