Альтернативные виртуальные функции вызывают реализации?

Неправда, что указатели vtable в объектах всегда наиболее эффективны. Мой компилятор для другого языка раньше использовал указатели в объектах по тем же причинам, но больше не использует: вместо этого он использует отдельную структуру данных, которая сопоставляет адрес объекта с требуемыми метаданными: в моей системе это информация формы для использования сборщиком мусора.

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

Фактический поиск выполняется чрезвычайно быстро, а требования к хранилищу очень скромны, потому что я использую лучшую структуру данных на планете: массивы Джуди.

Я также не знаю ни одного компилятора C++, использующего что-либо, кроме указателей vtable, но это не единственный способ. Фактически, семантика инициализации для классов с базами делает любую реализацию беспорядочной. Это связано с тем, что полный тип должен качаться по мере создания объекта. Как следствие этой семантики, сложные объекты примесей приводят к созданию массивных наборов виртуальных таблиц, больших объектов и медленной инициализации объектов. Это, вероятно, не столько следствие метода vtable, сколько необходимость рабски следовать требованию, чтобы тип подобъекта во время выполнения всегда был правильным. На самом деле нет веских причин для этого во время построения, поскольку конструкторы не являются методами и не могут разумно использовать виртуальную диспетчеризацию: мне это не так ясно для уничтожения, поскольку деструкторы являются реальными методами.

Насколько мне известно, все реализации C++ используют указатель vtable, хотя было бы довольно легко (и, возможно, не так уж плохо с точки зрения производительности, как вы могли бы подумать с учетом кешей) сохранить небольшой индекс типа в объекте (1-2 B) и впоследствии получите виртуальную таблицу и введите информацию с помощью поиска в небольшой таблице.

Другим интересным подходом может быть BIBOP (http://foldoc.org/BIBOP) — большой пакет страниц — хотя у него есть проблемы с C++. Идея: разместить на странице объекты одного типа. Получите указатель на дескриптор типа /vtable в верхней части страницы, просто отключив менее значимые биты указателя объекта. (Конечно, плохо работает для объектов в стеке!)

Другой другой подход заключается в кодировании тегов/индексов определенных типов в самих указателях объектов. Например, если по конструкции все объекты выровнены по 16 байтам, вы можете использовать 4 LSB, чтобы поместить туда тег 4-битного типа. (Не совсем достаточно.) Или (особенно для встроенных систем), если вы гарантированно неиспользуете более значащие биты в адресах, вы можете поместить туда больше битов тега и восстановить их с помощью сдвига и маски.

Хотя обе эти схемы интересны (и иногда используются) для других языковых реализаций, они проблематичны для C++. Определенная семантика C++, например, какие переопределения виртуальных функций базового класса вызываются во время построения и уничтожения объекта (базового класса), приводят вас к модели, в которой есть некоторое состояние в объекте, которое вы изменяете при вводе ctors/dtors базового класса.

Возможно, вам будет интересен мой старый учебник по реализации объектной модели Microsoft C++. http://www.openrce.org/articles/files/jangrayhood.pdf

Удачного взлома!

1. Я не думаю, что есть современные компиляторы с подходом, отличным от vptr/vtable. В самом деле, было бы трудно придумать что-то еще, что не было бы просто неэффективным.

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

   Если вас интересуют такие вещи, я настоятельно рекомендую прочитать Внутри объектной модели C++.

2. sizeof class зависит от компилятора. Если вам нужен переносимый код, не делайте никаких предположений.

Существуют ли какие-либо компиляторы, которые реализуют виртуальный механизм каким-либо другим способом, кроме виртуального указателя и механизма виртуальной таблицы? Насколько я видел, большинство (читай g++, Microsoft Visual Studio) реализуют его через виртуальную таблицу, механизм указателя. Итак, существуют ли вообще какие-либо другие реализации компилятора?

Все известные мне современные компиляторы используют механизм vtable.

Это возможная оптимизация, потому что в С++ выполняется статическая проверка типов.

В некоторых более динамичных языках вместо этого используется динамический поиск вверх по цепочке(ям) базовых классов, поиск реализации функции-члена, которая вызывается виртуально, начиная с самого производного класса объекта. Например, так это работало в оригинальном Smalltalk. А стандарт C++ описывает эффект виртуального вызова как если бы использовался такой поиск.

В Borland/Turbo Pascal в 1990-х годах такой динамический поиск использовался для поиска обработчиков оконных сообщений Windows API. И я думаю, возможно, то же самое в Borland C++. Это было дополнением к обычному механизму vtable, используемому исключительно для обработчиков сообщений.

Если он использовался в Borland/Turbo C++, я не могу вспомнить, тогда он был для поддержки языковых расширений, которые позволяли вам связывать идентификаторы сообщений с функциями обработчика сообщений.

Размер любого класса только с виртуальной функцией будет равен размеру указателя (vptr внутри this) на этот компилятор. Итак, учитывая, что сам механизм виртуальных ptr и tbl является реализацией компилятора, будет ли это утверждение, сделанное выше, всегда верным?

Формально нет (даже с учетом механизма vtable), это зависит от компилятора. Поскольку стандарт не требует механизма vtable, в нем ничего не говорится о размещении указателя vtable в каждом объекте. А другие правила позволяют компилятору свободно добавлять неиспользуемые байты в конец.

Но на практике возможно. ;-)

