Объектно-ориентированное программирование. Объектно-ориентированное программирование в действии. Объектноориентированное программирование
 Скачать 5.29 Mb.
|
|
Рис. 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 |