Duff's Device

Duff's Device ist ein nach seinem Erfinder Tom Duff benanntes Programmierverfahren zur Effizienzsteigerung bei Schleifen.

Problem

Soll der Computer eine Anweisung wiederholt ausführen, 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, springt die Schleife ans Ende der Schleifenstruktur. Ist sie es nicht, werden die Anweisungen im Rumpf der Schleife verarbeitet. Danach springt der Computer zurück an den Ausgangspunkt, die Abbruchbedingung wird erneut geprüft. In der Programmiersprache C wäre folgender Programmauschnitt möglich:

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

Hier werden die im Array quelle gespeicherten Daten in das Array ziel kopiert. Die Schleife wird anzahl-mal durchlaufen. In jedem Durchlauf wird die Bedingung stelle < anzahl geprüft.

Wird so eine Schleife auf einem langsamen Computer ausgeführt oder ist die Anwendung besonders zeitkritisch, ist es nützlich, den Aufwand pro Durchlauf zu reduzieren. Dies macht das folgende Programm:

        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 die Schleifenbedingung nur noch ein Viertel so oft geprüft werden. Dieses Verfahren ist auch unter dem Namen "Loop Unrolling" bekannt.

Diese Lösung birgt aber ein neues Problem: anzahl muss eine durch vier teilbare Zahl sein, sonst wird die Anweisung beim letzten Durchlauf bis zu 3 mal zu viel ausgeführt.

Lösung

Der Duffapparat löst das Problem:

        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 Schleifenablauf ggf. an einer entsprechend späten Stelle der Schleife beginnen lässt. Den Einstiegspunkt durch eine um die Schleife gebaute Fallunterscheidung festlegen zu können, ist eine Eigenart der Programmiersprache C.

Referenz

• Eintrag Duff's Device im Jargon File