¿Cómo funciona el dispositivo de Duff?

13 minutos de lectura

avatar de usuario
hhafez

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?

  • Mucha gente lee artículos de Wikipedia y termina más confundida que antes. A veces, aunque los artículos de Wikipedia tienen buenas citas. Estoy encontrando el citado del Dr. Dobb articulo mucho mas claro…

    –Alonso del Arte

    15 de noviembre de 2021 a las 17:47

avatar de usuario
ric tokio

É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);
}

  • buena publicación (además, tengo que encontrar una buena respuesta tuya para votar a favor;) 2 abajo, 13 restantes: stackoverflow.com/questions/359727#486543). Disfruta de la buena insignia de respuesta.

    – VoC

    6 de febrero de 2009 a las 7:40

  • El hecho crucial aquí, y que hizo que el dispositivo de Duff fuera incomprensible para mí durante mucho tiempo, es que por una peculiaridad de C, después de la primera vez que llega al tiempo, salta hacia atrás y ejecuta todas las sentencias. Así, incluso si len%8 era 4, ejecutará el caso 4, el caso 2, el caso 2 y el caso 1, y luego retrocederá y ejecutará todos los casos del siguiente bucle en adelante. Esta es la parte que necesita explicación, la forma en que el ciclo y la declaración de cambio “interactúan”.

    – ShreevatsaR

    24 de enero de 2012 a las 12:24

  • El artículo del Dr. Dobbs es bueno, sin embargo, aparte del enlace, la respuesta no agrega nada. Consulte la respuesta de Rob Kennedy a continuación, que en realidad proporciona un punto importante sobre el resto del tamaño de la transferencia que se maneja primero, seguido de cero o más bloques de transferencia de 8 bytes. En mi opinión, esa es la clave para entender este código.

    – Richard Cámaras

    20 de abril de 2013 a las 23:03

  • ¿Me estoy perdiendo algo, o en el segundo fragmento de código? len % 8 ¿No se copiarán los bytes?

    – novato

    30/03/2014 a las 21:54

  • Estaba atascado, olvidando que si no escribe una declaración de interrupción al final de la lista de declaraciones de un caso, C (o cualquier otro idioma) continuará ejecutando las declaraciones. Entonces, si se pregunta por qué funciona el dispositivo de Duff, esta es una parte crucial.

    – goonerify

    29 de julio de 2014 a las 4:24

avatar de usuario
clinton perforar

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++.

  • ¿Cómo se puede omitir la cláusula case 0: y continuar buscando las otras cláusulas que están dentro del bucle do while que es el argumento de la cláusula omitida? Si se omite la única cláusula que está fuera del ciclo do while, ¿por qué el interruptor no termina allí?

    – Aurelio

    17 de septiembre de 2015 a las 14:26


  • No mires los frenos con tanta fuerza. no mires a la do tanto. En su lugar, mira el switch y el while como se calcula a la antigua GOTO declaraciones o ensamblador jmp declaraciones con un desplazamiento. Él switch hace algo de matemáticas y luego jmps al lugar correcto. Él while hace una verificación booleana y luego ciegamente jmps a la derecha sobre donde el do era.

    -Clinton Pierce

    17/09/2015 a las 18:40

  • Si esto es tan bueno, ¿por qué no todos lo usan? ¿Hay algún inconveniente?

    – AlphaGoku

    25 de febrero de 2019 a las 5:14

  • @AlphaGoku Legibilidad.

    – LF

    08/01/2020 a las 10:00

  • Los compiladores modernos de @AlphaGoku pueden utilizar algo similar llamado desenrollado de bucles.

    – Hollay-Horváth Zsombor

    18 de septiembre de 2020 a las 22:58

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.

  • Esta explicación tiene más sentido. la clave para mí es entender que el resto se copia primero y luego el resto en bloques de 8 bytes, lo cual es inusual ya que, como se mencionó la mayoría de las veces, copiarías en bloques de 8 bytes y luego copiarías el resto. hacer el resto primero es la clave para entender este algoritmo.

    – Richard Cámaras

    20 abr 2013 a las 22:55

  • +1 por mencionar la loca ubicación/anidamiento de switch/while loop. Imposible de imaginar viniendo de un lenguaje como Java…

    – Parobay

    3 de febrero de 2014 a las 7:06

avatar de usuario
Aconcagua

Solo experimentando, encontré otra variante que se lleva bien sin intercalar switch declaración y dowhile-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.

avatar de usuario
johan dahlin

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.

  • Tenga en cuenta que el dispositivo de duff no está limitado a 8 duplicaciones en la declaración de cambio.

    – extraño

    5 de febrero de 2009 a las 1:29

  • ¿Por qué no puedes simplemente usar en lugar de –count, count = count-8? y usar un segundo bucle para tratar con el resto?

    – hhafez

    5 de febrero de 2009 a las 1:36

  • Hhafez, puedes usar un segundo ciclo para lidiar con el resto. Pero ahora tiene el doble de código para lograr lo mismo sin aumentar la velocidad.

    – Rob Kennedy

    5 de febrero de 2009 a las 1:39

  • Johan, lo tienes al revés. Los 4 bytes restantes se copian en el primero iteración del ciclo, no la última.

    – Rob Kennedy

    5 de febrero de 2009 a las 1:40

  • No estoy seguro de que sea un efecto secundario, desagradable o involuntario. creo que es solo como switch obras

    – Tim Randall

    3 de marzo de 2021 a las 15:19

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.

  • Tenga en cuenta que el dispositivo de duff no está limitado a 8 duplicaciones en la declaración de cambio.

    – extraño

    5 de febrero de 2009 a las 1:29

  • ¿Por qué no puedes simplemente usar en lugar de –count, count = count-8? y usar un segundo bucle para tratar con el resto?

    – hhafez

    5 de febrero de 2009 a las 1:36

  • Hhafez, puedes usar un segundo ciclo para lidiar con el resto. Pero ahora tiene el doble de código para lograr lo mismo sin aumentar la velocidad.

    – Rob Kennedy

    5 de febrero de 2009 a las 1:39

  • Johan, lo tienes al revés. Los 4 bytes restantes se copian en el primero iteración del ciclo, no la última.

    – Rob Kennedy

    5 de febrero de 2009 a las 1:40

  • No estoy seguro de que sea un efecto secundario, desagradable o involuntario. creo que es solo como switch obras

    – Tim Randall

    3 de marzo de 2021 a las 15:19

avatar de usuario
Pete Fordham

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”.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad