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

Последнее время занимаюсь самосовершенствованием: пытаюсь постигнуть дао монад. Получается с переменным успехом: на интуитивом уровне вроде понял, но мне этого мало, хочу понять их устройство на более глубоком уровне, чтобы не просто их использовать, но и понимать, как они работают. А пока копался в доках на вики и прочих источниках, наткнулся на ссылку о «Duff's device».

Википедию прочитать, думаю, под силу каждому, но цель этого поста скорее зафиксировать полученное знание и понимание концепции мной самим, чтобы потом не забыть =)

Если кратко: устройство Даффа — это обобщение оптимизации циклов путём их развёртки. Проблема развёртки цикла с неизвестным числом повторов n в том, что при заданной глубине развёртки m существует n mod m «остаточных» итераций, которые надо обработать как особый случай. Дафф нашёл очень элегантное решение этой задачи на C:

send(to, from, count)
register short *to, *from;
register count;
{
    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);
    }
}

Как это работает: цикл из count повторов разворачивается на n равных кусков по 8 операций в каждом, а остаток операций в n mod 8 штук выполняется через switch: при первой проходе мы попадаем на один из case'ов в зависимости от этого остатка и сразу выполняем нужное остаточное число операций, а потом цикл while() работает своим обычным образом, пропуская все куски, на которые разбит исходный цикл.

За подробностями, почему так сделано и почему *to не инкрементируется — см. ссылки. Если кратко: to это не просто ссылка на адрес в памяти, а ссылка на адрес в IO-памяти, а цель всего кода — передать устройству с портом ввода-вывода по адресу to набора из count команд из памяти начиная с адреса from.