Wie funktioniert Duffs Gerät?

Ich habe den Artikel auf Wikipedia auf dem Gerät des Duff gelesen und verstehe ihn 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 detailliertere Erklärung?

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

Angenommen, Sie kopieren 20 Bytes. Die Flusskontrolle des Programms für den ersten Durchgang 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...

20 Bytes werden jetzt kopiert.

Hinweis: Das Original-Duff-Gerät (siehe oben) wurde unter der toAdresse auf ein E / A-Gerät kopiert . Daher war es nicht erforderlich, den Zeiger zu erhöhen *to. Beim Kopieren zwischen zwei Speicherpuffern müssen Sie verwenden *to++.

Die Erklärung in Dr. Dobbs Tagebuch ist die beste, die ich zu diesem Thema gefunden habe.

Dies 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 an Duffs Gerät. Erstens, was meiner Meinung nach am einfachsten zu verstehen ist, wird die Schleife abgewickelt. Dies tauscht eine größere Codegröße gegen mehr Geschwindigkeit aus, indem ein Teil des Overheads vermieden wird, der mit der Überprüfung, ob die Schleife beendet ist, und dem Zurückspringen an die Spitze 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. Dadurch kann der Code beim ersten Durchgang in die Mitte der Schleife springen . Das Überraschende für die meisten Menschen ist, dass so etwas erlaubt ist. Nun, es ist erlaubt. Die Ausführung beginnt mit der berechneten Fallbezeichnung und fällt dann wie jede andere switch-Anweisung bis zu jeder nachfolgenden Zuweisungsanweisung durch . Nach der letzten Fallbezeichnung erreicht die Ausführung den unteren Rand der Schleife und springt an diesem Punkt wieder nach oben. Der obere Teil der Schleife befindet sich in der switch-Anweisung, sodass der switch 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 nicht ein Vielfaches von acht ist, bleiben einige Bytes übrig. Die meisten Algorithmen, die jeweils Byteblöcke kopieren, verarbeiten die restlichen Bytes am Ende, das Gerät von Duff jedoch am Anfang. Die Funktion berechnet count % 8für die switch-Anweisung, um den Rest zu ermitteln, springt für so viele Bytes zur Groß- / Kleinschreibung und kopiert sie. Dann kopiert die Schleife weiterhin Gruppen von acht Bytes.

Der Sinn 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 die Anzahl der Bytes von a nach b kopieren. Der einfache Ansatz besteht darin, Folgendes zu tun:

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

Wie oft müssen Sie die Anzahl vergleichen, um festzustellen, ob sie über 0 liegt? 'zählen' mal.

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

Angenommen, Sie möchten 20 Bytes mit dem Duffs-Gerät kopieren. Wie viele Vergleiche würden Sie benötigen? Nur 3, da Sie jeweils acht Bytes kopieren, mit Ausnahme des letzten ersten, bei dem Sie nur 4 Bytes kopieren.

AKTUALISIERT: Sie müssen nicht 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 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 hat Wikipedia eine sehr gute Erklärung

Das Gerät ist gültig, legal C aufgrund von zwei Attributen in C:

• Entspannte Angabe der switch-Anweisung in der Sprachdefinition. Zum Zeitpunkt der Erfindung des Geräts war dies die erste Ausgabe von The C Programming Language, die nur erfordert, dass die kontrollierte Anweisung des Schalters eine syntaktisch gültige (zusammengesetzte) Anweisung ist, in der Fallbezeichnungen vor jeder Unteranweisung stehen können. In Verbindung mit der Tatsache, dass bei Fehlen einer break-Anweisung der Kontrollfluss von einer von einem Falletikett kontrollierten Anweisung zu der von der nächsten kontrollierten Anweisung abfällt, bedeutet dies, dass der Code eine Folge von Zählkopien von angibt sequentielle Quelladressen an den speicherabgebildeten Ausgangsport.
• Die Fähigkeit, legal in die Mitte einer Schleife in C zu springen.

1: Das Duffs-Gerät ist eine besondere Folge des Abrollens von Schleifen. Was ist das Abrollen der Schleife?
Wenn Sie eine Operation haben, um N-mal in einer Schleife auszuführen, können Sie die Programmgröße gegen Geschwindigkeit eintauschen, indem Sie die Schleife N / n-mal ausführen und dann in der Schleife den Schleifencode n-mal einfügen (abrollen), z.

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 gut funktioniert, wenn N% n == 0 - keine Notwendigkeit für Duff! Wenn das nicht stimmt, müssen Sie den Rest erledigen - was ein Schmerz ist.

2: Wie unterscheidet sich das Duffs-Gerät von dieser Standard-Schleifenabwicklung?
Das Duffs-Gerät ist nur eine clevere Methode, um mit den verbleibenden Schleifenzyklen umzugehen, wenn N% n! = 0. Das gesamte do / while wird N / n gemäß dem Abrollen der Standardschleife N / n ausgeführt (da der Fall 0 zutrifft). Beim letzten Durchlauf der Schleife (das 'N / n + 1'-te Mal) tritt der Fall ein und wir springen zum Fall N% n und führen den Schleifencode die' verbleibende 'Anzahl von Malen aus.

