Тема 2.8. Оптимизация программ. Оптимизирующие компиляторы

Понятие оптимизации программ

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

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

Основная цель профилировки – это исследование характера поведения приложения во всех его точках. В зависимости от степени детализации в качестве «точки» рассматривается как отдельная машинная команда, так и целая конструкция высокого языка - функция, цикл, процедура. Сложная программа состоит из большого числа функций. Нет смысла оптимизировать их все – трудоемкость такого подхода будет выше выгод, полученных от оптимизации программы целиком. Для начала необходимо локализовать участки кода с максимальной вычислительной трудоемкостью. Участки программы, которые в наибольшей степени влияют на ее производительность, в силу наиболее частого выполнения или своей ресурсоемкости называются критическим кодом. В поиске критического кода программы используют профайлеры (профилировщики) – специальные программы, которые измеряют временные затраты на выполнение участков кода программы. Профилировщики представляют возможности для оптимизации программ. К таким программам относятся Intel VTune, AMD Code Analyst, profile.exe и множество других. Наиболее мощным из них на сегодняшний день является пакет от Intel. Эта программа позволяет измерить время обработки каждой команды и вывести полную статистику о состоянии процессора при выполнении каждой команды.

Большинство современных профилировщиков поддерживают следующий набор базовых операций:

• определение общего времени исполнения каждой точки программы;

• определение удельного времени исполнения каждой точки программы;

• определение причины и/или источника конфликтов;

• определение количества вызовов той или иной точки программы;

• определение степени покрытия программы.

Основные правила оптимизации:

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

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

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

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

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

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

1. Производительность программы признана удовлетворяющей;

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

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

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

Ко всем методам оптимизации алгоритма предъявляются следующие требования:

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

2. оптимизация не должна увеличивать трудоемкость разработки (в том числе тестирования) приложения более чем на 10-15%.

3. оптимизирующий алгоритм должен давать выигрыш не менее чем на 20-25% в скорости выполнения.

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

Алгоритмические приемы оптимизации

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

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

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

На практике используется весьма широкий набор машинно-независимых оптимизирующих преобразований, что связано с большим разнообразием неоптимальностей. К ним относятся:

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

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

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

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

• реализация действий - это способ повышения быстродействия программы за счет выполнения определенных ее вычислений на этапе трансляции.

• сокращение программы и другие методы.

Машинно-зависимые приемы оптимизации

Машинно-зависимые используют особенности устройства и работы конкретной системы. Ярким примером машинно-зависимой оптимизации является векторизация операций, т.е. использование потоковых расширений процессора, таких как MMX (MultiMedia eXtensions), SSE (Streaming SIMD Extensions) и т.п. Машино-зависимую оптимизацию можно выполнять двумя различными способами. Первый способ основан на понимании работы кодогенератора компилятора, его алгоритма и рекомендуется для приложений, в которых компилятор выбирается в начале проекта и в дальнейшем не меняется. При использовании такого способа преобразуется исходный код программы, написанный на языке высокого уровня. Для тех проектов, в которых заранее не известен компилятор (OpenSource проекты, кроссплатформенные приложения) применятся другой способ, основанный на замещении ресурсоемких участков кода ассемблерными вставками. При такой оптимизации ухудшается переносимость кода на другие платформы. Машинно-зависимые способы оптимизации довольно хорошо автоматизируются и большую часть их выполняют оптимизирующие компиляторы. Однако всегда остаются моменты в программе, которые можно оптимизировать вручную.