Введение

Механизм поддержки динамической диспетчеризации

В компьютерном программировании виртуальная таблица методов (VMT), виртуальная таблица функций, виртуальная таблица вызовов, таблица диспетчеризации, vtable или vftable — это механизм, используемый в языке программирования для поддержки динамической диспетчеризации (или связывания метода во время выполнения). Каждый раз, когда класс определяет виртуальную функцию (или метод), большинство компиляторов добавляют скрытую переменную-член в класс, которая указывает на массив указателей на (виртуальные) функции, называемый виртуальной таблицей методов. Эти указатели используются во время выполнения для вызова соответствующих реализаций функций, поскольку во время компиляции может быть ещё неизвестно, будет ли вызвана базовая функция или производная, реализованная классом, наследующим от базового класса. Существует множество различных способов реализации такой динамической диспетчеризации, но использование виртуальных таблиц методов особенно распространено в C++ и связанных языках (таких как D и C#). Языки, которые отделяют программный интерфейс объектов от реализации, такие как Visual Basic и Delphi, также склонны использовать этот подход, поскольку он позволяет объектам использовать другую реализацию, просто используя другой набор указателей методов. Этот метод позволяет создавать внешние библиотеки, где другие техники, возможно, не подойдут. Предположим, программа содержит три класса в иерархии наследования: суперкласс, и два подкласса, . Если класс определяет виртуальную функцию с именем , то его подклассы могут предоставить соответствующую реализацию (например, или ). Когда программа вызывает функцию по ссылке (которая может указывать на экземпляр , или экземпляр ), код должен определить, к какой реализации функции следует направить вызов. Это зависит от фактического класса объекта, а не от класса ссылки на него. Класс обычно нельзя определить статически (то есть во время компиляции), поэтому компилятор не может решить, какую функцию вызывать в этот момент. Вызов должен быть направлен в правильную функцию динамически (то есть во время выполнения).

Реализация

Виртуальная таблица методов объекта содержит адреса динамически связанных методов этого объекта. Вызовы методов выполняются путем получения адреса метода из виртуальной таблицы методов объекта. Виртуальная таблица методов одинакова для всех объектов, принадлежащих одному и тому же классу, и поэтому обычно совместно используется ими. Объекты, принадлежащие к классам, совместимым по типу (например, дочерние классы в иерархии наследования), будут иметь виртуальные таблицы методов с одинаковой структурой: адрес данного метода будет находиться в одном и том же смещении для всех совместимых по типу классов. Таким образом, получение адреса метода по заданному смещению в виртуальной таблице методов позволит получить метод, соответствующий фактическому классу объекта. Стандарты C++ не предписывают конкретный способ реализации динамической диспетчеризации, но компиляторы обычно используют незначительные вариации одной и той же базовой модели. Как правило, компилятор создает отдельную виртуальную таблицу методов для каждого класса. При создании объекта, указатель на эту таблицу, называемый указателем виртуальной таблицы, vpointer или VPTR, добавляется как скрытый член этого объекта. Следовательно, компилятор также должен генерировать "скрытый" код в конструкторах каждого класса для инициализации указателя виртуальной таблицы нового объекта адресом виртуальной таблицы методов его класса. Многие компиляторы размещают указатель виртуальной таблицы в качестве последнего члена объекта, другие – в качестве первого; переносимый исходный код работает в обоих случаях. Например, g++ ранее размещал указатель в конце объекта.

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

Виртуальный вызов требует как минимум дополнительной индексированной дереференции и иногда операции "исправления", по сравнению с невиртуальным вызовом, который представляет собой просто переход к скомпилированному указателю. Поэтому вызов виртуальных функций по своей природе медленнее вызова невиртуальных функций. Эксперимент, проведенный в 1996 году, показал, что примерно 6–13% времени выполнения тратится исключительно на перенаправление вызова к нужной функции, хотя накладные расходы могут достигать 50%. Стоимость виртуальных функций может быть не столь значительной на современных архитектурах ЦП (центрального процессора) благодаря значительно большим кэшам и улучшенному предсказанию переходов. Кроме того, в средах, где не используется JIT-компиляция, вызовы виртуальных функций обычно нельзя встроить (inline). В некоторых случаях компилятор может выполнить процесс, известный как девиртуализация, при котором, например, поиск и косвенный вызов заменяются условным выполнением тела каждой встроенной функции, но такие оптимизации встречаются нечасто. Чтобы избежать этих накладных расходов, компиляторы обычно стараются не использовать виртуальные таблицы методов, когда вызов можно разрешить во время компиляции. Таким образом, вызов f1, описанный выше, может не требовать поиска в таблице, поскольку компилятор может определить, что в данной точке d может содержать только объект типа D, а D не переопределяет f1. Или компилятор (или оптимизатор) может обнаружить, что в программе нет подклассов B1, переопределяющих f1. Вызов B1::f1 или B2::f2, вероятно, также не потребует поиска в таблице, поскольку реализация указана явно (хотя все равно требуется "исправление" указателя "this").

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

Виртуальная таблица методов обычно представляет собой хорошее соотношение между производительностью и возможностью динамической диспетчеризации, но существуют альтернативы, такие как диспетчеризация по бинарному дереву, которая в некоторых типичных случаях обеспечивает более высокую производительность, но имеет другие компромиссы. Однако виртуальные таблицы методов позволяют выполнять только однократную диспетчеризацию на основе специального параметра "this", в отличие от многократной диспетчеризации (как в CLOS, Dylan или Julia), где типы всех параметров учитываются при выборе метода. Виртуальные таблицы методов также работают только в том случае, если диспетчеризация ограничена известным набором методов, что позволяет разместить их в простом массиве, построенном во время компиляции, в отличие от языков с динамической типизацией (таких как Smalltalk, Python или JavaScript). Языки, предоставляющие одну или обе эти возможности, часто выполняют диспетчеризацию путем поиска строки в хеш-таблице или другим эквивалентным способом. Существуют различные методы повышения скорости этого процесса (например, интернирование/токенизация имен методов, кэширование результатов поиска, JIT-компиляция).