Оценка накладных расходов

3.

Динамическое связывание и эффективность

Доступ к предшественнику процедуры

Явное переопределение

Обсуждение

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

Роль предложения redefine состоит в улучшении читаемости и надежности. Компиляторам, на самом деле, оно не нужно, так как в классе может быть лишь один компонент с данным именем, то объявленный в данном классе компонент, имеющий то же имя, что и компонент некоторого предка, может быть только переопределением этого компонента (или ошибкой).

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

Напомним правило использования конструкции Precursor (...): она может появляться только в переопределяемой версии процедуры.

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

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

Дело в том, что динамическое связывание требует несколько большего объема действий во время выполнения. Сравним вызов обычной процедуры в традиционном языке программирования (Pascal, Ada, C,...)

f (x, a, b, c...)

с ОО-формой

x.f (a, b, c...)

Разница между этими двумя формами уже была разъяснена при введении понятия класса, для идентификации типа модуля. Но сейчас мы понимаем, что это связано не только со стилем, имеется также различие и в семантике. В форме (1), какой именно компонент обозначает имя f известно статически во время компиляции или, в худшем случае, во время компоновки, если для объединения раздельно откомпилированных модулей используется компоновщик. Однако при динамическом связывании такая информация недоступна статически: для f в форме (2) выбор компонента зависит от объекта, к которому присоединен x во время конкретного выполнения. Каким будет этот тип нельзя (в общем случае) определить по тексту программы, это служит источником гибкости этого ранее разрекламированного механизма.

Предположим вначале, что динамическое связывание реализовано наивно. Во время выполнения хранится копия иерархии классов. Каждый объект содержит информацию о своем типе - вершине в этой иерархии. Чтобы интерпретировать во время выполнения x.f, окружение ищет соответствующую вершину и проверяет, содержит ли этот класс компонент f. Если да, то прекрасно, мы нашли то, что требовалось. Если нет, то переходим к вершине-родителю и повторяем всю операцию. Может потребоваться проделать путь до самого верхнего класса (или нескольких таких классов в случае множественного наследования).

В типизированном языке нахождение подходящего компонента гарантировано, но в нетипизированном языке, таком как Smalltalk, поиск может быть неудачным, и придется завершить выполнение диагнозом "сообщение не понято".Такая схема все еще применяется с различными оптимизациями во многих реализациях не статически типизированных языков. Она приводит к существенным затратам, снижающим эффективность. Хуже того, эти затраты не прогнозируемы и растут с увеличением глубины структуры наследования, так как алгоритм может постоянно проходить путь до корня иерархии наследования. Это приводит к конфликту между повторным использованием и эффективностью, поскольку упорная работа над повторным использованием м приводит к введению дополнительных уровней наследования. Представьте состояние бедного разработчика, который перед добавлением нового уровня наследования должен оценить, как это ударит по эффективности. Нельзя ставить разработчиков ПО перед таким выбором.

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

К счастью, использование статической типизации устраняет эти неприятности. При правильно построенной системе типов и алгоритмах компиляции нет никакой нужды перемещаться по структуре наследования во время выполнения. Для ОО-языка со статической типизацией возможные типы x не произвольны, а ограничены потомками исходного типа x, поэтому компилятор может упростить работу системы выполнения, построив массив структурных данных, содержащих всю необходимую информацию. При наличии этих структур данных накладные расходы на динамическое связывание сильно уменьшаются: они сводятся к вычислению индекса и доступу к массиву. Важно не только то, что такие затраты невелики, но и то, что они ограничены константой, и поэтому можно не беспокоиться о рассмотренной выше проблеме соотношения между переиспользуемостью и эффективностью. Будет ли структура наследования в вашей системе иметь глубину 2 или 20, будет ли в ней 100 классов или 10000, максимальные накладные расходы всегда одни и те же. Они не зависят и от того, является ли наследование единичным или множественным.

Открытие в 1985г. этого свойства, т.е. того, что даже при множественном наследовании можно реализовать вызов динамически связываемого компонента за константное время, было главным побудительным толчком к разработке проекта (среди прочего приведшего к появлению первого и настоящего изданий этой книги), направленного на построение современного окружения для разработки ПО, отталкивающегося от идей великолепно введенных языком Simula 67, распространенных затем на множественное наследование (длительный опыт применения Симулы показал, что непозволительно ограничиваться единичным наследованием), приведенных в соответствие с принципами современной программной инженерии и объединяющих эти идеи с самыми полезными результатами формальных подходов к спецификации, построению и верификации ПО. Создание эффективного механизма динамического связывания за константное время, которое на первый взгляд может показаться второстепенным среди указанного набора целей, на самом деле было настоятельно необходимым.

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

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

Для процедуры, которая ничего не делает, т. е. описана как p1 is do end, превышение времени динамического связывания над временем статического связывания (например, над эквивалентной процедурой на C) составляет около 30%.

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

p2 (a, b, c: INTEGER) is

local

x, y

do

x:= a; y:= b + c + 1; x:= x * y; p2

if x > y then x:= x + 1 else x:= x - 1 end

end

то накладные расходы падают до 15%. Для программы, выполняющей нечто более существенное (например, некоторый цикл) их доля совсем мала.

Дата добавления: 2014-01-07