​​Loop unrolling. Duff's device
#опытным

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

Если приглядеться в механику этого кода

switch (r) {
    case 3: goto rest3;
    case 2: goto rest2;
    case 1: goto rest1;
    default: goto main_loop;
}

rest3:
    output[i] = i * i; ++i;
rest2:
    output[i] = i * i; ++i;
rest1:
    output[i] = i * i; ++i;

main_loop:
    for (; i < count; i += 4) {
        output[i]     = i * i;
        output[i + 1] = (i + 1) * (i + 1);
        output[i + 2] = (i + 2) * (i + 2);
        output[i + 3] = (i + 3) * (i + 3);
    }

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

Но эта механика же полностью закрывается функциональностью switch. Код может проходить от кейса к кейсу, пока не встретит break и изначально можно перейти в любой из кейсов.

Давайте сделаем трах-тебедох и представим код в другом виде:

if (count == 0) return;
size_t i = 0;
size_t n = (count + 3) / 4;
switch (count % 4) {
    case 0:
        do {
            output[i] = i * i; i++;
    case 3:
            output[i] = i * i; i++;
    case 2:
            output[i] = i * i; i++;
    case 1:
            output[i] = i * i; i++;
        } while (--n > 0);
}

Как это работает

👉🏿 n – число полных итераций развёрнутого цикла, необходимых для обработки всех элементов (с учётом возможного неполного первого прохода).

👉🏿 switch (count % 4) выбирает точку входа в тело цикла do-while в зависимости от остатка. При остатке 0 начинаем с начала (полная итерация), при остатке 3 – с третьей операции и т.д.

👉🏿 Тело цикла содержит четыре одинаковых операции (вычисление квадрата и сдвиг индекса), размеченных метками case. За счёт проваливания (fall-through) первая (неполная) итерация выполняет ровно столько операций, сколько нужно для обработки хвоста, а все последующие итерации – по четыре операции.

👉🏿 Цикл продолжается, пока --n > 0, что гарантирует обработку всех элементов.

Первым такую особенность заметил мисье Том Дафф. В тот момент он работал в Lucasfilm и пытался оптимизировать копирование данных в memory-mapped регистр для анимации реального времени. Ему нужно было развернуть цикл для скорости, но была проблема — количество итераций не всегда кратно размеру развёртки.

Он вдохновился приемами из ассемблера и написал на языке K&R С(одна из ранних версий С, до стандартизации) вот такую конструкцию:

send(to, from, count)
register short *to, *from;
register count;
{
    // Begin of the function
    register n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }
}

Функция send - это такой аналог memcpy, до внедрения в стандарт этой функции. Идея такая же: прыгаем в середину свитча для обработки остатка, а дальше крутимся в развернутом while, пока не скопируем все элементы.

С тех пор код такого вида называется Duff's device или устройство Даффа.

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

Но в современном мире не стоит даже и пытаться нечто такое написать в проде.Компиляторы cами отлично разворачивают циклы, часто лучше, чем ручная оптимизация.

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

Тем не менее Duff's device остался в истории как пример вырвиглазной эксплуатации тонкостей языка в гонке за производительностью.

Be relevant. Stay cool.

#compiler #optimization #performance