Однако это не то, на что вы должны полагаться или на что вам нужно полагаться. Но в другом направлении вы можете требовать это, например, если вы определяете ABI. Тогда любой компилятор, который этого не делает, просто не соответствует вашим требованиям.

Ура и чт.,

Существуют ли какие-либо компиляторы, которые реализуют виртуальный механизм каким-либо другим способом, кроме виртуального указателя и механизма виртуальной таблицы? Насколько я видел, большинство (читай g++, Microsoft Visual Studio) реализуют его через виртуальную таблицу, механизм указателя. Итак, существуют ли вообще какие-либо другие реализации компилятора?

Ничего из того, что я знаю об использовании компиляторов C++, хотя вам может быть интересно прочитать о Binary Tree Dispatch. Если вы заинтересованы в том, чтобы каким-либо образом использовать ожидания от виртуальных диспетчерских таблиц, вы должны знать, что компиляторы могут — если типы известны во время компиляции — иногда разрешать вызовы виртуальных функций во время компиляции, поэтому могут не обращаться к таблице.

Размер любого класса только с виртуальной функцией будет равен размеру указателя (vptr внутри this) на этот компилятор. Итак, учитывая, что сам механизм виртуальных ptr и tbl является реализацией компилятора, будет ли это утверждение, сделанное выше, всегда верным?

Предполагая отсутствие базовых классов с их собственными виртуальными членами и виртуальных базовых классов, это, скорее всего, будет правдой. Можно предусмотреть альтернативы, такие как анализ всей программы, выявляющий только один член в иерархии классов, и переключение на диспетчеризацию во время компиляции. Если требуется диспетчеризация во время выполнения, трудно представить, зачем какой-либо компилятор вводит дополнительную косвенность. Тем не менее, Стандарт намеренно не оговаривает эти вещи точно, чтобы реализации могли изменяться или изменяться в будущем.

Пытаясь представить альтернативную схему, я придумал следующее: Ответ Итрила. Насколько я знаю, ни один компилятор его не использует!

Учитывая достаточно большое виртуальное адресное пространство и гибкие процедуры выделения памяти ОС, new может размещать объекты разных типов в фиксированных, непересекающихся диапазонах адресов. Затем тип объекта можно было бы быстро вывести из его адреса с помощью операции сдвига вправо, а результат использовать для индексации таблицы виртуальных таблиц, таким образом сохраняя 1 указатель виртуальной таблицы на объект.

На первый взгляд может показаться, что в этой схеме возникают проблемы с объектами, размещенными в стеке, но с этим можно легко справиться:

