Wie funktioniert Duffs Gerät?

Ich habe die gelesen Artikel auf Wikipedia über das Duff-Gerät, und ich verstehe es nicht. Ich bin wirklich interessiert, aber ich habe die Erklärung dort ein paar Mal gelesen und verstehe immer noch nicht, wie das Gerät des Duff funktioniert.

Was wäre eine genauere Erklärung?

Es gibt an anderer Stelle einige gute Erklärungen, aber lassen Sie es mich versuchen. (Das ist auf einem Whiteboard viel einfacher!) Hier ist das Wikipedia-Beispiel mit einigen Notationen.

Angenommen, Sie kopieren 20 Bytes. Die Ablaufsteuerung des Programms für den ersten Durchlauf ist:

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

Starten Sie nun den zweiten Durchgang, wir führen nur den angegebenen Code aus:

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

Starten Sie nun den dritten Durchgang:

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

Es werden nun 20 Byte kopiert.

Hinweis: Das ursprüngliche Gerät von Duff (oben gezeigt) wurde auf ein E/A-Gerät kopiert to die Anschrift. Somit war es nicht erforderlich, den Zeiger zu inkrementieren *to. Beim Kopieren zwischen zwei Speicherpuffern müssten Sie verwenden *to++.

Das Erklärung in Dr. Dobb’s Journal ist das Beste, was ich zu diesem Thema gefunden habe.

Das ist mein AHA-Moment:

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

wird:

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

wird:

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

Es gibt zwei wichtige Dinge bei Duffs Gerät. Zuerst, was meiner Meinung nach der einfacher zu verstehende Teil ist, wird die Schleife entrollt. Dadurch wird eine größere Codegröße gegen mehr Geschwindigkeit eingetauscht, indem ein Teil des Overheads vermieden wird, der mit der Prüfung, ob die Schleife beendet ist, und dem Zurückspringen zum Anfang der Schleife verbunden ist. Die CPU kann schneller laufen, wenn sie geradlinigen Code ausführt, anstatt zu springen.

Der zweite Aspekt ist die switch-Anweisung. Es ermöglicht dem Code, in die zu springen Mitte der Schleife beim ersten Durchlaufen. Das Überraschende für die meisten Menschen ist, dass so etwas erlaubt ist. Nun, es ist erlaubt. Die Ausführung beginnt bei der berechneten Fallbezeichnung und dann bei ihr fällt durch zu jeder nachfolgenden Zuweisungsanweisung, genau wie jede andere switch-Anweisung. Nach dem letzten Case-Label erreicht die Ausführung das Ende der Schleife und springt an diesem Punkt zurück zum Anfang. Die Spitze der Schleife ist Innerhalb die switch-Anweisung, sodass der Schalter nicht mehr neu ausgewertet wird.

Die ursprüngliche Schleife wird achtmal abgewickelt, sodass die Anzahl der Iterationen durch acht geteilt wird. Wenn die Anzahl der zu kopierenden Bytes kein Vielfaches von acht ist, bleiben einige Bytes übrig. Die meisten Algorithmen, die Blöcke von Bytes gleichzeitig kopieren, verarbeiten die restlichen Bytes am Ende, aber Duffs Gerät verarbeitet sie am Anfang. Die Funktion rechnet count % 8 damit die switch-Anweisung herausfinden kann, was der Rest sein wird, springt sie zum case-Label für so viele Bytes und kopiert sie. Dann fährt die Schleife damit fort, Gruppen von acht Bytes zu kopieren.

Der Zweck des Duffs-Geräts besteht darin, die Anzahl der Vergleiche zu reduzieren, die in einer engen Memcpy-Implementierung durchgeführt werden.

Angenommen, Sie möchten ‘count’ Bytes von kopieren b zu abesteht der direkte Ansatz darin, Folgendes zu tun:

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

Wie oft müssen Sie die Anzahl vergleichen, um zu sehen, ob sie über 0 liegt? mal ‘zählen’.

Jetzt verwendet das Duff-Gerät einen unangenehmen unbeabsichtigten Nebeneffekt eines Switch-Falls, mit dem Sie die Anzahl der zum Zählen von / 8 erforderlichen Vergleiche reduzieren können.

Angenommen, Sie möchten 20 Bytes mit dem Duffs-Gerät kopieren. Wie viele Vergleiche würden Sie benötigen? Nur 3, da Sie außer den acht Bytes auf einmal kopieren letzte erste, wo Sie nur 4 kopieren.

