Dispozitivul lui Duff în programare este o implementare optimizată a copierii secvențiale, folosind aceeași tehnică folosită pentru derularea buclei . Prima descriere a fost făcută în noiembrie 1983 de Tom Duff ( ing. Tom Duff ), care lucra la Lucasfilm la acea vreme . Aceasta este poate cea mai neobișnuită utilizare a faptului că, în limbajul C, instrucțiunile dintr-un bloc sunt executate „prin” prin toate etichetele . switchcase
De remarcat că Duff nu pretinde că descoperă însuși conceptul de derulare a buclei, el deține doar expresia sa specifică în limbajul C.
În soluțiile moderne, utilitatea utilizării metodei Duff este îndoielnică. Acesta împiedică munca de optimizare a compilatorilor și a predictorului de ramuri. [1] De exemplu, după eliminarea codului Duff din XFree86 versiunea 4.0 (2000), fișierele binare au fost reduse cu aproximativ 0,5 MB și serverul a început să se încarce mai repede. [2]
Modul tradițional de copiere secvențială (înainte de descoperirea lui Duff) arăta astfel:
do { /* Presupuneți numărul > 0 */ * la = * de la ++ ; /* Aici indicatorul spre nu este incrementat */ } în timp ce ( -- număr > 0 );În acest exemplu, to nu crește deoarece Duff copia într-un singur registru I/O mapat în memorie. În C modern, definiția unei variabile totrebuie să fie susținută de cuvântul cheie volatile.
În timp ce a optimizat acest cod, Duff și-a dat seama că o versiune „derulată” a buclei ar putea fi implementată prin suprapunerea switch și do / while constructe .
strcpy ( la , de la , numără ) inregistreaza char * to , * from ; număr de înregistrări ; { registrul n = ( număr + 7 ) / 8 ; dacă ( ! numără ) întoarce ; comutare ( count % 8 ) { cazul 0 : do { * to = * from ++ ; cazul 7 : * la = * de la ++ ; cazul 6 : * la = * de la ++ ; cazul 5 : * la = * de la ++ ; cazul 4 : * la = * de la ++ ; cazul 3 : * la = * de la ++ ; cazul 2 : * la = * de la ++ ; cazul 1 : * la = * de la ++ ; } în timp ce ( -- n > 0 ); } } Explicații de exempluAlgoritmul în sine era cunoscut pe scară largă înainte: programatorii care dezvoltau programe în asamblare îl foloseau pentru a reduce numărul de comparații și ramuri la copiere.
La rândul său, implementarea metodei Duff în limbajul C pare neobișnuită la prima vedere. Cu toate acestea, acest cod este scris în conformitate cu descrierea și standardul limbajului C; Specificația construcției comutatorului permite această utilizare:
Combinația acestor două fapte face ca codul de mai sus să copieze de la adrese consecutive ( *from ) în portul de ieșire mapat ( *to ) de numărul specificat de ori ( count [3] ).
Metoda originală a lui Duff a fost copierea într-un registru I/O. Pentru a copia pur și simplu o bucată de memorie dintr-un loc în altul, trebuie să adăugați o creștere automată la fiecare mențiune despre :
* la ++ = * de la ++ ;Metoda lui Duff în această formă este dată ca un exercițiu în limbajul de programare C++ al lui Bjorn Stroustrup [4] . Aparent, schimbarea se datorează faptului că autorul nu se așteaptă ca un programator începător să fie familiarizat cu registrele I/O. Această opțiune nu are aplicație practică, deoarece biblioteca standard a limbajului C are deja o funcție pentru copierea unei zone de memorie ( memcpy).
Utilizarea directă a mașinilor cu stări finite de către programatori este adesea dificilă deoarece limbajul de programare ales nu permite o reprezentare clară și simplă a stării și tranzițiilor mașinii în cod (vezi exemplele din articolul „ Programare automată ”).
Una dintre opțiunile de succes a fost propusă [5] de Simon Tatham și este o modalitate de implementare a unui automat finit implicit folosind metoda Duff. La rândul lor, mașinile de stat au fost folosite de Tatham pentru a implementa corutine , ceea ce i-a permis să implementeze sarcina producător-consum fără utilizarea multithreading -ului și a problemelor aferente acesteia.
Aceeași abordare, printre altele, a fost folosită de Adam Dunkels [ în biblioteca sa „protothreads” [6] , care este dedicată diverselor modalități de implementare a pseudo-multithreading folosind mașini de stări implicite.
Abordarea propusă constă în construirea unei mașini cu stări finite în părți, folosind mai multe macro-uri C. Macrocomenzile simplificate arată astfel:
#define DECLARE() stare int #definiți starea INIT() = 0 #define BEGIN comutator (stare) { \ case 0: #define YIELD(val) do { \ state = __LINE__; \ returnează valoarea; \ case __LINE__: \ ; \ } în timp ce (0) #define END}Exemplu de utilizare (în C++):
#include <iostream> folosind namespace std ; mașină de clasă { DECLARE (); public : mașină () { INIT (); } const char * următorul () { ÎNCEPE ; RANDAMENT ( "mama" ); RENDAMENT ( "spun" ); RENDAMENT ( "cadru" ); SFÂRȘIT ; returnează NULL ; } }; int main () { mașină m ; while ( const char * val = m . next ()) { cout << val << ' ' ; } returnează 0 ; }Acest program va afișa „mama a spălat cadrul”, fiecare cuvânt generat de un pas separat al mașinii de stat.