Cosa fa questo codice C [dispositivo Duff]?

Question

void Send(int * to, const int* from, const int count) 
{ 
    int 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); 
    } 
} 

Answer 1

Questo è Duff's Device per la copia dei buffer di memoria.

Answer 2

leggere su Duff's Device

Answer 3

Questa commistione di un'istruzione switch e un ciclo while si chiama "Dispositivo di Duff". È un modo per srotolare i loop, che era un'ottimizzazione spesso utilizzata in passato.

Quindi questo codice copia ancora il contenuto della memoria da un posto all'altro, ma potrebbe essere più efficiente. Attenzione, sulle architetture di oggi dovresti sempre misurarlo, perché con la localizzazione della cache e le CPU incredibilmente veloci il ciclo di srotolamento è spesso una cattiva idea. Dispositivo

Answer 4

Duff's device

In computer science, Duff è un optimizedimplementation di una copia seriale che utilizza una tecnica ampiamente applicata in assembly language per loop unwinding. La sua scoperta è accreditata allo Tom Duff nel novembre 1983, che all'epoca stava lavorando per Lucasfilm. È forse l'uso più drammatico di case label fall-through nel C programming language fino ad oggi. Duff non rivendica credito per scoprire il concetto di loop unrolling, proprio questa particolare espressione in C.

Answer 5

Questo è funzionalmente identico al codice di seguito:

for(int i=0;i<n;i++) 
{ 
    *to++=*from++; 
} 

La differenza è che il codice srotola il ciclo in modo che sia richiesta una sola iterazione del ciclo per ogni 8 numeri interi copiati. Poiché non vi sono interruzioni per nessuno dei casi , l'esecuzione passa dall'etichetta di ogni caso alla successiva.

Quando il conteggio% 8 == 0, 8 copie sono eseguite all'interno del ciclo per la prima iterazione

quando il contatore% 8 == 7, 7 copie vengono eseguite per la prima iterazione

e così via. Dopo la prima iterazione con% 8 copie, esattamente 8 copie avvengono per iterazione.

Svolgendo il ciclo in questo modo, l'overhead del loop viene significativamente ridotto. È importante notare l'ordine dei valori del caso (0,7,6,5,4,3,2,1) che si prestano ad essere tradotti in una tabella di salto dal compilatore.

aggiornamento

Un problema con il codice di esempio inviato da OP è che un valore di conteggio di 0 causerà 8 copie avvengano, potenzialmente un buffer overflow.

Answer 6

Questo è Duff's Device. È un metodo di loop di srotolamento che evita di dover aggiungere un ciclo di correzione secondario per gestire le volte in cui il numero di iterazioni del ciclo non è noto per essere un multiplo esatto del fattore di srotolamento.

Poiché la maggior parte delle risposte qui sembra essere generalmente positiva, parlerò apertamente.

Con questo codice un compilatore farà fatica ad applicare qualsiasi ottimizzazione al corpo del loop. Se hai appena scritto il codice come un semplice ciclo, un moderno compilatore dovrebbe essere in grado di gestire lo srotolamento per te. In questo modo si mantiene la leggibilità e le prestazioni e si spera che altre ottimizzazioni vengano applicate al corpo del loop.

L'articolo di Wikipedia a cui si fa riferimento da altri dice anche quando questo "modello" è stato rimosso dalle prestazioni del codice sorgente Xfree86 effettivamente migliorate.

Questo risultato è tipico della mano cieca che ottimizza qualsiasi codice che pensi possa averne bisogno. Impedisce al compilatore di svolgere correttamente il suo lavoro, rende il tuo codice meno leggibile e più incline a bug e in genere rallenta. Se stavate facendo le cose nel modo giusto in primo luogo, cioè scrivendo codice semplice, quindi creando profili per i colli di bottiglia, quindi ottimizzando, non avreste mai nemmeno pensato di usare qualcosa del genere. Non con una CPU e un compilatore moderni comunque.

Va bene a capirlo, ma sarei sorpreso se lo usassi mai davvero.