Comment fonctionne l'appareil de Duff?

Question

J'ai lu l'article sur Wikipedia sur le dispositif de Duff, et je ne comprends pas. Je suis vraiment intéressé, mais j'ai lu l'explication là-bas plusieurs fois et je ne comprends toujours pas comment fonctionne le dispositif de Duff.

Quelle serait une explication plus détaillée?

Answer 1

Il existe de bonnes explications ailleurs, mais laissez-moi essayer. (C'est beaucoup plus facile sur un tableau blanc!) Voici l'exemple de Wikipédia avec quelques notations.

Disons que vous copiez 20 octets. Le contrôle de flux du programme pour le premier passage est :

int count;                        // Défini à 20
{
    int n = (count + 7) / 8;      // n est maintenant 3. (Le "while" va être exécuté trois fois.)

    switch (count % 8) {          // Le reste est de 4 (20 modulo 8) donc
                                  // sauter au cas 4

    case 0:                       // [saute]
             do {                 // [saute]
                 *to = *from++;   // [saute]
    case 7:      *to = *from++;   // [saute]
    case 6:      *to = *from++;   // [saute]
    case 5:      *to = *from++;   // [saute]
    case 4:      *to = *from++;   // Commencez ici. Copier 1 octet (total 1)
    case 3:      *to = *from++;   // Copier 1 octet (total 2)
    case 2:      *to = *from++;   // Copier 1 octet (total 3)
    case 1:      *to = *from++;   // Copier 1 octet (total 4)
           } while (--n > 0);     // N = 3 Réduire N de 1, puis sauter en haut
                                  //      à "do" s'il est toujours
    }                             //       supérieur à 0 (et c'est le cas)
}

Maintenant, commencez le deuxième passage, nous exécutons juste le code indiqué :

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

    switch (count % 8) {          //
                                  //

    case 0:                       //
             do {                 // Le while saute ici.
                 *to = *from++;   // Copier 1 octet (total 5)
    case 7:      *to = *from++;   // Copier 1 octet (total 6)
    case 6:      *to = *from++;   // Copier 1 octet (total 7)
    case 5:      *to = *from++;   // Copier 1 octet (total 8)
    case 4:      *to = *from++;   // Copier 1 octet (total 9)
    case 3:      *to = *from++;   // Copier 1 octet (total 10)
    case 2:      *to = *from++;   // Copier 1 octet (total 11)
    case 1:      *to = *from++;   // Copier 1 octet (total 12)
           } while (--n > 0);     // N = 2 Réduire N de 1, puis sauter en haut
                                  //       à "do" s'il est toujours
    }                             //       supérieur à 0 (et c'est le cas)
}

Maintenant, commencez le troisième passage :

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

    switch (count % 8) {          //
                                  //

    case 0:                       //
             do {                 // Le while saute ici.
                 *to = *from++;   // Copier 1 octet (total 13)
    case 7:      *to = *from++;   // Copier 1 octet (total 14)
    case 6:      *to = *from++;   // Copier 1 octet (total 15)
    case 5:      *to = *from++;   // Copier 1 octet (total 16)
    case 4:      *to = *from++;   // Copier 1 octet (total 17)
    case 3:      *to = *from++;   // Copier 1 octet (total 18)
    case 2:      *to = *from++;   // Copier 1 octet (total 19)
    case 1:      *to = *from++;   // Copier 1 octet (total 20)
           } while (--n > 0);     // N = 1  Réduire N de 1, puis sauter en haut
                                  //       à "do" s'il est toujours
    }                             //       supérieur à 0 (et ce n'est pas le cas, donc abandon)
}                                 // continuer ici...

20 octets sont maintenant copiés.

Note : Le Duff's Device original (montré ci-dessus) copiait vers un périphérique d'E/S à l'adresse to. Ainsi, il n'était pas nécessaire d'incrémenter le pointeur *to. Lors de la copie entre deux tampons mémoire, vous auriez besoin d'utiliser *to++.

