Duff’s Device

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Duff's Device (auf deutsch etwa: Duffs Mittel) 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[Bearbeiten]

Duff arbeitete 1983 beim Filmproduktionsunternehmen Lucasfilm und hatte festgestellt, dass die folgende Funktion zur Ausgabe von Bilddaten auf spezieller Hardware zu langsam lief:

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

Duff fand heraus, dass diese Implementierung die Hälfte der 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 übliche Technik, 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[Bearbeiten]

Die Funktion bekommt beim Aufruf die Adressen eines Outputregisters (*to) und eines Arrays im Speicher (*from) und die Anzahl der zu übertragenden Daten (short steht i. A. 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 kopierende Elemente dann ein Vielfaches von acht. Von da an wird der Schleifenrumpf dann immer komplett durchlaufen und jeweils acht Elemente am Stück verarbeitet.

Nachteile[Bearbeiten]

Auf heute üblichen Prozessoren ist es nicht gesagt, dass eine Anwendung dieser Methode zu einer Effizienzsteigerung führt, da sie sich negativ auf das Cache-Verhalten auswirken kann. Moderne Compiler verfügen selbst über Verfahren zum Abrollen von Programmierschleifen, wobei sie die jeweilige Zielplattform berücksichtigen. Der Code kann durch häufige Anwendungen der Methode extrem vergrößert werden.[3] Zudem verringert die Methode die Expressivität des Codes.

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. a b 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)