Comment fonctionne l'appareil de Duff?

J'ai lu l' article sur Wikipédia sur l'appareil du Duff , et je ne comprends pas. Je suis vraiment intéressé, mais j'ai lu l'explication à plusieurs reprises et je ne comprends toujours pas comment fonctionne l'appareil du Duff.

Quelle serait une explication plus détaillée?

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

Disons que vous copiez 20 octets. Le contrôle de flux du programme pour la première passe est:

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

Maintenant, lancez la deuxième passe, nous exécutons juste le code indiqué:

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

Maintenant, commencez le troisième passage:

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 octets sont maintenant copiés.

Remarque: Le périphérique Duff's original (illustré ci-dessus) copié sur un périphérique d'E / S à l' toadresse. Ainsi, il n'était pas nécessaire d'incrémenter le pointeur *to. Lors de la copie entre deux tampons de mémoire, vous devez utiliser *to++.

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

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

Il y a deux éléments clés dans l'appareil de Duff. Premièrement, ce que je soupçonne est la partie la plus facile à comprendre, la boucle est déroulée. Cela échange une taille de code plus grande pour plus de vitesse en évitant une partie de la surcharge impliquée dans la vérification de la fin de la boucle et le retour au sommet de la boucle. Le processeur peut fonctionner plus rapidement lorsqu'il exécute du code en ligne droite au lieu de sauter.

Le deuxième aspect est l'instruction switch. Il 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 autorisée. Eh bien, c'est permis. L'exécution commence à l'étiquette de cas calculée, puis passe à chaque instruction d'affectation successive, comme toute autre instruction switch. Après la dernière étiquette de cas, l'exécution atteint le bas de la boucle, à quel point elle revient en haut. Le haut de la boucle se trouve à l' intérieur de l'instruction switch, donc le switch n'est plus réévalué.

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

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

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

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

Combien de fois avez-vous besoin de comparer le nombre pour voir s'il est supérieur à 0? «compter» fois.

Maintenant, le dispositif duff utilise un effet secondaire involontaire désagréable d'un boîtier de commutation qui vous permet de réduire le nombre de comparaisons nécessaires pour compter / 8.

Supposons maintenant que vous souhaitiez copier 20 octets à l'aide de l'appareil duffs, de combien de comparaisons auriez-vous besoin? Seulement 3, puisque vous copiez huit octets à la fois sauf le dernier premier où vous n'en copiez que 4.

MISE À JOUR: Vous n'avez pas à faire 8 comparaisons / instructions de cas dans le commutateur, mais c'est un compromis raisonnable entre la taille de la fonction et la vitesse.

Lorsque je l'ai lu pour la première fois, je l'ai automatiquement formaté

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 quand cette question a été posée, mais maintenant Wikipedia a une très bonne explication

L'appareil est valide, légal C en vertu de deux attributs en C:

• Spécification assouplie 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 de programmation C qui exige seulement que l'instruction contrôlée du commutateur soit une instruction syntaxiquement valide (composée) dans laquelle les étiquettes de cas peuvent apparaître en préfixant toute sous-instruction. En conjonction avec le fait qu'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 copies de comptage à partir de adresses source séquentielles vers le port de sortie mappé en mémoire.
• La possibilité de sauter légalement au milieu d'une boucle en C.

1: Le dispositif Duffs est une implémentation particulière du déroulement de boucle. Qu'est-ce que le déroulement de boucle?
Si vous avez une opération à effectuer N fois dans une boucle, vous pouvez échanger la taille du programme contre la vitesse en exécutant la boucle N / n fois, puis dans la boucle en insérant (déroulant) le code de la boucle n fois, par exemple en remplaçant:

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

avec

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

Ce qui fonctionne très bien si N% n == 0 - pas besoin de Duff! Si ce n'est pas vrai, vous devez gérer le reste - ce qui est pénible.

2: En quoi le dispositif Duffs diffère-t-il de ce déroulement de boucle standard?
Le dispositif Duffs est juste une manière intelligente de traiter les cycles de boucle restants lorsque N% n! = 0. L'ensemble do / while exécute N / n nombre de fois selon le déroulement de boucle standard (car le cas 0 s'applique). Lors de la dernière exécution de la boucle (la «N / n + 1» fois), le cas entre en jeu et nous sautons au cas N% n et exécutons le code de la boucle le nombre de fois «restant».

Bien que je ne sois pas sûr à 100% de ce que vous demandez, voici ...

Le problème que le périphérique de Duff aborde est celui du déroulement de la boucle (comme vous l'aurez sans doute vu sur le lien Wiki que vous avez publié). Cela équivaut essentiellement à une optimisation de l'efficacité d'exécution, par rapport à l'empreinte mémoire. L'appareil de Duff traite de la copie en série, plutôt que de n'importe quel problème ancien, mais est un exemple classique de la façon dont les optimisations peuvent être effectuées en réduisant le nombre de fois qu'une comparaison doit être effectuée en boucle.

Comme exemple alternatif, qui peut faciliter la compréhension, imaginez que vous avez un tableau d'éléments que vous souhaitez boucler, et ajoutez-leur 1 à chaque fois ... normalement, vous pouvez utiliser une boucle for, et boucler environ 100 fois . Cela semble assez logique et, c'est ... cependant, une optimisation peut être faite en déroulant la boucle (évidemment pas trop loin ... ou vous pouvez tout aussi bien ne pas utiliser la boucle).

Donc une boucle for régulière:

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

devient

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

Ce que fait l'appareil de Duff, c'est implémenter cette idée, en C, mais (comme vous l'avez vu sur le Wiki) avec des copies en série. Ce que vous voyez ci-dessus, avec l'exemple déroulé, ce sont 10 comparaisons contre 100 dans l'original - cela équivaut à une optimisation mineure, mais peut-être significative.

Voici une explication non détaillée qui est ce que je ressens être le cœur de l'appareil de Duff:

Le fait est que C est fondamentalement une belle façade pour le langage d'assemblage (l'assemblage PDP-7 pour être précis; si vous étudiiez cela, vous verriez à quel point les similitudes sont frappantes). Et, en langage d'assemblage, vous n'avez pas vraiment de boucles - vous avez des étiquettes et des instructions de branche conditionnelle. La boucle n'est donc qu'une partie de la séquence globale d'instructions avec une étiquette et une branche quelque part:

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

et une instruction de commutation se ramifie / saute quelque peu:

        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 assemblage, il est facilement concevable de combiner ces deux structures de contrôle, et quand on y pense de cette façon, leur combinaison en C ne semble plus si étrange.

C'est une réponse que j'ai postée à une autre question sur l'appareil de Duff qui a reçu des votes positifs avant que la question ne soit fermée en double. Je pense que cela fournit ici un contexte précieux sur les raisons pour lesquelles vous devriez éviter cette construction.

"Ceci est l'appareil de Duff . C'est une méthode de déroulement de boucles qui évite d'avoir à ajouter une boucle de correction secondaire pour gérer les moments où le nombre d'itérations de boucle n'est pas connu comme étant un multiple exact du facteur de déroulement.

Étant donné que la plupart des réponses ici semblent généralement positives à ce sujet, je vais souligner les inconvénients.

Avec ce code, un compilateur aura du mal à appliquer une optimisation au corps de la boucle. Si vous venez d'écrire le code sous forme de simple boucle, un compilateur moderne devrait être capable de gérer le déroulement à votre place. De cette façon, vous maintenez la lisibilité et les performances et vous avez l'espoir que d'autres optimisations soient appliquées au corps de la boucle.

L'article Wikipédia référencé par d'autres indique même que lorsque ce «modèle» a été supprimé du code source Xfree86, les performances se sont réellement améliorées.

Ce résultat est typique de l'optimisation à l'aveuglette de tout code dont vous pensez qu'il pourrait en avoir besoin. Cela empêche le compilateur de faire son travail correctement, rend votre code moins lisible et plus sujet aux bogues et le ralentit généralement. Si vous faisiez les choses de la bonne façon au départ, c'est-à-dire en écrivant du code simple, puis en établissant un profil pour les goulots d'étranglement, puis en optimisant, vous ne penseriez même jamais à utiliser quelque chose comme ça. Pas avec un processeur et un compilateur modernes de toute façon.

C'est bien de le comprendre, mais je serais surpris si jamais vous l'utilisez réellement. "

Juste en expérimentant, j'ai trouvé une autre variante sans commutateur et boucle entrelacées:

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