Duff’s Device

Duff's Device (auf deutsch etwa: Duff-Apparat) ist ein nach seinem Erfinder Tom Duff benanntes Programmierverfahren zur Effizienzsteigerung bei Schleifen unter Ausnutzung einer speziellen Eigenschaft der Programmiersprache C.

Hintergrund

Soll ein Computer eine Anweisung wiederholt ausführen, so wird sie innerhalb einer Schleife ausgeführt. Dabei wird am Ausgangspunkt der Schleife überprüft, ob die Abbruchbedingung erfüllt ist. Wenn sie es ist, wird die Programmausführung hinter der Schleifenstruktur fortgesetzt. Ist sie es nicht, werden die Anweisungen im Schleifenrumpf abgearbeitet und danach ein Sprung an den Ausgangspunkt ausgeführt, wo die Abbruchbedingung erneut geprüft wird. In C wäre beispielsweise folgendes möglich:

        while(stelle < anzahl) {
                ziel[stelle] = quelle[stelle]; stelle++;
        }

Hier werden die Daten aus dem Array quelle in das Array ziel kopiert. Die Schleife wird anzahl mal durchlaufen. Zu Beginn wird die Bedingung (stelle < anzahl) geprüft und nach Durchlaufen des Schleifenkörpers ein Sprung zurück an den Anfang (erneute Prüfung der Bedingung) der Schleife ausgeführt.

Problem

Wird solch eine Schleife auf einem langsamen Computer ausgeführt, oder ist die Anwendung besonders zeitkritisch, so ist es nützlich, den Aufwand dadurch zu senken, dass die Schleife weniger oft durchlaufen wird und dafür mehrere gleichartige Anweisungen je Durchlauf ausgeführt werden. Dies veranschaulicht das folgende Programmfragment:

        while(stelle < anzahl) {
                ziel[stelle] = quelle[stelle]; stelle++;
                ziel[stelle] = quelle[stelle]; stelle++;
                ziel[stelle] = quelle[stelle]; stelle++;
                ziel[stelle] = quelle[stelle]; stelle++;
        }

Die Anweisung im Schleifenrumpf wurde vervierfacht. Auf diese Weise muss nur noch ein Viertel so oft die Schleifenbedingung geprüft und gesprungen werden. Dieses Verfahren wird Loop Unwinding oder Loop Unrolling genannt. Dieser Lösungsansatz birgt allerdings ein neues Problem: anzahl muss eine durch vier teilbare Zahl sein, sonst wird die Anweisung beim letzten Durchlauf durch den Schleifenkörper bis zu dreimal zu oft ausgeführt. Es muss also durch zusätzlichen Programmieraufwand dieses Problem umgangen werden.

Lösung

Duff's Device löst das Problem auf folgende Weise:

        n = (anzahl + 3) / 4;
 
        switch(anzahl % 4) {
        case 0:        do { ziel[stelle] = quelle[stelle]; stelle++;
        case 3:             ziel[stelle] = quelle[stelle]; stelle++;
        case 2:             ziel[stelle] = quelle[stelle]; stelle++;
        case 1:             ziel[stelle] = quelle[stelle]; stelle++;
                       } while(--n > 0);
        }

Zunächst wird in n der aufgerundete Quotient von anzahl und 4 gespeichert. Bei n-maliger Ausführung würde die Anweisung (anzahl % 4)-mal zu viel ausgeführt. Abhilfe schafft die switch-Anweisung, die den ersten Schleifendurchlauf an einer entsprechend weiter hinten gelegenen Position des Schleifenkörpers beginnen lässt. Zwei besondere Eigenschaften der Programmiersprache C (und direkt von ihr abgeleiteter Sprachen wie z. B. C++) ermöglichen es, die Anweisungen innerhalb der Schleife mit einem Fallunterscheidungskonstrukt zu verzahnen und so den Einstiegspunkt frei zu wählen:

1. Es ist zulässig, direkt in den Rumpf einer Schleife zu springen.
2. Der sogenannte fall-through bewirkt, dass, wenn die einer case-Marke folgende Anweisungssequenz nicht mit dem Schlüsselwort break abgeschlossen ist, die Programmausführung einfach mit dem direkt folgenden Programmcode fortsetzt und nicht ans Ende des switch-Blocks springt.

Einen Nachteil hat jedoch auch diese Methode: hat anzahl den Wert 0, so wird der gesamte Schleifenkörper genau einmal (statt überhaupt nicht) abgearbeitet. Dies kann aber leicht durch eine vorherige Prüfung vermieden werden.^[1]

Original

Das oben beschriebene Beispiel, wie es ähnlich auch Bjarne Stroustrup in seinem Buch The C++ Programming Language verwendet, dient letztlich nur der Veranschaulichung des Prinzips. Das Kopieren von Inhalten zwischen Speicherbereichen wird in C gleich gut oder effizienter durch vorgefertigte Funktionen der Standardbibliothek erledigt, was natürlich auch Tom Duff bewusst war. Seine Problemstellung wich aber von dem oben geschilderten Szenario dahingehend ab, dass er möglichst effizient konsekutive Speicherinhalte sequenziell auf genau eine Speicherstelle, nämlich ein Ausgaberegister, schreiben musste. Er arbeitete 1983 bei Lucasfilm und hatte festgestellt, dass die folgende Funktion zur Ausgabe von Bilddaten auf eine spezielle Hardware zu langsam lief:

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

Da ein solches Konstrukt sich eben nicht einfach durch effizientere Standardfunktionen ersetzen lässt, entwickelte er folgende Originalversion von Duff's Device:

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

Diese Funktion bekommt beim Aufruf die Adressen zweier Speicherstellen und die Anzahl zu kopierender Daten übergeben und verwendet ein achtfaches Loop Unwinding. Nach jeder Zuweisung von Quelldaten an das Ausgaberegister to wird die Quelladresse from inkrementiert.^[2][3]

Kritik

Duff's Device erfüllte in seiner ursprünglichen Verwendung seinen Zweck und widerspricht auch nicht den Regeln der Sprache C^[3], wirkt sich aber negativ auf die Lesbarkeit des Programmtextes aus und ist besonders für ungeübte Programmierer nicht auf Anhieb zu durchschauen. Der Erfinder selbst stand seiner Kreation ambivalent gegenüber und schrieb dazu wörtlich:

„Many people (even bwk^[4]?) have said that the worst feature of C is that switches don't break automatically before each case label. This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.“

„Viele Leute (...) halten die Tatsache, dass switch nicht vor jeder case-Marke automatisch abbricht, für das schlechteste Merkmal von C. Dieser Code stellt eine Art Argument in dieser Diskussion dar, aber ich bin mir nicht sicher, ob dafür oder dagegen.“

– Tom Duff: Tom Duff on Duff's Device^[3]

Schwerer als die umstrittene Eleganz der Lösung wiegt jedoch, dass sich solche manuellen Mikro-Optimierungen von Programmen in der Praxis häufig kontraproduktiv auswirken, da sie die Erzeugung von effizientem Maschinencode für heute übliche Prozessorarchitekturen durch moderne Compiler verhindern. Diese verfügen nämlich selbst über Verfahren zum Loop Unrolling und zum Prüfen der Zweckmäßigkeit solcher Optimierungen.^[5]

Einzelnachweise

1. ↑ Ausführlicher Eintrag in der C-FAQ von Steve Summit auf www.c-faq.com (englisch)
2. ↑ Eintrag Duff's Device im Jargon File auf www.catb.org (englisch)
3. ↑ ^{a b c} Tom Duff on Duff's Device auf www.lysator.liu.se (englisch)
4. ↑ Brian W. Kernighan, Koautor des Buches The C Programming Language
5. ↑ Theodore Ts'o zu XFree86 und Performance im Linux Kernel Archive auf lkml.indiana.edu (englisch)

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 Institute (Hrsg.): The C Standard - Incorporating TC1 - BS ISO/IEC 9899:1999. John Wiley & Sons, 2003. ISBN 0-470-84573-2