Duff’s Device

Duff’s Device ist ein nach seinem Erfinder Tom Duff benanntes Programmierverfahren zum geschickten Abrollen von Schleifen (englisch loop unrolling) in der Programmiersprache C. Es löst auf Code-sparende Weise das Problem, dass die Anzahl der Schleifendurchläufe evtl. kein Vielfaches der n-fach-Entrollung der Schleife ist oder die Anzahl an Durchläufen variabel ist und sich erst zur Laufzeit ergibt. Duff’s Device ist in jeder Programmiersprache anwendbar, die Einsprünge in den Schleifenkörper erlaubt.

Funktionsweise

Duff arbeitete 1983 beim Filmproduktionsunternehmen Lucasfilm und stellte fest, dass die folgende Funktion zur Ausgabe von Bilddaten auf spezieller Hardware für seine Anwendung zu langsam lief:

send(to, from, count)
register short *to, *from;
register count;
{
    do
        *to = *from++;
    while (--count>0);
}

Duff störte, dass diese Implementierung viel Zeit mit dem Prüfen der Schleifenbedingung verbrachte. Das Standardverfahren, um die Ausführungsgeschwindigkeit von Schleifen zu erhöhen, besteht darin, sie abzurollen. Dabei bleibt jedoch ein partieller Durchlauf übrig. Aus der Assembler-Programmierung kannte Duff die Möglichkeit, direkt in die Schleife hineinzuspringen. In der Programmiersprache C kann dies mithilfe der Switch-Anweisung gelöst werden:[1]

send(to, from, count)
register short *to, *from;
register count;
{
    register 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);
    }
}

Erklärung

Die Funktion erhält beim Aufruf die Adressen eines Ausgaberegisters (*to) und eines Arrays im Speicher (*from) und die Anzahl der zu übertragenden Daten (short steht meist für zwei Bytes) übergeben. Sie verwendet ein loop unrolling, bei dem jeweils acht Elemente ausgerollt werden.[2][1]

Die Zählvariable n enthält die Anzahl der Schleifendurchläufe (count/8, aufgerundet). Ist count kein Vielfaches von acht, so wird beim ersten Durchlauf über die Switch-Anweisung ein Teil der Schleife übersprungen und nur Rest(count div 8) Elemente kopiert. Ab dem zweiten Durchlauf ist die Anzahl der noch zu kopierenden Elemente dann ein Vielfaches von acht. Anschließend wird immer der gesamte Schleifenrumpf durchlaufen und jeweils acht Elemente am Stück verarbeitet.

Nachteile

Auf modernen Prozessoren führt diese Methode nicht notwendigerweise zu einer Effizienzsteigerung, da sie sich negativ auf das Cache-Verhalten auswirken kann. Moderne Compiler verwenden selbst Verfahren zum Abrollen von Programmierschleifen, wobei sie die jeweilige Zielplattform berücksichtigen. Zudem kann der Code durch häufige Anwendungen der Methode extrem vergrößert werden.[3]

Literatur

Einzelnachweise
  1. Tom Duff on Duff’s Device auf lysator.liu.se (englisch)
  2. Eintrag Duff’s Device im Jargon File auf catb.org (englisch)
  3. Theodore Ts’o zu XFree86 und Performance im Linux Kernel Archive auf lkml.indiana.edu (englisch)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.