El dispositivo de Duff es un truco para expresar el desarrollo del bucle directamente en C o C++ sin código adicional para tratar el bucle parcial sobrante. El truco consiste en utilizar una sentencia switch en la que todas las etiquetas de los casos excepto una están en medio de un bucle while. Además, todos los casos caen hasta el final del bucle while. A pesar de la impresión, da la impresión de que el dispositivo de Duff es un código C y C++ legal (sin embargo, no es válido en Java).
¿Cómo es útil?
Hay dos cosas clave en el dispositivo de Duff.
- Primero, se desenrolla el bucle. Obtenemos más velocidad al evitar algunos de los gastos generales involucrados en verificar si el bucle está terminado y volver a la parte superior del bucle. La CPU puede funcionar más rápido cuando ejecuta código de línea recta en lugar de saltar. Sin embargo, el tamaño del código se vuelve más grande.
- El segundo aspecto es la instrucción switch. Permite que el código salte a la mitad del ciclo la primera vez. La parte sorprendente para la mayoría de la gente es que tal cosa está permitida. Bueno, está permitido.
Ejemplo
// C program to illustrate the working of
// Duff's Device. The program copies given
// number of elements bool array src[] to
// dest[]
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
// Copies size bits from src[] to dest[]
void copyBoolArray(bool src[], bool dest[],
int size)
{
// Do copy in rounds of size 8.
int rounds = size / 8;
int i = 0;
switch (size % 8)
{
case 0:
while (!(rounds == 0))
{
rounds = rounds - 1;
dest[i] = src[i];
i = i + 1;
// An important point is, the switch
// control can directly reach below labels
case 7:
dest[i] = src[i];
i = i + 1;
case 6:
dest[i] = src[i];
i = i + 1;
case 5:
dest[i] = src[i];
i = i + 1;
case 4:
dest[i] = src[i];
i = i + 1;
case 3:
dest[i] = src[i];
i = i + 1;
case 2:
dest[i] = src[i];
i = i + 1;
case 1:
dest[i] = src[i];
i = i + 1;
};
}
}
// Driver code
int main()
{
int size = 20;
bool dest[size], src[size];
// Assign some random values to src[]
int i;
for (i=0; i<size; i++)
src[i] = rand()%2;
copyBoolArray(src, dest, size);
for (i=0; i<size ; i++)
printf("%d\t%d\n", src[i], dest[i]);
}
Producción:
1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1
¿Cómo funciona el programa anterior?
En el ejemplo anterior, estamos tratando con 20 bytes y copiando estos 20 bits aleatorios de la array src a la array de destino. El número de pases para los que se ejecutará también depende del tamaño de la array de origen.
Para el primer paso, la ejecución comienza en la etiqueta de caso calculada y luego pasa a cada declaración de asignación sucesiva, como cualquier otra declaración de cambio. Después de la última etiqueta de caso, la ejecución llega al final del bucle, momento en el que vuelve a la parte superior. La parte superior del ciclo está dentro de la declaración de cambio, por lo que el cambio ya no se vuelve a evaluar.
El bucle original se desenrolla ocho veces, por lo que el número de iteraciones se divide por ocho. Si el número de bytes a copiar no es un múltiplo de ocho, entonces sobran algunos bytes. La mayoría de los algoritmos que copian bloques de bytes a la vez manejarán los bytes restantes al final, pero el dispositivo de Duff los maneja al principio. La función calcula el conteo % 8 para que la declaración de cambio calcule cuál será el resto, salta a la etiqueta del caso para esa cantidad de bytes y los copia. Luego, el ciclo continúa copiando grupos de ocho bytes en los pases de la izquierda.
Para el primer pase:
rounds = count / 8;
// rounds = 2 for count =20
i = 0;
switch(count % 8)
{
// The remainder is 4 (20 modulo 8)
// so jump to the case 4
case 0:
while( !(rounds == 0) )
{
//[skipped]
rounds = rounds - 1;
dest[i] = src[i];
i = i + 1;
case 7:
dest[i] = src[i];
i = i + 1; //[skipped]
case 6:
dest[i] = src[i];
i = i + 1; //[skipped]
case 5:
dest[i] = src[i];
i = i + 1; //[skipped]
case 4:
dest[i] = src[i];
i = i + 1; //Start here. Copy 1 byte (total 1)
case 3:
dest[i] = src[i];
i = i + 1; //Copy 1 byte (total 2)
case 2:
dest[i] = src[i];
i = i + 1; //Copy 1 byte (total 3)
case 1:
dest[i] = src[i];
i = i + 1; //Copy 1 byte (total 4)
};
}
Para el segundo pase:
rounds = count / 8;
i = 0;
switch(count % 8)
{
case 0:
while( !(rounds == 0) )
{
// rounds is decremented by 1 as while
// loop works, now rounds=1
rounds = rounds - 1;
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 5)
case 7:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 6)
case 6:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 7)
case 5:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 8)
case 4:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 9)
case 3:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 10)
case 2:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 11)
case 1:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 12)
}
}
Para el tercer pase:
rounds = count / 8;
i = 0;
switch(count % 8)
{
case 0:
while( !(rounds == 0) )
{
//now while loop works
rounds = rounds - 1; //rounds is decremented by 1, now rounds=0
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 13)
case 7:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 14)
case 6:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 15)
case 5:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 16)
case 4:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 17)
case 3:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 18)
case 2:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 19)
case 1:
dest[i] = src[i];
i = i + 1; // Copy 1 byte (total 20)
};
}
Referencias:
Wikipedia
http://www.lysator.liu.se/c/duffs-device.html
Este artículo es una contribución de Nikhil Kumar Sharma . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA