Dispositiu de Duff

En el llenguatge de programació C, el dispositiu de Duff és una manera d'implementar manualment el desenrotllament de bucles entrellaçant dues construccions sintàctiques de C: eldo -whilebucle i una instrucció switch. El seu descobriment se li atribueix a Tom Duff el novembre de 1983, quan Duff treballava per a Lucasfilm i el va utilitzar per accelerar un programa d'animació en temps real.

El desenrotllament del bucle intenta reduir la sobrecàrrega de ramificació condicional necessària per comprovar si es fa un bucle, executant un lot de cossos de bucle per iteració. Per gestionar els casos en què el nombre d'iteracions no és divisible pels increments del bucle desenrotllat, una tècnica comuna entre els programadors de llenguatge ensamblador és saltar directament al mig del cos del bucle desenrotllat per gestionar la resta. Duff va implementar aquesta tècnica en C utilitzant la funció de caiguda de l'etiqueta de cas de C per saltar al cos desenrotllat.

Versió original

El problema de Duff va ser copiar nombres enters sense signe de 16 bits ("curts" en la majoria de les implementacions C) d'una matriu a un registre de sortida assignat a la memòria, indicat en C per un punter. El seu codi original, en C, era el següent:

send(to, from, count)
register short *to, *from;
register count;
{
 do { /* count > 0 assumed */
 *to = *from++;
 } while (--count > 0);
}

Aquest codi assumeix aquesta inicialcount > 0. Com que la ubicació de sortida és un registre assignat a memòria, el punterto no s'incrementa com seria necessari per a una còpia de memòria a memòria. Sicount sempre eren divisibles per vuit, el desenrotllament d'aquest bucle vuit vegades produiria el següent:

send(to, from, count)
register short *to, *from;
register count;
{
 register n = count / 8;
 do {
 *to = *from++;
 *to = *from++;
 *to = *from++;
 *to = *from++;
 *to = *from++;
 *to = *from++;
 *to = *from++;
 *to = *from++;
 } while (--n > 0);
}

Duff es va adonar que per gestionar els casos en quècount no és divisible per vuit, la tècnica del programador de muntatges de saltar al cos del bucle es podria implementar entrellaçant les estructures d'una declaració d'interruptor i un bucle, posant les etiquetes de la instrucció switch als punts del cos del bucle que corresponen a la resta decount/8:

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);
 }
}

El dispositiu de Duff es pot aplicar de manera similar amb qualsevol altra mida per al bucle desenrotllat, no només vuit com a l'exemple anterior.

Mecanisme

Basat en un algorisme utilitzat àmpliament pels programadors que codifiquen en llenguatge ensamblador per minimitzar el nombre de proves i ramificacions durant una còpia, el dispositiu de Duff apareix fora de lloc quan s'implementa en C. El dispositiu és C vàlid en virtut de dos atributs en C:

1. Especificació relaxada de laswitchdeclaració en la definició de l'idioma. En el moment de la invenció del dispositiu, aquesta era la primera edició del llenguatge de programació C que només requereix que el cos delswitch sigui una sentència (composta) sintàcticament vàlida dins de la qualcaseles etiquetes poden aparèixer com a prefix de qualsevol subinstrucció. En conjunció amb el fet que, a falta d'abreakdeclaració , el flux de control caurà a partir d'una instrucció controlada per uncaseetiqueta a la que controla el següent, això significa que el codi especifica una successió decount les còpies des d'adreces font seqüencials al port de sortida assignat a la memòria.
2. La capacitat de saltar al mig d'un bucle en C.

Això condueix al que l'Arxiu d'argot anomena "l'ús més dramàtic fins ara vist de la caiguda en C". El fall-through predeterminat de C en les declaracions de cas ha estat durant molt de temps una de les seves característiques més controvertides; El mateix Duff va dir que "Aquest codi forma algun tipus d'argument en aquest debat, però no estic segur de si està a favor o en contra".

Tot i que vàlid en C, el dispositiu de Duff va en contra de les directrius C comunes, com ara les directrius MISRA. Alguns compiladors (per exemple, CompCert) estan restringits a aquestes directrius i, per tant, poden rebutjar el dispositiu de Duff.