​​Loop unrolling. Хвосты
#новичкам

Предыдущий пост тут.

Следующие пару постов могут быть немного скучными и замудренными, но темы по смыслу именно так бьются. Разговор о хвостах нужен, чтобы правильно понять одну технику(спойлер: Duff device)

Удобненько получилось, что в прошлом посте число итераций цикла делилось на 4. 1024 % 4 = 0.

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];
}

Но как разворачивать циклы, если число итераций не делится нацело на фактор развертывания(количество повторов операции в развертке)?

Да тем же циклом. Обрабатываем целую часть развернутым циклом и потом дорабатываем остаток:

int sum = 0;
int i = 0;
int unroll_factor = 4;

int main_limit = n - n % unroll_factor;
for (; i < main_limit; i += unroll_factor) {
    sum += arr[i];
    sum += arr[i + 1];
    sum += arr[i + 2];
    sum += arr[i + 3];
}
// HERE
for (; i < n; ++i) {
    sum += arr[i];
}

Последний цикл - это и есть дообработка хвоста.

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

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

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

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

See the job through. Stay cool.

#performance