6. Аспектно-ориентированное программирование
Аспектно-ориентированное программирование (АОП) — парадигма программирования, основанная на идее разделения функциональности для улучшения разбиения программы на модули. Методология аспектно-ориентированного программирования была предложена группой инженеров исследовательского центра Xerox PARC под руководством Грегора Кичалеса (Gregor Kiczales). Ими же был разработан аспектно-ориентированное расширение для языка Java, получившее название AspectJ — (2001 год).
Существующие парадигмы программирования, такие как процедурное, модульное и объектно-ориентированное программирование, предоставляют определённые способы для разделения и выделения функциональности (функции, классы, модули), но некоторую функциональность с помощью предложенных методов невозможно выделить в отдельные сущности. Такую функциональность называют сквозной ( scattered, разбросанная или tangled, переплетённая), так как её реализация рассыпана по различным модулям программы. Сквозная функциональность приводит к рассредоточенному и запутанному коду, сложному для понимания и сопровождения.
Все языки АОП предоставляют средства для выделения сквозной функциональности в отдельную сущность. Так как AspectJ является родоначальником этого направления, используемые в этом расширении концепции распространились на большинство языков АОП. Основные понятия АОП:
Аспект ( aspect) — модуль или класс, реализующий сквозную функциональность. Аспект изменяет поведение остального кода, применяя совет в точках соединения, определённых некоторым срезом.
Совет ( advice) — средство оформления кода, который должен быть вызван из точки соединения. Совет может быть выполнен до, после или вместо точки соединения.
Точка соединения ( join point) — точка в выполняемой программе, где следует применить совет. Многие реализации АОП позволяют использовать вызовы методов и обращения к полям объекта в качестве точек соединения.
Срез ( pointcut) — набор точек соединения. Срез определяет, подходит ли данная точка соединения к данному совету. Самые удобные реализации АОП используют для определения срезов синтаксис основного языка (например, в AspectJ применяются Java-cигнатуры) и позволяют их повторное использование с помощью переименования и комбинирования.
Внедрение ( introduction, введение) — изменение структуры класса и/или изменение иерархии наследования для добавления функциональности аспекта в инородный код. Обычно реализуется с помощью некоторого метаобъектного протокола ( metaobject protocol, MOP).
Ведение лога и обработка ошибок — типичные примеры сквозной функциональности. Другие примеры: трассировка; авторизация и проверка прав доступа; контрактное программирование (в частности, проверка пред- и постусловий). Для программы, написанной в парадигме ООП, любая функциональность, по которой не была проведена декомпозиция, является сквозной.
Однако как утверждают некоторые авторы, АОП может успешно применяться и для решения задач защиты, многопоточности, управления транзакциями и многих других.
Контрольные вопросы
Дайте понятие парадигмы программирования.
Может ли язык программирования поддерживать сразу несколько парадигм?
Охарактеризуйте процедурное программирование?
Охарактеризуйте функциональное программирование?
В чем особенность логического программирования?
Что такое автоматное программирование?
В чем особенность объектно-ориентированного программирования (ООП)?
Какой язык был первым в ООП и когда он появился?
Какое понятие является важнейшим в ООП?
Поясните основные принципы ООП?
Перечислите родственные ООП методологии.
От какого принципа отказались в прототипном программировании?
Какие особенности ООП приводят к снижению производительности программных систем?
Охарактеризуйте обязательный набор синтаксических средств объектно-ориентированного языка программирования.
В чем заключается аспектно-ориентированное программирование?
Глава 12. Эффективность и оптимизация программ
1. Общие понятия эффективности
Основной задачей программирования является создание правильных, а не эффективных программ. Эффективная программа не нужна, если она не обеспечивает правильных результатов. Это правило Ван Тассела. Эффективная, но неправильная программа редко может быть сделана правильной, в то время как правильную, хотя и неэффективную программу можно оптимизировать и сделать эффективной. Поэтому оптимизация является вторым этапом программирования. Первый этап — получение правильной программы.
Наиболее разумный подход к программированию заключается в создании программы наилучшим возможным способом, не уделяя особого внимания эффективности. Затем, если
программа в таком виде пригодна,
если она нужна для работы,
если ее будут выполнять многократно и
если статус проекта и фирмы позволяет,
тогда и только тогда следует рассмотреть возможность ее оптимизации.
Обычно большая часть времени расходуется на выполнение очень небольшой части программы (<
5% ее объема), называемой критической областью. Как правило, только критическая область объектной программы оптимизируется программистом вручную. Погоня за эффективностью часто ведет к злоупотреблению. Замечено, что программисты тратят огромное количество времени, думая и беспокоясь о работе некритических областей программы. Современные компьютеры отличаются высоким быстродействием и очень мала разница во времени выполнения программы, если некоторые, редко выполняемые операторы удается сделать эффективными. Экономию можно получить только за счет многократно выполняемых циклов.
Некоторые программисты считают архаичной задачу написания эффективной программы. Это справедливо только в отношении небольших программ, для выполнения которых используются машины с высоким быстродействием и большим объемом памяти. Что же касается больших программ, то еще на стадии проектирования определяются требуемые параметры, включающие время и емкость памяти. Для экономических задач емкость памяти часто более критичный параметр, чем время. Создатель системного программного обеспечения должен установить необходимые объем памяти и производительность каждого модуля, особенно при создании больших программных проектов. Требования к эффективности программы определяются на стадии проектирования.
Существуют три типа программ, и для каждого из них эффективность должна быть различной.
К первому типу относятся часто используемые программы. Это операционные системы, компиляторы, прикладные подпрограммы и системы резервирования авиабилетов. Для этих программ эффективность является первостепенной задачей вследствие их частого использования и специфического выполнения.
Второй тип составляют производственные программы, используемые длительное время. Этот тип программ пишут профессиональные программисты. Хотя эффективность таких программ существенна, обычно еще больше внимания уделяют их эксплуатационным характеристикам.
Третий тип программ—программы, созданные не программистами, а научными работниками или администраторами. Время для этих людей важнее всего. Здесь эффективность имеет значение только для программ, которые должны уместиться в заданном объеме памяти и выполняться за приемлемое время.
Следовательно, еще до написания программы необходимо установить, насколько эффективной она должна быть. Очевидно, что следует модифицировать только те программы, которые выполняются многократно. Программисты, «экономящие на спичках», сокращают на 10 мкс время выполнения редко используемой программы, затрачивая при этом 2 ч на программирование и много минут на компилирование и тестирование. Очевидно, что в этом случае вы ничего не сэкономите. Зато, как и при любом изменении программы, можете добавить в нее ошибки. Однако человеческая натура такова, что эффективность программ всегда будет вызывать интерес.
Многие методы, делающие программу эффективной, не наносят ущерба ее удобочитаемости. Эти методы следует использовать всегда. Но некоторые меры по повышению эффективности могут быть просто вредными для получения удобочитаемой программы. Удобочитаемость программы более существенна, чем ее эффективность. Дело в том, что удобочитаемую программу легче отлаживать, модифицировать и использовать. А всякую большую программу обычно изменяет, модифицирует и применяет совсем не тот человек, который ее писал. Лишь в особых случаях программу следует делать более эффективной: программа: либо не помещается в памяти, либо слишком долго выполняется. Или же программа должна быть включена в библиотеку и часто использоваться. В этом случае эффективность становится очень важным фактором и ей отдают предпочтение в ущерб удобочитаемости.
2. Оптимизирующие компиляторы
Эффективность важна на двух стадиях разработки программы: компилирования и выполнения. Если компилятор работает быстро, то он обычно составляет программу, которая выполняется медленно. Компиляторы, создающие эффективную объектную программу, обычно бывают большими и работают медленно, так как оптимизируют объектную программу.
Некоторые современные компиляторы позволяют пользователю выбрать ресурс, который нужно оптимизировать. Пользователь может потребовать, чтобы был минимизирован размер памяти, необходимый для выполнения программы, либо время выполнения. Оптимизация одного ресурса выполняется за счет другого.
К сожалению, об увеличении скорости компилирования можно сказать немного. Некоторые программные ухищрения могут сократить время компилирования, но они либо тривиальны, либо сильно зависят от компилятора. Методы, дающие положительный результат при использовании в одном компиляторе, не дают тех же улучшений в другом компиляторе. Некоторые компиляторы работают более эффективно, если длины имен переменных распределены равномерно. Другие компиляторы более эффективны, если метки операторов равномерно распределены по последнему символу. Естественно, что исключение неиспользуемых меток и выражений также уменьшает время компилирования любого компилятора. Наличие меток препятствует некоторым типам оптимизации, поэтому неиспользуемые метки ухудшают эффективность объектной программы. При повторном прогоне программы следует исправить все ошибки в исходной программе, а число предупреждающих диагностических сообщений должно минимизироваться каждый раз, когда это возможно.
Описанные методы оптимизации не зависят от машины и применяемого языка и пригодны для оптимизации времени выполнения и минимизации объема памяти компилируемых программ. Эти методы машинно-независимы, так как улучшения, сделанные в программе с их помощью, приведут к ускорению работы программы на разных машинах. Методы не зависят от языка (за исключением методов, специфичных для определенного языка) в том смысле, что они применимы в общем случае для языков высокого уровня. Некоторые из этих методов при их реализации на одних машинах будут давать более заметные результаты, чем на других. Даже различные модели одной и той же машины могут иметь разные наборы команд ассемблера, которые обусловят заметную разницу в оптимизации.
Некоторые компиляторы оптимизируют выполнение программы. Имеются два типа такой оптимизации: машинно-зависимая и машинно-независимая.
К первому типу относятся способы, результат применения которых зависит от используемой машины. Как правило, эти способы оптимизации обычно не известны или не понятны программистам на уровне входного языка. Они состоят из способов обработки индексов, назначения регистров и анализа машинных команд.
Второй тип оптимизации — машинно-независимая оптимизация,— которая выполняется на уровне входного языка. Хотя компилятор может оптимизировать программу, но обычно у программиста большие возможности для этого. Многие способы оптимизации может сделать только программист, так как они требуют знания логики программы. Некоторые способы оптимизации, выполняемые компилятором, могли бы быть применены, но не реализуются просто потому, что требуют слишком много машинного времени. Таким образом, программисты, создающие программы, могут сделать очень много для оптимизации своих программ.
Использование обсуждавшихся здесь способов оптимизации не исключает необходимости в оптимизирующем компиляторе, так как машинно-зависимая оптимизация редко предусматривается на уровне исходной программы. Кроме того, даже наилучшим образом оптимизированная человеком исходная программа будет улучшена оптимизирующим компилятором.
3. Оптимизация программ
Часто возникает необходимость в оптимизации некоторой рабочей программы, потому что, либо она выполняется слишком долго, либо для нее требуется слишком большой объем памяти. Вполне возможно, что при создании программы не думали о том, часто ли ее будут использовать, и не позаботились о ее эффективности. Или в результате значительной модификации программа стала неэффективной, а теперь она используется довольно часто и занимает слишком много машинного времени или, возможно, близка к превышению объема памяти, имеющегося в ее распоряжении. Поэтому нужно попытаться сделать программу более эффективной.
Если программу следует оптимизировать, необходимо прежде всего тщательно проверить алгоритм. Основными критериями при этом должны являться время и объем памяти, используемые программой. Если оптимизация старого алгоритма не дает желаемого результата, тогда, возможно, следует выбрать другой алгоритм. В дальнейшем предполагается, что первоначальный алгоритм обоснован и целесообразен, однако программисты, которым нужно оптимизировать свою программу, никогда не должны делать такого предположения.
Сегментация программ
Программу, подлежащую оптимизации, следует разделить на подпрограммы. Оптимизация значительно облегчается, если программа уже разделена на подпрограммы в соответствии с принципами структурного программирования. Как только подпрограммы выделены, следует ответить на три вопроса:
Какой процент общего времени использует каждая подпрограмма?
Насколько (в процентном выражении) оптимизируется каждая подпрограмма?
Сколько человеко-часов необходимо для достижения этой цели?
Каждый из этих вопросов подробно обсуждается далее.
Время работы подпрограмм
После деления программы на подпрограммы следует определить процент времени, используемый каждой подпрограммой. Это необходимо сделать для того, чтобы узнать, какие части программы расходуют больше всего времени.
Если для определения времени работы каждой подпрограммы используются оценки и предположения, то часто возникают ошибки и оптимизировать программу не удается. Поверхностные исследования приведут к тому, что для оптимизации будут выбраны не те подпрограммы. После того как установлено фактическое время работы, подпрограмма, которая используется больше других, должна оптимизироваться в первую очередь. Предположим, что программа разделена на четыре подпрограммы и время их выполнения составляет для
подпрограммы А — 5%, подпрограммы С — 15%,
подпрограммы В — 60%, подпрограммы В — 20%.
Очевидно, что, даже если подпрограмму А исключить совсем (что, вообще говоря, невозможно), мы смогли бы сэкономить только 5% общего времени работы программы. Таким образом, попытку оптимизации, вероятно, следует предпринять в первую очередь в отношении подпрограммы В, где возможна наибольшая экономия.
Если нельзя получить фактическое время выполнения каждой подпрограммы, применяется другой подход, заключающийся в подсчете количества операторов в подпрограмме, используя листинг программы на входном языке высокого уровня. Операторы, включенные в тело цикла, следует учитывать многократно. Подсчет количества операторов — достаточно надежный показатель времени, требуемого для каждой подпрограммы, но определение фактического времени работы подпрограммы гораздо лучше.
Большинство программ имеет одну критическую точку, которая использует большую часть времени выполнения. Нередко какая-либо малая часть программы расходует более 50% времени выполнения. Очевидно, что эту часть программы следует оптимизировать в первую очередь.
После оптимизации первой критической точки хорошо проанализировать программу еще раз, чтобы найти теперь уже другую критическую точку, которую также следует оптимизировать. Этот процесс можно повторять до тех пор, пока будут получены значительные результаты.
Оценивайте возможное улучшение
Если точно определен процент общего времени, используемый подпрограммой, следует оценить ее возможное улучшение. Если подпрограмма расходует небольшой процент от общего времени программы и ее можно лишь незначительно улучшить, то не стоит тратить на это усилий. При определении возможного улучшения необходима или возможна только приблизительная оценка. Не так уж важно, составляет возможное улучшение 20 или 25%. Однако существенно, будет оно 5 или 70%.
Определение возможного улучшения — не тривиальная задача. Опыт здесь, вероятно, самый лучший руководитель. Предлагается множество способов написания эффективных программ. Используя данные здесь рекомендации, можно обнаруживать операторы, которые следует модифицировать. Наиболее оправдывает себя тщательная проверка циклов и операторов ввода-вывода.
Теперь можно установить некоторый параметр, который будет показывать возможное улучшение. Если у нас имеется подпрограмма, использующая 50% общего времени работы программы, но дающая только 5% повышения эффективности, мы получим в результате 2,5% (.50 * .05 = .025) общего улучшения эффективности. Другая подпрограмма, которая использует 10% общего времени, но дает 50% повышения эффективности, обеспечивает 5% (.50 * .10 = .05) общего улучшения эффективности. Таким образом, вторую подпрограмму следует оптимизировать в первую очередь, так как это дает больший выигрыш. Итак, при выборе подпрограммы для оптимизации следует учитывать произведение процента потребления времени и процента улучшения.
Необходимые усилия.
При определении возможного улучшения мы должны оценить работу, необходимую для достижения этого улучшения. Для каждой подпрограммы можно вычислить следующий коэффициент:
(Процент времени*Процент улучшения ) / Необходимые усилия
Подпрограмму с самым высоким коэффициентом следует оптимизировать в первую очередь. Главное преимущество тщательного выбора подпрограмм, подлежащих оптимизации, состоит в том, что важные ресурсы (время программиста и время машины) будут использоваться там, где они принесут наибольшую пользу. Если ресурсы распределены плохо, можно затратить много усилий и получить в результате лишь небольшое увеличение эффективности. Если нет достаточного времени или нет оснований для переделки всей программы, можно переделать наиболее важные подпрограммы.
Существуют два подхода к оптимизации имеющихся программ:
«чистка»
перепрограммирование.
Оба подхода имеют как достоинства, так и недостатки.
Первый подход заключается в исправлении очевидных небрежностей в исходной программе. Для этого можно использовать любые особенности языка, пригодные для оптимизации. Достоинство этого подхода состоит в том, что он требует мало времени. Однако повышение эффективности при этом обычно незначительно.
Второй подход состоит в переделке исходной программы. Если программа разделена на подпрограммы, можно переделать подпрограмму, которая расходует наибольшую часть времени. Реализация этого подхода обеспечивает обычно наилучший результат. Однако этот подход и самый дорогой. Особенно полезно перепрограммировать задачу, если программа подверглась значительному изменению. Частые переделки могут привести к изменению цели первоначальной программы. Программа может постоянно переделываться в течение некоторого времени. И когда, наконец, результаты работы программы окажутся приемлемыми и дальнейшие пересмотры будут менее обширными и менее частыми, следует заняться переделкой, используя приобретенные знания и поставив новые цели, что приведет к значительной экономии времени выполнения программы.
Шаги оптимизации
Оптимизируйте только в случае необходимости, так как, выполняя оптимизацию, можно ухудшить удобочитаемость программы, либо добавить ошибки, либо потерять много времени на программирование.
Если оптимизация необходима, попытайтесь вначале использовать оптимизирующий компилятор. Возможно, он умеет делать все, что вам нужно.
Определите критические области, подлежащие оптимизации.
Оптимизация некритичных частей программ - пустая трата времени.
Применяйте локальную оптимизацию в критических областях.
Слишком часто программисты тратят много времени, улучшая редко используемую программу.
4. Эффективность выполнения программ
Эффективность программы во время выполнения определяется использованием двух ресурсов. Первый из них - необходимое для работы время, а второй — память, которая требуется программе. Время — более важный фактор для программиста, так как в большинстве случаев программа оценивается количеством машинного времени, необходимого для ее выполнения. Обычно проблема памяти существенна только тогда, когда ее недостаточно.
Оптимизировать память труднее, чем время выполнения. Нет ничего удивительного в том, что после оптимизации программа будет выполняться на 25% быстрее, но было бы необычно получить уменьшение размера используемой ею памяти на 25%; при этом предполагается, что не было допущено серьезных ошибок в первоначальном варианте программы.
Однако, что если бы вы выбрали новый лучший алгоритм и перепрограммировали задачу, то могли бы существенно улучшить как время выполнения, так и объем потребляемой памяти. Очень трудно значительно сократить используемую программой память, потому что сэкономленные области памяти разбросаны в небольших количествах по всей программе. В отличие от этого скорость выполнения можно значительно увеличить, например, оптимизируя такую часть программы, как цикл, который многократно повторяется.
Но иногда даже небольшая экономия памяти бывает просто необходима (чтобы можно было использовать конкретную программу для данной машины), тогда как небольшая экономия времени не так уже важна.
Мы увеличиваем эффективность выполнения программы, улучшая ее, насколько возможно, на стадии компилирования. Компилирование включает такие действия, как инициирование массивов и переменных, вычисление констант и распределение памяти. Распределение памяти на стадии компилирования обычно увеличивает расход памяти за счет сэкономленного времени выполнения программы.
Хорошие приемы программирования приводят к уменьшению как времени выполнения, так и объема используемой памяти, однако зачастую улучшение одного из этих факторов происходит за счет ухудшения другого. Большинство из обсуждающихся здесь методов экономит как время, так и память. Если использование метода приводит к возникновению конфликта между временем и памятью, это будет оговорено.
В большинстве случаев небольшое увеличение эффективности не имеет смысла, если оно связано с тратой значительного количества времени на программирование и вызывает ухудшение удобочитаемости, надежности, универсальности или удобства. Однако иногда это стоит делать. Типичным примером является компилятор, при создании которого затрачиваются большие усилия для получения эффективной программы. Но, поскольку компилятор используется неоднократно, даже малое увеличение эффективности приносит большие дивиденды. Эффективность также очень важна в библиотеках программ. Поскольку эти программы используются часто, небольшое увеличение эффективности будет, как правило, сокращать время работы машины. В каждом конкретном случае повышение эффективности зависит от ряда факторов, таких, как
стоимость улучшения программы,
частота ее использования,
относительная скорость выполнения различных операций в машине,
способ компилирования различных операторов.
Хорошей считается программа, которая выполняется при минимальном расходе машинного времени. В этом случае за данный отрезок времени можно выполнить еще и другие задания. С появлением мультипроцессорной обработки (т. е. выполнением более одного задания за то же время) стало желательным также и минимальное использование памяти, так как при работе в указанном режиме каждая программа должна находиться в оперативной памяти. Чем меньший объем памяти требуется каждой программе, тем больше программ можно разместить в оперативной памяти и обработать за одно и то же время. В режиме мультипроцессорной ^обработки использование оперативной памяти так же важно, как и расход времени. Сокращение занимаемой памяти или расхода времени будет уменьшать стоимость выполнения программы. Так как ресурсы машины очень дороги, то экономия даже небольшого количества времени или памяти в многократно используемой программе может вполне стоить затраченных усилий.
Обычно любая попытка улучшить эффективность предназначается для часто используемых программ. Хотя это весьма результативный подход, однако есть другой путь сэкономить большое количество машинного времени. Вырабатывайте комплекс привычек, которые будут способствовать составлению более эффективной программы и соответственно экономии машинного времени.
5. Оптимизация использования памяти
Обычно программисты не заботятся о памяти до тех пор, пока не превысят ее размеры. Тогда становится очевидным, что память не бесконечна. Идеальной считается ситуация, когда мы располагаем машиной с высоким быстродействием и достаточным объемом памяти. Однако размер задач увеличивается по мере увеличения размера памяти. Экономное использование памяти почти всегда сопровождается увеличением времени работы программистов и времени выполнения программы. Поэтому, если память не используется полностью, вопрос о ее распределении не представляет интереса до тех пор, пока ее достаточно.
Оверлейность программы
Под оверлейностью программы понимают возможность перенесения подпрограмм во время работы программы в быстродействующую память из некоторого другого типа памяти таким образом, что несколько подпрограмм в различное время занимают одну и ту же область памяти. Оверлейность используют в том случае, когда общие требования к объему программы превышают размер имеющейся в нашем распоряжении оперативной памяти. Программу следует разделить на логические части таким образом, чтобы не перекрывающиеся по времени части можно было последовательно вызывать в память по мере необходимости. Обычно для оверлейности используются программные модули. Чтобы пересылать модули из периферийной памяти, необходимо дополнительное время. Оверлейность экономит память, однако приводит к дополнительному расходу времени программистов высокого класса и машинного времени.
Виртуальная память
Возможность оверлейности реализуется также при использовании виртуальной памяти. Программисты полагают, что они имеют в своем распоряжении оперативную память очень большого объема даже на машине со сравнительно небольшим размером памяти. Однако, если для работы нужна часть программы, которой нет в оперативной памяти, теряется время: недостающая часть считывается с диска. Чем реже возникает такая ситуация, тем быстрее будет выполняться программа.
Программист может принять некоторые меры для повышения эффективности выполнения программы при использовании виртуальной памяти. Программу следует писать с подпрограммами. Это улучшает свойство локализованности программы, т. е. степени, до которой во время выполнения удается выделить в программе некоторый ее фрагмент. Это легко выполняемый прием программирования. Локализованность улучшается при использовании методов структурного программирования. Избегайте использования глобальных переменных, так как они приводят к ухудшению локальности. Организация циклов и подпрограмм также способствует локализованности, так как приводит к многократному выполнению небольшой части всей программы. Чем выше степень локализованности в программе, использующей виртуальную память, тем более эффективно будет выполняться программа, так как ей не придется вызывать в память много страниц. Таким образом, при использовании виртуальной памяти храните части программ, связанные друг с другом, рядом.
Другой способ повышения эффективности выполнения программ при использовании виртуальной памяти состоит в расположении подпрограмм в том порядке, в каком они будут обращаться друг к другу. Это уменьшит количество страниц, которые нужно будет считать в оперативную память.
Советы:
Структурированные программы и использование модулей увеличат локализованность.
Удаляйте подпрограммы, обрабатывающие исключения, подпрограммы обработки ошибок и другие редко используемые разделы программы из ее основной части, чтобы увеличить интенсивность обращений к наиболее часто используемым страницам.
Присваивайте начальные значения элементам каждого массива данных непосредственно перед первым его использованием, а не перед началом работы программы.
Обращайтесь к данным для считывания (или для записи) в порядке их расположения в памяти. Например, если массивы расположены в памяти по столбцам, выполните вначале все обращения к одному столбцу, прежде чем перейти к следующему.
Данные, не являющиеся массивом, можно разместить рядом, перегруппировав их описания. Лучше всего располагать рядом наиболее часто используемые массивы.
Эквивалентность
В большинстве машинных языков предусмотрены операторы, позволяющие двум переменным занимать одну и ту же ячейку памяти. Если одна переменная используется только в начале программы, а вторая переменная нужна в другой части программы, обе переменные могут занимать одну и ту же ячейку памяти, так как они используются в программе в разное время.
Этот тип операторов можно применять для экономии памяти, потому что, как правило, в программе имеются переменные, которые используются только в отдельных сегментах программы. Установив эквивалентность массивов, можно сэкономить память, поэтому в программах, требующих большого объема памяти, этому вопросу следует уделить особое внимание. Традиционным способом сокращения объема памяти является уменьшение размера массивов. Это следует делать до установления эквивалентности двух массивов в памяти. А так как эквивалентность несвязанных переменных может быть неявно выраженной, ее следует соответствующим образом прокомментировать.
Использование циклов
Использование циклов для повторения последовательности операторов является обычным способом экономии памяти. Разные части программ нередко содержат одинаковые последовательности операторов. Если программист стремится к экономному расходованию памяти, он должен найти одинаковые части программы, которые могут быть преобразованы в циклы. Циклы требуют некоторого дополнительного количества памяти на инициирование, проверку, изменение индекса и установку всех констант. Однако уменьшение общего объема памяти за счет удаления повторяющихся команд весьма значительно. Не многократно повторяющиеся последовательности операторов, требующие сложной организации циклов, часто можно писать последовательно, а не итеративно.
6. Некоторые приёмы повышения эффективности программ
1.Вычисление констант
Программы становятся более удобочитаемыми, если в них используются выражения, включающие константы. Для выполнения вычислений, содержащих только константы, применяют множество различных методов компилирования. Некоторые компиляторы вычисляют все выражения с константами во время компилирования и запоминают результат. Другие компиляторы запоминают константы, а вычисления осуществляются во время выполнения. Второй способ неэффективен, если выражения находятся внутри циклов. Если выражения с константами не вычисляются во время компилирования, необходимо их всегда располагать вне цикла.
Процесс выполнения операторов, значения которых известны на стадии компилирования, что позволяет не выполнять их во время прогона программы, обычно называют сверткой. Свертка выполняется также для значений, которые могут быть определены внутри блоков программы.
2.Инициирование переменных
Если начальные значения присваиваются переменным одновременно с их объявлением, то тем самым экономится время выполнения программы. В этом случае переменные получают начальные значения во время компилирования, а не во время выполнения. Инициирование переменных во время их объявления облегчает документирование программ, а также помогает избежать ошибок, которые могут возникнуть в случае, если переменным не были присвоены начальные значения.
Инициируйте переменные во время компилирования.
3.Арифметические операции
Арифметические операции выполняются с различной скоростью. Полезно знать, какие операции выполняются быстрее, так как иногда бывает целесообразно заменить одну операцию другой. Перечислим математические операции в порядке возрастания времени их выполнения: 1) сложение или вычитание, 2) умножение, 3) деление, 4) возведение в степень.
Некоторые медленно выполняемые операции легко заменить на более быстрые.
Сложение выполняется быстрее, чем умножение, поэтому умножение на небольшое целое число следует заменять сложением. Так, 3*1 должно быть заменено на 1+1+1. Если в выражении не все числа являются целыми, то при замене может быть утеряна точность. Ошибка округления действительных чисел имеет тенденцию накапливаться, а не уменьшаться. Так, если К — действительное число, а I — целое, то 1*К более правильно, чем К+К+К+К— (I раз).
Преобразование уравнений может привести к исключению операций. Например, выражение Х = 2*Y+(А—1)/Р+2*Т можно заменить уравнением
Х = 2*(Y+Т) + (А—1)/Р, что исключает одну операцию умножения.
Поскольку деление является более медленной операцией, всюду, где возможно, его следует заменять умножением. Умножение выполняется по меньшей мере в два раза быстрее деления. Исключайте деление из вашей программы всюду, где это возможно: вместо А/5.0 пишите А*0.2.
Если в вычислениях вы все время делите на некоторое число, папример на X, замените его на обратную величину.
Важно также правильно задать тип показателя степени в операции возведения в степень. Всегда, когда это возможно, следует использовать целые числа. Например,
Медленный способ: А**8.0 или А**Р, где Р — число с плавающей точкой.
Более быстрый способ: А**8 или А**1, где I — целое число.
Второй способ обеспечивает более быстрое выполнение; кроме
того, он и более точен, так как при этом исключаются некоторые
типы ошибок. Таким образом, если выполняется возведение в степень целых чисел, делайте показатель степени целым числом.
Если показатель степени — целое число, то операцию возведения в степень выполняют повторяющимся умножением. Если показатель степени является числом с плавающей точкой, то для выполнения операции возведения в степень необходимо вызвать специальную подпрограмму.
Функция извлечения квадратного корня реализуется обычно гораздо быстрее, и точность при этом выше, чем при выполнении операции возведения в степень.
Умножение выполняется значительно быстрее возведения в степень, поэтому, если показатель степени — небольшое целое число, то операцию возведения в степень следует заменять несколькими операциями умножения:
Для возведения в степень обычно требуется библиотечная программа. Поэтому замена его несколькими операциями умножения экономит и память, и время, если показатель степени является небольшим целым числом.
Заменяйте Х**2 на Х*Х Заменяйте Х**3 на Х*Х*Х Заменяйте Х**4 на (Х*Х)#(Х*Х)
или на (((Х*Х)*Х)*Х)
Последний пример содержит повторяющееся вычисление (Х*Х), которое в дальнейшем может быть оптимизировано. Замена одной операции другой, выполняемой более быстро, называется уменьшением силы операции. Уменьшение силы операции может иногда ухудшить удобочитаемость программ, и об этом следует всегда помнить. Кроме того, при таком преобразовании некоторое количество машинного времени затрачивается на управление промежуточными результатами.
4. Арифметика с фиксированной точкой
Большинство машинных языков допускает целочисленную арифметику. Она может применяться для любых типов вычислительных операций. Для целых чисел используются специальные процедуры, потому что многие вычислительные задачи имеют дело только с целыми числами (обработкой информации, связанной с инвентаризацией, переписью), а целочисленная арифметика обычно выполняется одной машинной командой, в то время как арифметика с плавающей точкой часто выполняется подпрограммами, включающими множество команд машинного языка.
Некоторые машины могут выполнять 50 операций сложения целых чисел за время, требуемое для выполнения одной операции сложения с плавающей точкой. В этом случае целочисленную арифметику следует использовать всюду, где это возможно, особенно для выполнения большого числа простых арифметических операций над целыми числами, такими, как индексы. Использование неправильного типа переменных для индексов может значительно увеличить время выполнения любой программы.
Впрочем, некоторые машины выполняют операции с плавающей точкой быстрее, чем операции с фиксированной точкой. Обычно это большие машины, служащие для проведения научных расчетов. Они имеют специальное оборудование, обеспечивающее выполнение арифметических операций с плавающей точкой.
Особое внимание следует уделить тому, чтобы внутренние переключатели, счетчики и переменные, встречающиеся в многочисленных вычислениях, были такого типа, который приводит к самым эффективным вычислениям. Это чаще всего является проблемой при работе с переменными, являющимися строками символов. Если возникает такая ситуация, то для каждого вычисления необходимо делать многочисленные преобразования. И память, и время можно сэкономить правильным описанием переменных.
5. Смешанные типы данных
Смешанные типы данных получаются в результате использования чисел различного типа в арифметических и логических операциях. Если вы смешиваете числа разного типа, то при выполнении арифметических операций часто бывают необходимы преобразования. Ситуацию можно улучшить, объявляя как можно больше переменных одинакового типа. В этом случае нужно меньше заботиться о том, чтобы избежать смешанных вычислений, поскольку почти все переменные одного типа. Хотя смешанная арифметика допускается, чтобы уменьшить количество ошибок и помочь программисту, ее следует избегать, так как она занимает больше времени и памяти.
Избегайте смешанных типов данных,
6. Способ устранения ошибок
В некоторых простых компиляторах следует тщательно выбирать тип используемых констант. Например, А = 0 (неэффективно) А = 0.0 ( эффективно).
Некоторые компиляторы требуют преобразования целого нуля в вещественный во время выполнения программы, как в случае А = 0; во втором случае необходимость в преобразовании отсутствует. Хороший компилятор запоминает константу в нужной форме при компилировании, а не во время выполнения.
Если преобразование необходимо, оно может занять очень много времени при его выполнении внутри цикла.
7. Выравнивание десятичных чисел
Программы, использующие переменные в фиксированном десятичном формате, можно сделать более эффективными, если тщательно выбирать их атрибуты. Если эффективность важна, полезно изучить руководство по языку для вашей машины, чтобы знать, когда необходимо выполнять преобразования в арифметических операциях.
8. Упорядочивание памяти
Можно получить значительную экономию времени и памяти, если переменные в памяти .надлежащим образом упорядочить. Другими словами, некоторые типы переменных должны быть выравнены в памяти на границу слова или двойного слова. Если этого не сделать то компилятор будет создавать команды, которые производят соответствующее выравнивание во время выполнения программы.
Если массивы не выравнены, могут иметь место значительные потери времени и памяти. Чтобы получить точную информацию о выравнивании, следует обратиться к руководству по программированию для соответствующего языка.
9. Группировка
При выполнении операций одного приоритета над операндами разного типа следует группировать операнды одного типа, заключая их в круглые скобки. Например, если операнд I относится к типу 1, операнд А — к типу 2, операнд К — к типу 3, то выражение вида 1*А*1*К*А* К* I следует записать как ((1*1*1)* А*А)* К*К.
Группировка и скобки помогает избежать преобразований, которые необходимо выполнить для первого выражения.
Можно избежать лишних преобразований, если вначале выполнить преобразование одного типа данных в другой, а затем использовать нужный тип. Например, если I и А — переменные, которые используются вместе и требуют дополнительных преобразований, преобразуйте их сразу и используйте полученную форму в дальнейшем во всех математических операциях.
Например,
Медленный способ:
В = А*1
С=(А+1)*2.0
Д = А* А/1
Эти операторы используют переменные А и I несколько раз. Лучше преобразовать один раз переменную I в переменную типа А и затем пользоваться новой переменной.
Более быстрый способ:
А1 = 1
В=А*А1
С=(А+А1)*2.0
Д=А*А/А1
Здесь переменную I следует преобразовать не три раза, а только один.
10. Исключение циклов
Всегда, когда это возможно, избегайте циклов, так как при их использовании тратится время на приращение и проверку параметра цикла. Использование циклов может увеличить время выполнения на одну треть. Небольшие вычисления часто можно делать, минуя циклы. Например, вычисление полинома по формуле
РОLY =((А(1)*Х+А(2))*Х+А(3))*Х+А(4)
выполняется быстрее, чем в цикле:
POLY=A(I)
DO 1 I=2,4
1 РОLY = РОLY*Х+А(1)
Кроме того, в каждом языке есть свои особенности инициирования массивов.
Один из способов уменьшения количества циклов состоит в объединении двух и более циклов в один. Уменьшение количества циклов часто бывает возможно, если тщательно проанализировать задачу перед программированием. Программы, которые подверглись значительной модификации, должны быть подвергнуты особенно тщательному анализу.
11. Организация циклов
Значительная часть времени при использовании циклов тратится на инициирование и проверку индекса цикла. Тщательной организацией вложенных циклов можно сэкономить время. Таким образом, число инициирований и завершений цикла может быть сокращено вложением циклов друг в друга таким образом, чтобы внешний цикл имел наименьшее число итераций.
При попытке ускорить выполнение программы циклы обычно являются самым важным фактором. Это очевидно, так как операторы внутри цикла могут выполняться много тысяч раз и любая экономия, даже совсем небольшая, будучи увеличена в тысячи раз, дает существенный выигрыш. Программы можно сделать более эффективными, если пользоваться приемами программирования, изложенными в этой главе. Однако, если программист тратит много времени, пытаясь повысить эффективность своей программы, улучшая оператор, который выполняется только один раз, это подобно попытке уменьшить свой вес, остригая ногти,— вы можете добиться некоторого успеха, но весьма незначительного.
Поэтому уделяйте основное внимание циклам. Разберем пример:
Цикл А 100 итераций
Цикл В 100 итераций
Цикл С 100 итераций
Конец С
Конец В
Конец А
Рассмотрим вначале цикл С. Любая экономия, даже самая малая, будет здесь увеличиваться в 100*10О*10О=1 000 000 раз, т. е. коэффициент улучшения равен одному миллиону. Очень малое улучшение внутри цикла С гораздо выгоднее, чем значительное улучшение вне его. Затем рассмотрите цикл В, и, наконец, цикл А.
Вычисления внутри цикла следует минимизировать. Почти все предложения по оптимизации следует применять для циклов, особенно в случае повторяющихся вычислений, неизменяемых индексов, арифметических операций и преобразования данных.
Повторяющиеся вычисления в циклах являются наиболее типичными ошибками, влияющими на эффективность. Можно значительно сэкономить время выполнения программы просто проверкой циклов, выполняющих много итераций, и уменьшением повторяющихся вычислений внутри этих циклов. Этот процесс обычно называют исключением инвариантных выражений или чисткой циклов. Инвариантными являются выражения, которые не изменяются внутри цикла. Если при компилировании можно удалить одну операцию умножения из цикла, который повторяется при выполнении программы 1000 раз, мы сэкономим время, которое затрачивается на выполнение 999умножений.
Оптимизируйте сначала внутренние циклы.
Часто циклы можно объединять, что сокращает как время, так и память (сжатие циклов). Иногда используется обратный прием – разъединение циклов, что может позволить уменьшить время за счет расхода памяти .
12. Условные и логические выражения
На первом месте располагается условие, которое, чаще является истинным (например, имеет значение А=3, тогда эта проверка должна стоять первой в конструкции IF). Остальные условия также располагаются в порядке их вероятности быть истинными.
Правильное расположение логических выражений может сэкономить время выполнения.
13. Ввод-вывод
Операции ввода-вывода расходуют много времени. Не вводите данные, которые можно вычислить внутри программы. В некоторых случаях возможен даже переход к неформатному вводу-выводу, что резко экономит время, поскольку не выполняются преобразования.
14. Использование сведения о машине и компиляторе
Каждая машина и каждый компилятор имеют некоторые особенности, изучение и использование которых позволит более эффективно компилировать и выполнять программу. Информацию такого типа можно получить, изучая листинги ассемблера.
Например, в одном широко распространенном компиляторе сделано так, что если номера операторов распределены равномерно по всему диапазону, то программа будет компилироваться быстрее. Эта ситуация возникает потому, что компилятор для своих внутренних потребностей располагает номера операторов в таблицы, состоящие из строк, в которых во время компилирования выполняется многократный поиск. Если количество входов в каждую строку примерно одинаково, сокращается среднее время, необходимое для нахождения номера оператора.
Номера операторов записывают в пяти строках таблицы согласно последней цифре номера оператора. Номера операторов, оканчивающиеся на 0 или 1, размещаются в первой строке, на 2 или .4 — во второй строке, на 4 или 5 — в третьей и т. д. Таким образом, если номера операторов распределены равномерно, сокращается время компилирования.
Подобная ситуация имеет место и с именами переменных. Имена записываются в строки в соответствии с длиной имени переменной. Имена, имеющие длину в один символ, записываются в первой строке, имена из двух символов — во второй строке и т. д. Таким образом, если имена распределены довольно равномерно по разным строкам, затрачивается меньше времени на нахождение каждого имени.
Изложенные здесь замечания показывают, что, если эффективность очень важна, вы должны знать не только общие приемы, позволяющие ее повысить, но также и обладать некоторыми сведениями о машине, ее компиляторе и операционной системе.
7. Советы программисту по оптимизации программ
Если программа неправильна, не имеет значения, какова ее эффективность.
Определяйте требования к эффективности программы на стадии проектирования.
Удобочитаемость программы обычно более важна, чем эффективность.
Используйте оптимизирующий компилятор. Инициируйте переменные во время компилирования.
Избегайте смешанных типов данных.
Оптимизируйте сначала внутренние циклы.
Используйте для индексации наиболее предпочтительный тип данных.
Группируйте записи в эффективные блоки для ввода-вывода.
Используйте загрузочные модули.
Контрольные вопросы
Что является наиболее важным при написании эффективных программ?
Какой тип программ следует оптимизировать? Какой тип программ оптимизировать не надо?
Что означают понятия: оверлейность программ, свертка, уменьшение силы операции, исключение повторяющихся выражений, исключение циклов, исключение инвариантных выражений, развертка цикла, критическая область, локализованность?
В каком случае использовать цикл менее эффективно, чем программировать последовательно?
Как следует располагать вложенные циклы, чтобы сократить число инициирований и проверок цикла?
Какие области программы наиболее выгодны для оптимизации?
Расположите нижеуказанные операции по скорости их выполнения— от самой быстрой к самой медленной:
1) деление, 4) извлечение корня,
2) сложение, 5) возведение в степень,
3) умножение, 6) вычитание.
Имеется ли оптимизирующий компилятор, пригодный для нашего языка программирования? Если да, то какие типы оптимизации он выполняет?
Имеется ли в вашем компиляторе версия, минимизирующая использование объема памяти в объектной программе за счет снижения скорости выполнения? Можно ли повысить скорость выполнения за счет памяти?
Выберите два различных оператора в вашем языке программирования и разработайте тесты, выявляющие, какой оператор выполняется быстрее.
Охарактеризуйте типы программ по степени важности для них эффективности.
Почему удобочитаемость программ зачастую более существенна, чем эффективность?
В чем особенности оптимизирующего компилятора?
Что понимают под машинно-зависимой и машинно-независимой оптимизацией?
Что такое критическая точка программы? Как это понятие используется при оптимизации?
Охарактеризуйте приемы чистки и перепрограммирования программного кода.
Каковы шаги оптимизации программы?
Особенности оптимизации использования памяти?
Какова роль описания переменных, инициирования переменных, вычисления констант, арифметических операций в повышении эффективности программ?
Охарактеризуйте влияние циклов на эффективность программы.
|
Скачать 7.57 Mb.