Все программы должны быть корректными, но некоторые программы должны быть быстрыми. Если программа обрабатывает видео-фреймы или сетевые пакеты в реальном времени, производительность является ключевым фактором. Недостаточно использовать эффективные алгоритмы и структуры данных. Нужно писать такой код, который компилятор легко оптимизирует и транслирует в быстрый исполняемый код.
В этой статье мы рассмотрим базовые техники оптимизации кода, которые могут увеличить производительность вашей программы во много раз. Мы также коснёмся устройства процессора. Понимание как работает процессор необходимо для написания эффективных программ.
На написание этой статьи меня вдохновила пятая глава из книги Computer Systems: A Programmer's Perspective. Моя следующая статья будет называться “Оптимизация кода: память”, где я рассмотрю техники оптимизации для лучшего использования кэша. Все программы написаны на языке C и протестированы на машине с процессором Pentium 2117U. Производительность на вашей машине может быть другая.
Блокировщики оптимизации
Компиляторы сами пытаются оптимизировать код. Когда GCC запущен с параметром -Og, он выполняет базовый уровень оптимизации, с параметром -O1 первый уровень оптимизаици. Существует и более высокие уровни оптимизации: -O2, -O3 и т. д. Чем выше уровень оптимизации, тем более радикальные изменения компилятор вносит в программу. Компиляторы могут применять только безопасные оптимизации. Это значит, что компилятор может изменять программу только так, чтобы это не изменило её поведение для всех входных данных.
Нам, как программистам, нужно понимать, что существуют определённые характеристики кода, которые не позволят компилятору совершить оптимизацию. Мы их называем блокировщиками оптимизации. Рассмотрим два типа блокировщиков оптимизации. Одним из них являются указатели. Компилятор не может точно знать, будут ли два указателя указывать на одну и ту же область памяти, и поэтому не выполняет некоторые оптимизации. Рассмотрим пример:
void twiddle1(long *xp, long *yp) {
*xp += *yp;
*xp += *yp;
}
void twiddle2(long *xp, long *yp) {
*xp += 2*(*yp);
}Функция twiddle2 выглядит более эффективной, она выполняет всего три запроса к памяти (прочитать *xp, прочитать *yp, записать *xp), в то время, как *twiddle1* выполняет шесть запросов (четыре чтения и две записи). Можно ожидать, что эти две функции имеют одинаковое поведение. Однако представьте, что xp и yp указывают на одну и ту же ячейку памяти. Тогда *twiddle1* увеличит *xp в четыре раза, а *twiddle2* – в два раза. Эти функции имеют разное поведение в некотором случае. По этой причине компилятор не посмеет трансформировать менее эффективную функцию в более эффективную.
Другой блокировщик оптимизации – вызов функций. Вообще, вызовы функций влекут накладные расходы, и нам нужно стараться их избегать. Рассмотрим пример:
long f();
long func1() {
return f() + f() + f() + f();
}
long func2() {
return 4*f();
}Вторая функция вызывает *f* четыре раза, когда первая – только один раз. Мы ожидаем, что компилятор догадается и преобразует первую функцию во вторую. Но функция *f* может иметь побочные эффекты, она может изменять глобальное состояние, как в этом примере:
long counter = 0;
long f() {
return counter++;
}В этом члучае *func1* и *func2* вернут разные результаты. Компилятору тяжело определить, имеет вызов функции побочные эффекты или нет. Когда он не может этого сделать, он рассчитывает на худшее и не выполняет оптимизацию.
Демонстрационная программа
Обычно медленные программы выполняют вычисления над большими массивами данных. Разумно будет оценивать эффективность таких программ в среднем количестве циклов, которые процессор тратит на обработку одного элемента. Введём метрику CPE (cycles per element). Если мы говорим, что программа имеет производительность CPE 2.5, значит она в среднем тратит 2.5 цикла процессора на обработку одного элемента.
Мы представим простую программу, на примере которой продемонстрируем мощные приёмы оптимизации. Структура vec является вектором элементов типа float. Функция combine0 вычисляет результат перемножения всех элементов вектора. Эту функцию мы и будем оптимизировать. Размер массива сделаем 5000 и инициализируем его случайными числами.
typedef struct {
long len;
float *data;
} vec;
long vec_len(vec *v) {
return v->len;
}
void combine0(vec *v, float *dest)
{
long i;
*dest = 1;
for (i = 0; i < vec_len(v); i++) {
*dest *= v->data[i];
}
}
#define SIZE 5000
float a[SIZE];
vec v = {a, SIZE};
int main() {
float res;
for (long i = 0; i < SIZE; i++) // инициализация вектора случайными числами
a[i] = rand();
combine0(&v, &res);
}Все программы в этой статье мы будем компилировать при помощи GCC с параметром -Og (базовый уровень оптимизации). Скомпилировав программу и сделав необходимые замеры, я получаю производительность CPE 11.05.
Для измерения производительности программы можно использовать счётчик циклов процессора (RDTSC). Предупреждаю, что это ненадёжный метод. Нужно сравнить значения счётчика до и после выполнения программы. Можно просто замерять потраченное процессорное время.
Избавляемся от неэффективностей цикла
Обычно самым интенсивным местом программы являются циклы, особенно самый внутренний цикл. Именно там и нужно прежде всего искать возможности для оптимизации. В цикле нашей программы мы постоянно вызываем функцию vec_len, которая возвращает длину вектора. Бессмысленно делать это в каждой итерации, потому что длина вектора на протяжении цикла не меняется. Разумнее будет вызвать эту функцию один раз и сохранить результат в переменную. Поэтому вынесем вызов этой функции за пределы цикла.
void combine1(vec *v, float *dest)
{
long i, len = vec_len(v);
*dest = 1;
for (i = 0; i < len; i++) {
*dest *= v->data[i];
}
}Производительность новой версии не изменилась – CPE 11.05. Видимо, компилятор сам догадался выполнить эту оптимизацию. Давайте запустим GCC без параметра -Og и скомпилируем обе версии функции вообще без оптимизации. Теперь разница заметна: combine0 – CPE 12.7, combine1 – CPE 11.1.
В данном случае компилятор догадался вставить тело функции в место вызова этой функции. Но часто компилятор не будет этого делать, потому что не сможет определить, имеет функция побочные эффекты или нет. Если функция производит какие-то дополнительные действия, подобная трансформация может изменить поведение программы. Как экстремальный пример рассмотрим цикл, который превращает прописные буквы в строчные:
void lower(char *s) {
for (long i = 0; i < strlen(s); i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}Функция *strlen* обходит всю строку, пока не встретит нулевой символ, и делает это на каждой итерации. Это катастрофически замедляет программу. Для больших строк цикл будет выполняться в тысячи раз медленнее, чем более эффективный. В идеале компилятор должен распознать, что вызов strlen всегда возвращает то же самое значение, и вынести его за пределы цикла. Но для этого нужно глубоко проанализировать тело цикла и определить, что хотя программа и изменяет символы в строке, никакой символ она не превращает в нулевой. Это за пределами возможностей современных компиляторов.
Избавляемся от лишних обращений к памяти
Многие программы часто обращаются к памяти для чтения или записи. Это занимает много времени. Желательно работать с регистрами процессора, а не с памятью. Для таких программ нужно искать возможность ввести временную локальную переменную, в которую производить запись, и только через какое-то время произвести запись из этой переменной в память.
Подсчитаем сколько раз мы обращаемся к памяти в каждой итерации. Мы читаем элемент из массива, читаем dest, складываем эти значения и записываем результат в dest. Всего три обращения к памяти. Нам не нужно каждый раз читать и писать в dest после обработки очередного элемента. Мы введём временную переменную-аккумулятор, в которой будем хранить результат, и только в самом конце произведём запись в dest. Саму переменную-аккумулятор компилятор разместит в регистре, поэтому мы избавимся от ненужных обращений к памяти.
void combine2(vec *v, float *dest)
{
long i, len = vec_len(v);
float acc = 1;
for (i = 0; i < len; i++) {
acc *= v->data[i];
}
*dest = acc;
}
Теперь мы выполняем только одно обращение к памяти в каждой итерации. Производительность улучшается с CPE 11.05 до CPE 5.02. Если вы ожидаете, что компилятор сам догадается и выполнит эту оптимизацию, то подумайте что будет если dest указывает на какой-либо элемент в векторе. В этом случае версии с аккумулятором и без вычислят разное значение. Компилятор не может знать чему будут равны указатели, поэтому готовится к наихудшему и не выполняет оптимизацию. Вызовы функций и указатели серьёзно блокируют оптимизирующие возможности компилятора.
Развёртывание цикла
Мы достигли CPE 5.02. Это не простое число, мой процессор тратит 5 циклов на выполнение умножения чисел с плавающей точкой. Можно сказать, что мы достигли определённой нижней границы.
Мой процессор тратит один цикл на выполнение сложения чисел типа int. Интересно, если вместо перемножения значений типа float, я буду складывать значения типа int, добьюсь ли я производительности CPE 1.0? Я не буду приводить здесь код, но внесу необходимые изменения в свою программу. Я получаю всего CPE 1.58. Откуда такая неэффективность?
Всё дело в том, что при выполнении цикла, процессор выполняет не только инструкции вычисления, в которых мы заинтересованы, но также инструкции, обслуживающие цикл: инкрементирование счётчика, проверка условия, переход в начало цикла. То есть обслуживание цикла имеет свои накладные расходы, и процессор производит много ненужной работы. Если тело цикла маленькое, эти пустые вычисления занимают большую долю процессорного времени.
Техника развёртывания цикла заключается в том, что за одну итерацию обрабатываются не один, а несколько элементов. Мы как бы «разворачиваем» цикл, увеличивая длину его тела и уменьшая количество витков. Таким образом мы выполняем меньше итераций, за одну итерацию совершаем больше полезной работы, и накладные расходы составляют уже не такую большую долю. Давайте немного изменим функции, складывающую целые числа:
void combine_plus(vec *v, int *dest)
{
long i, limit = vec_len(v)-1;
int acc = 0;
for (i = 0; i < limit; i+=2) {
acc = acc + v->data[i] + v->data[i+1];
}
if (i < len) acc += v->data[i];
*dest = acc;
}
Теперь программа добавляет к аккумулятору два элемента за итерацию. Обратите внимание, что последний элемент может быть не обработан в цикле, поэтому его нужно добавить к аккумулятору позже. CPE падает с 1.58 до 1.15. Обрабатывая четыре элемента за итерацию, я получаю CPE 1.03, близко к тому значению, которое хотел получить.
CPE 5.02, который мы получили, равно количеству циклов, которые тратит мой процессор на совершение умножения чисел с плавающей точкой. Для обработки одного элемента мы выполняем одно умножение, и, казалось бы, это предел, ниже которого мы не опустимся. Но на самом деле мы можем достигнуть CPE 1.04 . Чтобы понять более продвинутые техники оптимизации, нужно сперва разобраться, как работает процессор.
Введение в работу процессора
Современные процессоры очень сложны. Внутреннее устройство процессора называется микроархитектурой, и это отдельный мир, над которым мы не имеем контроля. Когда процессор читает инструкции программы, он разбивает их на примитивы, понятные ему, и обрабатывает их как ему вздумается. Если смотреть на код ассемблера, то кажется, что процессор выполняет инструкции последовательно, одна за одной, как они представлены в коде. На самом деле процессор может выполнять инструкции параллельно и даже в противоположном порядке, если уверен что это не изменит конечный результат. Выполнение процессором инструкций параллельно называется параллелизмом на уровне инструкций.
Процессор разбит на части, которые выполняют разные типы задач, мы их называем функциональными блоками. Каждый блок выполняет определённый ряд задач: чтение из памяти, запись в память, сложение целых чисел, умножение чисел с плавающей точкой и т. д. Мой процессор имеет два блока, которые выполняют сложение целых чисел. Это значит, что он может параллельно выполнять два сложения.
Представьте, что процессору нужно получить данные из памяти и это занимает 100 циклов. Но процессору будет неразумно ждать завершения этой операции, чтобы начать следующую. Ведь чтением данных из памяти занимается отдельный блок, а остальные блоки в это время могут производить другие вычисления. Поэтому процессор наперёд считывает несколько следующих инструкций и пытается нагрузить ими все функциональные блоки, даже если придётся выполнять инструкции в неправильном порядке.
Считывание инструкций наперёд называется предвыборкой. Если во время предвыборки, процессор встречает ветвление (к примеру, конструкция if-else), он пытается угадать, какая ветвь будет взята и считывает инструкции оттуда. Если позже он понимает, что была взята неправильная ветвь, он сбрасывает произведённые вычисления, восстанавливает предыдущее состояние и идёт по другой ветви. Такая ошибка стоит процессору нескольких потерянных циклов. Для многих процессоров это примерно 20 циклов.
Конвейер
Мой процессор имеет один функциональный блок, выполняющий умножения чисел с плавающей точкой, и на одно умножение он тратит пять циклов. И казалось бы, если нам нужно выполнить N умножений, нам придётся потратить 5*N циклов. Но это не так, благодаря такому устройству как конвейер.
В американских фильмах вы наверняка видели как клиент в столовой проходит с подносом нескольких поваров и каждый ковшом накладывает ему что-то своё. Это и есть конвейер. Представим столовую с пятью поварами, и обслужиться у одного из них занимает один цикл. Они могли бы обслуживать клиентов так: сначала один клиент проходит всех поваров, потом второй, потом третий и так далее. В этом случае каждые пять циклов от них отходил бы клиент с полным подносом. Но это неэффективно. Лучше если все клиенты выстроятся в очередь, и каждый цикл эта очередь будет продвигаться к следующему повару. В этом случае каждый цикл от поваров будет отходить клиент с полным подносом. Заметьте, что обслуживание одного клиента всё равно будет занимать пять циклов, но обслуживание N клиентов (если N велико) займёт примерно N циклов.
По принципу конвейера устроены функциональные блоки в процессоре. Они разделяют всю работу на несколько этапов, и на разных этапах могут одновременно обрабатываться разные инструкции. Несмотря на то, что выполнение одной инструкции может занимать несколько циклов, многие блоки могут принимать в конвейер новую инструкцию каждый цикл. Такие блоки называются полностью конвейерными. Все операции, кроме деления, выполняются в полностью конвейерном режиме. Деление считается сложной операцией, занимает 3-30 циклов и вообще не имеет конвейера.
Зависимость данных и несколько аккумуляторов
Но если конвейер позволяет нам тратить один цикл на операцию, почему тогда мы получили CPE 5.02, а не CPE 1.02? Всё дело в такой плохой вещи как зависимость данных. Вернёмся к примеру со столовой. Допустим, первый повар в столовой накладывает или рис или гречку, и по странному правилу, каждый клиент, пройдя всех поваров, решает что должен наложить первый повар следующему клиенту. Тогда мы не можем начать обслуживание следующего клиента пока текущий клиент не пройдёт всех поваров. Нам приходится ждать, потому что есть определённая зависимость. Также и в работе процессора, мы говорим, что между данными есть зависимость, если для начала работы над одними данными нам нужны другие данные, и мы должны дождаться завершения работы над ними.
В нашей программе такую зависимость данных создаёт переменная-аккумулятор. Процессор может вычислять инструкции цикла на несколько итераций вперёд. Но в каждой итерации мы вычисляем новое значение аккумулятора, учитывая его значение, вычисленное в предыдущей итерации. Поэтому мы не можем начать умножение в следующей итерации, пока полностью не завершится умножение в предыдущей. То есть каждое умножение должно пройти весь конвейер, прежде чем мы отправим в конвейер следующее. Это и мешает нам загрузить конвейер.
Давайте подумаем, как можно избавиться от этой зависимости. Если нам нужно перемножить последовательность чисел, мы может перемножать их одно на другое последовательно. А можем сначала перемножить все числа с чётным индексом, потом все числа с нечётным, а в конце перемножить два полученных результата. В таком случае перемножение двух последовательностей будут независимы друг от друга, и операции умножения из разных последовательностей смогут находиться в конвейере одновременно.
Для большей наглядности мы упростим код и будем передавать в функцию не векторную структуру, а сразу массив чисел. Такое изменение на производительность не повлияет, зато читать код станет проще. Следующая техника называется развёртывание цикла с несколькими аккумуляторами.
float combine3(float a[], long size)
{
long i, limit = size-1;
float acc0 = 1;
float acc1 = 1;
for (long i = 0; i < limit; i+=2) {
acc0 *= a[i];
acc1 *= a[i+1];
}
while (i < size) acc0 *= a[i++];
return acc0 * acc1;
}
Как видите, мы поддерживаем два независимых аккумулятора, которые в конце перемножаются, чтобы дать окончательный результат. CPE падает до с 5.02 до 2.5. Давайте сделаем развёртывание с четырьмя аккумуляторами.
float combine4(float a[], long size)
{
long i, limit = size-3;;
float acc0 = 1;
float acc1 = 1;
float acc2 = 1;
float acc3 = 1;
for (long i = 0; i < limit; i+=4) {
acc0 *= a[i];
acc1 *= a[i+1];
acc2 *= a[i+2];
acc3 *= a[i+3];
}
while (i < size) acc0 *= a[i++];
return acc0 * acc1 * acc2 * acc3;
}
CPE падает до 1.28. При восьми аккумуляторах я получаю CPE 1.04, что практически равно тому, что можно выжать из моего процессора. При написании кода таким образом нужно не забывать обрабатывать оставшиеся несколько элементов.
Мой процессор имеет только один функциональный блок, который выполняет умножение чисел с плавающей точкой. Core i7 Haswell имеет два таких блока, на нём наше приложение может достичь CPE 0.5, но пришлось бы использовать больше аккумуляторов. Вообще, если операция занимает C циклов и её выполняют N блоков, необходимое количество аккумуляторов может быть C*N.
Ассоциативность
Как мы уже говорили, компиляторы очень консервативны, боятся навредить и никогда не вносят изменения в программу, которые могут повлиять на конечный результат в каком-то случае. Компиляторы знают о технике развёртывания цикла с несколькими аккумуляторами. GCC применяет эту технику, когда запущен с третьим уровнем оптимизации или выше. Компиляторы будут применять эту оптимизацию для целых чисел, но никогда не применят её для чисел с плавающей точкой. Всё дело в ассоциативности, то есть в том, влияет ли порядок, в котором мы складываем или перемножаем числа, на конечный результат.
Если у нас есть последовательность целых чисел, то неважно в каком порядке мы их будем складывать или перемножать, мы всё равно получим один и тот же результат, даже если будет переполнение. Мы говорим, что операции сложения и умножения для целых чисел являются ассоциативными операциями. Сложение и умножение для чисел с плавающей точкой не являются ассоциативными. Допустим в последовательности чисел типа float есть очень маленькие числа и очень большие. Если мы сначала перемножим очень маленькие, то получим ноль. Умножая все остальные на ноль, мы в итоге получим ноль. Если же изначально очень маленькие мы будем умножать на очень большие, в итоге мы могли бы получить адекватный результат.
Для большинства реальных приложений нет разницы в каком порядке выполнять операции над числами, поэтому мы можем использовать эту технику оптимизации.
Векторизация
Мы ещё можем улучшить производительность. CPE 1.04, который мы достигли – не предел. Современные процессоры поддерживают специальные расширения, называемые SSE или AVX, которые позволяют работать над векторами данных. В процессоре есть специальные векторные регистры, называемые %ymm0-%ymm15, размером 16 или 32 байта. Текущие AVX регистры имеют размер 32 байта и могут содержать четыре 64-битных числа, или восемь 32-битных числа, не важно целых или с плавающей точкой. Можно считать из памяти в один такой регистр сразу 32 байта данных, считать 32 байта данных в другой регистр и выполнить арифметическую операцию сразу над четырьмя или восьмью числами параллельно.
Это железо находится в процессоре не используемое, пока вы явно не задействуете его. GCC поддерживает расширение языка C, которое позволит вам это сделать. Можно, конечно, написать код на ассемблере, но тогда программа перестанет быть переносимой. Используя эти возможности процессора, можно дальше увеличить производительность программы в 4 или 8 раз, в зависимости от размера регистров. В нашем случае, мы могли бы понизить CPE до 0.25 или 0.12.
Итоги оптимизации
Мы начали с программы, которая имела производительность CPE 11.05. Потом мы избавились от лишних вызовов функций и запросов к памяти и улучшили производительность до CPE 5.02. Потом использовали развёртывание цикла с несколькими аккумуляторами. Так смогли избавиться от зависимости данных, смогли полностью загрузить конвейер и получили CPE 1.04.То есть мы увеличили скорость выполнения программы в 11 раз. Используя векторизацию, можно заставить программу выполняться в 44-88 раза быстрее по сравнению с первоначальной версией.
Для компиляции первоначальной версии программы мы использовали базовый уровень оптимизации. Поэтому компилятор не сгенерировал максимально быстрый код. Давайте скомпилируем её с высоким, третьим уровнем оптимизации и посмотрим на что способен компилятор. Я получаю производительность CPE 5.02. Это далеко от CPE 1.04, которое мы получили, вручную трансформируя код. Мы можем также использовать векторизацию, чтобы дальше увеличить производительность в 4-8 раз, компилятор за вас этого не сделает.
Проблемы
Количество функциональных блоков, которые выполняют чтение и запись в память может быть узким местом производительности. Заметим, что эти блоки полностью конвейерные и могут принимать новую инструкцию каждый цикл. Мой процессор имеет один блок, выполняющий чтение данных из памяти в процессор. Если для обработки одного элемента, мне нужно будет получить из памяти два числа, я не смогу сделать лучше, чем CPE 2.0, потому что получение двух чисел займёт два цикла. Core i7 Haswell имеет четыре блока, которые выполняют сложения целых чисел. Но если вам нужно сложить элементы целочисленного вектора, вы не сможете добиться CPE 0.25. Потому что этот процессор имеет только два блока, выполняющих чтение из памяти – это устанавливает нижнюю границу на CPE 0.5.
Значение каждого аккумулятора хранится в отдельном регистре. x86-64 процессор имеет 16 регистров для целых чисел и 16 YMM регистров для чисел с плавающей точкой. Если мы будем использовать слишком много аккумуляторов, для них может не хватить регистров. Придётся хранить значения некоторых из них в памяти, что ухудшит производительность. Если увеличить количество аккумуляторов в нашей программе с 8 до 20, производительность падает с CPE 1.04 до CPE 1.35.
Оптимизация усложняет код, делает его трудным для понимания. Поэтому, как правило, оптимизируют критически важные части кода, где требуется максимальная производительность. Оптимизация увеличивает число потенциальных багов. Оптимизированный код нужно тщательно тестировать после каждого этапа оптимизации.
Другие техники оптимизации: реассоциация
Существует техника, называемая реассоциацией. Это когда мы в каком-то выражении расставляем кавычки по-другому, и это позволяет уменьшить зависимость данных и улучшить производительность. Допустим в нашей программе мы хотим перемножать три элемента за одну итерацию.
for (long i = 0; i < limit; i+=3) {
float x = a[i], y = a[i+1], z = a[i+2];
acc = acc * x * y * z;
}
Этот цикл имеет производительность CPE 5.02. По правилам языка C, когда нет кавычек, операции умножения выполняются слева направо. В данном случае, легко увидеть, что все операции умножения зависят от переменной acc. Процессор не может начать умножать в следующей итерации, пока не завершит все умножения в текущей. Расставим кавычки по-другому:
acc = acc * ((x * y) * z);
Значение переменных x, y и z в одной итерации не зависят от их значений в любой другой. Поэтому, пока выполняется текущая итерация, процессор может заранее вычислять два последних умножения в следующих итерациях. Производительность улучшается до CPE 1.69.
Другие техники оптимизации: условная передача данных
Как уже было сказано, процессор выполняет предвыборку, то есть считывает инструкции наперед. Если ему встречается ветвление (команды ассемблера je, jg, jl и т. д. ), он пытается угадать по какой ветви пойдёт вычисление. Если он угадывает неправильно, то теряет несколько циклов. Это называется условная передача управления.
Существует команда ассемблера cmov. Выполняя эту команду, процессор проверяет какое-то условие. Если это условие верно, он копирует значение из одного регистра в другой. Это называется условная передача данных. В данном случае не создаётся ветвления и процессору не надо ничего угадывать и рисковать потерей циклов.
Идея заключается в том, чтобы уменьшить количество ветвлений в программе, сделав поток выполнения более прямым. Для этого некоторые передачи управления выгодно заменить на передачу данных. Обычно компилятор транслирует конструкции if-else, используя команды ассемблера je, jg, jl и т. д., но иногда может использовать команду cmov. Рассмотрим такую конструкцию if-else:
if (условие)
v = выражение1;
else
v = выражение2;
Если транслировать этот код, используя передачу управления, то при выполнении программы будет вычислено или одно выражение или другое, но есть вероятность, что процессор совершит ошибку в выборе ветвления и потеряет циклы. Компилятор может избежать ветвления, если преобразует этот код следующим образом:
v1 = выражение1;
v2 = выражение2;
v = (условие) ? v1 : v2;
Когда условная инструкция очень простая, в ней только присваивается какое-то значение одной переменной, компилятор транслирует эту инструкцию на язык ассемблера с помощью команды cmov. Поэтому, последняя строка в предыдущем примере будет транслирована, используя передачу данных, не создавая ветвления. Процессору придётся вычислить оба выражения, что занимает больше циклов, но он не выполняет предсказания ветвления, что потенциально экономит циклы. Если выражения довольно просты, такое преобразование может быть выгодным.
Иногда компилятор не выполняет эту оптимизацию, потому что считает, что это ухудшит производительность. Мы можем заставить его выполнить её если перепишем код в более функциональном стиле, как представлено в предыдущем примере. Рассмотрим реальную программу.
void minmax1(int a[], int b[], int n)
{
for (int i = 0; i < n; i++) {
if (a[i] > b[i]) {
int t = a[i];
a[i] = b[i];
b[i] = t;
}
}
}
void minmax2(int a[], int b[], int n)
{
for (int i = 0; i < n; i++) {
int min = a[i] < b[i] ? a[i] : b[i];
int max = a[i] < b[i] ? b[i] : a[i];
a[i] = min;
b[i] = max;
}
}
Обе функции делают одно и то же. Они параллельно обходят пары чисел из двух массивов, устанавливая в массив a наименьшее из них, а в массив b наибольшее. Только вторая функция использует хитрую технику: она вычисляет минимальное число, вычисляет максимальное число, записывает каждое из чисел в своё место. Условия в вычислении переменных min и max настолько простые, что компилятор использует для них условную передачу данных. Разница в производительности наибольшая, если выполнить компиляцию с третьим уровнем оптимизации: minmax1 – CPE 15.6, minmax2 – CPE 1.18 (в 13.2 раза быстрее).
Заключение
Современный процессор скрывает огромную вычислительную мощь. Но чтобы получить к ней доступ, нужно писать программы в определённом стиле. Решить какие трансформации и к какой части кода применить есть «чёрная магия» написания быстрого кода. Обычно анализ совмещают с экспериментом: пробуют разные подходы, делают измерения производительности, исследуют код ассемблера для обнаружения узких мест.
Мы предложили базовую стратегию оптимизации кода:
- Высокоуровневый дизайн. Выбирайте эффективные алгоритмы и структуры данных. Никакой компилятор не заменит плохие алгоритмы или структуры данных на хорошие.
- Базовые принципы кодирования. Избегайте блокировщиков оптимизации, чтобы помочь компилятору генерировать эффективный код. Избавьтесь от ненужных вызовов функций. Если возможно, вынесите вычисления за пределы цикла. Избавьтесь от ненужных запросов к памяти. Введите временные переменные для хранения промежуточных результатов.
- Низкоуровневая оптимизация. Применяйте развёртывание циклов, чтобы уменьшить пустые вычисления. Задействуйте параллелизм на уровне инструкций, используя несколько аккумуляторов и реассоциацию. Пишите инструкции if-else в функциональном стиле, чтобы компилятор мог использовать условную передачу данных.
Автор: horowitz
