Некоторые приемы оптимизации программ
Приступая к выполнению нового проекта, программист должен иметь в виду, что главная цель – создание такой программы, которая работает правильно, т.е. сообщает пользователю решение той задачи, которая интересует заказчика. Если цель достигнута, можно считать, что проект выполнен успешно. Но иногда оказывается, что решение поставленной задачи получается слишком дорогой ценой. Если речь идет, например, о расчете характеристик новой модели автомобиля, то для получения набора расчетных характеристик могут потребоваться часы, а то и сутки процессорного времени. С одной стороны, это тормозит работу по проектированию новой модели, а с другой стороны – процессорное время часто является оплачиваемым ресурсом, стоимость которого может быть достаточно большой. При работе с базами данных может оказаться, что время доступа к требуемой записи слишком велико и т.д. В этом случае программисту приходится заниматься оптимизацией задачи.
Оптимизацией называется такое преобразование исходного текста программы, при котором результат ее выполнения остается неизменным, но улучшаются ее некоторые характеристики. Эти характеристики зависят от выбранных критериев оптимизации. Основными критериями оптимизации являются:
время выполнения программы;
затраты оперативной памяти;
При оптимизации программы необходимо выявить те фрагменты исходного текста, которые являются «основными потребителями» ресурса, а затем перепрограммировать эти фрагменты, решая задачу оптимизации.
Обратимся к проблеме оптимизации программы по затратам процессорного времени. Такая оптимизация особенно важна для расчетных программ, в которых большой удельный вес имеют математические вычисления.
Оптимизация, не зависящая от компилятора
Современные компиляторы, т.е. программы, создающие на основе исходного текста программы исполняемый код, как правило, выполняют и оптимизацию этого кода, размещают инструкции процессору таким образом, чтобы увеличить скорость выполнения программы. Вмешательство программиста в этот процесс не требуется. Следует иметь в виду, что оптимизация компилятором выполняется достаточно осторожно и возможности такой автоматической оптимизации ограничены.
Перечислим некоторые приемы, которые может использовать программист для написания исходного текста программы.
инициализация объектов данных
Во многих программах какую-то часть объектов данных необходимо инициализировать, т.е. присваивать им начальные значения. Такое присваивание выполняется либо в самом начале программы, либо, например, в начале цикла. Правильная инициализация объектов данных позволяет сэкономить драгоценное процессорное время. Так, например, если речь идет об инициализации массивов, использование цикла, скорее всего, будет менее эффективным, чем объявление этого массива типизированной константой.
программирование арифметических операций
В том случае, когда значительная часть работы программиста отводится арифметическим вычислениям, немалые резервы повышения скорости работы программы таятся в правильном программировании арифметических (и логических) выражений. Важно понимать, что различные арифметические операции значительно различаются по быстродействию. Самыми быстрыми являются операции сложения и вычитания. Более медленным является умножение, затем идет деление. Относительно много времени тратится на обращение к подпрограммам. Быстродействие также зависит и от типа операндов.
Оптимизация времени выполнения программы на С++ (убираем условные переходы)
При оптимизации времени выполнения алгоритма, использующего LDPC декодер, профайлер привел к функции, вычисляющей следующее значение:
где a и b — целые числа. Количество вызовов шло на миллионы, а реализация ее была достаточно проста и бесхитростна:
int LLR(int a, int b) < if (a>0) return (b>0) ? __min(a,b) : -__min(a,-b); else return (b>0) ? -__min(-a,b) : __min(-a,-b); > Функция состоит, по сути, из трех последовательных операций сравнения. Это дает (с учетом оптимизации компилятора) два (если числа разных знаков) или три (если одного) условных перехода для получения результата. Вспомнив о потенциальных проблемах конвеера при большом количестве условных переходов, было решено уменьшить их количество или даже избавиться от них. Для оценки быстродействия был написан небольшой
#include static inline int LLR(int a, int b) < if (a>0) return (b>0) ? __min(a,b) : -__min(a,-b); else return (b>0) ? -__min(-a,b) : __min(-a,-b); > int _tmain(int argc, _TCHAR* argv[]) < SetPriorityClass(GetCurrentProcess(),REALTIME_PRIORITY_CLASS); SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_TIME_CRITICAL); srand(0); int x(0); __int64 t1,t2; QueryPerformanceCounter((LARGE_INTEGER*)&t1); for (size_t i=0;i>4;i++) < int a = rand() - RAND_MAX / 2; int b = rand() - RAND_MAX / 2; /* x += LLR(a,b);*/ >QueryPerformanceCounter((LARGE_INTEGER*)&t2); t2 -= t1; QueryPerformanceFrequency((LARGE_INTEGER*)&t1); _tprintf_s(_T("%f"),t2/(t1*1.)); return 0; > Сборка производилась в MSVS 2008 в конфигурации Release (настройки по умолчанию) для платформы x86.
Для начала, закомментируем вызов расчетной функции чтобы оценить время выполнения цикла с генерацией случайных чисел (к сожалению, вызов QueryPerformanceCounter() сам по себе довольно медленный и приводит к значительному искажению результата если его делать внутри цикла). Запускаем проект несколько раз, чтобы убедится в повторяемости результата. На машине с процессором Intel Core i7-3770 c частотой 3.4 ГГц время выполнения составляет в среднем 9.2 секунды. Если раскомментировать вызов расчетной функции, пересобрать проект и повторить эксперимент — получаем примерно 11.5 секунд. Прирост времени выполнения налицо, с ним и будем бороться.
Попробуем избавиться от условных операторов. Для начала выясним знак произведения a и b. Вычислять его в лоб некорректно из-за возможного переполнения. Так как нам важен только знак (то есть значение бита знакового разряда целого числа), то уместно воспользоваться операцией xor для определения знака произведения a и b. Далее, сдвинем результат a xor b вправо на 31 бит (оставляя только знаковый разряд) и получим 0 в случае неотрицательного числа и 1 в случае отрицательного. Умножим это значение на два, вычтем из единицы и получим -1 для отрицательного числа и 1 для неотрицательного:
Теперь рассчитаем модули a и b. Аналогичным методом определяем знаковые коэффициенты a и b и умножаем на них:
int c; c = 1-2*(((unsigned)a)>>31); a *= c; c = 1-2*(((unsigned)b)>>31); b *= c; Перейдем к расчету минимума. Поскольку a и b уже имеют неотрицательные значения, рассчитать минимум можно, ориентируясь на знак их разности:
int numbers[2], min; numbers[0] = b; numbers[1] = a; a -= b; c = (unsigned(a))>>31; min = numbers[c]; static inline int LLR_2(int a, int b) < int sign, numbers[2]; sign = 1-2*(((unsigned)a^b)>>31); a *= 1-2*(((unsigned)a)>>31); b *= 1-2*(((unsigned)b)>>31); numbers[0] = b; numbers[1] = a; a -= b; return sign*numbers[((unsigned)a)>>31]; > Заменим вызов LLR() на LLR_2() и посмотрим, что получилось. В ассемблерном коде теперь ни одного условного перехода, зато появились три инструкции целочисленного умножения imul (умножение на 2 компилятор сам заменяет на сдвиг). Прогнав тестовую программу, получаем следующий результат — время выполнения составляет 9.4 секунды! Итого, сравнивая времена «нетто» (2.1 и 0.2 секунды соответственно) для двух вариантов расчета искомого значения, получаем десятикратное * увеличение скорости выполнения требуемой операции.
Попробуем пойти еще немного дальше. Целочисленное умножение необходимо только для перемены знака числа, которую можно выполнить напрямую. В частности, вычисление модуля числа a можно реализовать следующим образом:
unsigned int mask[] = ; unsigned int constant[] = ; int c = ((unsigned)a)>>31; a = a^mask[c]+constant[c]; И наконец, заменим сдвиг вправо на 31 бит единичным циклическим сдвигом влево с помощью функции _rotl(). Забегая вперед отметим, что компилятор преобразует ее вызов напрямую в инструкцию rol без использования call. Соберем все вместе еще раз и получим
static unsigned int mask[] = ; static unsigned int constant[] = ; static inline int LLR_3(int a, int b)
Заменяем вызов LLR()_2 на LLR_3() и видим, что значимого прироста это не дает (время выполнения составляет примерно те же 9.4 секунды с небольшой разницей в третьем знаке в меньшую сторону). Получается, что imul на современных процессорах выполняется довольно быстро!
Вернемся к алгоритму, с которого все началось. Описанной оптимизацией только лишь одной функции удалось сократить время обработки единичного блока данных со 160 до 140 секунд (при выполнении на i7), что составляет более 10% и является весьма неплохим результатом. На очереди еще несколько похожих функций…
Ну и напоследок предлагаю вариант реализации функции определения максимума двух целых 32-разряздных чисел. Написан он был уже чисто из академического любопытства. Желающие могут не спешить заглядывать под спойлер и попробовать реализовать подобное сами. Вариант без условных переходов работает примерно втрое быстрей стандартного макроса __max() (при выполнении на i7). Удачи в оптимизации ваших программ!
static inline int max(int a, int b) < int numbers[2][2]; numbers[0][0] = b; numbers[0][1] = a; numbers[1][0] = a; numbers[1][1] = b; int sign_a = (unsigned)a>>31; int sign_b = (unsigned)b>>31; int sign_ab = (unsigned)(a^b)>>31; int abs_a = (1-2*sign_a)*a; int abs_b = (1-2*sign_b)*b; int sign_a_b = (unsigned)(abs_a-abs_b)>>31; int c0 = sign_ab; int c1 = ((1^(sign_a_b)^(sign_a | sign_b)) & (1^c0)) | (sign_ab & sign_a); int result = numbers[c0][c1]; return result; > *UPD. В комментариях пользователь shodan привел пример, в котором rand() убран из подсчета времени, а чтение данных производится из заранее сформированного массива. В этом случае прирост производительности приблизительно трехкратный. По-видимому, это связано с более эффективной работой конвеера при чтении данных из массива.