En el C lenguaje de programación, el dispositivo de Duff es una forma de implementar manualmente bucle desenrollado entrelazando dos construcciones sintácticas de C: el hacer - mientras bucle y una sentencia switch . Su descubrimiento se atribuye a Tom Duff en noviembre de 1983, cuando Duff trabajaba para Lucasfilm y lo utilizó para acelerar un programa de animación en tiempo real.
El desenrollado de bucle intenta reducir la sobrecarga de la bifurcación condicional necesaria para comprobar si se realiza un bucle, mediante la ejecución de un lote de cuerpos de bucle por iteración. Para manejar los casos en los que el número de iteraciones no es divisible por los incrementos del bucle desenrollado, una técnica común entre los programadores de lenguaje ensamblador es saltar directamente al medio del cuerpo del bucle desenrollado para manejar el resto. [1] Duff implementó esta técnica en C utilizando la función de caída de la etiqueta de la caja de C para saltar al cuerpo desenrollado. [2]
Versión original
El problema de Duff era copiar enteros sin signo de 16 bits ("cortos" en la mayoría de las implementaciones de C) de una matriz a un registro de salida mapeado en memoria , indicado en C por un puntero . Su código original, en C , tenía el siguiente aspecto: [3] [4]
enviar ( a , desde , contar ) registro corto * a , * desde ; registro de recuento ; { do { / * count> 0 asumido * / * to = * from ++ ; } while ( - cuenta > 0 ); }
Este código asume que inicial cuenta> 0 . El puntero a no se incrementa como sería necesario para una copia de memoria a memoria. Si count eran siempre divisibles por ocho, desenrollar este bucle ocho veces produciría lo siguiente:
enviar ( a , desde , contar ) registro corto * a , * desde ; registro de recuento ; { registro n = recuento / 8 ; hacer { * a = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; } while ( - n > 0 ); }
Duff se dio cuenta de que para manejar casos en los que count no es divisible por ocho, la técnica del programador de ensamblaje de saltar al cuerpo del bucle podría implementarse entrelazando las estructuras de una instrucción switch y un bucle, colocando el switch etiquetas de caso en los puntos del cuerpo del bucle que corresponden al resto de recuento / 8 : [1]
enviar ( a , desde , contar ) registro corto * a , * desde ; registro de recuento ; { registro n = ( cuenta + 7 ) / 8 ; cambiar ( contar % 8 ) { caso 0 : hacer { * a = * desde ++ ; 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 ++ ; } while ( - n > 0 ); } }
El dispositivo de Duff se puede aplicar de manera similar con cualquier otro tamaño para el bucle desenrollado, no solo ocho como en el ejemplo anterior.
Mecanismo
Basado en un algoritmo utilizado ampliamente por los programadores que codifican en ensamblador para minimizar el número de pruebas y ramificaciones durante una copia, el dispositivo de Duff parece fuera de lugar cuando se implementa en C. El dispositivo es válido en C en virtud de dos atributos en C:
- Especificación relajada del instrucción de cambio en la definición del lenguaje. En el momento de la invención del dispositivo, esta era la primera edición del lenguaje de programación C, que solo requiere que el cuerpo del switch sea una sentencia sintácticamente válida (compuesta) dentro de la cual Las etiquetas de caso pueden aparecer anteponiendo cualquier subenunciado. Junto con el hecho de que, en ausencia de un declaración de ruptura , el flujo de control caerá a través de una declaración controlada por uno etiqueta de caso a la controlada por la siguiente, esto significa que el código especifica una sucesión de contar copias de direcciones de origen secuenciales al puerto de salida asignado en memoria.
- La capacidad de saltar al medio de un bucle en C.
Esto lleva a lo que el Jargon File llama "el uso más dramático hasta ahora visto de la caída en C". [5] La falla predeterminada de C en las declaraciones de casos ha sido durante mucho tiempo una de sus características más controvertidas; El propio Duff dijo que "este código forma algún tipo de argumento en ese debate, pero no estoy seguro de si es a favor o en contra". [5]
Explicación simplificada
Una versión funcionalmente equivalente con switch y while desenredada |
---|
enviar ( a , desde , contar ) registro corto * a , * desde ; registro de recuento ; { registro n = ( cuenta + 7 ) / 8 ; cambiar ( recuento % 8 ) { caso 0 : * a = * desde ++ ; 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 ++ ; } while ( - n > 0 ) { * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; * hasta = * desde ++ ; } } |
La idea básica del desenrollado de bucles es que el número de instrucciones ejecutadas en un bucle se puede reducir reduciendo el número de pruebas de bucle, a veces reduciendo la cantidad de tiempo que se pasa en el bucle. Por ejemplo, en el caso de un bucle con una sola instrucción en el código de bloque, la prueba del bucle se realizará normalmente para cada iteración del bucle, es decir, cada vez que se ejecute la instrucción. Si, en cambio, se colocan ocho copias de la misma instrucción en el ciclo, entonces la prueba se realizará solo cada ocho iteraciones, y esto puede ganar tiempo al evitar siete pruebas. Sin embargo, esto solo maneja un múltiplo de ocho iteraciones, requiriendo algo más para manejar cualquier resto de iteraciones. [1]
El dispositivo de Duff proporciona una solución al realizar primero el resto de las iteraciones, seguido de iterar tantas veces como sea necesario el múltiplo de ocho instrucciones similares. Para determinar el número de iteraciones restantes, el código primero calcula el número total de iteraciones módulo ocho. De acuerdo con este resto, la ejecución del programa a continuación, saltar a una case
declaración seguida de exactamente el número de iteraciones necesarias . Una vez hecho esto, todo es sencillo: el código continúa haciendo iteraciones de grupos de ocho instrucciones, esto ha sido posible ya que el número restante de iteraciones es un múltiplo de ocho. [1]
El dispositivo de Duff proporciona un desenrollado de bucle compacto mediante el uso de la palabra clave case tanto dentro como fuera del bucle . Esto es inusual porque el contenido de una declaración de caso se considera tradicionalmente como un bloque de código anidado dentro de la declaración de caso, y un lector normalmente esperaría que terminara antes de la siguiente declaración de caso. Según las especificaciones del lenguaje C, esto no es necesario; de hecho, las declaraciones de casos pueden aparecer en cualquier lugar dentro del bloque de código de conmutación ya cualquier profundidad; la ejecución del programa simplemente saltará a la siguiente instrucción, donde sea que esté.
Actuación
Muchos compiladores optimizarán el cambio a una tabla de rama tal como se haría en una implementación de ensamblado.
El aumento principal de velocidad frente a un bucle simple y directo proviene del desenrollado del bucle que reduce el número de bifurcaciones realizadas, que son computacionalmente costosas debido a la necesidad de vaciar y, por lo tanto, paralizar la tubería de instrucciones . La switch
declaración se usa para manejar el resto de los datos que no son divisibles de manera uniforme por el número de operaciones desenrolladas (en este ejemplo, se desenrollan ocho movimientos cortos, por lo que switch
maneja automáticamente entre 1 y 7 cortos adicionales).
Este manejo automático del resto puede no ser la mejor solución en todos los sistemas y compiladores; en algunos casos, dos bucles pueden ser más rápidos (un bucle, desenrollado, para hacer la copia principal, y un segundo bucle para manejar el resto). El problema parece deberse a la capacidad del compilador para optimizar correctamente el dispositivo; también puede interferir con la canalización y la predicción de ramificaciones en algunas arquitecturas. [6] Cuando se eliminaron numerosas instancias del dispositivo de Duff del servidor XFree86 en la versión 4.0, hubo una mejora en el rendimiento y una reducción notable en el tamaño del ejecutable. [7] Por lo tanto, al considerar este código como una optimización de programa , puede valer la pena ejecutar algunos puntos de referencia para verificar que en realidad es el código más rápido en la arquitectura de destino, en el nivel de optimización de destino, con el compilador de destino, así como sopesando el riesgo de que el código optimizado se utilice más adelante en diferentes plataformas donde no es el código más rápido.
Para el propósito de las copias de memoria a memoria (que, como se mencionó anteriormente, no era el uso original del dispositivo de Duff), la biblioteca C estándar proporciona la función memcpy
; [8] no funcionará peor que una versión de copia de memoria a memoria de este código, y puede contener optimizaciones específicas de la arquitectura que lo hacen significativamente más rápido. [9] [10]
Ver también
- Coroutine : el dispositivo de Duff se puede usar para implementar corrutinas en C / C ++
- Dispositivo de Jensen
Referencias
- ↑ a b c d Holly, Ralf (1 de agosto de 2005). "Un dispositivo Duff reutilizable" . Diario del Dr. Dobb . Consultado el 18 de septiembre de 2015 .
- ^ Duff, Tom (29 de agosto de 1988). "Asunto: Re: Explicación, ¡por favor!" . Lysator . Consultado el 3 de noviembre de 2015 .
- ^ "¡El asombroso dispositivo de Duff de Tom Duff!" . doc.cat-v.org . Consultado el 8 de junio de 2017 .
- ^ Cox, Russ (30 de enero de 2008). "investigación! rsc: en el dispositivo de Duff y corrutinas" . research.swtch.com . Consultado el 24 de enero de 2017 .
- ^ a b El archivo de jerga
- ^ Diario de USENIX 2003 de James Ralston [ enlace muerto permanente ]
- ^ Tso, Ted (22 de agosto de 2000). "Re: [PATCH] Re: Movimiento de controladores de entrada, se necesita alguna palabra de usted" . lkml.indiana.edu . Lista de correo del kernel de Linux . Consultado el 22 de agosto de 2014 .
Jim Gettys tiene una maravillosa explicación de este efecto en el servidor X. Resulta que con las predicciones de bifurcaciones y la velocidad relativa del cambio de la CPU frente a la memoria durante la última década, el desenrollado de bucles no tiene sentido. De hecho, al eliminar todas las instancias del dispositivo de Duff del servidor XFree86 4.0, el servidor se redujo en tamaño _half_ _a_ _megabyte_ (!!!), y fue más rápido de arrancar, porque la eliminación de todo ese código sobrante significó que el servidor X no estaba destrozando tanto las líneas de caché.
- ^ "memcpy - cppreference.com" . En.cppreference.com . Consultado el 6 de marzo de 2014 .
- ^ Wall, Mike (19 de marzo de 2002). "Uso de Block Prefetch para optimizar el rendimiento de la memoria" (PDF) . mit.edu . Consultado el 22 de septiembre de 2012 .
- ^ Niebla, Agner (29 de febrero de 2012). "Optimización de subrutinas en lenguaje ensamblador" (PDF) . Facultad de Ingeniería de la Universidad de Copenhague . págs. 100 y sigs . Consultado el 22 de septiembre de 2012 .
Otras lecturas
- Kernighan, Brian ; Ritchie, Dennis (marzo de 1988). El lenguaje de programación C (2ª ed.). Englewood Cliffs, Nueva Jersey: Prentice Hall. ISBN 0-13-110362-8.
enlaces externos
- Descripción y correo original de Duff en Lysator
- Las corrutinas de Simon Tatham en C utilizan el mismo truco de cambio / caso
- Protothreads de Adam Dunkels: subprocesos ligeros y sin apilamiento en C también utiliza declaraciones de conmutador / caso anidadas (consulte también los subprocesos ligeros más ligeros, Protothreads )
- El dispositivo de Pigeon es una técnica relacionada: conmutador / caso entrelazados y declaraciones if / else