risorse | duff's device
Il Duff's device è un costrutto C/C++ che effettua l'unroll di un ciclo tramite una combinazione piuttosto «creativa» di uno switch e un while. La formulazione originale è la seguente (cfr. [4]):
/*
* loop standard
*/
register short *to, *from;
register count;
{
do
*to = *from++;
while (--count > 0);
}
/*
* duff's device equivalente
*/
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);
}
}
Per quanto esoterico, il codice è perfettamente legale. In rete si trovano diverse risorse che ne spiegano il funzionamento[2][3]. Di seguito, il mio tentativo.
La versione iniziale del loop:
#include <iostream>
int main() {
int i = 0;
int n = 19;
while (n > 0) {
std::cout << ++i << " ";
--n;
}
std::cout << std::endl;
return 0;
}
/* output:
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
Versione con unroll di ampiezza 8; si noti il secondo ciclo for, che si occupa di effettuare le operazioni non coperte dal ciclo “srotolato” nel caso il numero di ripetizioni richieste non sia un multiplo di 8:
// ...
const int unrolled_loops = n / 8;
for (int j = 0; j < unrolled_loops; ++j) {
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
}
const int uncovered_by_unrolled_looping = n % 8;
for (int j = 0; j < uncovered_by_unrolled_looping; j++) {
std::cout << ++i << " ";
}
// ...
/* output
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
Nulla cambia se il secondo ciclo for viene eseguito prima dell'unrolling:
// ...
const int uncovered_by_unrolled_looping = n % 8;
for (int j = 0; j < uncovered_by_unrolled_looping; j++) {
std::cout << ++i << " ";
}
const int unrolled_loops = n / 8;
for (int j = 0; j < unrolled_loops; ++j) {
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
}
// ...
/* output
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
L'idea che apre la porta al Duff's Device è che il primo ciclo si può evitare, se si ha l'accortezza di entrare nella posizione corretta del ciclo “srotolato”:
// ...
int loop = (n + 7) / 8;
if (n % 8 == 1) goto one;
if (n % 8 == 2) goto two;
if (n % 8 == 3) goto three;
if (n % 8 == 4) goto four;
if (n % 8 == 5) goto five;
if (n % 8 == 6) goto six;
if (n % 8 == 7) goto seven;
while (loop > 0) {
std::cout << ++i << " ";
seven: std::cout << ++i << " ";
six: std::cout << ++i << " ";
five: std::cout << ++i << " ";
four: std::cout << ++i << " ";
three: std::cout << ++i << " ";
two: std::cout << ++i << " ";
one: std::cout << ++i << " ";
--loop;
}
// ...
/* output
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
La sequenza di if può essere sostituita da uno switch:
// ...
int loop = (n + 7) / 8;
switch (n % 8)
{
case 1: goto one;
case 2: goto two;
case 3: goto three;
case 4: goto four;
case 5: goto five;
case 6: goto six;
case 7: goto seven;
}
while (loop > 0) {
std::cout << ++i << " ";
seven: std::cout << ++i << " ";
six: std::cout << ++i << " ";
five: std::cout << ++i << " ";
four: std::cout << ++i << " ";
three: std::cout << ++i << " ";
two: std::cout << ++i << " ";
one: std::cout << ++i << " ";
--loop;
}
// ...
/* output
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
La sequenza di goto può essere eliminata sfruttando il fall-thriugh:
// ...
int loop = (n + 7) / 8;
switch (n % 8)
{
case 7: std::cout << ++i << " ";
case 6: std::cout << ++i << " ";
case 5: std::cout << ++i << " ";
case 4: std::cout << ++i << " ";
case 3: std::cout << ++i << " ";
case 2: std::cout << ++i << " ";
case 1: std::cout << ++i << " ";
--loop;
}
while (loop > 0) {
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
std::cout << ++i << " ";
--loop;
}
// ...
/* output
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
I blocchi dello switch e del ciclo while hanno una struttura molto simile; in particolare, il primo contiene un numero di “srotolamenti” inferiore di una unità rispetto al secondo. Ciò tuttavia non impedisce di fondere i due cicli, sfruttando una particolarità del linguaggio C (e di conseguenza del C++) che richiede, relativamente all'istruzione switch, solamente che il suo corpo sia sintatticamente corretto e consente che le etichette case siano poste a prefisso di una qualunque sua istruzione. Il seguente codice è dunque perfettamente legale:
// ...
int loop = (n + 7) / 8;
switch (n % 8)
{
case 0:
while (loop > 0) {
std::cout << ++i << " ";
case 7: std::cout << ++i << " ";
case 6: std::cout << ++i << " ";
case 5: std::cout << ++i << " ";
case 4: std::cout << ++i << " ";
case 3: std::cout << ++i << " ";
case 2: std::cout << ++i << " ";
case 1: std::cout << ++i << " ";
--loop;
}
}
// ...
/* output
*
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*/
Rispetto alla versione originale, questa implementazione non richiede un valore strettamente positivo per la variabile n.
Pagina modificata il 25/09/2012