1. Для каждого объекта, размещенного в стеке, компилятор добавляет код, который добавляет запись в глобальный массив из (address range, type) пар при создании объекта и удаляет запись при его уничтожении.
2. Диапазон адресов, составляющий стек, будет отображаться в одну виртуальную таблицу, содержащую большое количество преобразователей, которые считывают указатель this, сканируют массив, чтобы найти соответствующий тип (vptr) для объекта по этому адресу, и вызывают соответствующий метод в виртуальной таблице. указал на. (То есть 42-й преобразователь вызовет 42-й метод в vtable — если наибольшее количество виртуальных функций, используемых в любом классе, равно n, то требуется как минимум n переходников.)

Очевидно, что эта схема влечет за собой нетривиальные накладные расходы (не менее O(log n) для поиска) для вызовов виртуальных методов для объектов на основе стека. При отсутствии массивов или композиции (вмещения в другой объект) объектов на основе стека можно использовать более простой и быстрый подход, при котором vptr помещается в стек непосредственно перед объектом (обратите внимание, что он не считается частью стека). объекта и не влияет на его размер, измеренный sizeof). В этом случае преобразователи просто вычитают sizeof (vptr) из this, чтобы найти правильный vptr для использования, и пересылают, как и раньше.

IIRC Eiffel использует другой подход, и все переопределения метода в конечном итоге объединяются и компилируются по одному и тому же адресу с прологом, в котором проверяется тип объекта (поэтому каждый объект должен иметь идентификатор типа, но это не указатель на VMT). Это для C++ потребует, конечно, чтобы окончательная функция создавалась во время компоновки. Однако я не знаю ни одного компилятора C++, использующего этот подход.

1. Я никогда не слышал и не видел ни одного компилятора, использующего альтернативную реализацию. Причина популярности vtables заключается в том, что это не только самая эффективная реализация, но и самый простой дизайн и самая очевидная реализация.

2. Практически на любом компиляторе, который вы захотите использовать, это почти наверняка верно. Однако это не гарантировано и не всегда верно — вы не можете полагаться на это, даже если это почти всегда так. Ваш любимый компилятор также может изменить его выравнивание, увеличив его размер, для забавы, не сказав вам об этом. Из памяти он также может вставлять любую отладочную информацию и все, что ему нравится.

C++/CLI отличается от обоих предположений. Если вы определяете класс ref, он вообще не компилируется в машинный код; вместо этого компилятор компилирует его в управляемый код .NET. В промежуточном языке классы являются встроенной функцией, а набор виртуальных методов определяется в метаданных, а не в таблице методов.

Конкретная стратегия реализации макета и диспетчеризации объектов зависит от виртуальной машины. В Mono объект, содержащий только один виртуальный метод, не имеет размера одного указателя, а нуждается в двух указателях в Структура MonoObject; второй для синхронизации объекта. Поскольку это определяется реализацией, а также не очень полезно знать, sizeof не поддерживается для классов ref в C++/CLI.

Во-первых, было упомянуто проприетарное расширение Borland для C++, Dynamic Dispatch Virtual Tables (DDVT), и вы можете кое-что прочитать об этом в файле с именем DDISPATC.ZIP. У Borland Pascal были как виртуальные, так и динамические методы и Delphi представила еще один синтаксис "сообщения", похожий на динамический, но для сообщений. На данный момент я не уверен, что у Borland C++ такие же функции. Ни в Pascal, ни в Delphi не было множественного наследования, поэтому Borland C++ DDVT мог отличаться от Pascal или Delphi.

Во-вторых, в 1990-х и чуть раньше были эксперименты с разными объектными моделями, и Borland была не самой передовой. Лично я считаю, что закрытие IBM SOMobjects нанесло миру ущерб, от которого мы все до сих пор страдаем. Перед закрытием SOM ​​проводились эксперименты с компиляторами Direct-to-SOM C++. Таким образом, вместо способа вызова методов C++ используется SOM. Он во многом похож на C++ vtable, за несколькими исключениями. Во-первых, чтобы предотвратить проблему хрупкого базового класса, программы не используют смещения внутри vtable, потому что они не знают это смещение. Это может измениться, если базовый класс представит новые методы. Вместо этого вызывающие объекты вызывают преобразователь, созданный во время выполнения, который содержит эти знания в своем ассемблерном коде. И есть еще одно отличие. В C++ при использовании множественного наследования объект может содержать несколько VMT IIRC. В отличие от C++, каждый объект SOM имеет только один VMT, поэтому код отправки должен отличаться от «call dword ptr [VMT+offset]».

