​​Loop unrolling. Мотивация.
#новичкам

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

Компилятор позволяет нам думать о логике, в то время как сам заботится о перформансе.

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

Сегодня и дальше мы поговорим про одну из таких оптимизаций - loop unrolling или развертывание цикла.

В чём проблема обычного цикла?

Возьмём простейшую задачу: просуммировать элементы массива.

int sum = 0;
for (int i = 0; i < 1024; ++i) {
    sum += arr[i];
}

На каждый проход цикла процессор делает:

1️⃣ Загружает arr[i]
2️⃣ Прибавляет к sum
3️⃣ Увеличивает i
4️⃣ Сравнивает i с 1024
5️⃣ Если не конец — прыгает обратно

Можно было просуммировать элементы вот так:

int sum = 0;
sum += arr[0];
sum += arr[1];
sum += arr[2];
...
sum += arr[1023];

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

Так вот шаги 3–5 — это чистые накладные расходы (overhead) на использование этой абстракции. На 1024 итерациях мы теряем 1024 сравнения и 1024 условных перехода. Все это вносит свой, да мизерный, но вклад, в просадку перфа.

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

Полностью получить все плюшки и убрать все минусюшки не получится. Но получится смешать два подхода. Будем делать цикл не по каждой итерации i, а через 4 числа:

int sum = 0;
for (int i = 0; i < 1024; i += 4) {
    sum += arr[i];
    sum += arr[i+1];
    sum += arr[i+2];
    sum += arr[i+3];
}

Теперь на 256 итерациях мы делаем те же 1024 сложения, но сравнений и переходов в 4 раза меньше.

Круто? Круто. Это и называется loop unrolling.

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

Получается такой трейдоф: ускоряем код за счет красоты кода и увеличения бинаря. Классический баланс используемой памяти и скорости кода.

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

Optimize your performance. Stay cool.

#compiler #performance