Альтернативные реализации виртуального механизма?

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

Счастливый взлом!

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

Приветствия и hth.,

Ответ 5

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

Ответ 9

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

Ответ 10

Ответ Tony D правильно указывает, что компиляторам разрешено использовать анализ всей программы для замены вызова виртуальной функции статическим вызовом на реализацию уникальной возможной функции; или компилировать 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
}

Карел Дризен и Урс Хёльзл (Karel Driesen) и Урс Хёльзл (Karsl Driesen) и Урс Хёльзл (Karsl Driesen) и Урс Хёльзл (Karsl Driesen) и Урс Хёльзл (Karsl Driesen) и Урс Хёльзл (Karsl Driesen) "Прямая стоимость виртуальных вызовов функций на С++" . (PDF файл доступен бесплатно, если вы Google для него.) К сожалению, они сравнивают только отправку vtable и отличную статическую отправку; они не сравнивали его с отправкой двоичного дерева.

Они отметили, что на самом деле есть два типа vtables, когда вы говорите о языках (например, С++), которые поддерживают множественное наследование. При множественном наследовании, когда вы вызываете виртуальный метод, который унаследован от второго базового класса, вам нужно "исправить" указатель объекта, чтобы он указывал на экземпляр второго базового класса. Это смещение фиксации может быть сохранено как данные в таблице vtable, или оно может быть сохранено как код в "thunk". (Подробнее см. В документе.)

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

Ответ 11

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

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

Существует документ, связанный с SOM, Совместимость с двоичной версией Release-to-Release в SOM. Вы можете найти сравнение SOM с другими проектами, которые я мало знаю, например Delta/С++ и Sun OBI. Они решают подмножество проблем, которые SOM решает, и тем самым они также имеют несколько измененный код активации.

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

• Загрузите VAC 3.5 fixpak 9 из IBM FTP. Этот fixpak содержит много файлов, поэтому вам даже не нужен полный компилятор (у меня есть дистрибутив 3.5.7, но fixpak 9 был достаточно большим, чтобы выполнить некоторые тесты).
• Распаковать в e. г. C:\дом\октаграмма\DTS
• Запустите командную строку и выполните следующие команды там
• Запустить: установить SOMBASE = C:\home\OCTAGRAM\DTS\ibmcppw
• Запуск: C:\home\OCTAGRAM\DTS\ibmcppw\bin\SOMENV.BAT
• Выполнить: cd C:\home\OCTAGRAM\DTS\ibmcppw\samples\compiler\dts
• Запуск: nmake clean
• Запуск: nmake
• hhmain.exe и его dll находятся в разных каталогах, поэтому мы должны заставить их найти друг друга каким-то образом; поскольку я делал несколько экспериментов, я выполнил "set PATH =% PATH%; C:\home\OCTAGRAM\DTS\ibmcppw\samples\compiler\dts\xhmain\dtsdll" один раз, но вы можете просто скопировать dll рядом с hhmain. ехе
• Запуск: 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

}