Существует документ, связанный с SOM, Двоичная совместимость между выпусками в SOM. Вы можете найти сравнение SOM с другими проектами, о которых я мало знаю, например Delta/C++ и Sun ОБИ. Они решают подмножество проблем, которые решает SOM, и при этом они также несколько подправили код вызова.

Недавно я нашел достаточно фрагмента компилятора Visual Age C++ v3.5 для Windows, чтобы заставить все работать и фактически коснуться его. Большинство пользователей вряд ли получат виртуальную машину OS/2 только для того, чтобы играть с DTS C++, но наличие компилятора Windows — это совсем другое дело. VAC v3.5 — первая и последняя версия, поддерживающая функцию Direct-to-SOM C++. VAC v3.6.5 и v4.0 не подходят.

1. Загрузите пакет исправлений 9 для VAC 3.5 с FTP-сервера IBM. Этот пакет исправлений содержит много файлов, поэтому вам даже не нужен полный компилятор (у меня дистрибутив 3.5.7, но пакет исправлений 9 был достаточно большим, чтобы провести некоторые тесты).
2. Распаковать в эл. г. C:\домой\ОКТАГРАММА\DTS
3. Запустите командную строку и выполните там последующие команды
4. Выполнить: set SOMBASE=C:\home\OCTAGRAM\DTS\ibmcppw
5. Выполнить: C:\home\OCTAGRAM\DTS\ibmcppw\bin\SOMENV.BAT
6. Выполнить: cd C:\home\OCTAGRAM\DTS\ibmcppw\samples\compiler\dts
7. Выполнить: nmake clean
8. Выполнить: Nmake
9. hhmain.exe и его dll находятся в разных каталогах, поэтому надо заставить их как-то найти друг друга; так как я проводил несколько экспериментов, я один раз выполнил "set PATH=%PATH%;C:\home\OCTAGRAM\DTS\ibmcppw\samples\compiler\dts\xhmain\dtsdll", но вы можете просто скопировать dll рядом с hhmain. EXE
10. Выполнить: hhmain.exe

У меня есть вывод таким образом:

Local anInfo->x = 5
Local anInfo->_get_x() = 5
Local anInfo->y = A
Local anInfo->_get_y() = B
{An instance of class info at address 0092E318

}

Ответ Тони Д. правильно указывает, что компиляторам разрешено использовать анализ всей программы для замены вызов виртуальной функции со статическим вызовом единственно возможной реализации функции; или скомпилировать obj->method() в эквивалент

if (auto frobj = dynamic_cast<FrequentlyOccurringType>(obj)) {
    frobj->FrequentlyOccurringType::method();  // static dispatch on hot path
} else {
    obj->method();  // vtable dispatch on cold path
}

Еще в 1996 году Карел Дризен и Урс Хёльцле написали действительно увлекательную статью, в которой они смоделировали эффект идеальной оптимизации всей программы для типичных приложений C++: "Прямая стоимость вызовов виртуальных функций в C++". (PDF-файл доступен бесплатно, если вы погуглите его.) К сожалению, они сравнивали диспетчеризацию vtable только с идеальной статической диспетчеризацией; они не сравнивали это с отправкой двоичного дерева.

Они действительно указали, что на самом деле существует два вида виртуальных таблиц, когда вы говорите о языках (таких как C++), поддерживающих множественное наследование. При множественном наследовании, когда вы вызываете виртуальный метод, унаследованный от второго базового класса, вам необходимо «исправить» указатель объекта, чтобы он указывал на экземпляр второго базового класса. Это смещение исправления может храниться как данные в виртуальной таблице или как код в «преобразователе». (Подробнее см. в документе.)

Я считаю, что все приличные компиляторы в наши дни используют преобразователи, но потребовалось 10 или 20 лет, чтобы проникновение на рынок достигло 100%.