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

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

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

Таким образом, оптимизация программного кода – это один из способов модификация с целью повышения эффективности (производительности) работы кода.

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

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

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

Оптимизация должна происходить в несколько этапов:

1. на стадии проектирования программы (выбор оптимальных алгоритмов)

2. на стадии написания программы/после написания (оптимальная реализация выбранных алгоритмов)

3. оптимизация программы под заданную архитектуру (учет особенностей процессора, организации памяти)

Зачем нужна оптимизация, неужели компиляторы не смогут хорошо оптимизировать нашу программу? На такой вопрос можно возразить так:

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

● Компилятор не обладает базой алгоритмов.

● Может ваша программа так и должна выполняться как вы ее написали?

● Знание программиста о программе (предметной области) много шире, чем знание компилятора о ней.

● Плохую программу ни один компилятор не сможет хорошо оптимизировать.

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

Среди целей оптимизации можно выделить:

• уменьшение размера кода

• уменьшение объема используемой оперативной памяти

• уменьшение объема потребления ресурсов процессорного, сетевого трафика итд

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

• сокращение времени ответа

• уменьшение количества операций ввода – вывода.

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

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

Оптимизация стоит на трех «китах» — естественность, производительность, затраченное время. Давайте разберемся подробнее, что они означают.

1. Естественность. Код должен быть аккуратным, модульным и легко читабельным.

Каждый модуль должен естественно встраиваться в программу.

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

2. Производительность. В результате оптимизации вы должны получить прирост производительности программного продукта.

Как правило, удачно оптимизированная программа увеличивает быстродействие минимум на 20-30% в сравнение с исходным вариантом.

3. Время. Оптимизация и последующая отладка должны занимать небольшой период времени. Оптимальными считаются сроки, не превышающие 10 – 15 % времени, затраченного на написание самого программного продукта. Иначе это будет нерентабельно.

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

Существуют такие понятия как высокоуровневая и низкоуровневая оптимизация.

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

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

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

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

Принципиально различаются два основных вида оптимизирующих преобразований:

- преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка

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

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

- преобразования результирующей объектной программы.

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

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

Машинно-независимые методы оптимизации кода (зависят от типов синтаксических конструк­ций исходного языка), сокращают затраты процессорного времени:

• оптимизация линейных участков программы

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

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

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

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

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

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

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

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

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

К арифметическим преобразованиям можно отнести такие действия:

+ замена возведения в степень на умножение

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

+ замена умножения сложением

+ замена чисел с плавающей запятой числами с фиксированной точкой или целые числа

+ замена чисел с плавающей запятой с удвоенной точностью числами с одинарной точностью

+ замена тригонометрических функций их эквивалентами;

• Инициализация объектов данных

Часть объектов необходимо инициализировать, то есть присвоить им начальные значения.

Такое присваивание выполняется либо в самом начале программы, либо, например, в конце цикла.

Так, например, если речь идет об инициализации массивов, использование цикла, скорее всего, будет менее эффективным, чем объявление этого массива прямым присвоение

• Оптимизация логических выражений

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

Иногда по результату первой операции или даже по значению одного операнда можно заранее определить результат вычисления все­го выражения.

Операция называется предопределенной для некоторого значения операнда, если ее результат зависит только от этого операнда и остается неизменным (инвари­антным) относительно значений других операндов.

Для оптимизации логических выражений используются факты:

+ Операция логического сложения (or) является предопределенной для логиче­ского значения «истина» (true)

+ Операция логического умножения (and) предопре­делена для логического значения «ложь» (false).

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

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

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

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

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

- Прекращение проверки сразу же после получения ответа - Некоторые языки поддерживают так называемую «сокращенную оценку выражений», при которой компилятор генерирует код, автоматически прекращающий проверку после получения ответа.

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

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

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

• Оптимизация вызовов процедур и функций

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

- передача параметров через регистры процессора - позволяет разместить все или часть параметров, передаваемых в процедуру или функцию, непосредствен­но в регистрах процессора, а не в стеке.

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

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

- подстановка кода функции в вызывающий объектный код (inline-подстановка) - основан на том, что объектный код функции непосредственно включается в вызывающий объектный код всякий раз в месте вызова функции.

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

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

• Оптимизация циклов

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

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

Но есть методы оптимизации программ, специально ориентированные на оптимиза­цию циклов:

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

Инвариантные фрагменты кода – фрагменты, которые не зависят от управляющей переменной цикла.

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

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

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

Простейшей индуктивной переменной является переменная-счетчик цикла с пе­речислением значений (цикл типа for, который встречается в синтаксисе многих современных языков программирования).

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

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

- Зависимость типа цикла и времени выполнения – цикл со счетчиком и цикл с постусловием при всех прочих равных условиях совпадает, при этом цикл с предусловием выполняется несколько дольше (примерно на 20-30 %).

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

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

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

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

Настройка окружения. Используемая СУБД или операционная система могут иметь некорректные настройки «по умолчанию». Рекомендуется проверить настройки, для исключения лишних функций, замедляющих процесс.

Удаление ненужного функционала. Сокращение ненужного кода или реализация функционала с чистого листа.

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

Для реализации меморизации перед тем, как функция будет выполняться, необходимо проверять условие – исполнялась ли функция ранее.

По итогам можно получить два варианта:

 функция вызвана в первый раз, тогда она выполняется, а результат

сохраняется;

 модуль уже работал, можно использовать сохраненный результат.

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

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

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

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

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

Отличия рефакторинга и оптимизации производительности

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

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

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

Цель оптимизации — улучшение производительности программы

Цель рефакторинга —улучшение понятности кода.

После оптимизации исходный код может стать сложнее для понимания.

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

Контрольные вопросы:

1. Основные цели оптимизации

2. Оптимизация программного кода - это

3. Основные принципы оптимизации

4. В чем заключается смысл высокоуровневой и низкоуровневой оптимизации

5. Вида оптимизирующих преобразований

6. Машинно-независимые методы - это

7. Машинно-зависимые методы - это

8. Опишите какие существуют методы оптимизации

9. Отличия рефакторинга и оптимизации производительности

10. Этапы проведения оптимизации

11. Что относится к арифметическим преобразованиям

12. Что относится к оптимизации логических выражений

!! Описать самостоятельно !!

Дополнительные методы оптимизации:

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

• Распределение регистров процессора

• Оптимизация кода для процессоров, допускающих распараллеливание вычислений

2. Файловый ввод/вывод

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

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

3. Оптимизация работы с памятью

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

• производить сжатие данных;

• производить перевычисление данных;

• избегать дублирования данных.

Сжатие данных здесь понимается двояко: как более компактное представление данных с которыми можно работать в сжатом виде и как сжатие только в целях минимизации памяти.

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

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

4. Инструменты оптимизации программ: VTune (Intel), Code Analyst (AMD), gprof (GNU).

5. Способы измерения и программные средства для измерения. Описать алгоритм проведения измерений:

- объема используемой оперативной памяти

- объема потребления ресурсов процессорного

- скорости выполнения программы

- времени ответа