Альтернативные реализации виртуального механизма? - PullRequest
48 голосов
/ 04 декабря 2010

C ++ поддерживает динамическое связывание через виртуальный механизм.Но, как я понимаю, виртуальный механизм - это деталь реализации компилятора, и стандарт просто определяет поведение того, что должно происходить при определенных сценариях.Большинство компиляторов реализуют виртуальный механизм через виртуальную таблицу и виртуальный указатель.И да, я знаю, как это работает, поэтому мой вопрос не о деталях реализации виртуальных указателей и таблиц.Мои вопросы:

  1. Существуют ли какие-либо компиляторы, которые реализуют Виртуальный механизм любым другим способом, кроме виртуального указателя и механизма виртуальной таблицы?Насколько я видел, большинство (читай g ++, Microsoft visual studio) реализуют это через виртуальную таблицу, механизм указателей.Итак, есть ли вообще какие-либо другие реализации компилятора?
  2. Размер sizeof любого класса с виртуальной функцией будет размером указателя (vptr внутри this) на этом компиляторе , С учетом того, что сам виртуальный механизм ptr и tbl является реализацией компилятора, будет ли это утверждение, которое я сделал выше, всегда верным?

Ответы [ 11 ]

21 голосов
/ 07 декабря 2010

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

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

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

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

7 голосов
/ 12 декабря 2010

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

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

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

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

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

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

5 голосов
/ 07 декабря 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 голосов
/ 12 декабря 2010

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

4 голосов
/ 12 декабря 2010

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

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

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

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

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

3 голосов
/ 09 декабря 2010

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

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

3 голосов
/ 07 декабря 2010

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

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

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

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

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

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

0 голосов
/ 07 декабря 2014

Во-первых, было упомянуто собственное расширение Borland для C ++, Dynamic Dispatch Virtual Table (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, потому что они не знают этого смещения. Это может измениться, если базовый класс вводит новые методы. Вместо этого вызывающие вызывают thunk, созданный во время выполнения, который имеет эти знания в коде сборки. И есть еще одно отличие. В C ++, когда используется множественное наследование, объект может содержать несколько VMT IIRC. В отличие от C ++, каждый объект SOM имеет только один VMT, поэтому код отправки должен отличаться от «call dword ptr [VMT + offset]».

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

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

  1. Скачать VAC 3.5 fixpak 9 с IBM FTP. Этот пакет FixPak содержит много файлов, поэтому вам даже не нужен полный компилятор (у меня есть дистрибутив 3.5.7, но пакет FixPak 9 был достаточно большим, чтобы выполнить некоторые тесты).
  2. Распаковать на эл. г. C: \ главная \ октаграмма \ * DTS * 1028
  3. Запустить командную строку и выполнить там следующие команды
  4. Выполнить: установить 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. ехе
  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

}
...