AKTUALISIERT: Sie müssen keine 8 Vergleiche/Case-in-Switch-Anweisungen durchführen, aber es ist ein vernünftiger Kompromiss zwischen Funktionsgröße und Geschwindigkeit.

Als ich es zum ersten Mal las, habe ich es automatisch so formatiert

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

und ich hatte keine Ahnung, was los war.

Vielleicht nicht, als diese Frage gestellt wurde, aber jetzt Wikipedia hat eine sehr gute Erklärung

Das Gerät ist gültiges, legales C aufgrund von zwei Attributen in C:

• Lockere Angabe der switch-Anweisung in der Sprachdefinition. Zum Zeitpunkt der Erfindung des Geräts war dies die erste Ausgabe der C-Programmiersprache, die nur erfordert, dass die kontrollierte Anweisung des Schalters eine syntaktisch gültige (zusammengesetzte) Anweisung ist, in der Fallbezeichnungen erscheinen können, die jeder Unteranweisung vorangestellt sind. In Verbindung mit der Tatsache, dass in Abwesenheit einer break-Anweisung der Kontrollfluss von einer Anweisung, die von einem case-Label gesteuert wird, zu der von der nächsten gesteuerten Anweisung durchfällt, bedeutet dies, dass der Code eine Folge von Count-Kopien von angibt sequentielle Quelladressen an den speicherabgebildeten Ausgangsport.
• Die Möglichkeit, legal in die Mitte einer Schleife in C zu springen.

1: Das Duffs-Gerät ist eine spezielle Implementierung des Schleifenabrollens. Loop Unrolling ist eine Optimierungstechnik, die anwendbar ist, wenn Sie eine Operation haben, die N-mal in einer Schleife ausgeführt werden soll. Sie können die Programmgröße gegen Geschwindigkeit eintauschen, indem Sie die Schleife N / n-mal ausführen und dann in der Schleife den Schleifencode n-mal einbetten (entrollen), z ersetzen:

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

mit

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

Was großartig funktioniert, wenn N % n == 0 – keine Notwendigkeit für Duff! Wenn das nicht stimmt, dann müssen Sie mit dem Rest fertig werden – was ein Schmerz ist.

2: Wie unterscheidet sich Duffs Gerät von diesem Standard-Loop-Abrollen?
Das Duffs-Gerät ist nur eine clevere Methode, um mit den Restschleifenzyklen umzugehen, wenn N % n ! = 0. Das gesamte do / while führt N / n Mal gemäß dem Standard-Schleifenabrollen aus (weil der Fall 0 zutrifft). Auf der letzte Wenn Sie zuerst die Schleife durchlaufen, tritt der Fall ein, und wir führen den Schleifencode die verbleibende Anzahl von Malen aus – die verbleibenden Durchläufe durchlaufen die Schleife „normal“.

Obwohl ich nicht 100% sicher bin, wonach du fragst, hier geht es …

Das Problem, das Duffs Gerät adressiert, ist das Abwickeln der Schleife (wie Sie zweifellos auf dem von Ihnen geposteten Wiki-Link gesehen haben). Was dies im Grunde bedeutet, ist eine Optimierung der Laufzeiteffizienz gegenüber dem Speicherbedarf. Das Gerät von Duff befasst sich mit seriellem Kopieren und nicht mit irgendeinem alten Problem, sondern ist ein klassisches Beispiel dafür, wie Optimierungen vorgenommen werden können, indem die Anzahl der Vergleiche reduziert wird, die in einer Schleife durchgeführt werden müssen.

Stellen Sie sich als alternatives Beispiel, das das Verständnis erleichtern könnte, vor, Sie haben eine Reihe von Elementen, die Sie durchlaufen möchten, und fügen Sie ihnen jedes Mal 1 hinzu … normalerweise könnten Sie eine for-Schleife verwenden und etwa 100 Mal durchlaufen . Dies erscheint ziemlich logisch und ist es auch … jedoch kann eine Optimierung vorgenommen werden, indem die Schleife abgewickelt wird (offensichtlich nicht zu weit … oder Sie können die Schleife auch einfach nicht verwenden).

Also eine normale for-Schleife:

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

wird

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

Duffs Gerät implementiert diese Idee in C, aber (wie Sie im Wiki gesehen haben) mit seriellen Kopien. Was Sie oben sehen, mit dem abgewickelten Beispiel, sind 10 Vergleiche im Vergleich zu 100 im Original – dies kommt einer geringfügigen, aber möglicherweise signifikanten Optimierung gleich.