Obwohl ich nicht 100% sicher bin, wonach Sie fragen, geht es weiter ...

Das Problem, das Duffs Gerät anspricht, ist das Abwickeln der Schleife (wie Sie zweifellos auf dem von Ihnen geposteten Wiki-Link gesehen haben). Dies entspricht im Wesentlichen einer Optimierung der Laufzeiteffizienz über den Speicherbedarf. Das Gerät von Duff befasst sich eher mit seriellem Kopieren als mit irgendeinem alten Problem, ist jedoch ein klassisches Beispiel dafür, wie Optimierungen vorgenommen werden können, indem die Häufigkeit reduziert wird, mit der ein Vergleich in einer Schleife durchgeführt werden muss.

Als alternatives Beispiel, das das Verständnis erleichtern könnte, stellen Sie sich vor, Sie haben eine Reihe von Elementen, über die Sie eine Schleife ausführen möchten, und fügen jedes Mal 1 hinzu. Normalerweise verwenden Sie eine for-Schleife und eine Schleife etwa 100 Mal . Dies scheint ziemlich logisch zu sein und es ist ... eine Optimierung kann jedoch durch Abwickeln der Schleife vorgenommen werden (offensichtlich nicht zu weit ... oder Sie können die Schleife auch einfach nicht verwenden).

Also eine reguläre 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 mit dem abgewickelten Beispiel sehen, sind 10 Vergleiche im Vergleich zu 100 im Original - dies ist eine geringfügige, aber möglicherweise signifikante Optimierung.

Hier ist eine nicht detaillierte Erklärung, die meiner Meinung nach der Kern von Duffs Gerät ist:

Die Sache ist, C ist im Grunde eine schöne Fassade für die Assemblersprache (PDP-7-Assemblierung um genau zu sein; wenn Sie das studieren würden, würden Sie sehen, wie auffällig die Ähnlichkeiten sind). Und in Assemblersprache haben Sie nicht wirklich Schleifen - Sie haben Beschriftungen und Anweisungen für bedingte Verzweigungen. Die Schleife ist also nur ein Teil der gesamten Befehlsfolge mit einer Beschriftung und einem Zweig irgendwo:

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

und eine Schaltanweisung verzweigt sich / springt etwas vorwärts:

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

In der Montage ist es leicht vorstellbar, wie diese beiden Kontrollstrukturen kombiniert werden sollen, und wenn man es so betrachtet, scheint ihre Kombination in C nicht mehr so ​​seltsam zu sein.

Dies ist eine Antwort, die ich auf eine andere Frage zu Duffs Gerät gepostet habe, die einige positive Bewertungen erhalten hat, bevor die Frage als Duplikat geschlossen wurde. Ich denke, es bietet hier einen wertvollen Kontext dafür, warum Sie dieses Konstrukt vermeiden sollten.

"Das ist Duffs Gerät . Es ist eine Methode zum Abrollen von Schleifen, bei der vermieden wird, dass eine sekundäre Fixup-Schleife hinzugefügt werden muss, um Zeiten zu bewältigen, in denen die Anzahl der Schleifeniterationen kein genaues Vielfaches des Abrollfaktors ist.

Da die meisten Antworten hier allgemein positiv zu sein scheinen, werde ich die Nachteile hervorheben.

Mit diesem Code wird ein Compiler Schwierigkeiten haben, eine Optimierung auf den Schleifenkörper anzuwenden. Wenn Sie den Code nur als einfache Schleife geschrieben haben, sollte ein moderner Compiler in der Lage sein, das Abrollen für Sie zu erledigen. Auf diese Weise behalten Sie die Lesbarkeit und Leistung bei und hoffen, dass weitere Optimierungen auf den Schleifenkörper angewendet werden.

Der Wikipedia-Artikel, auf den andere verweisen, sagt sogar, als dieses "Muster" aus dem Xfree86-Quellcode entfernt wurde, hat sich die Leistung tatsächlich verbessert.

Dieses Ergebnis ist typisch für die blinde Handoptimierung von Code, von dem Sie glauben, dass er benötigt wird. Es verhindert, dass der Compiler seine Arbeit ordnungsgemäß ausführt, macht Ihren Code weniger lesbar und anfälliger für Fehler und verlangsamt ihn normalerweise. Wenn Sie die Dinge an erster Stelle richtig machen würden, dh einfachen Code schreiben, dann Profile für Engpässe erstellen und dann optimieren, würden Sie niemals daran denken, so etwas zu verwenden. Jedenfalls nicht mit einer modernen CPU und einem modernen Compiler.

Es ist in Ordnung, es zu verstehen, aber ich wäre überrascht, wenn Sie es jemals tatsächlich benutzen würden. "

Beim Experimentieren habe ich eine andere Variante gefunden, die ohne Verschachtelung von Schalter und Schleife auskommt:

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