Answer 2

La explication dans le Journal de Dr. Dobb est la meilleure que j'ai trouvée sur le sujet.

Cela étant mon moment AHA :

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

devient :

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

devient :

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 3

Il y a deux éléments clés dans l'appareil de Duff. Tout d'abord, ce que je soupçonne être la partie la plus facile à comprendre, c'est que la boucle est déroulée. Cela échange une taille de code plus grande contre plus de vitesse en évitant une partie des frais généraux liés à la vérification de la fin de la boucle et au retour au sommet de la boucle. Le processeur peut s'exécuter plus rapidement lorsqu'il exécute un code en ligne droite au lieu de sauter.

Le deuxième aspect est l'instruction switch. Elle permet au code de sauter au milieu de la boucle la première fois. La partie surprenante pour la plupart des gens est qu'une telle chose est permise. Eh bien, c'est permis. L'exécution commence à l'étiquette de cas calculée, puis elle passe à travers chaque déclaration d'assignation successive, comme toute autre instruction switch. Après la dernière étiquette de cas, l'exécution atteint le bas de la boucle, moment où elle retourne au sommet. Le sommet de la boucle est à l'intérieur de l'instruction switch, donc le switch n'est plus réévalué.

La boucle originale est déroulée huit fois, donc le nombre d'itérations est divisé par huit. Si le nombre d'octets à copier n'est pas un multiple de huit, alors il reste des octets. La plupart des algorithmes qui copient des blocs d'octets à la fois traiteront les octets restants à la fin, mais l'appareil de Duff les traite au début. La fonction calcule count % 8 pour l'instruction switch afin de déterminer ce qu'il reste, saute à l'étiquette de cas pour ce nombre d'octets, et les copie. Ensuite, la boucle continue à copier des groupes de huit octets.

Answer 4

Le but du dispositif de Duff est de réduire le nombre de comparaisons effectuées dans une implémentation serrée de memcpy.

Supposons que vous vouliez copier 'count' octets de b à a, l'approche directe consiste à faire ce qui suit :

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

Combien de fois avez-vous besoin de comparer count pour voir s'il est supérieur à 0 ? 'count' fois.

Maintenant, le dispositif de Duff utilise un effet secondaire malencontreux d'une instruction switch qui vous permet de réduire le nombre de comparaisons nécessaires à count / 8.

Supposons maintenant que vous vouliez copier 20 octets en utilisant le dispositif de Duff, combien de comparaisons aurez-vous besoin ? Seulement 3, puisque vous copiez huit octets à la fois à l'exception du premier où vous n'en copiez que 4.

MISE À JOUR : Vous n'êtes pas obligé de faire 8 comparaisons/instructions switch par cas, mais c'est un compromis raisonnable entre la taille de la fonction et la vitesse.

Answer 5

Quand je l'ai lu pour la première fois, je l'ai autoformaté comme ça

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

et je n'avais aucune idée de ce qui se passait.

Peut-être pas lorsque cette question a été posée, mais maintenant Wikipedia a une très bonne explication

Le dispositif est valide, légal en C en raison de deux attributs en C :

• Spécification détendue de l'instruction switch dans la définition du langage. Au moment de l'invention du dispositif, il s'agissait de la première édition du langage C qui exigeait uniquement que l'instruction contrôlée de l'instruction switch soit une instruction (composée) syntaxiquement valide dans laquelle des étiquettes de cas peuvent apparaître préfixant toute sous-instruction. En conjonction avec le fait que, en l'absence d'une instruction break, le flux de contrôle passera d'une instruction contrôlée par une étiquette de cas à celle contrôlée par la suivante, cela signifie que le code spécifie une succession de count copies à partir d'adresses source séquentielles vers le port de sortie mappé en mémoire.
• La capacité de sauter légalement au milieu d'une boucle en C.