В информатике динамическая диспетчеризация — это процесс выбора реализации полиморфной операции ( метода или функции) для вызова во время выполнения . Она обычно используется и считается основной характеристикой языков и систем объектно-ориентированного программирования (ООП). [1]
Объектно-ориентированные системы моделируют проблему как набор взаимодействующих объектов, которые выполняют операции, ссылающиеся на имя. Полиморфизм — это явление, при котором несколько взаимозаменяемые объекты каждый из них выставляют операцию с тем же именем, но, возможно, отличающуюся поведением. Например, объект File и объект Database имеют метод StoreRecord , который может использоваться для записи записи о персонале в хранилище. Их реализации различаются. Программа содержит ссылку на объект, который может быть либо объектом File , либо объектом Database . Какой именно, может быть определено настройкой времени выполнения, и на этом этапе программа может не знать или не заботиться о том, какой именно. Когда программа вызывает StoreRecord для объекта, что-то должно выбрать, какое поведение будет выполнено. Если представить ООП как отправку сообщений объектам, то в этом примере программа отправляет сообщение StoreRecord объекту неизвестного типа, предоставляя системе поддержки времени выполнения отправку сообщения нужному объекту. Объект выполняет то поведение, которое он реализует. [2]
Динамическая диспетчеризация отличается от статической диспетчеризации , в которой реализация полиморфной операции выбирается во время компиляции . Цель динамической диспетчеризации — отложить выбор подходящей реализации до тех пор, пока не станет известен тип параметра (или нескольких параметров) во время выполнения.
Динамическая диспетчеризация отличается от позднего связывания (также известного как динамическое связывание). Связывание имени связывает имя с операцией. Полиморфная операция имеет несколько реализаций, все из которых связаны с одним и тем же именем. Связывания могут быть сделаны во время компиляции или (с поздним связыванием) во время выполнения. При динамической диспетчеризации одна конкретная реализация операции выбирается во время выполнения. В то время как динамическая диспетчеризация не подразумевает позднее связывание, позднее связывание подразумевает динамическую диспетчеризацию, поскольку реализация операции с поздним связыванием неизвестна до времени выполнения. [ необходима цитата ]
Выбор версии метода для вызова может быть основан либо на одном объекте, либо на комбинации объектов. Первый вариант называется одиночной диспетчеризацией и напрямую поддерживается распространенными объектно-ориентированными языками, такими как Smalltalk , C++ , Java , C# , Objective-C , Swift , JavaScript и Python . В этих и подобных языках можно вызвать метод для деления с синтаксисом, который напоминает
делимое . делить ( делитель ) # делимое / делительгде параметры необязательны. Это рассматривается как отправка сообщения с именем divide с параметром divisor в dividend . Реализация будет выбрана только на основе типа dividend (возможно, rational , floating point , matrix ), игнорируя тип или значение divisor .
Напротив, некоторые языки диспетчеризируют методы или функции на основе комбинации операндов; в случае деления типы делимого и делителя вместе определяют, какая операция деления будет выполнена. Это известно как множественная диспетчеризация . Примерами языков, которые поддерживают множественную диспетчеризацию, являются Common Lisp , Dylan и Julia .
Язык может быть реализован с различными механизмами динамической диспетчеризации. Выбор динамического механизма диспетчеризации, предлагаемого языком, в значительной степени изменяет парадигмы программирования, которые доступны или являются наиболее естественными для использования в данном языке.
Обычно в типизированном языке механизм отправки будет выполняться на основе типа аргументов (чаще всего на основе типа получателя сообщения). Языки со слабой или отсутствующей системой типизации часто содержат таблицу отправки как часть данных объекта для каждого объекта. Это позволяет реализовать поведение экземпляра , поскольку каждый экземпляр может сопоставлять данное сообщение с отдельным методом.
Некоторые языки предлагают гибридный подход.
Динамическая диспетчеризация всегда влечет за собой накладные расходы, поэтому некоторые языки предлагают статическую диспетчеризацию для определенных методов.
C++ использует раннее связывание и предлагает как динамическую, так и статическую диспетчеризацию. Форма диспетчеризации по умолчанию — статическая. Чтобы получить динамическую диспетчеризацию, программист должен объявить метод как virtual .
Компиляторы C++ обычно реализуют динамическую диспетчеризацию с помощью структуры данных, называемой таблицей виртуальных функций (vtable), которая определяет отображение имени в реализацию для данного класса как набор указателей функций-членов. Это чисто деталь реализации, поскольку спецификация C++ не упоминает vtables. Экземпляры этого типа затем будут хранить указатель на эту таблицу как часть своих данных экземпляра, усложняя сценарии при использовании множественного наследования . Поскольку C++ не поддерживает позднее связывание, виртуальная таблица в объекте C++ не может быть изменена во время выполнения, что ограничивает потенциальный набор целей диспетчеризации конечным набором, выбранным во время компиляции.
Перегрузка типов не приводит к динамической диспетчеризации в C++, поскольку язык считает типы параметров сообщения частью формального имени сообщения. Это означает, что имя сообщения, которое видит программист, не является формальным именем, используемым для связывания.
В Go , Rust и Nim используется более универсальный вариант раннего связывания. Указатели Vtable переносятся вместе со ссылками на объекты как «толстые указатели» («интерфейсы» в Go или «объекты-характеристики» в Rust [3] [4] ).
Это отделяет поддерживаемые интерфейсы от базовых структур данных. Каждая скомпилированная библиотека не должна знать весь спектр поддерживаемых интерфейсов, чтобы правильно использовать тип, а только конкретную схему vtable, которая им требуется. Код может передавать различные интерфейсы к одному и тому же фрагменту данных различным функциям. Эта универсальность достигается за счет дополнительных данных с каждой ссылкой на объект, что проблематично, если много таких ссылок хранятся постоянно.
Термин fat pointer просто относится к указателю с дополнительной связанной информацией. Дополнительная информация может быть указателем vtable для динамической диспетчеризации, описанной выше, но чаще всего это размер связанного объекта для описания, например, среза . [ необходима цитата ]
Smalltalk использует диспетчер сообщений на основе типов. Каждый экземпляр имеет один тип, определение которого содержит методы. Когда экземпляр получает сообщение, диспетчер ищет соответствующий метод в карте сообщений-методов для типа, а затем вызывает метод.
Поскольку тип может иметь цепочку базовых типов, этот поиск может быть дорогим. Наивная реализация механизма Smalltalk, по-видимому, имеет значительно более высокие накладные расходы, чем у C++, и эти накладные расходы будут возникать для каждого сообщения, которое получает объект.
Реальные реализации Smalltalk часто используют технику, известную как встроенное кэширование [5] , которая делает отправку методов очень быстрой. Встроенное кэширование в основном сохраняет предыдущий адрес метода назначения и класс объекта места вызова (или несколько пар для многостороннего кэширования). Кэшированный метод инициализируется наиболее распространенным целевым методом (или просто обработчиком промахов кэша) на основе селектора методов. Когда место вызова метода достигается во время выполнения, он просто вызывает адрес в кэше. (В динамическом генераторе кода этот вызов является прямым вызовом, поскольку прямой адрес обратно исправляется логикой промахов кэша.) Затем код пролога в вызываемом методе сравнивает кэшированный класс с фактическим классом объекта, и если они не совпадают, выполнение переходит к обработчику промахов кэша, чтобы найти правильный метод в классе. Быстрая реализация может иметь несколько записей кэша, и часто требуется всего несколько инструкций, чтобы выполнить выполнение правильного метода при начальном промахе кэша. Обычным случаем будет сопоставление кэшированного класса, и выполнение просто продолжится в методе.
Внеочередное кэширование также может использоваться в логике вызова метода, используя класс объекта и селектор метода. В одном из вариантов класс и селектор метода хэшируются и используются в качестве индекса в таблице кэша диспетчеризации метода.
Поскольку Smalltalk является рефлексивным языком, многие реализации позволяют мутировать отдельные объекты в объекты с динамически генерируемыми таблицами поиска методов. Это позволяет изменять поведение объектов на основе каждого объекта. Из этого выросла целая категория языков, известных как языки на основе прототипов , наиболее известные из которых — Self и JavaScript . Тщательная разработка кэширования диспетчеризации методов позволяет даже языкам на основе прототипов иметь высокопроизводительную диспетчеризацию методов.
Многие другие динамически типизированные языки, включая Python , Ruby , Objective-C и Groovy, используют схожие подходы.
класс Cat : def speak ( self ): print ( "Мяу" )класс Собака : def speak ( self ): print ( "Гав" )def speak ( pet ): # Динамически отправляет метод speak # pet может быть экземпляром Cat или Dog pet . speak ()кот = Кот () говорит ( кот ) собака = Собака () говорит ( собака )#include <iostream> // делаем Pet абстрактным виртуальным базовым классом class Pet { public : virtual void speak () = 0 ; }; class Dog : public Pet { public : void speak () override { std :: cout << "Гав! \n " ; } }; class Cat : public Pet { public : void speak () override { std :: cout << "Мяу! \n " ; } }; // speak() сможет принять все, что происходит от Pet void speak ( Pet & pet ) { pet . speak (); } int main () { Собака Фидо ; Кот Симба ; говорить ( Фидо ); говорить ( Симба ); вернуть 0 ; } Объекты-характеристики выполняют динамическую диспетчеризацию […] Когда мы используем объекты-характеристики, Rust должен использовать динамическую диспетчеризацию. Компилятор не знает всех типов, которые могут использоваться с кодом, использующим объекты-характеристики, поэтому он не знает, какой метод реализован на каком типе для вызова. Вместо этого во время выполнения Rust использует указатели внутри объекта-характеристики, чтобы узнать, какой метод вызывать. Этот поиск влечет за собой затраты времени выполнения, которые не возникают при статической диспетчеризации. Динамическая диспетчеризация также не позволяет компилятору выбирать встраивание кода метода, что, в свою очередь, предотвращает некоторые оптимизации.(xxix+1+527+3 страницы)
[…] Причина, по которой Geos требуется 16 прерываний, заключается в том, что схема используется для преобразования межсегментных ("far") вызовов функций в прерывания без изменения размера кода. Причина, по которой это делается, заключается в том, что "что-то" (ядро) может подключиться к каждому межсегментному вызову, сделанному приложением Geos, и убедиться, что правильные сегменты кода загружены из виртуальной памяти и заблокированы. В терминах DOS это можно сравнить с загрузчиком оверлея , но таким, который можно добавить, не требуя явной поддержки со стороны компилятора или приложения. Происходит что-то вроде этого: […] 1. Компилятор реального режима генерирует такую инструкцию: CALL <segment>:<offset> -> 9A <offflow><offhigh><seglow><seghigh>, где <seglow><seghigh> обычно определяется как адрес, который должен быть исправлен во время загрузки в зависимости от адреса, по которому был помещен код. […] 2. Компоновщик Geos превращает это во что-то другое: INT 8xh -> CD 8x […] DB <seghigh>,<offflow>,<offhigh> […] Обратите внимание, что это снова пять байтов, поэтому его можно исправить «на месте». Теперь проблема в том, что прерывание требует два байта, в то время как инструкция CALL FAR требует только один. В результате 32-битный вектор (<seg><ofs>) должен быть сжат до 24 бит. […] Это достигается двумя вещами: во-первых, адрес <seg> кодируется как «дескриптор» сегмента, чей младший полубайт всегда равен нулю. Это экономит четыре бита. Кроме того, […] оставшиеся четыре бита идут в младший полубайт вектора прерывания, таким образом создавая что-либо от INT 80h до 8Fh. […] Обработчик прерываний для всех этих векторов один и тот же. Он «распаковывает» адрес из трех с половиной байтовой нотации, ищет абсолютный адрес сегмента и перенаправляет вызов после того, как выполнит свою задачу по загрузке виртуальной памяти... Возврат из вызова также пройдет через соответствующий код разблокировки. […] Младший полубайт вектора прерывания (80h–8Fh) содержит биты с 4 по 7 дескриптора сегмента. Биты 0–3 дескриптора сегмента (по определению дескриптора Geos) всегда равны 0. […] все API Geos работают по схеме «наложения» […]: когда приложение Geos загружается в память, загрузчик автоматически заменяет вызовы функций в системных библиотеках соответствующими вызовами на основе INT. В любом случае, они не являются константами, а зависят от дескриптора, назначенного сегменту кода библиотеки.[…] Geos изначально планировалось перевести в защищенный режим на очень раннем этапе […], с реальным режимомбудучи всего лишь «устаревшим вариантом» […] почти каждая строка ассемблерного кода готова к этому […]
[…] в случае таких искаженных указателей […] много лет назад Аксель и я думали о том, как использовать *одну* точку входа в драйвер для нескольких векторов прерываний (так как это сэкономило бы нам много места для нескольких точек входа и более или менее идентичного кода кадрирования запуска/выхода во всех них), а затем переключиться на разные обработчики прерываний внутренне. Например: 1234h:0000h […] 1233h:0010h […] 1232h:0020h […] 1231h:0030h […] 1230h:0040h […] все указывают на одну и ту же точку входа. Если вы подключите INT 21h к 1234h:0000h и INT 2Fh к 1233h:0010h и так далее, они все пройдут через одну и ту же «лазейку», но вы все равно сможете различать их и переходить к разным обработчикам внутри. Подумайте о «сжатой» точке входа в заглушку A20 для загрузки HMA . Это работает до тех пор, пока ни одна программа не начнет выполнять магию сегмента: смещения. […] Сравните это с противоположным подходом, когда есть несколько точек входа (возможно, даже поддерживающих протокол IBM Interrupt Sharing Protocol ), который потребляет гораздо больше памяти, если вы подключите много прерываний. […] Мы пришли к выводу, что на практике это, скорее всего, не будет спасением, поскольку никогда не знаешь, нормализуют или денормализуют указатели другие драйверы, и по каким-либо причинам. […](Примечание. Что-то похожее на « толстые указатели », специально для сегмента реального режима Intel : адресация смещения на процессорах x86 , содержащее как намеренно денормализованный указатель на общую точку входа кода, так и некоторую информацию, позволяющую различать различные вызывающие объекты в общем коде. Хотя в открытой системе нормализацию указателей сторонними экземплярами (в других драйверах или приложениях) нельзя полностью исключить на общедоступных интерфейсах , эту схему можно безопасно использовать на внутренних интерфейсах, чтобы избежать избыточных последовательностей кода входа.)