Устройство Даффа

Те, кто интересуется системными языками вроде C и C++ обычно рано или поздно натыкаются на так называемый “Метод Даффа” (Duff’s Device). Его идея в общем заключается в ускорении работы циклов при помощи трюка, который, вероятно, сильно удивит пользователей современных языков программирования.

Такой трюк достаточно нормален для программистов на ассемблере, и ещё один лишний пример того, что на low-level уровне программирования можно выжать из железа больше.

Попробую объяснить максимально просто.

Я немного упростил код, чтобы не отвлекаться на особенности синтаксиса C. С “нормальной” версией можно ознакомиться на википедии

Допустим, нам нужен цикл, чтобы повторить (например, копирование значений куда-то) определённую операцию n-ное число раз. Типичная реализация такого цикла будет выглядеть примерно так:

register count = 123; /* любая цифра числа итераций, но больше 0 */
do {                 
    /* КАКАЯ-ТО ОПЕРАЦИЯ; */;
} while (--count > 0);

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

Дело в том, что операция сравнения, определяющая условие цикла, в терминах машинного кода довольно “медленная” и для ускорения проводить её следует как можно реже. Как это сделать? Можно увеличить количество операций в теле цикла, скажем, до 8 (цифра 8 особо ничем не обусловлена, это число может быть как больше, так и меньше):

register count = 32;
register n = count / 8;
do {
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
    /* ОПЕРАЦИЯ; */
} while (--n > 0);

Такой код будет проверять условие цикла while в 8 раз реже, что даст выигрыш в производительности по сравнению с предыдущим, однако возникает проблема: что если число итераций не кратно 8? Как быть с остатком?

Тут то нам и пригодится Метода Даффа (сама техника изобретена не Даффом, и была известна до этого ассемблер-программистам, но ему принадлежит это выражение на языке C):

register count = 19;
register n = (count + 7) / 8;
switch (count % 8) {
    case 0: do { /* ОПЕРАЦИЯ; */
    case 7:      /* ОПЕРАЦИЯ; */
    case 6:      /* ОПЕРАЦИЯ; */
    case 5:      /* ОПЕРАЦИЯ; */
    case 4:      /* ОПЕРАЦИЯ; */
    case 3:      /* ОПЕРАЦИЯ; */
    case 2:      /* ОПЕРАЦИЯ; */
    case 1:      /* ОПЕРАЦИЯ; */
           } while (--n > 0);
}

Выглядит страшно, но попробуем разобраться. Да, кусок конструкции switch-case находится прямо внутри цикла, причём не целиком (case 0: остался снаружи). Тут оказывается, что синтаксис C не запрещает нам “прыгнуть” к любой инструкции в теле цикла, например с помощью goto (так как цикл представляет собой набор инструкций с jmp-условием, которое проверяет, следует ли его продолжать). Теперь разберёмся с switch-case: каждый case это по сути просто лейбл (а switch-case в целом более ограниченный и контролируемый вариант использования goto лебл). Еще одна фишка case в том, что прыгнув на нужный case и не встретив break мы проваливаемся дальше по следующим case'ам, пока конструкция не закончится или всё-таки не возникнет break.

Теперь с этим знанием попробуем проследить, как работает эта конструкция для, например, count = 19:

• переменная n = (19 + 7) / 8 = 3 (целочисленное деление).
• в switch: 19 % 8 = 3, переходим к case 3:
• после case 3: нужная операция воспроизведётся 3 раза (это мы сразу разобрались с остатком от деления числа циклов на 8).
• далее мы оказываемся в обычном цикле do-while, case нам никак не мешает и ничего больше не делает, и мы спокойно “проваливается” сквозь.
• цилк повторится по числу n 2 раза, что добавит нам 8 * 2 = 16.
• Итого: получаем 16 + 3 = 19 выполнений операций, столько сколько нам нужно, и всего за 2 цикла (с кусочком), т.е. всего за 2 проверки условия цикла.

На сегодняшний день метод Даффа используют редко, он смущает компилятор, мешая ему проводить разного рода оптимизации кода (прекрасно понимаю его). В отдельных случаях он также может приводить к замедлению работы кода и увеличению размера исполняемого файла (см. статью на вики) (не забываем также второе правило программирования Роба Пайка). Чуть более “нормальный” вариант этого же подхода - использовать 2 цикла: один для “больших шагов по +/-8 операций за раз” плюс цикл для завершения остатков.

Но что больше всего меня поражает в этой

Потому что это буквально “хак” на уровне языка. Просто для контраста по сравнению с современными высокоуровневыми языками с их классами, функторами и виртуальными машинами, примитивная и первобытная сила C ощущается совсем иначе. Язык C в каком-то смысле абсолютно “поломанный” по сравнению с тем что ЯП предлагают сегодня, при этом его естественное состояние. За долгие годы никто (к счастью) кардинально не “““улучшил””” Си, он почти такой же, как и 40 лет назад. Но, в том числе поэтому нельзя избавиться от ощущения насколько близко находится “реальное железо” при работе с C, и насколько по настоящему можно управлять компьютером на нём.