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
- Brian W. Kernighan, Dennis Ritchie: The C Programming Language. 2. Auflage. Prentice Hall, 1988, ISBN 81-203-0596-5.
- Bjarne Stroustrup: The C++ Programming Language. 3. Auflage. Addison-Wesley, 1997, ISBN 0-201-88954-4.
- British Standards Institution (Hrsg.): The C Standard – Incorporating TC1 – BS ISO/IEC 9899:1999. John Wiley & Sons, 2003, ISBN 0-470-84573-2.
Einzelnachweise
- ↑ a b Tom Duff on Duff’s Device auf lysator.liu.se (englisch)
- ↑ Eintrag Duff's Device im Jargon File auf catb.org (englisch)
- ↑ Theodore Ts’o zu XFree86 und Performance im Linux Kernel Archive auf lkml.indiana.edu (englisch)
