Часто возникает необходимость в оптимизации некоторой рабочей программы, потому что либо она выполняется слишком долго*

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

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

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

3.4.1. СЕГМЕНТАЦИЯ ПРОГРАММ

Программу, подлежащую оптимизации, следует разделить на подпрограммы. Оптимизация значительно, облегчается, если программа уже разделена на подпрограммы в соответствии с принципами структурного программирования. Как только подпрограммы выделены, следует ответить на три вопроса:

1. Какой процент общего времени использует каждая подпрограмма?

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

3. Сколько человеко-часов необходимо для достижения этой цели?

Каждый из этих вопросов подробно обсуждается в трех следующих разделах.

3.4.2, ВРЕМЯ РАБОТЫ ПОДПРОГРАММ

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

Если для определения времени работы каждой подпрограммы используются оценки и предположения, то часто возникают ошибки и оптимизировать программу не удается. Поверхностные исследования приведут к тому, что для оптимизации будут выбраны не те подпрограммы. После того как установлено фактическое время работы, подпрограмма, которая используется больше других, должна оптимизироваться в первую очередь. Предположим, что программа разделена на четыре подпрограммы и время их выполнения составляет для подпрограммы А — 5%, подпрограммы В — 60%, подпрограммы С— 15%, подпрограммы В — 20%.

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

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

Большинство программ имеет одну критическую точку, которая использует большую часть времени выполнения. Нередко какая-либо малая часть программы расходует более 50% времени выполнения. Очевидно, что эту часть программы следует оптимизировать в первую очередь".

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

3.4.3. ПРОФИЛИ ВРЕМЕНИ ВЫПОЛНЕНИЯ

Раньше определение фактического времени выполнения частей программы было самым лучшим из возможных методов, пригодных для проверки программ на потери потребляемого времени. Сегодня в компиляторах КОБОЛа, ФОРТРАНа, ПЛ/1 и АЛГОЛа для этих целей используются профили времени выполнения.

Неоднократно отмечалось, что разработчики программ не делают правильных оценок эффективности времени и памяти для критических областей. Они создают программы, не используя методы программного обеспечения для определения критических областей; иначе говоря, эти критические области так и остаются неизвестными.

Профилируйте ваши программы.

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

3.4.4. ОЦЕНИВАЙТЕ ВОЗМОЖНОЕ УЛУЧШЕНИЕ

Если точно определен процент общего времени, используемый подпрограммой, следует оценить ее возможное улучшение. Если подпрограмма расходует небольшой процент от общего времени программы и ее можно лишь незначительно улучшить, то не стоит тратить на это усилий.

При определении возможного улучшения необходима или возможна только приблизительная оценка. Не так уж важно, составляет возможное улучшение 20 или 25%. Однако существенно, будет оно 5 или 70%.

Определение возможного улучшения — не тривиальная задача. Опыт здесь, вероятно, самый лучший руководитель.

В настоящей главе предлагается множество способов написа- -ния эффективных программ. Используя данные здесь рекомендации, можно обнаруживать операторы, которые следует модифицировать. Наиболее оправдывает себя тщательная проверка циклов и операторов ввода-вывода.

Теперь мы можем установить некоторый параметр, который будет показывать возможное улучшение. Если у нас имеется подпрограмма, использующая 50% общего времени работы программы, но дающая только 5% повышения эффективности, мы получим в результате 2,5% (.50 * .05 = .025) общего улучшения эффектив-ярсти. Другая подпрограмма, которая использует 10*% общего времени, но дает 50% повышения эффективности, обеспечивает 5% (.50 * .10 = .05) общего улучшения эффективности. Таким образом, вторую подпрограмму следует оптимизировать в первую очередь, так как это дает больший выигрыш. Итак, при выборе подпрограммы для оптимизации следует учитывать произведение процента потребления времени и процента улучшения.

3.4.5. НЕОБХОДИМЫЕ УСИЛИЯ

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

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

Существуют два подхода к оптимизации имеющихся программ: "чистка" и перепрограммирование. Оба подхода имеют как достоинства, так и недостатки. Первый подход заключается в исправлении очевидных небрежностей в исходной программе. Для этого можно использовать любые особенности языка, пригодные для оптимизации. Многие предложения, изложенные в этой главе, помогут в дан'ном случае. Достоинство этого подхода состоит в том, что он требует мало времени. Однако повышение эффективности при этом обычно незначительно.

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

Вероятно, многому можно научиться при первоначальной попытке написания программы; эту информацию можно использовать при перепрограммировании. Особенно полезно перепрограммировать задачу, если программа подверглась значительному изменению. Частые переделки могут привести к изменению цели первоначальной программы. Программа может постоянно переделываться в течение некоторого времени. И когда наконец результаты работы программы окажутся приемлемыми и дальнейшие пересмотры будут менее обширными и менее частыми, следует заняться переделкой, используя приобретенные знания и поставив новые цели, что приведет к значительной экономии времени выполнения программы.

3.4.6. ШАГИ ОПТИМИЗАЦИИ

Прежде чем перейти к методам оптимизации выходной программы, подведем итоги вышеизложенного материала:

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

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

3. Определите критические области, подлежащие оптимизации. Оптимизация некритичных частей программ — пустая трата времени.

4. Применяйте локальную оптимизацию в критических областях.

Слишком часто программисты тратят много времени, улучшая редко используемую программу. Остаток главы посвящен последнему шагу — локальной оптимизации.