Стратегии оптимизации кода

Исторически противоречивая проблема — повышение производительности кода. В 1960-х годах ресурсы компьютеров были крайне ограниченны, поэтому эффективность их использования была вопросом первостепенной важности. По мере роста производительности компьютеров в 70-х программисты начали понимать, насколько упор на производительность вредит удобочитаемости и легкости сопровождения кода, и оптимизация кода отошла на задний план. Вместе с микрокомпьютерной революцией, свидетелями которой мы стали в 80-х, проблема эффективного использования ресурсов вернулась, но в 90-х ее важность постепенно уменьшилась. В 2000-х мы опять столкнулись с этой проблемой, только теперь она связана с ограниченной памятью мобильных телефонов, карманных ПК и подобных устройств, а также со временем выполнения интерпретируемого кода.

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

Общее обсуждение производительности ПО

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

Характеристики качества и производительность

Некоторые люди смотрят на мир через розовые очки. Программисты склонны воспринимать мир через кодовые очки. Мы полагаем, что чем лучше будет наш код, тем сильнее наше ПО понравится клиентам.

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

Приведу пример. Я делаю цифровой камерой минимум 50 снимков в неделю. Чтобы скопировать снимки на компьютер при помощи ПО, поставляемого с камерой, я должен выбрать каждый снимок по очереди, причем в окне программы отображаются только 6 снимков сразу. В результате копирование 50 изображений превращается в долгий и нудный процесс, требующий десятков щелчков и массы переключений между окнами. Устав от всего этого, я купил карту памяти, подключаемую прямо к компьютеру и воспринимаемую им как диск. Теперь для копирования изображений на диск компьютера я могу использовать Проводник Windows. Я делаю пару щелчков, нажимаю Ctrl+A и перетаскиваю все файлы в нужное место. Меня не волнует, передает ли карта памяти каждый файл вдвое медленнее или быстрее, чем другое ПО, потому что сейчас я могу обработать больший объем информации за меньшее время. Каким бы быстрым или медленным ни был код драйвера карты памяти, его производительность выше.

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

Производительность и оптимизация кода

Решив, что эффективность кода — будь то его быстродействие или объем — должна быть приоритетом, не торопитесь улучшать быстродействие или объем на уровне кода, а рассмотрите несколько вариантов. Подумайте об эффективности в контексте:
— требований к программе;
— проекта программы;
— проектов классов и методов;
— взаимодействия программы с ОС;
— компиляции кода;
— оборудования;
— оптимизации кода.

Требования к программе

Высокая производительность считается требованием гораздо чаще, чем на самом деле им является. Барри Бом рассказывает, что при разработке одной системы в компании TRW сначала решили, что время реакции системы не должно превышать 1 секунды. Это требование привело к разработке очень сложного проекта, на реализацию которого пришлось бы потратить примерно 100 млн долларов. Дальнейший анализ показал, что в 90% случаев пользователей устроит время реакции, равное 4 секундам. Изменение требования позволило снизить общую стоимость системы примерно на 70 млн долларов (Boehm, 2000b).

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

Проект программы

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

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

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

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

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

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

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

Проекты классов и методов

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

Взаимодействие программы с ОС

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

Компиляция кода

Хорошие компиляторы преобразуют ясный высокоуровневый код в оптимизированный машинный код. Иногда правильный выбор компилятора позволяет вообще забыть о дальнейшей оптимизации кода.

Оборудование

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

Оптимизация кода

Оптимизацией кода (code tuning), которой посвящена оставшаяся часть этой главы, называют изменение корректного кода, направленное на повышение его эффективности. «Оптимизация» подразумевает внесение небольших изменений, затрагивающих один класс, один метод, а чаще всего — несколько строк кода. Крупно-масштабные изменения проекта или другие высокоуровневые способы повышения производительности оптимизацией не считаются.

Каждый из уровней от проектирования системы до оптимизации кода допускает существенное повышение производительности ПО. Джон Бентли утверждает, что в некоторых случаях формула общего повышения производительности системы имеет мультипликативный характер (Bentley, 1982). Так как каждый из шести уровней допускает десятикратный рост производительности, значит, что теоретически производительность программы может быть повышена в миллион раз. Хотя для этого необходимо, чтобы результаты, получаемые на каждом из уровней, были независимы от других уровней (что наблюдается редко), этот потенциал вдохновляет.

