ОПТИМИЗАЦИЯ РАБОТЫ ПРОГРАММЫ

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

1. ОПТИМИЗАЦИИ В КОМПИЛЯТОРАХ

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

Рисунок 1. Свёртка констант

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

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

Рисунок 2. Раскрутка цикла

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

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

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

Рисунок 3. Суммирование элементов одномерного массива

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

Итак, лучше работать с небольшим количеством переменных и обращаться к ним как можно чаще.

2. ХОРОШИЙ АЛГОРИТМ

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

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

Рисунок 4. Наивный алгоритм поиска НОД чисел a и b

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

Лемма

Пусть a ≥ b > 0 r – остаток от деления a на b. Тогда НОД(a,b) = НОД(r,b).

Достаточно доказать, что НОД(a,b) = НОД(a-b,b).

НОД(a,b) < НОД(a-b,b): если d делит a и b, то делит и a - b.

НОД(a,b) > НОД(a-b, b): если d делит a-b и b,  то делит и a = (a-b) +b

Основанный на данной лемме алгоритм известен как алгоритм Евклида. 

Рисунок 5. Алгоритм Евклида

Сначала на вход подаётся два числа a и b, НОД которых требуется найти. Затем идет проверка на равенство каждого из чисел нулю. Если a⩾b, тогда a делится на b и рекурсивно вызывается тот же алгоритм. Аналогично при b⩾a.

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

Итак, для того чтобы программа работала не только правильно, но и быстро необходимо:

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

Список литературы:

1. Тихонов В.А., Баранов А.В. Организация ЭВМ и систем: Учебник / Под ред. акад. В.К. Левина. — М.: Гелиос АРВ, 2008. — 400 с.
2. Спиричева Н.Р., Доросинский Л.Г.; Науч. ред. Глызин В.И.; [Урал. гос. техн. ун-т- УПИ]. Структуры данных и основные алгоритмы: Учебник — Екатеринбург: Издательство УМЦ УПИ, 2001. - 95 с.
3. Шень. А., Логарифм и экспонента. — 2-е изд., стереотипное. — М.: МЦНМО, 2013. — 24 с.