En el lenguaje de programación C , el dispositivo de Duff es una forma de implementar manualmente el desenrollado de bucles intercalando dos construcciones sintácticas de C: el bucle do - while 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 bucles intenta reducir la sobrecarga de la ramificación condicional necesaria para comprobar si se ha completado un bucle, ejecutando 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 paso a través de la etiqueta de caso de C para saltar al cuerpo desenrollado. [2]
El problema de Duff era copiar números enteros sin signo de 16 bits ("shorts" en la mayoría de las implementaciones de C) desde una matriz a un registro de salida asignado a la memoria , denotado en C por un puntero . Su código original, en C , era el siguiente: [3] [4]
enviar ( a , desde , contar ) registrar corto * a , * desde ; registrar contar ; { hacer { /* contar > 0 asumido */ * a = * desde ++ ; } mientras ( -- contar > 0 ); } Este código supone que el recuento inicial > 0. Dado que la ubicación de salida es un registro asignado a la memoria, el puntero a no se incrementa como sería necesario para una copia de memoria a memoria.
Si el conteo fuera siempre divisible por ocho, desenrollar este bucle ocho veces produciría lo siguiente:
enviar ( a , desde , contar ) registro corto * a , * desde ; registro contar ; { registro n = contar / 8 ; hacer { * a = * desde ++ ; * a = * desde ++ ; * a = * desde ++ ; * a = * desde ++ ; * a = * desde ++ ; * a = * desde ++ ; * a = * desde ++ ; * a = * desde ++ ; } while ( -- n > 0 ); } Duff se dio cuenta de que para manejar casos donde count no es divisible por ocho, la técnica del programador de ensamblaje de saltar al cuerpo del bucle se podía implementar entrelazando las estructuras de una declaración switch y un bucle, poniendo las etiquetas de caso de switch en los puntos del cuerpo del bucle que corresponden al resto de count/8 : [1]
enviar ( a , desde , contar ) registro corto * a , * desde ; registro contar ; { registro n = ( contar + 7 ) / 8 ; cambiar ( contar % 8 ) { caso 0 : hacer { * a = * desde ++ ; caso 7 : * a = * desde ++ ; caso 6 : * a = * desde ++ ; caso 5 : * a = * desde ++ ; caso 4 : * a = * desde ++ ; caso 3 : * a = * desde ++ ; caso 2 : * a = * desde ++ ; caso 1 : * a = * desde ++ ; } mientras ( -- n > 0 ); } } El dispositivo de Duff se puede aplicar de manera similar con cualquier otro tamaño de bucle desenrollado, no solo ocho como en el ejemplo anterior.
Basado en un algoritmo ampliamente utilizado por programadores que codifican en ensamblador para minimizar la cantidad de pruebas y bifurcaciones 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:
Esto conduce a lo que el Jargon File llama "el uso más dramático visto hasta ahora de fall-through en C". [5] El fall-through predeterminado de C en las declaraciones de caso ha sido durante mucho tiempo una de sus características más controvertidas; el propio Duff dijo que "este código forma una especie de argumento en ese debate, pero no estoy seguro de si es a favor o en contra". [5]
Aunque es válido en C, el dispositivo de Duff va en contra de las pautas comunes de C, como las pautas MISRA . Algunos compiladores (por ejemplo, CompCert ) están restringidos a dichas pautas y, por lo tanto, rechazan el dispositivo de Duff a menos que se indique específicamente lo contrario.
La idea básica del desenrollado de bucles es que la cantidad de instrucciones ejecutadas en un bucle se puede reducir al reducir la cantidad de pruebas de bucle, lo que a veces reduce 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 de bucle se realizará normalmente para cada iteración del bucle, es decir, cada vez que se ejecuta la instrucción. Si, en cambio, se colocan ocho copias de la misma instrucción en el bucle, 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, lo que requiere algo más para manejar cualquier resto de iteraciones. [1]
El dispositivo de Duff proporciona una solución ejecutando primero el resto de iteraciones, seguido de iterar tantas veces como sea necesario el múltiplo de ocho instrucciones similares. Para determinar el número de iteraciones del resto, el código calcula primero el número total de iteraciones módulo ocho. De acuerdo con este resto, la ejecución del programa saltará entonces a una caseinstrucción seguida exactamente del 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 se ha vuelto 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 case se considera tradicionalmente como un bloque de código anidado dentro de la declaración case, y un lector normalmente esperaría que terminara antes de la siguiente declaración case. De acuerdo con las especificaciones del lenguaje C, esto no es necesario; de hecho, las declaraciones case pueden aparecer en cualquier lugar dentro del bloque de código switch , y a cualquier profundidad; la ejecución del programa simplemente saltará a la siguiente declaración, donde sea que esté.
Muchos compiladores optimizarán el cambio a una tabla de ramas tal como se haría en una implementación de ensamblaje.
El principal aumento de velocidad en comparación con un bucle simple y directo proviene del desenrollado del bucle , que reduce la cantidad de bifurcaciones realizadas, que son costosas desde el punto de vista computacional debido a la necesidad de vaciar (y, por lo tanto, detener) la secuencia de instrucciones . La switchinstrucción se utiliza para manejar el resto de los datos que no son divisibles de manera uniforme por la cantidad de operaciones desenrolladas (en este ejemplo, se desenrollan ocho movimientos cortos, por lo que switchmaneja automáticamente entre 1 y 7 movimientos 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 realmente más rápidos (un bucle, desenrollado, para hacer la copia principal, y un segundo bucle para manejar el resto). El problema parece reducirse a la capacidad del compilador para optimizar correctamente el dispositivo; también puede interferir con la canalización y la predicción de bifurcaciones 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 realmente sea 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 sopesar el riesgo de que el código optimizado se use más adelante en diferentes plataformas donde no sea el código más rápido.
Para el propósito de realizar 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 hagan significativamente más rápido. [9] [10]
Jim Gettys tiene una explicación maravillosa de este efecto en el servidor X. Resulta que con las predicciones de bifurcación y la velocidad relativa de la CPU frente a la memoria cambiando durante la última década, el desenrollado de bucles es prácticamente inútil. De hecho, al eliminar todas las instancias del dispositivo de Duff del servidor
XFree86
4.0, el servidor se redujo en tamaño en _medio_ _megabyte_ (!!!), y fue más rápido al arrancar, porque la eliminación de todo ese exceso de código significaba que el servidor X no estaba agotando tanto las líneas de caché.