Введение в оптимизацию кода

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

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

Кроме того, овладение мастерством написания эффективного кода — признак превращения в серьезного программиста. В теннисе вы не получаете очков за то, как берете мяч, но все же должны освоить правильный способ делать это. Вы не можете просто наклониться и взять его рукой. Если вы не хотите показаться новичком, вы ударяете по нему ракеткой, пока он не подпрыгнет до пояса, и тогда вы его ловите. Более трех ударов мяча о землю — серьезная оплошность. Несмотря на кажущуюся незначительность, способ подбора мяча считается в культуре теннисистов отличительным признаком. Компактность вашего кода также обычно не волнует никого, кроме вас и других программистов. Тем не менее в программисткой культуре способность создавать компактный и эффективный код служит подтверждением вашего класса. Увы, эффективный код не всегда является «лучшим». Этот вопрос мы и обсудим ниже.

Принцип Парето

Принцип Парето, известный также как «правило 80/20», гласит, что 80% резуль# тата можно получить, приложив 20% усилий. Относящийся не только к программированию, этот принцип очень точно характеризует оптимизацию программ.

Барри Бом сообщает, что на 20% методов программы приходятся 80%времени ее выполнения (Boehm, 1987b). В классической работе «An Empirical Study of Fortran Programs» Дональд Кнут указал, что менее 4% кода обычно соответствуют более чем 50% времени выполнения программы (Knuth, 1971).

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

Джон Бентли описывает случай, когда программа из 1000 строк проводила 80% времени в 5-строчном методе вычисления квадратного корня. Утроив быстродействие этого метода, он удвоил быстродействие программы (Bentley, 1988). Опираясь на принцип Парето, можно дать еще один совет: напишите большую часть кода на интерпретируемом языке (скажем, на Python), а потом перепишите проблемные фрагменты на более быстром компилируемом языке, таком как C.

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

Разработчики языка ALGOL — прародителя большинства современных языков, сыгравшего одну из самых главных ролей в истории программирования, — руководствовались принципом «Лучшее — враг хорошего». Стремление к совершенству может мешать завершению работы. Доведите работу до конца и только потом совершенствуйтесь. Часть, которую нужно довести до совершенства, обычно невелика.

Бабушкины сказки

С оптимизацией кода связано множество заблуждений.

Сокращение числа строк высокоуровневого кода повышает быстродействие или уменьшает объем итогового машинного кода — НЕВЕРНО!

Многие убеждены в том, что, если сократить какой-то фрагмент до одной или двух строк, он будет максимально эффективным. Рассмотрим код инициализации массива из 10 элементов:

for i = 1 to 10
a[ i ] = i
end for

Как вы думаете, он выполнится быстрее или медленнее, чем эти 10 строк, решающих ту же задачу?

a[ 1 ] = 1
a[ 2 ] = 2
a[ 3 ] = 3
a[ 4 ] = 4
a[ 5 ] = 5
a[ 6 ] = 6
a[ 7 ] = 7
a[ 8 ] = 8
a[ 9 ] = 9
a[ 10 ] = 10

Если вы придерживаетесь старой догмы «меньшее число строк выполняется быстрее», вы скажете, что первый фрагмент быстрее. Однако тесты на Microsoft Visual Basic и Java показали, что второй фрагмент минимум на 60% быстрее первого.

Примечания:
(1) Временные показатели в этой и следующих таблицах данной главы указываются в секундах, а их сравнение имеет смысл только в пределах конкретных строк каждой из таблиц. Действительные показатели будут зависеть от компилятора, параметров компилятора и среды, в которой выполняется тестирование.
(2) Большинство результатов сравнительного тестирования основано на выполнении фрагментов кода от нескольких тысяч до многих миллионов раз, что призвано устранить колебания результатов.
(3) Конкретные марки и версии компиляторов не указываются. Показатели производительности во многом зависят от марки и версии компилятора.
(4) Сравнение результатов тестирования фрагментов, написанных на разных языках, имеет смысл не всегда, так как компиляторы разных языков не всегда позволяют задать одинаковые параметры генерирования кода.
(5) Фрагменты, написанные на интерпретируемых языках (PHP и Python), в большинстве случаев тестировались с использованием более чем в 100 раз меньшего числа тестов, чем фрагменты, написанные на других языках.
(6) Некоторые из показателей «экономии времени» не совсем точны из-за округления «времени выполнения кода до оптимизации» и «времени выполнения оптимизированного кода».

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

Одни операции, вероятно, выполняются быстрее или компактнее других— НЕВЕРНО! Если речь идет о производительности, не может быть никаких «вероятно». Без измерения производительности вы никак не сможете точно узнать, помогли ваши изменения программе или навредили. Правила игры изменяются при каждом изменении языка, компилятора, версии компилятора, библиотек, версий библиотек, процессора, объема памяти, цвета рубашки, которую вы надели (ладно, это шутка), и т. д. Результаты, полученные на одном компьютере с одним набором инструментов, вполне могут оказаться противоположными на другом компьютере с другим набором инструментов.

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

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

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

До создания полностью работоспособной программы найти узкие места в коде почти невозможно. Программисты очень плохо угадывают, на какие 4% кода приходятся 50% времени выполнения, поэтому, оптимизируя код по мере его написания, они будут тратить примерно 96% времени на оптимизацию кода, который не нуждается в оптимизации. На оптимизацию по-настоящему важных 4% кода времени у них уже не останется.

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

Концентрация на оптимизации во время первоначальной разработки отвлекает от достижения других целей. Разработчики погружаются в анализ алгоритмов и сокровенные дискуссии, от которых пользователям ни тепло, ни холодно. Корректность, сокрытие информации, удобочитаемость и т. д. становятся вторичными целями, хотя потом улучшить их сложнее, чем производительность. Работа над повышением производительности после создания полной программы обычно затрагивает менее 5% кода. Что легче: повысить производительность 5% кода или улучшить удобочитаемость всего кода?

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

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

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

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

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

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

—И как быстро выполняется ваша программа?

—Ну, в среднем она обрабатывает каждый набор введенных данных примерно за 10 секунд.

—Ага! Но моей программе для этого требуется только 1 секунда.

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

— Да, но ваша программа не работает. Если бы моя не обязана была работать, я мог бы сделать так, чтобы она обрабатывала ввод почти мгновенно.

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

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

Несколько лет назад я работал над программой на C++, которая должна была генерировать графики, помогающие анализировать данные об инвестициях. Написав код расчета первого графика, мы провели тестирование, показавшее, что программа отображает график примерно за 45 минут, что, конечно, было неприемлемо. Чтобы решить, что с этим делать, мы провели собрание группы. На собрании один из разработчиков выкрикнул в сердцах: «Если мы хотим иметь хоть какой-то шанс выпустить приемлемый продукт, мы должны начать переписывать весь код на ассемблере прямо сейчас». Я ответил, что мне так не кажется — что около 50% времени выполнения скорее всего приходятся на 4% кода. Было бы лучше исправить эти 4% в конце работы над проектом. После еще некоторых споров наш руководитель поручил мне поработать над производительностью программы ( что мне и было нужно: «О, нет! Только не бросай меня в тот терновый куст!» ).

Как часто бывает, я очень быстро нашел в коде пару ослепительных узких мест. Внеся несколько изменений, я снизил время рисования с 45 минут до менее чем 30 секунд. Гораздо меньше 1% кода соответствовало 90% времени выполнения. Ну, а к моменту выпуска ПО нам удалось сократить время рисования почти до 1 секунды.

Оптимизация кода компилятором

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

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

Хороший оптимизирующий компилятор может повысить быстродействие кода на 40 и более процентов, тогда как многие из методик, описанных в следующей главе, — только на 15–30%.Так почему ж просто не написать ясный код и не позволить компилятору выполнить свою работу? Вот результаты нескольких тестов, показывающие, насколько успешно компиляторы оптимизировали метод вставки-сортировки:

Единственное различие между версиями метода заключалось в том, что при первой компиляции оптимизация была отключена, а при второй включена. Очевидно, что одни компиляторы выполняют оптимизацию лучше, чем другие, а некоторые изначально генерируют максимально эффективный код без его оптимизации. Некоторые виртуальные машины Java (Java Virtual Machine, JVM) также более эффективны, чем другие. Эффективность вашего компилятора или вашей JVM может быть другой; оцените ее сами.

