Бадд Т. Объектно-ориентированное программирование
Подождите немного. Документ загружается.
представлении. Обычно пользователю никогда не требуется знать это имя, если только
нет необходимости анализировать ассемблерный код, созданный компилятором.
В языках программирования, подобных C++, позволяющих еще более перегружать
методы за счет снятия неоднозначности путем анализа типов аргументов, требуется более
сложное кодирование в стиле Гёделя1 с использованием имени класса, имени метода и
типов аргументов. Например, три конструктора класса Complex, описанные в предыдущих
главах, получат соответственно внутренние имена Complex::Complex,
Complex::Complex_float и Complex::Complex_float_float. Такие внутренние имена
называются кусочно-составными (mangled). Они бывают очень длинными. Как мы видели,
внутреннее имя не используется для пересылки сообщения; оно применяется только при
конструировании таблиц виртуальных методов с целью сделать имена уникальными для
редактора связей.
Множественное наследование несколько усложняет использование таблиц виртуальных
методов. Детали, однако, выходят за рамки данной книги. Заинтересовавшиеся читатели
могут найти более полное описание в [Ellis 1990].
21.2.5. Таблицы диспетчеризации
Поскольку языки программирования, подобные C++ и Object Pascal, являются языками со
статическими типами данных, они могут определить на этапе компиляции по крайней
мере тип родительского класса любого «объектного» выражения. Тем самым таблица
виртуальных методов должна быть ровно такой, чтобы вместить методы, реализованные
для класса. Для языков программирования с динамическими типами данных (вроде
Objective-C) таблица виртуальных методов обязана включать все сообщения, понимаемые
всеми классами, и она повторяется для каждого класса. К примеру, если приложение
содержит 20 классов и в среднем каждый класс использует 10 методов, то нам
требуется 20 таблиц, каждая из которых состоит из 200 записей. Требования к размеру
таблиц быстро становятся чрезмерными, и тогда возникает потребность в более удачном
подходе.
Рис. 21.5. Объект и его таблица диспетчеризации
Альтернативный подход состоит в том, чтобы связать с каждым классом таблицу, которая,
в отличие от таблицы виртуальных методов, состоит из пар «селектор/метод». Она
называется таблицей диспетчеризации. Селекторы соответствуют только тем методам,
которые фактически реализованы для данного класса. К наследуемым методам доступ
осуществляется через указатель из этой таблицы, который указывает на таблицу
диспетчеризации родительского класса (рис. 21.5).
Как и в системе с таблицами виртуальных методов, при использовании таблиц
диспетчеризации каждый объект содержит внутри себя неявный (то есть необъявленный)
PDF created with pdfFactory Pro trial version www.pdffactory.com
указатель на таблицу диспетчеризации, связанную с его классом. Этот неявный указатель
называется указателем связи isa (isa link) (не смешивать с условием «быть экземпляром»
(is-a relation) для классов). Пересылка сообщения в языке Objective-C вроде следующего
выражения из задачи о восьми ферзях
[neighbor checkrow: row column: column]
преобразуется компилятором языка Objective-C1 в код
objc_msgSend(neighbor, "checkrow:column:", row, column)
Функция objc_msgSend, называемая функцией пересылки сообщений, следует по
указателю связи isa для первого аргумента с тем, чтобы найти соответствующую таблицу
диспетчеризации. Затем функция пересылки сообщений просматривает таблицу
диспетчеризации в поисках записи, соответствующей селектору. Если такая запись
найдена, вызывается нужный метод. Если подобного метода не обнаружено, поиск
продолжается в таблице диспетчеризации надкласса. Если в конце концов достигнут
корневой класс Object, а метод так и не найден, выдается сообщение об ошибке этапа
выполнения.
Кэширование методов
Хотя для языков программирования с динамическими типами данных таблицы
диспетчеризации являются более экономичными по объему, чем таблицы виртуальных
методов, затраты времени на вызов метода значительно больше. Кроме того, эти затраты
пропорциональны глубине наследования. Если бы эти накладные расходы были
непреодолимы, то разработчики скорее отказались бы вообще от механизма наследования,
согласившись на потерю мощи ради выигрыша в эффективности.
К счастью, мы можем в значительной степени снизить эти потери во время выполнения
программы за счет следующего простого подхода. Будем хранить единую для всей
системы кэш-таблицу методов, к которым недавно осуществлялся доступ. Она
индексируется хэш-кодом
2
определяемым по селектору метода. Каждая запись в кэш-таблице представляет собой
тройку, состоящую из указателя на класс (для этой цели служит собственно таблица
диспетчеризации), значения селектора и указателя на метод.
Когда функцию пересылки сообщений просят найти метод, который соответствует паре
«класс–селектор», она прежде всего осуществляет поиск в кэш-таблице (рис. 21.6). Если
запись в кэше по месту расположения хэш-кода соответствует требуемым селектору и
классу, то соответствующий метод может быть выполнен немедленно. Если нет —
проводится процесс поиска, описанный выше. В результате поиска непосредственно перед
выполнением найденного метода происходит обновление кэш-таблицы. При этом запись,
содержавшаяся по месту соответствующего хэш-кода (рассчитываемому по селектору
2
Хэширование (hashing) — метод приближенного индексирования для сокращения поиска нужных данных.
При хэшировании каждому данному ставится в соответствие хэш-код (hash-code), который используется для
упорядочивания данных в хэш-таблице и служит селектором при их поиске. Характерная черта хэш-кода
состоит в том, что он, вообще говоря, не является уникальным (то есть различные данные могут порождать
при вычислениях одинаковый хэш-код). Однако он быстро вычисляется и позволяет значительно сократить
область поиска данных. Примером хэширования служит словарь с закладками по месту смены первой буквы
слов. Здесь первая буква слова выступает в качестве его хэш-кода. — Примеч. перев.
PDF created with pdfFactory Pro trial version www.pdffactory.com
сообщения), перезаписывается новыми данными. Обратите внимание, что значение класса
в кэше соответствует классу, с которого был начат поиск метода, а не классу, в котором
метод был в конце концов найден.
Рис. 21.6. Функция пересылки сообщения, проверяющая кэш таблицу
При надлежащем выборе функций вычисления хэш-кода и размера кэша можно достичь
частоты попадания в кэш около 90–95 процентов, что уменьшает накладные затраты на
передачу сообщения до уровня, лишь примерно в два раза большего, чем расходы на
стандартный вызов процедуры [Cox 1986]. Этот показатель вполне благоприятно
сравнивается с затратами при использовании таблиц виртуальных методов.
21.3. Интерпретаторы
Интерпретаторы обычно предпочтительнее компиляторов, когда изменчивость действий
программы превышает некоторый порог, приемлемый для фиксированного ассемблерного
кода. Изменчивость действий порождается разнообразными источниками. Например, для
языков с динамическими типами данных на этапе компиляции нельзя предсказать, к
какому типу данных будет относиться значение переменной (хотя язык Objective-
C служит примером языка программирования с динамическими типами данных, который
тем не менее, компилируется). Другой источник изменчивости возникает, если
пользователю позволено переопределять методы во время выполнения программы.
Подход, обычно используемый для интерпретаторов, — преобразовывать исходную
программу в «ассемблерный язык» высокого уровня, часто называемый байт-кодом,
поскольку обычно каждая инструкция закодирована в одном байте. На рис. 21.7 показан
байт-код системы Little Smalltalk. Старшие четыре бита используются для кодирования
операции, а младшие используются для указания номера операнда. Если требуются
номера операндов большие шестнадцати, применяется расширенная форма инструкции, и
последующий байт целиком содержит значение операнда. Немногие инструкции (типа
«послать сообщение» и некоторые специальные) требуют дополнительных байтов.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Рис. 21.7. Байт-код в системе Little Smalltalk
Сердцем интерпретатора является цикл, который охватывает огромный оператор
переключения switch (case, select и т. д.). Цикл считывает последовательные байт-коды, а
оператор выбора передает управление той цепочке кода, которая выполняет требуемое
действие. Мы не будем вдаваться в дискуссии о внутреннем представлении программы
(заинтересованные читатели могут обратиться к работе [Budd 1987]) и сконцентрируемся
исключительно на обработке передачи сообщений.
while (timeslice-- > 0)
{
high = nextByte(); // считать следующий байт-код
low = high & 0x0F; // выделить младшие 4 бита
high >>= 4; // сдвинуть старшие четыре бита
if (high == 0) // это расширенная форма?
{ // если так,
high = low; // код операции находится в low
low = nextByte(); // присвоить настоящий операнд
}
switch (high)
{
case PushInstance: ...
...
case PushArgument: ...
...
}
}
Подобно тому как все объекты в рассмотренных ранее компилируемых системах
содержали указатель на таблицу виртуальных методов, все объекты в системе Smalltalk
поддерживают указатель на свой класс. Разница состоит в том, что, как мы видели в
главе 20, класс сам по себе является объектом. Среди полей, содержащихся в объекте-
классе, есть набор всех методов, которые соответствуют сообщениям, распознаваемым
экземплярами класса (рис. 21.8). Другое поле указывает на надкласс этого класса.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Рис. 21.8. Внутренняя структура класса
Когда должно быть послано сообщение, интерпретатор обязан прежде всего определить
получателя. Через указатель на класс внутри получателя интерпретатор находит объект,
соответствующий классу получателя. Затем интерпретатор производит поиск в наборе
методов, стараясь найти тот, который соответствует пересылаемому сообщению. Если
такого метода не обнаружено, интерпретатор следует по цепочке наследования, проводя
поиск среди методов надклассов, пока либо подходящий метод не будет найден, либо
цепочка надклассов не будет исчерпана. В последнем случае интерпретатор сообщает об
ошибке. Это в точности та же последовательность действий, которая выполняеся
функцией пересылки сообщений при использовании таблиц диспетчеризации. Как и в
случае указанной техники, здесь может быть использовано кэширование для ускорения
процесса поиска метода.
Язык программирования Java использует подобный интерпретатор байт-кода, хотя
реальные коды отличаются от описанных выше.
Литература для дальнейшего чтения
Для читателя, заинтересованного в получении дополнительной информации по
реализации объектно-ориентированных языков, можно порекомендовать работу Кокса
[Cox 1986], содержащую детальный анализ затрат времени/памяти для различных схем
реализации. Реализация множественного наследования в C++ вкратце описана в работе
[Ellis 1990], которая основывается на более раннем алгоритме языка Simula
[Krogdahl 1985]. Детальное описание реализаций языка C++ приводится Липманом
[Lippman 1996].
Интерпретатор языка Smalltalk-80 описан в работе [Goldberg 1983]. Сборник [Krasner
1983] содержит несколько статей, которые описывают методы улучшения эффективности
системы Smalltalk-80. Упрощенный интерпретатор языка Smalltalk детально представлен в
работе [Budd 1987]. Камин [Kamin 1990] приводит хороший общий обзор приемов
реализации нетрадиционных языков программирования.
Упражнения
1. Как следует видоизменить метод таблиц диспетчеризации чтобы разрешить
множественное наследование?
2. Компилятор языка Objective-C допускает необязательные описания переменных
объекта. Объясните, как компилятор может использовать подобные описания для
ускорения обработки сообщений, включающих такие значения. Рассмотрите, что
происходит при операции присваивания и как пересылка сообщений может быть
сделана более эффективной.
PDF created with pdfFactory Pro trial version www.pdffactory.com
3. Объясните, почему методы, которые в языке C++ не описаны как виртуальные,
могут вызываться более эффективно, чем виртуальные методы. Как бы вы
произвели замеры времени, чтобы определить, является ли разница существенной?
4. Исследуйте технику кэширования, описанную в разделе 21.2. Объясните, почему
класс, запоминаемый в кэш-таблице, — это класс, с которого начинается поиск, а
не тот класс, внутри которого найден метод. Объясните, как бы изменился
алгоритм просмотра кэш-таблицы, если бы использовалось второе значение. Как
вы думаете, новый алгоритм будет работать быстрее или медленнее? Обоснуйте
свой ответ.
5. Опишите вкратце структуру интерпретатора языка Smalltalk, основанного на байт-
кодах, представленных в тексте.
PDF created with pdfFactory Pro trial version www.pdffactory.com