El dispositivo de Duff en programación es una implementación optimizada de copia secuencial, que utiliza la misma técnica que se utiliza para el desenrollado de bucles . La primera descripción fue realizada en noviembre de 1983 por Tom Duff ( ing. Tom Duff ), quien trabajaba para Lucasfilm en ese momento . Este es quizás el uso más inusual del hecho de que en el lenguaje C, las instrucciones dentro de un bloque se ejecutan "a través" de todas las etiquetas . switchcase
Cabe señalar que Duff no pretende descubrir el concepto mismo de desenrollado de bucles, solo posee su expresión específica en el lenguaje C.
En soluciones modernas, la utilidad de usar el método Duff es dudosa. Dificulta el trabajo de optimización de los compiladores y el predictor de ramas. [1] Por ejemplo, después de eliminar el código Duff de XFree86 versión 4.0 (2000), los archivos binarios se redujeron en aproximadamente 0,5 MB y el servidor comenzó a cargarse más rápido. [2]
La forma tradicional de copia secuencial (antes del descubrimiento de Duff) se veía así:
hacer { /* Asumir cuenta > 0 */ * a = * desde ++ ; /* Aquí el puntero a no se incrementa */ } while ( -- cuenta > 0 );En este ejemplo, to no se incrementa porque Duff estaba copiando a un solo registro de E/S mapeado en memoria. En C moderno, la definición de una variable todebe respaldarse con la palabra clave volatile.
Mientras optimizaba este código, Duff se dio cuenta de que se podía implementar una versión "desenrollada" del bucle superponiendo las construcciones switch y do / while .
strcpy ( hasta , desde , contar ) registrar char * hasta , * desde ; registro de conteo ; { registro n = ( cuenta + 7 ) / 8 ; si ( ! cuenta ) regresa ; cambiar ( contar % 8 ) { caso 0 : hacer { * a = * de ++ ; caso 7 : * a = * de ++ ; caso 6 : * a = * de ++ ; caso 5 : * a = * de ++ ; caso 4 : * a = * de ++ ; caso 3 : * a = * de ++ ; caso 2 : * a = * de ++ ; caso 1 : * a = * de ++ ; } mientras ( -- n > 0 ); } } Explicaciones por ejemploEl algoritmo en sí era ampliamente conocido antes: los programadores que desarrollaban programas en ensamblador lo usaban para reducir la cantidad de comparaciones y bifurcaciones al copiar.
A su vez, la implementación del método Duff en el lenguaje C parece inusual a primera vista. Sin embargo, este código está escrito de acuerdo con la descripción y el estándar del lenguaje C; La especificación de la construcción del interruptor permite este uso:
La combinación de estos dos hechos hace que el código anterior se copie desde direcciones consecutivas ( *from ) al puerto de salida asignado ( *to ) el número especificado de veces ( count [3] ).
El método original de Duff era copiar a un registro de E/S. Para simplemente copiar una parte de la memoria de un lugar a otro, debe agregar un incremento automático a cada mención de a :
* a ++ = * de ++ ;El método de Duff en esta forma se da como un ejercicio en The C++ Programming Language [4] de Bjorn Stroustrup . Aparentemente, el cambio se debe a que el autor no espera que un programador novato esté familiarizado con los registros de E/S. Esta opción no tiene aplicación práctica, ya que la biblioteca estándar del lenguaje C ya tiene una función para copiar un área de memoria ( ). memcpy
El uso directo de máquinas de estados finitos por parte de los programadores suele ser difícil porque el lenguaje de programación elegido no permite una representación clara y sencilla del estado y las transiciones de la máquina en el código (ver ejemplos en el artículo " Programación automática ").
Una de las opciones exitosas fue propuesta [5] por Simon Tatham y es una forma de implementar un autómata finito implícito usando el método Duff. A su vez, Tatham usó máquinas de estado para implementar corrutinas , lo que le permitió implementar la tarea productor-consumidor sin el uso de subprocesos múltiples y sus problemas concomitantes.
El mismo enfoque, entre otros, fue utilizado por Adam Dunkels [ en su biblioteca "protothreads" [6] , que está dedicada a varias formas de implementar pseudo-multithreading utilizando máquinas de estado implícitas.
El enfoque propuesto consiste en construir una máquina de estados finitos en partes, usando varias macros en C. Las macros simplificadas se ven así:
#define DECLARE() estado int #define INIT() estado = 0 #define BEGIN switch (estado) { \ case 0: #define RENDIMIENTO(val) do { \ estado = __LINE__; \ valor de retorno; \ caso __LINE__: \ ; \ } mientras (0) #definir FIN}Ejemplo de uso (en C++):
#incluir <iostream> utilizando el espacio de nombres estándar ; máquina de clase { DECLARAR (); público : máquina () { INICIO (); } const char * siguiente () { COMENZAR ; RENDIMIENTO ( "mamá" ); RENDIMIENTO ( "jabón" ); RENDIMIENTO ( "marco" ); FIN ; devuelve NULL ; } }; int principal () { máquina m ; while ( const char * val = m . siguiente ()) { cout << val << ' ' ; } devolver 0 ; }Este programa generará "mamá lavó el marco", con cada palabra generada por un paso de máquina de estado separado.