Где искать жир и патоку?

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

Частые причины снижения эффективности

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

Вот результаты сравнения эффективности случайного доступа к элементам 100-элементного массива «в памяти» и записям аналогичного файла, хранящегося на диске:

Судя по этим результатам, доступ к данным «в памяти» выполняется в 1000 раз быстрее, чем доступ к данным, хранящимся во внешнем файле. В случае моего компилятора C++ время доступа к данным «в памяти» не удалось даже измерить.

Результаты аналогичного тестирования последовательного доступа к данным похожи:

Примечание: при тестировании последовательного доступа данные были в 13 раз более объемными, чем при тестировании случайного доступа, поэтому результаты двух видов тестов сравнивать нельзя.

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

Конечно, эти результаты сильно зависят от скорости сети, объема трафика, расстояния между компьютером и сетевым диском, производительности сетевого и локального дисков, фазы Луны и других факторов.

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

Замещение страниц Операция, заставляющая ОС заменять страницы памяти, выполняется гораздо медленнее, чем операция, ограниченная одной страницей памяти. Иногда самое простое изменение может принести огромную пользу. Например, один программист обнаружил, что в системе, использующей страницы объемом по 4 кб, следующий цикл инициализации вызывает массу страничных ошибок:

Пример цикла инициализации, вызывающего много страничных ошибок (Java)

Это хорошо отформатированный цикл с удачными именами переменных, так в чем же проблема? Проблема в том, что каждая строка (row) массива table содер# жит около 4000 байт. Если массив включает слишком много строк, то при каж# дом обращении к новой строке ОС должна будет заменить страницы памяти. В предыдущем фрагменте изменение номера строки, а значит, и подкачка новой страницы с диска выполняются при каждой итерации внутреннего цикла.

Программист реорганизовал цикл:

Пример цикла инициализации, вызывающего немного страничных ошибок (Java)

Этот код также вызывает страничную ошибку при каждом изменении номера строки, но это происходит только MAX_ROWS раз, а неMAX_ROWS * MAX_COLUMNS раз.

Степень снижения быстродействия кода из-за замещения страниц во многом зависит от объема памяти. На компьютере с небольшим объемом памяти второй фрагмент кода выполнялся примерно в 1000 раз быстрее, чем первый. При наличии большего объема памяти различие было всего лишь двукратным и было заметно лишь при очень больших значениях MAX_ROWS и MAX_COLUMNS.

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

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

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

В программе, про оптимизацию которой я рассказал в подразделе «Когда выполнять оптимизацию?» использовался класс AppTime, производный от коммерческого класса BaseTime (имена изменены). Объекты AppTime использовались в программе на каждом шагу и исчислялись десятками тысяч. Через несколько месяцев мы обнаружили, что объектыBaseTime инициализировались в конструкторе значением системного времени. В нашей программе системное время не играло никакой роли, а это означало, что мы без надобности генерировали тысячи системных вызовов. Простое переопределение конструктора класса BaseTime так, чтобы полеtime инициализировалось нулем, дало нам такое же повышение производительности, что и все остальные изменения, вместе взятые.

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

Относительное быстродействие кода, написанного на разных языках

Как видите, в плане быстродействия языки C++, Visual Basic и C# примерно одинаковы. Код на Java выполняется несколько медленнее. PHP и Python — интерпретируемые языки, и код, написанный на них, обычно выполняется в 100 и более раз медленнее, чем написанный на C++, Visual Basic, C# или Java. Однако к общим результатам, указанным в этой таблице, следует относиться с осторожностью. Относительная эффективность C++, Visual Basic, C#, Java и других языков во многом зависит от конкретного кода.

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

При работе над первой версией одного приложения мы столкнулись с операцией, выполнявшейся гораздо медленнее других похожих операций. Сделав массу попыток объяснить этот факт, мы выпустили версию 1.0, так и не поняв полностью, в чем дело. Однако, работая над версией 1.1, я обнаружил, что таблица БД, используемая в этой операции, не была проиндексирована! Простая индексация таблицы повысила скорость некоторых операций в 30 раз. Определение индекса для часто используемой таблицы нельзя считать оптимизацией — это просто хорошая практика программирования.

