Comment fonctionne L'appareil de Duff?

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

C'est 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 choses clés à l'appareil de Duff. D'abord, ce que je pense être la partie la plus facile à comprendre, la boucle est bouclée. Ceci échange une plus grande taille de code pour plus de vitesse en évitant une partie des frais généraux impliqués dans la vérification si la boucle est terminée et en sautant vers le haut de la boucle. Le CPU peut courir plus vite quand il exécute du code en ligne droite au lieu de sauter.

le second aspect est l'indication de l'interrupteur. Il permet au code de sauter dans le moyen de la boucle la première fois. Ce qui est étonnant 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, et puis il tombe à travers à chaque instruction d'affectation successive, comme n'importe quelle autre instruction d'interrupteur. Après la dernière étiquette de cas, l'exécution atteint le bas de la boucle, à ce moment-là elle remonte vers le haut. Le haut de la boucle est intérieur la déclaration de l'interrupteur, de sorte que l'interrupteur 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 ya quelques octets. La plupart des algorithmes qui copient des blocs d'octets à la fois vont traiter les octets restants à la fin, mais le périphérique de Duff les gère au début. La fonction calcule count % 8 pour l'instruction de commutation à figure ce que le reste sera, saute à l'étiquette de cas pour autant d'octets, et les Copie. Puis la boucle continue à copier des groupes de huit octets.

le point de Duffs dispositif est de réduire le nombre de comparaisons effectuées dans une mise en œuvre memcpy serré.

supposons que vous voulez copier les octets 'count' de a à b, l'Approche Directe est de faire ce qui suit:

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

combien de fois faut-il comparer le nombre pour voir s'il est supérieur à 0? "compte" fois.

maintenant, le dispositif duff utilise un effet secondaire involontaire méchant d'un boîtier de commutateur qui vous permet réduire le nombre de comparaisons nécessaires pour compter / 8.

supposons maintenant que vous voulez copier 20 octets en utilisant Duffs device, combien de comparaisons auriez-vous besoin? Seulement 3, puisque vous copiez huit octets à la fois sauf le dernier premier où vous copiez seulement 4.

mise à JOUR: Vous n'avez pas à faire 8 comparaisons/cas-dans-les instructions switch, mais il est raisonnable d'un compromis entre la taille de la fonction et de la vitesse.

quand je l'ai lu pour la première fois, je l'ai autoformaté à ce

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

le dispositif est valable, juridique C en vertu de deux attributs dans C:

• assouplissement de la spécification de l'indication de l'interrupteur le langage de définition. Au moment de l'invention de l'appareil, il s'agissait de la première édition du langage de programmation C qui exige seulement que la déclaration contrôlée du commutateur soit une déclaration (composé) valide sur le plan syntaxique dans laquelle les étiquettes de cas peuvent apparaître préfixant n'importe quelle sous-déclaration. En conjonction avec le fait qu'en l'absence d'une mention de rupture, le flux de contrôle passera d'une mention 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 Compte à partir d'adresses source séquentielles vers le port de sortie en mémoire.
• Le droit de sauter au milieu d'une boucle en C.

1: Duffs appareil est un particulier implémentation de déroulement de la boucle. Quel est le déroulement de la boucle?

Si vous avez une opération pour effectuer N fois dans une boucle, vous pouvez échanger la taille du programme pour la vitesse en exécutant la boucle n / n fois et puis dans la boucle inlining (déroulante) le code de 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!
}

qui fonctionne très bien si N % n = = 0-pas besoin de Duff! si ce est pas vrai alors vous devez gérer le reste - qui est une douleur.

2: en quoi le dispositif Duffs diffère-t-il de cette boucle standard?

Duffs device est juste une façon intelligente de traiter les cycles de boucle de reste quand N % n != 0. Le do / while entier exécute N / n nombre de fois selon la boucle standard déroulante (parce que le cas 0 s'applique). Lors du dernier passage à travers la boucle (le 'N/N+1'e fois) le cas s'enclenche et nous sautons vers le cas n % n et exécuter le code de boucle le "reste" nombre de fois.

même si je ne suis pas sûr à 100% de ce que vous demandez, voilà...

le problème que les adresses de l'appareil de Duff est une boucle de déroulement (comme vous aurez sans doute vu sur le Wiki lien que vous avez posté). Ce qui revient essentiellement à une optimisation de l'efficacité de l'exécution, par rapport à l'empreinte mémoire. Le dispositif de Duff traite de la copie en série, plutôt que de n'importe quel vieux problème, mais est un exemple classique de la façon dont les optimisations peuvent être faites en réduisant le nombre de fois qu'un la comparaison doit être faite en boucle.

comme exemple alternatif, qui peut le rendre plus facile à comprendre, imaginez que vous avez un tableau d'articles que vous souhaitez boucler, et ajouter 1 à chaque fois... normalement, vous pourriez utiliser un pour boucle, et boucle environ 100 fois. Cela semble assez logique et, il est... toutefois, une optimisation peut être réalisée en dévissant la boucle (évidemment pas trop loin)... ou vous pouvez tout simplement pas utiliser la boucle).

donc un régulier pour boucle:

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 le périphérique de Duff est d'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 unwound, c'est 10 comparaisons par rapport à 100 dans l'original-cela revient à une optimisation mineure, mais peut-être significative.

Voici une explication non-détaillée qui est ce que je sens être le nœud du dispositif de Duff:

la chose est, C est fondamentalement une belle façade pour le langage d'assemblage (Assemblée PDP-7 à être spécifique; si vous avez étudié que vous verriez comment frappant les similitudes sont). Et, en langage assembleur, vous n'avez pas vraiment de boucles - vous avez des étiquettes et des instructions de branche conditionnelle. Donc, la boucle est juste une partie de l'ensemble de la séquence d'instructions avec une étiquette et une branche quelque part:

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

et une instruction d'aiguillage se ramifie / saute quelque peu en avant:

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

dans l'assemblage, il est facile de concevoir comment combiner ces deux structures de commande, et quand on y pense de cette façon, leur combinaison en C ne semble plus si étrange.

vient d'expérimenter, a trouvé une autre variante obtenir le long sans interrupteur et boucle entrelacés:

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