Dispositivo de Duff

Dispositivo de Duff

Saltar a navegación, búsqueda

En el ámbito de las ciencias de la computación un Dispositivo de Duff es una implementación optimizada de una copia secuencial para programas en lenguaje C que utiliza una técnica normalmente empleada en lenguaje ensamblador para desenrollar bucles. Su descubrimiento se atribuye a Tom Duff que en Noviembre de 1983 publicó^[1] un mensaje en USENET describiendo este hallazgo. La misma se basa en aprovechar la característica de caída en cascada de la instrucción case.

Normalmente una copia secuencial se podría escribir de la siguiente forma:^[2]

do { /* se asume count > 0 */
   *to++ = *from++;
} while (--count);

Mientras intentaba optimizar este bucle, Tom Duff se dio cuenta de que la versión desdoblada del mismo podía ser reescrita intercalando las estructuras de las instrucciones switch y loop.

/* se asume count > 0 */
 int 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);
 }

La optimización se produce debido a que sólo se realiza una comparación y decremento cada 8 elementos copiados en lugar de por cada uno.

Si bien la técnica de desenrollado de bucles era conocida con anterioridad, esta forma de escribirla resultó una novedad y aunque extraña y poco intuitiva se trata de una construcción perfectamente válida en C, y muchos compiladores generan instrucciones de máquina tal cual un programador en lenguaje ensamblador lo hubiera hecho a mano.

Notas

1. ↑ Una copia del mensaje se puede ver (en Inglés) en Google Groups
2. ↑ El código tal cual fue publicado no incrementa el puntero to ya que se trata del envío de una secuencia de datos a un puerto de entrada/salida. Para facilitar la comprensión aquí optamos por la variante de copia de datos, aunque la librerías de C ya poseen rutinas de copia altamente optimizadas.

Obtenido de "Dispositivo de Duff"