Относительное быстродействие распространенных операций

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

Табл. Быстрота выполнения часто используемых операций

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

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

Оценка производительности

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

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

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

Пример простого кода, суммирующего элементы матрицы (C++)

Как видите, код был прост, но суммирование элементов матрицы должно было выполняться как можно быстрее, а я знал, что все обращения к массиву и проверки условий цикла довольно дороги. Я знал, что при каждом обращении к двумерному массиву выполняются дорогие операции умножения и сложения. Так, обработка матрицы размером 100 на 100 требовала 10 000 умножений и сложений, что дополнялось еще и затратами, связанными с управлением циклами. Использовав указатели, рассудил я, я смогу просто увеличивать указатель, заменив 10 000 дорогих умножений на 10 000 относительно дешевых операций инкремента. Я тщательно преобразовал код и получил:

Пример попытки оптимизации кода, суммирующего элементы матрицы (C++)

Хотя код стал менее удобочитаемым, особенно для программистов, не являющихся экспертами в C++, я был очень доволен собой. Оно и понятно: все-таки я избавился от 10 000 умножений и многих операций, связанных с управлением циклами! Я был так доволен, что решил подкрепить свои чувства конкретными цифрами и оценить повышение скорости, хотя в то время я выполнял это не всегда.

Знаете, что я обнаружил? Никакого улучшения. Ни для матриц размером 100 на 100. Ни для матриц размером 10 на 10. Ни для каких-либо других матриц. Я был так разочарован, что погрузился в ассемблерный код, сгенерированный компилятором, чтобы понять, почему моя оптимизация не сработала. К моему удивлению, оказалось, что я был не первым, кому понадобилось перебирать элементы массива: компилятор сам преобразовывал обращения к массиву в операции над указателями. Я понял, что единственным результатом оптимизации, в котором можно быть полностью уверенным без измерения производительности, является затруднение чтения кода. Если оценка эффективности не оправдывает себя, не стоит приносить понятность кода в жертву сомнительному повышению производительности.

Джон Бентли описывает похожий случай, когда переписывание кода с использованием указателей снизило производительность примерно на 10%. В другой ситуации этот же подход повысил производительность более чем на 50%. См. «Software Exploratorium: Writing Efficient C Programs» (Bentley, 1991).

Ни один программист никогда не мог предсказать или обнаружить узкие места, не обладая данными. Что бы вы ни думали, реальность окажется совершенно другой. Джозеф М. Ньюкамер (Joseph M. Newcomer)

Оценка должна быть точной

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

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

Итерация

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

Однажды я написал программную реализацию алгоритма Data Encryption Standard (DES). Ну, на самом деле я писал ее не один раз, а около тридцати. При шифровании по алгоритму DES цифровые данные кодируются так, что их нельзя расшифровать без правильного пароля. Этот алгоритм шифрования так хитер, что иногда кажется, что он сам зашифрован. Моя цель состояла в том, чтобы файл объемом 18 кб шифровался на IBM PC за 37 секунд. Первая реализация алгоритма выполнялась 21 минуту 40 секунд, так что мне предстояла долгая работа.

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

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

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

Подход к оптимизации кода: резюме

Рассматривая целесообразность оптимизации кода, придерживайтесь следующего алгоритма:

1.Напишите хороший и понятный код, поддающийся легкому изменению.
2. Если производительность вас не устраивает:
a.сохраните работоспособную версию кода, чтобы позднее вы могли вернуться к «последнему нормальному состоянию»;
b.оцените производительность системы с целью нахождения горячих точек;
c.узнайте, обусловлено ли плохое быстродействие неадекватным проектом, не# верными типами данных или неудачными алгоритмами и определите, умест# на ли оптимизация кода; если оптимизация кода неуместна, вернитесь к п. 1;
d.оптимизируйте узкое место, определенное на этапе (c);
e.оцените каждое улучшение по одному за раз;
f.если оптимизация не привела к улучшению кода, вернитесь к коду, сохраненному на этапе (a) (как правило, более чем в половине случаев попытки оптимизации будут приводить лишь к незначительному повышению производительности или к ее снижению).
3. Повторите процесс, начиная с п. 2.

Ключевые моменты

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

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

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