Стратегии ускорения

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

Улучшайте алгоритм и структуру данных. Наиболее важным фактором в уменьшении времени работы программы является выбор алгоритма или структуры данных — между эффективным алгоритмом и неэффективным разница может быть просто огромной. Для нашего спам-фильт-ра мы изменили структуру данных и получили выигрыш в десять раз; еще более внушительным улучшением могло стать применение нового алгоритма, который бы сократил вычисления на порядок, скажем с 0(п2) до 0(п log n). Мы уже обсуждали эту тему в главе 2, так что теперь не будем к ней возвращаться.

Убедитесь в том, что сложность такая, как надо; если она завышена, то именно в ней может крыться источник недостаточной производительности. Этот, линейный на первый взгляд, алгоритм для сканирования строки

на самом деле вовсе не линейный, а квадратичный: если s содержит п символов, то цикл выполняется п раз и при каждом исполнении вызов st rlen обходит п символов строки.

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

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

Оптимизация компилятора обычно увеличивает производительность программы в диапазоне от нескольких процентов до двух раз. Иногда, однако, она может даже замедлить программу, так что не забудьте произвести новые замеры времени. Мы сравнили результаты неоптимизированной и оптимизированной компиляции пары версий спам-фильтра. В тестовых примерах для окончательной версии алгоритма сравнения изначальное время исполнения равнялось 8.1 секунды и упало до 5.9 секунды после включения оптимизации, так что улучшение составило более 25 %. В то же время версия, которая использовала исправленную strstr, после включения оптимизации не показала никаких видимых улучшений, поскольку библиотечная функция strstr уже была оптимизирована при инсталляции; оптимизатор обращается только к исходному коду, компилируемому непосредственно в данный момент, но не к системным библиотекам. Правда, некоторые компиляторы имеют глобальный оптимизатор, который в поисках возможных улучшений анализирует всю программу целиком. Если такой компилятор есть в вашей системе, попробуйте использовать его, — может, он ужмет еще несколько циклов.

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

Тонкая настройка кода. Если объемы данных достаточно существенны, серьезное значение имеет правильный выбор алгоритма. Более того, улучшенный алгоритм будет работать на любых машинах, компиляторах и языках. Но если и при должном алгоритме вопрос быстродействия по-прежнему стоит на повестке дня, то можно попробовать тонко настроить (tune) код — отполировать детали циклов и выражений, чтобы заставить их работать еще быстрее.

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

На этой версии после компиляции с оптимизатором наш набор тестов исполнялся за 6.6 секунды. Внутренний цикл в своем условии содержал индекс массива (nstarting[c]), а его значение фиксировано для каждой итерации внешнего цикла. Мы можем избежать его многократного вычисления, единожды сохранив значение в локальной переменной:

После этого изменения время уменьшилось до 5.9 секунды, то есть примерно на 10 % — типичное значение для ускорения, которого можно достичь с помощью тонкой настройки. Есть и еще одна переменная, которую мы можем вытащить из тела цикла, — startingfc] также фиксировано. Вроде бы, если мы уберем ее вычисление из цикла, то это улучшит производительность, однако наши тесты не показали никакого изменения. Надо сказать, что это тоже типично при тонкой настройке, — некоторые вещи помогают, а некоторые нет, и это можно определить только замерами времени. Кроме того, результаты могут варьироваться для разных машин и компиляторов.

Есть и еще одно изменение, которое можно внести в спам-фильтр. Внутренний цикл сравнивает образец со строкой, однако алгоритм построен на том, что их первые символы совпадают. Соответственно, мы можем настроить код так, чтобы memcmp начинала сравнение со второго байта. Мы попробовали так сделать, и результатом стал З-процентньп прирост производительности. Это, конечно, немного, но от нас требовалось изменить всего три строчки кода, что не так уж сложно.

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

Сколько времени стоит тратить на увеличение скорости работы программы? Главный критерий — будут ли изменения достаточно результативны, чтобы окупиться. В качестве простейшего принципа можно принять следующее требование: время, потраченное на увеличение производительности программы, не должно быть больше, чем тот выигрыш во времени, который накопится благодаря внесенным изменениям за жизненный цикл программы. Исходя из этого правила, можно сказать, что изменения алгоритма в isspam были оправданы, — они потребовали дня работы, а сэкономили (и продолжают экономить) по нескольку часов каждый день. Удаление индекса массива из внутреннего цикла не сыграло столь глобальной роли, однако все равно имело смысл, поскольку программа эксплуатируется большим количеством пользователей. Оптимизация программ, которые используются коллективно, — вроде спам-фильтра или библиотеки — выгодна практически всегда, а оптимизация тестовых программ не выгодна почти никогда. Программу, которая будет считать что-нибудь в течение года, стоит доводить до максимального совершенства; более того, если через месяц ее работы вы придумаете способ 10-процентного ее ускорения, то эту программу стоит запустить заново.

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

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