Duffs enhet i programmering är en optimerad implementering av sekventiell kopiering, med samma teknik som används för loop- avlindning . Den första beskrivningen gjordes i november 1983 av Tom Duff ( eng. Tom Duff ), som arbetade för Lucasfilm vid den tiden . Detta är kanske den mest ovanliga användningen av det faktum att i C-språket exekveras instruktioner inom ett block "genom" genom alla etiketter . switchcase
Det bör noteras att Duff inte gör anspråk på att upptäcka själva konceptet med loopavveckling, han äger bara dess specifika uttryck på C-språket.
I moderna lösningar är användbarheten av att använda Duff-metoden tveksam. Det hindrar arbetet med att optimera kompilatorer och grenprediktorn. [1] Till exempel, efter att ha tagit bort Duff-koden från XFree86 version 4.0 (2000), reducerades binärfilerna med cirka 0,5 MB och servern började laddas snabbare. [2]
Det traditionella sättet för sekventiell kopiering (innan Duffs upptäckt) såg ut så här:
gör { /* Antag antal > 0 */ * till = * från ++ ; /* Här ökas inte till-pekaren */ } while ( -- count > 0 );I det här exemplet to ökar den inte eftersom Duff kopierade till ett enda minnesmappat I/O-register. toI modern C måste definitionen av en variabel säkerhetskopieras med nyckelordet volatile.
Medan han optimerade den här koden insåg Duff att en "avlindad" version av slingan kunde implementeras genom att lägga över switch och do / while -konstruktioner .
strcpy ( till , från , räkna ) registrera char * till , * från ; registerantal ; _ { register n = ( antal + 7 ) / 8 ; om ( ! räkna ) returnera ; switch ( räkning % 8 ) { fall 0 : gör { * till = * från ++ ; fall 7 : * till = * från ++ ; fall 6 : * till = * från ++ ; fall 5 : * till = * från ++ ; fall 4 : * till = * från ++ ; fall 3 : * till = * från ++ ; fall 2 : * till = * från ++ ; fall 1 : * till = * från ++ ; } while ( -- n > 0 ); } } Förklaringar till exempelAlgoritmen i sig var allmänt känd tidigare: programmerare som utvecklade program i assembler använde den för att minska antalet jämförelser och grenar vid kopiering.
I sin tur ser implementeringen av Duff-metoden på C -språket ovanligt ut vid första anblicken. Denna kod är dock skriven i enlighet med beskrivningen och standarden för C-språket; Specifikationen för switchkonstruktionen tillåter denna användning:
Kombinationen av dessa två fakta gör att ovanstående kod kopieras från på varandra följande adresser ( *från ) till den mappade utgångsporten ( *till ) det angivna antalet gånger ( count [3] ).
Duffs ursprungliga metod var att kopiera till ett I/O-register. För att helt enkelt kopiera en bit minne från en plats till en annan måste du lägga till automatisk ökning för varje omnämnande av till :
* till ++ = * från ++ ;Duffs metod i denna form ges som en övning i Bjorn Stroustrups The C++ Programming Language [4] . Tydligen beror förändringen på det faktum att författaren inte förväntar sig att en novis programmerare ska vara bekant med I/O-register. Det här alternativet har ingen praktisk tillämpning, eftersom standardbiblioteket för C-språket redan har en funktion för att kopiera ett minnesområde ( memcpy).
Programmerares direkta användning av finita tillståndsmaskiner är ofta svår eftersom det valda programmeringsspråket inte tillåter en tydlig och enkel representation av maskinens tillstånd och övergångar i kod (se exempel i artikeln " Automatisk programmering ").
Ett av de framgångsrika alternativen föreslogs [5] av Simon Tatham och är ett sätt att implementera en implicit finit automat med Duff-metoden. I sin tur användes statliga maskiner av Tatham för att implementera coroutines , vilket gjorde det möjligt för honom att implementera uppgiften producent-konsument utan användning av multithreading och dess åtföljande problem.
Samma tillvägagångssätt, bland andra, användes av Adam Dunkels [ i hans "protothreads"-bibliotek [6] , som är dedikerat till olika sätt att implementera pseudo-multithreading med hjälp av implicita tillståndsmaskiner.
Det föreslagna tillvägagångssättet består i att konstruera en finita tillståndsmaskin i delar, med hjälp av flera C-makron. Förenklade makron ser ut så här:
#define DECLARE() int state #define INIT() tillstånd = 0 #define BEGIN switch (tillstånd) { \ fall 0: #define YIELD(val) do { \ state = __LINE__; \ returvärde; \ case __LINE__: \ ; \ } medan (0) #definiera SLUT}Användningsexempel (i C++):
#include <iostream> använder namnutrymme std ; klass maskin { FÖRKLARA (); offentliga : maskin () { INIT (); } const char * nästa () { BÖRJA ; AVKASTNING ( "mamma" ); AVKASTNING ( "tvål" ); YIELD ( "ram" ); SLUT ; returnera NULL ; } }; int main () { maskin m ; while ( const char * val = m . nästa ()) { cout << val << ' ' ; } returnera 0 ; }Detta program kommer att mata ut "mamma tvättade ramen", med varje ord som genereras av ett separat tillståndsmaskinsteg.