Трюк Даффа () — один зі спрособів розмотування циклу з використанням перемежовування двох синтаксичних конструкцій мови програмування 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 Мб і завантаження сервера пришвидшилось.

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

Див. також Трюк Єнсена

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

Примітки