Динамическая отправка - Dynamic dispatch

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

Объектно-ориентированные системы моделируют проблему как набор взаимодействующих объектов, выполняющих операции, указанные по имени. Полиморфизм - это явление, при котором несколько взаимозаменяемых объектов подвергаются одноименной операции, но, возможно, различаются по поведению. Например, объект File и объект Database имеют метод StoreRecord, который можно использовать для записи кадровой записи в хранилище. Их реализации различаются. Программа содержит ссылку на объект, который может быть либо объектом File, либо объектом базы данных . Что это может быть определено настройкой времени выполнения, и на этом этапе программа может не знать или не заботиться о том, что именно. Когда программа вызывает StoreRecord для объекта, что-то должно выбрать, какое поведение будет реализовано. Если рассматривать ООП как отправку сообщений объектам, то в этом примере программа отправляет сообщение StoreRecord объекту неизвестного типа, оставляя его системе поддержки времени выполнения для отправки сообщения нужному объекту. Объект реализует любое поведение, которое он реализует.

Динамическая отправка отличается от статической отправки , в которой реализация полиморфной операции выбирается во время компиляции . Цель динамической диспетчеризации - отложить выбор подходящей реализации до тех пор, пока не станет известен тип времени выполнения параметра (или нескольких параметров).

Динамическая отправка отличается от позднего связывания (также известного как динамическое связывание). Привязка имени связывает имя с операцией. Полиморфная операция имеет несколько реализаций, связанных с одним и тем же именем. Связывание может быть выполнено во время компиляции или (с поздним связыванием) во время выполнения. При динамической отправке во время выполнения выбирается одна конкретная реализация операции. В то время как динамическая отправка не подразумевает позднего связывания, позднее связывание подразумевает динамическую отправку, поскольку реализация операции с поздним связыванием неизвестна до времени выполнения.

Единичная и множественная отправка

Выбор версии метода для вызова может быть основан либо на одном объекте, либо на комбинации объектов. Первый называется однократной отправкой и напрямую поддерживается общими объектно-ориентированными языками, такими как Smalltalk , C ++ , Java , C # , Objective-C , Swift , JavaScript и Python . В этих и подобных языках можно вызвать метод деления с синтаксисом, похожим на

dividend.divide(divisor)  # dividend / divisor

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

Напротив, некоторые языки отправляют методы или функции на основе комбинации операндов; в случае деления типы делимого и делителя вместе определяют, какая операция деления будет выполнена. Это известно как множественная отправка . Примерами языков, поддерживающих множественную отправку, являются Common Lisp , Dylan и Julia .

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

Язык может быть реализован с различными механизмами динамической диспетчеризации. Выбор механизма динамической диспетчеризации, предлагаемый языком, в значительной степени изменяет парадигмы программирования, которые доступны или наиболее естественны для использования в данном языке.

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

Некоторые языки предлагают гибридный подход.

Динамическая отправка всегда будет сопряжена с накладными расходами, поэтому некоторые языки предлагают статическую отправку для определенных методов.

Реализация на C ++

C ++ использует раннее связывание и предлагает как динамическую, так и статическую отправку. Форма отправки по умолчанию - статическая. Чтобы получить динамическую отправку, программист должен объявить метод как виртуальный .

Компиляторы C ++ обычно реализуют динамическую отправку со структурой данных, называемой таблицей виртуальных функций (vtable), которая определяет сопоставление имени и реализации для данного класса как набор указателей на функции-члены. (Это чисто деталь реализации; в спецификации C ++ не упоминаются vtables.) Экземпляры этого типа затем сохранят указатель на эту таблицу как часть своих данных экземпляра. Это сложно при использовании множественного наследования . Поскольку C ++ не поддерживает позднее связывание, виртуальная таблица в объекте C ++ не может быть изменена во время выполнения, что ограничивает потенциальный набор целей отправки конечным набором, выбранным во время компиляции.

Перегрузка типов не приводит к динамической отправке в C ++, поскольку язык рассматривает типы параметров сообщения как часть формального имени сообщения. Это означает, что имя сообщения, которое видит программист, не является формальным именем, используемым для привязки.

Реализация Go и Rust

В Go и Rust используется более универсальный вариант раннего связывания. Указатели Vtable передаются со ссылками на объекты как «жирные указатели» («интерфейсы» в Go или «объекты признаков» в Rust).

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

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

Реализация Smalltalk

Smalltalk использует диспетчер сообщений на основе типов. Каждый экземпляр имеет единственный тип, определение которого содержит методы. Когда экземпляр получает сообщение, диспетчер ищет соответствующий метод в карте «сообщение-метод» для типа, а затем вызывает метод.

Поскольку тип может иметь цепочку базовых типов, этот поиск может быть дорогостоящим. Наивная реализация механизма Smalltalk, казалось бы, будет иметь значительно более высокие накладные расходы, чем у C ++, и эти накладные расходы будут возникать для каждого сообщения, которое получает объект.

Реальные реализации Smalltalk часто используют технику, известную как встроенное кэширование, которая делает отправку методов очень быстрой. Встроенное кэширование в основном сохраняет предыдущий адрес метода назначения и класс объекта сайта вызова (или несколько пар для многостороннего кэширования). Кэшированный метод инициализируется наиболее распространенным целевым методом (или просто обработчиком промахов кэша) на основе селектора метода. Когда во время выполнения достигается сайт вызова метода, он просто вызывает адрес в кеше. (В генераторе динамического кода этот вызов является прямым вызовом, поскольку прямой адрес исправляется логикой промаха кэша.) Затем код пролога в вызываемом методе сравнивает кэшированный класс с фактическим классом объекта, и если они не совпадают выполнение переходит к обработчику промахов кэша, чтобы найти правильный метод в классе. Быстрая реализация может иметь несколько записей в кеше, и часто требуется всего пара инструкций, чтобы заставить правильный метод выполнить при начальном промахе в кеше. Обычным случаем будет совпадение кэшированного класса, и выполнение будет просто продолжено в методе.

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

Поскольку Smalltalk является языком рефлексии, многие реализации позволяют преобразовывать отдельные объекты в объекты с помощью динамически генерируемых таблиц поиска методов. Это позволяет изменять поведение объекта для каждого объекта. Из этого выросла целая категория языков, известных как языки на основе прототипов , наиболее известными из которых являются Self и JavaScript . Тщательная разработка кэширования диспетчеризации методов позволяет даже языкам на основе прототипов иметь высокопроизводительную диспетчеризацию методов.

Многие другие языки с динамической типизацией, включая Python , Ruby , Objective-C и Groovy, используют аналогичные подходы.

Пример на Python

class Cat:
    def speak(self):
        print("Meow")

class Dog:
    def speak(self):
        print("Woof")


def speak(pet):
    # Dynamically dispatches the speak method
    # pet can either be an instance of Cat or Dog
    pet.speak()

cat = Cat()
speak(cat)
dog = Dog()
speak(dog)

Смотрите также

использованная литература

Библиография