sucursales - tags h1 ejemplos

¿Cómo funciona el dispositivo de Duff?

Question

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

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

Answer 1

1: El dispositivo Duffs es una implementación particular del desenrollado del lazo. ¿Qué es el bucle que se desenrolla?
Si tiene una operación para realizar N veces en un bucle, puede cambiar el tamaño del programa por velocidad ejecutando el bucle N / n veces y luego en el bucle enlining (desenrollando) el código del bucle n veces, por ejemplo, reemplazando:

for (int i=0; i<N; i++) {
// [The loop code...]
}

con

for (int i=0; i<N/n; i++) {
// [The loop code...]
// [The loop code...]
// [The loop code...]
...
// [The loop code...] // n times!
}

Lo cual funciona muy bien si N% n == 0 - ¡no es necesario para Duff! Si eso no es cierto, entonces debes manejar el resto, lo cual es un problema.

2: ¿En qué se diferencia el dispositivo Duff de este despliegue estándar de bucle?
El dispositivo Duffs es solo una forma inteligente de lidiar con los ciclos de bucle restantes cuando N% n! = 0. El conjunto do / while ejecuta N / n número de veces según el desenrollado normal del bucle (porque se aplica el caso 0). En la última pasada del ciclo (el ''N / n + 1''es tiempo), el caso entra en acción y saltamos al caso N% n y ejecutamos el código del bucle el'' resto ''de veces.

Answer 2

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

El caso es que C es básicamente una fachada agradable para el lenguaje de ensamblaje (el ensamblaje de PDP-7 es específico; si estudias eso, verás lo impactantes que son las similitudes). Y, en lenguaje ensamblador, realmente no tiene bucles; tiene etiquetas e instrucciones de ramas condicionales. 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 ramifica un poco más adelante:

 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 el ensamblaje es fácil concebir 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.

Answer 3

Aunque no estoy 100% seguro de lo que estás pidiendo, aquí va ...

El problema que aborda el dispositivo de Duff es uno de desenrollado de bucle (como sin duda habrá visto en el enlace Wiki que publicó). Lo que esto básicamente equivale a una optimización de la eficiencia en tiempo de ejecución, sobre la huella de memoria. El dispositivo de Duff se ocupa de la copia en serie, más que de cualquier problema anterior, pero es un ejemplo clásico de cómo se pueden hacer las optimizaciones al reducir el número de veces que se debe hacer una comparación en un bucle.

Como ejemplo alternativo, que puede hacer que sea más fácil de entender, imagina que tienes una serie de elementos sobre los que deseas hacer bucles y agrega 1 cada vez ... normalmente, puedes usar un ciclo for, y dar vueltas alrededor de 100 veces . Esto parece bastante lógico y, sin embargo, es una optimización que se puede realizar desenrollando el ciclo (obviamente, no muy lejos ... o puede que simplemente no use el ciclo).

Entonces un bucle for regular:

for(int i = 0; i < 100; i++)
{
myArray[i] += 1;
}

se convierte

for(int i = 0; i < 100; i+10)
{
myArray[i] += 1;
myArray[i+1] += 1;
myArray[i+2] += 1;
myArray[i+3] += 1;
myArray[i+4] += 1;
myArray[i+5] += 1;
myArray[i+6] += 1;
myArray[i+7] += 1;
myArray[i+8] += 1;
myArray[i+9] += 1;
}

Lo que hace el dispositivo de Duff es implementar esta idea, en C, pero (como viste en el Wiki) con copias en serie. Lo que está viendo arriba, con el ejemplo desenrollado, es 10 comparaciones en comparación con 100 en el original; esto equivale a una optimización menor, pero posiblemente significativa.

Answer 4

Cuando lo leí por primera vez, lo auto-identifiqué a este

void dsend(char* to, char* from, count) {
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 > 0);
}
}

y no tenía idea de lo que estaba pasando.

Tal vez no cuando se hizo esta pregunta, pero ahora Wikipedia tiene una muy buena explicación

El dispositivo es válido, legal C en virtud de dos atributos en C:

• Especificación relajada de la instrucción switch en la definición del lenguaje. En el momento de la invención del dispositivo, esta era la primera edición de The C Programming Language, que solo requiere que la instrucción controlada del switch sea una afirmación sintácticamente válida (compuesta) dentro de la cual las etiquetas de los casos pueden aparecer prefijando cualquier subenunciado. Junto con el hecho de que, en ausencia de una declaración de interrupción, el flujo de control pasará de una declaración controlada por una etiqueta de caso a la controlada por la siguiente, esto significa que el código especifica una sucesión de copias de conteo de direcciones de fuente secuencial al puerto de salida mapeado en memoria.
• La capacidad de saltar legalmente en el medio de un ciclo en C.

Answer 5

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

Supongamos que quiere copiar bytes ''contar'' de aab, el enfoque directo es hacer lo siguiente:

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

¿Cuántas veces necesita comparar el recuento para ver si está por encima de 0? ''contar'' veces.

Ahora, el dispositivo duff utiliza un desagradable efecto secundario no intencional de una caja de conmutadores que le permite reducir el número de comparaciones necesarias para contar / 8.

Ahora supongamos que quiere copiar 20 bytes usando el dispositivo duffs, ¿cuántas comparaciones necesita? Solo 3, ya que copia ocho bytes a la vez, excepto el último primero en el que copia solo 4.

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

Answer 6

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á copiando 20 bytes. El control de flujo del programa para el primer pase 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, inicie el segundo pase, 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, comienza 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...

20 bytes ahora están copiados.

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

Answer 7

Hay dos cosas clave para el dispositivo de Duff. Primero, que sospecho que es la parte más fácil de entender, el ciclo se desenrolla. Esto intercambia un tamaño de código más grande para obtener más velocidad al evitar algunos de los gastos indirectos involucrados al verificar si el ciclo ha finalizado y salta al principio del ciclo. La CPU puede correr más rápido cuando está ejecutando código de línea recta en lugar de saltar.

El segundo aspecto es la declaración de cambio. Permite que el código salte al medio del ciclo 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 en 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 ciclo, en cuyo punto salta de nuevo a la parte superior. La parte superior del ciclo está dentro de la declaración del interruptor, por lo que el interruptor 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 quedan 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 el count % 8 de la instrucción de conmutación para calcular cuál será el resto, salta a la etiqueta de la caja para tantos bytes y los copia. Luego, el ciclo continúa copiando grupos de ocho bytes.

Answer 8

La explicación en el Dr. Dobb''s Journal es la mejor que encontré sobre el tema.

Este es 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++;
}

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

Answer 9

Simplemente experimentando, descubrió que otra variante se llevaba bien sin el interruptor de entrelazado y el ciclo:

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