¿Cómo funciona el dispositivo de Duff?

he leído el artículo en Wikipedia sobre el dispositivo de Duff, y no lo entiendo. Estoy realmente interesado, pero he leído la explicación allí un par de veces y todavía no entiendo cómo funciona el dispositivo de Duff.

¿Cuál sería una explicación más detallada?

Él explicación en Dr. Dobb’s Journal es lo mejor que encontre sobre el tema.

Siendo este mi momento AHA:

for (i = 0; i < len; ++i) {
    HAL_IO_PORT = *pSource++;
}

se convierte en:

int n = len / 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
}

n = len % 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
}

se convierte en:

int n = (len + 8 - 1) / 8;
switch (len % 8) {
    case 0: do { HAL_IO_PORT = *pSource++;
    case 7: HAL_IO_PORT = *pSource++;
    case 6: HAL_IO_PORT = *pSource++;
    case 5: HAL_IO_PORT = *pSource++;
    case 4: HAL_IO_PORT = *pSource++;
    case 3: HAL_IO_PORT = *pSource++;
    case 2: HAL_IO_PORT = *pSource++;
    case 1: HAL_IO_PORT = *pSource++;
               } while (--n > 0);
}

Hay algunas buenas explicaciones en otros lugares, pero déjame intentarlo. (¡Esto es mucho más fácil en una pizarra!) Aquí está el ejemplo de Wikipedia con algunas anotaciones.

Digamos que estás copiando 20 bytes. El control de flujo del programa para la primera pasada es:

int count;                        // Set to 20
{
    int n = (count + 7) / 8;      // n is now 3.  (The "while" is going
                                  //              to be run three times.)

    switch (count % 8) {          // The remainder is 4 (20 modulo 8) so
                                  // jump to the case 4

    case 0:                       // [skipped]
             do {                 // [skipped]
                 *to = *from++;   // [skipped]
    case 7:      *to = *from++;   // [skipped]
    case 6:      *to = *from++;   // [skipped]
    case 5:      *to = *from++;   // [skipped]
    case 4:      *to = *from++;   // Start here.  Copy 1 byte  (total 1)
    case 3:      *to = *from++;   // Copy 1 byte (total 2)
    case 2:      *to = *from++;   // Copy 1 byte (total 3)
    case 1:      *to = *from++;   // Copy 1 byte (total 4)
           } while (--n > 0);     // N = 3 Reduce N by 1, then jump up
                                  //       to the "do" if it's still
    }                             //        greater than 0 (and it is)
}

Ahora, inicia la segunda pasada, ejecutamos solo el código indicado:

int count;                        //
{
    int n = (count + 7) / 8;      //
                                  //

    switch (count % 8) {          //
                                  //

    case 0:                       //
             do {                 // The while jumps to here.
                 *to = *from++;   // Copy 1 byte (total 5)
    case 7:      *to = *from++;   // Copy 1 byte (total 6)
    case 6:      *to = *from++;   // Copy 1 byte (total 7)
    case 5:      *to = *from++;   // Copy 1 byte (total 8)
    case 4:      *to = *from++;   // Copy 1 byte (total 9)
    case 3:      *to = *from++;   // Copy 1 byte (total 10)
    case 2:      *to = *from++;   // Copy 1 byte (total 11)
    case 1:      *to = *from++;   // Copy 1 byte (total 12)
           } while (--n > 0);     // N = 2 Reduce N by 1, then jump up
                                  //       to the "do" if it's still
    }                             //       greater than 0 (and it is)
}

Ahora, inicia el tercer pase:

int count;                        //
{
    int n = (count + 7) / 8;      //
                                  //

    switch (count % 8) {          //
                                  //

    case 0:                       //
             do {                 // The while jumps to here.
                 *to = *from++;   // Copy 1 byte (total 13)
    case 7:      *to = *from++;   // Copy 1 byte (total 14)
    case 6:      *to = *from++;   // Copy 1 byte (total 15)
    case 5:      *to = *from++;   // Copy 1 byte (total 16)
    case 4:      *to = *from++;   // Copy 1 byte (total 17)
    case 3:      *to = *from++;   // Copy 1 byte (total 18)
    case 2:      *to = *from++;   // Copy 1 byte (total 19)
    case 1:      *to = *from++;   // Copy 1 byte (total 20)
           } while (--n > 0);     // N = 1  Reduce N by 1, then jump up
                                  //       to the "do" if it's still
    }                             //       greater than 0 (and it's not, so bail)
}                                 // continue here...

Ahora se copian 20 bytes.

Nota: El dispositivo de Duff original (mostrado arriba) copiado a un dispositivo de E/S en el to dirección. Por lo tanto, no fue necesario incrementar el puntero *to. Al copiar entre dos búferes de memoria, necesitaría usar *to++.

Hay dos cosas clave en el dispositivo de Duff. Primero, que sospecho que es la parte más fácil de entender, se desenrolla el bucle. Esto cambia un tamaño de código más grande por más velocidad al evitar algunos de los gastos generales involucrados en verificar si el ciclo está terminado y volver a la parte superior del ciclo. La CPU puede funcionar más rápido cuando ejecuta código de línea recta en lugar de saltar.

El segundo aspecto es la instrucción switch. Permite que el código salte al medio del bucle la primera vez. La parte sorprendente para la mayoría de la gente es que tal cosa está permitida. Bueno, está permitido. La ejecución comienza en la etiqueta de caso calculada y luego cae a través a cada declaración de asignación sucesiva, al igual que 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 bucle es en el interior 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 count % 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.

Solo experimentando, encontré otra variante que se lleva bien sin intercalar switch declaración y do–while-círculo:

int n = (count + 1) / 8;
switch (count % 8)
{
    LOOP:
case 0:
    if(n-- == 0)
        break;
    putchar('.');
case 7:
    putchar('.');
case 6:
    putchar('.');
case 5:
    putchar('.');
case 4:
    putchar('.');
case 3:
    putchar('.');
case 2:
    putchar('.');
case 1:
    putchar('.');
default:
    goto LOOP;
}

Técnicamente, el goto todavía implementa un bucle, pero esta variante podría ser un poco más legible.

El objetivo del dispositivo duffs es reducir el número de comparaciones realizadas en una implementación estricta de memcpy.

Supongamos que desea copiar bytes de ‘recuento’ de a a b, el enfoque directo es hacer lo siguiente:

  do {                      
      *a = *b++;            
  } while (--count > 0);

¿Cuántas veces necesita comparar el conteo para ver si está por encima de 0? ‘contar’ veces.

Ahora, el dispositivo duff usa un desagradable efecto secundario involuntario de una caja de cambio que le permite reducir la cantidad de comparaciones necesarias para contar / 8.

Ahora suponga que desea copiar 20 bytes usando el dispositivo duffs, ¿cuántas comparaciones necesitaría? Solo 3, ya que copia ocho bytes a la vez excepto el ultimo el primero donde copias solo 4.

ACTUALIZADO: no tiene que hacer 8 comparaciones/declaraciones de cambio de caso, pero es una compensación razonable entre el tamaño de la función y la velocidad.

Aquí hay una explicación no detallada que es lo que siento que es el quid del dispositivo de Duff:

La cuestión es que C es básicamente una buena fachada para el lenguaje ensamblador (ensamblado PDP-7 para ser específico; si lo estudiara, vería cuán sorprendentes son las similitudes). Y, en lenguaje ensamblador, realmente no tiene bucles: tiene etiquetas e instrucciones de ramificación condicional. Entonces, el ciclo es solo una parte de la secuencia general de instrucciones con una etiqueta y una rama en alguna parte:

        instruction
label1: instruction
        instruction
        instruction
        instruction
        jump to label1  some condition

y una instrucción de cambio se está bifurcando/saltando un poco:

        evaluate expression into register r
        compare r with first case value
        branch to first case label if equal
        compare r with second case value
        branch to second case label if equal
        etc....
first_case_label: 
        instruction
        instruction
second_case_label: 
        instruction
        instruction
        etc...

En ensamblador es fácilmente concebible cómo combinar estas dos estructuras de control, y cuando lo piensas de esa manera, su combinación en C ya no parece tan extraña.

Esta es una respuesta que publiqué a otra pregunta sobre el dispositivo de Duff que obtuvo algunas mejoras antes de que la pregunta se cerrara como un duplicado. Creo que proporciona un poco de contexto valioso aquí sobre por qué debería evitar esta construcción.

“Este es Dispositivo de Duff. Es un método de desenrollar bucles que evita tener que agregar un bucle de reparación secundario para lidiar con momentos en los que no se sabe si el número de iteraciones del bucle es un múltiplo exacto del factor de desenrollado.

Dado que la mayoría de las respuestas aquí parecen ser generalmente positivas al respecto, voy a resaltar las desventajas.

Con este código, un compilador tendrá dificultades para aplicar cualquier optimización al cuerpo del bucle. Si acaba de escribir el código como un ciclo simple, un compilador moderno debería poder manejar el desenrollado por usted. De esta manera, mantiene la legibilidad y el rendimiento y tiene alguna esperanza de que se apliquen otras optimizaciones al cuerpo del bucle.

El artículo de Wikipedia mencionado por otros incluso dice que cuando se eliminó este ‘patrón’ del código fuente de Xfree86, el rendimiento realmente mejoró.

Este resultado es típico de la optimización manual ciega de cualquier código que creas que podría necesitarlo. Impide que el compilador haga su trabajo correctamente, hace que su código sea menos legible y más propenso a errores y, por lo general, lo ralentiza. Si estuviera haciendo las cosas de la manera correcta en primer lugar, es decir, escribiendo un código simple, luego perfilando los cuellos de botella y luego optimizando, nunca pensaría en usar algo como esto. No con una CPU y un compilador modernos de todos modos.

Está bien entenderlo, pero me sorprendería si alguna vez lo usaras”.