Трюк Даффа

Трюк Даффа (англ. Duff's device) — один зі спрособів розмотування циклу з використанням перемежовування двох синтаксичних конструкцій мови програмування C: циклу do while та оператора switch. Був відкритий Томом Даффом у листопаді 1983 року, коли Дафф працював для Lucasfilm, для пришвидшення малювання анімації.

Розмотування циклу укрупненням відбувається для зменшення кількості операцій умовного переходу (які сповільнюють конвеєр команд), за рахунок:

• виконанням деякої кількості k (наприклад k=8) операцій за один оборот циклу та
• умовним переходом із зовні в одну із k точок всередині циклу (якщо загальна кількість операцій не кратна k).

Сам алгоритм на той час вже був відомий та використовувався в програмах на мовах ассемблера.

Буквально код Даффа, який в циклі копіював значення масиву в зовнішній порт, виглядав так. До оптимізації:

send(to, from, count)
register short *to, *from;
register count;
{
    do { /* count > 0 assumed */
        *to = *from++;
    } while (--count > 0);
}

Після оптимізації:

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

Дафф зрозумів, що «розкручений» варіант цикла може бути реалізований накладанням конструкцій switch та do while.

Хоча цей код виглядає дивно, він написаний згідно зі стандартом мови С:

• На момент винайдення цього прийому перше видання книги The C Programming Language вимагало лише, щоб тілом оператора switch був синтаксично коректний (складений) оператор, усередині якого мітки case передували будь-якому вкладеному оператору.
• У поєднанні з тим фактом, що за відсутності оператора break потік керування продовжує виконання оператора за наступною міткою case.

В даний час застосування трюку Даффа для розмотування циклів невиправдане, оскільки заважає роботі оптимізувальних компіляторів, які генерують кращий код. Наприклад, після видалення кода Даффа з XFree86 версії 4.0 (2000 рік) бинарні файли зменшились на 0,5 Мб і завантаження сервера пришвидшилось.^[1]

Цей трюк використовується для реалізації співпрограм в C/C++.

• Трюк Єнсена

• Опис та перше повідомлення Даффа на сайті Lysator.