Оптимизация
Поговорим об оптимизации.
Что нужно оптимизировать? Когда? И нужно ли вообще? В этих вопросах легко заблудиться, если с самого начала не выбрать правильную точку зрения. Взгляд со стороны пользователя, все сразу ставит на свои места:
- Программа должна делать то, что от нее требуется.
- Она должна это делать хорошо.
- работа с внешними устройствами
- системные вызовы
- вызовы собственных функций
- локальные управляющие структуры
- специальный подбор команд и оптимальное использование регистров
Именно так: глупо оптимизировать неправильно работающий код. Если же пользователя устраивает текущее быстродействие -- не стоит искать неприятности.
Итак, анализ проведен, решение принято -- ускоряемся! Что может ускорить нашу программу? Да все, что угодно; вопрос поставлен некорректно. Что может существенно ускорить нашу программу? А вот над этим уже стоит подумать.
Прежде всего, стоит подумать о "внешнем" ускорении, т.е. о не приводящих к изменению исходного кода действиях. Самый широкораспространенный метод -- использование более мощного "железа". Увы, зачастую это не самый эффективный способ. Как правило, гораздо большего можно добиться путем правильного конфигурирования того, что есть. Например, работа с БД -- практически всегда самое узкое место. Должно быть очевидно, что правильная настройка сервера БД -- это одно из самых важных действий и за него всегда должен отвечать компетентный специалист. Вы будете смеяться, но грубые оплошности админов происходят слишком часто, чтобы не обращать на них внимание (из моей практики: неоднократно время работы приложения уменьшалось с нескольких часов до нескольких минут (!) из-за очевидной команды UPDATE STATISTICS; фактически, перед анализом плана испонения тяжелых SQL-запросов всегда полезно невзначай поинтересоваться актуальностью статистики. Не менее частым происшествием является "случайная потеря" индекса важной таблицы в результате реорганизации или резервного копирования БД).
Коль скоро среда исполнения правильно сконфигурирована, стоит обратить внимание непосредственно на код. Очевидно, что максимальная скорость эскадры определяется скоростью самого медленного корабля. Он-то нам и нужен. Если "эскадрой" является набор SQL-запросов работающего с БД приложения, то, как правило, никаких трудностей с определением узких мест не возникает. Трудности возникают с определением узких мест "обычных" приложений.
Узкие места нужно искать только с помощью объективных измерений, т.к. интуиция в данной области чаще всего не срабатывает (не стоит утверждать, что не работает вообще). Причем измерять относительную производительность имеет смысл только при "релиз"-настройках компилятора (при отключенной оптимизации узкие места могут быть найдены там, где их нет. Увы, данного рода ошибки допускают даже опытные программисты) и на реальных "входных данных" (так, например, отличные сравнительные характеристики в сортировке равномерно распределенных int, отнють не гарантируют отличную работу на реальных ключах реальных данных). Действительно серьезным подспорьем в поиске узких мест являются профайлеры -- неотъемлемая часть любой профессиональной среды разработки.
Когда критический участок кода локализован, можно приступать к непосредственному анализу. С чего начать? Начинать нужно с самых ресурсоемких операций. Как правило, по требуемому для исполнения времени, операции легко разделяются на слои, отличающиеся друг от друга на несколько порядков:
Например, не стоит заниматься вопросами размещения управляющей переменной цикла в соответствующем регистре процессора, если в данном цикле происходит обращение к диску. Вызовы собственных функций существенно отличаются от системных вызовов тем, что когда мы обращаемся к системе, происходит переключение контекста потока (системный код имеет больше привилегий, обращаться к нему можно только через специальные шлюзы) и обязательная проверка достоверности переданных аргументов (например, система проверяет действительно ли ей передана корректная строка путем ее посимвольного сканирования; если при этом произойдет нарушение прав доступа или ошибка адресации, то приложение будет об этом проинформировано; тем самым исключается возможность сбоя внутри ядра системы, когда неясно что делать и кто виноват; наиболее вероятный результат -- blue death screen, system trap и т.д., т.е. невосстановимый сбой самой системы).
Как правило, только в исключительных случаях заметного ускорения работы можно достичь путем локальных улучшений (которыми пестрят древние наставления: a+a вместо 2*a, register int i; и т.д.), современные компиляторы прекрасно справляются с ними без нас (вместе с тем, генерация компилятором недостаточно оптимального кода "в данном конкретном месте" все еще не является редкостью). Серьезные улучшения обычно приносит только изменение алгоритма работы.
Первым делом стоит обратить внимание на сам алгоритм (классическим примером является сортировка с алгоритмами O(N*N), O(N*log(N)) и O(N*M) стоимости или выбор подходящего контейнера). Но не попадите в ловушку! Память современных компьютеров уже не является устройством произвольного доступа, в том смысле, что промах мимо кэша при невинном обращении по указателю может обойтись гораздо дороже вызова тривиальной функции, чей код уже попал в кэш. Известны случаи, когда изменение прохода большой двумерной матрицы с последовательного построчного на "обманывающий" кэш постолбцовый замедляло работу алгоритма в несколько раз!
Если же принципиальный алгоритм изначально оптимален, можно попробовать использовать замену уровней ресурсоемкости. Классическим примером является все то же кэширование. Например вместо дорогостоящего считывания данных с диска, происходит обращение к заранее подготовленной копии в памяти, тем самым мы переходим с первого уровня на второй-третий. Стоит отметить, что техника кэширования находит свое применение не только в работе с внешними устройствами. Если, например, в игровой программе узким местом становится вычисление sin(x), то стоит подумать об использовании заранее рассчитанной таблицы синусов (обычно достаточно 360 значений типа int вместо потенциально более дорогой плаваючей арифметики). Более "прикладной" пример -- это длинный switch по типам сообщений в их обработчике. Если он стал узким местом, подумайте об использовании таблицы переходов или хэширования (стоимость O(1)) или же специальной древовидной структуры (стоимость O(log(N))) -- существенно лучше O(N), обычно обеспечиваемого switch. Ну а про возможность использования виртуальной функции вместо switch я даже не стану напоминать.
Все эти замечания применимы в равной степени к любому языку. Давайте посмотрим на что стоит обратить внимание программистам на C++.
Прежде всего, стоит отметить, что все более-менее существенные маленькие хитрости собственно C++ уже были рассмотрены в предыдущих примерах, так же как и скрытые накладные расходы. Быть может, за кадром осталась только возможность "облегченного вызова функции", т.к. она является не частью (стандартного) C++, а особенностью конкретных реализаций.
C++ как и C при вызове функции размещает параметры в стеке. Т.е. имея параметр в регистре, компилятор заносит его в стек, вызывает функцию, а в теле функции опять переносит параметр в регистр. Всего этого можно избежать использовав соответствующее соглашение вызова (в некоторых реализациях используется зарезервированное слово _fastcall), когда параметры перед вызовом размещаются непосредственно в регистрах, исключая тем самым ненужные стековые операции. Например в простом тесте: void f1(int arg) { Var+=arg; }
void _fastcall f2(int arg) { Var+=arg; }
функция f1() работала на 50% медленнее. Конечно, реальную выгоду из этого факта можно получить только при массовом использовании функций облегченного вызова во всем проекте. И эта совершенно бесплатная разница может быть достаточно существенной.
Еще один немаловажный фактор -- размер программ. Откуда взялись все эти современные мегабайты? Увы, большая их часть -- мертвый код, реально, более 90% загруженного кода никогда не будет вызвано! Не беда, если эти мегабайты просто лежат на диске, реальные трудности появляются, когда вы загружаете на выполнение несколько таких монстров. Падение производительности системы во время выделения дополнительной виртуальной памяти может стать просто катастрофическим.
Если при разработке большого проекта изначально не придерживаться политики строгого определения зависимостей между исходными файлами (и не принимать серьезных мер для их минимизации), то в итоге, для успешной линковки будет необходимо подключить слишком много мусора из стандартного инструментария данного проекта. В несколько раз больше, чем полезного кода. Из-за чего это происходит? Если функция f() из file1.cpp вызывает g() из file2.cpp, то, очевидно, мы обязаны подключить file2.cpp к нашему проекту. При этом, если не было принято специальных мер, то в file2.cpp почти всегда найдется какая-нибудь g2(), как правило не нужная для работы g() и вызывающая функции еще какого-либо файла; и пошло-поехало... А когда каждое приложение содержит свыше полусотни исходных файлов, а в проекте несколько сотен приложений, то навести порядок постфактум уже не представляется возможным.
Отличное обсуждение локальных приемов оптимизации можно найти у Paul Hsieh "Programming Optimization". Не очень глубокий, а местами и откровенно "слабый", но, тем не менее, практически полезный обзор более высокоуровневых техник представлен в книге Steve Heller "Optimizing C++".
