¿Cómo funciona el dispositivo de Duff?
Leí 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?
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, comenzamos 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, 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...
Ahora se copian 20 bytes.
Nota: El dispositivo Duff original (que se muestra arriba) se copió a un dispositivo de E/S en la todirección. Por tanto, no fue necesario incrementar el puntero *to. Al copiar entre dos buffers de memoria, necesitarás usar *to++.
La explicación en el Diario del Dr. Dobb 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++;
}
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 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 parte de la sobrecarga involucrada en verificar si el ciclo está finalizado 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 declaración de cambio. Permite que el código salte al medio del bucle la primera vez. Lo sorprendente para la mayoría de la gente es que tal cosa esté permitida. Bueno, está permitido. La ejecución comienza en la etiqueta del caso calculado y luego pasa a cada declaración de asignación sucesiva, como 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 está dentro de 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 que se van a copiar no es múltiplo de ocho, entonces quedarán 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 % 8la instrucción de cambio para calcular 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.
El objetivo del dispositivo duffs es reducir la cantidad de comparaciones realizadas en una implementación estricta de memcpy.
Supongamos que desea copiar bytes de 'recuento' de ba a, el método más sencillo es hacer lo siguiente:
do {
*a = *b++;
} while (--count > 0);
¿Cuántas veces necesitas comparar el recuento para ver si es superior a 0? 'contar' veces.
Ahora, el dispositivo duff utiliza un desagradable efecto secundario involuntario de una caja de interruptor que le permite reducir la cantidad de comparaciones necesarias para contar / 8.
Ahora suponga que desea copiar 20 bytes usando un dispositivo duffs, ¿cuántas comparaciones necesitaría? Solo 3, ya que copia ocho bytes a la vez excepto el último primero donde copia solo 4.
ACTUALIZADO: No es necesario hacer 8 comparaciones/declaraciones de cambio de caso en caso, pero es razonable un equilibrio entre el tamaño y la velocidad de la función.
