imported>SchlurcherBot: Bot: http → https

2025-06-25T13:49:18Z

Bot: http → https

Neue Seite

'''Duff’s Device''' ist ein nach seinem Erfinder [[Tom Duff]] benanntes Programmierverfahren zum geschickten [[Loop unrolling|Abrollen von Schleifen]] ({{enS|''loop unrolling''}}) in der Programmiersprache [[C (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:


<syntaxhighlight lang="c">
send(to, from, count)
register short *to, *from;
register count;
{
do
*to = *from++;
while (--count>0);
}
</syntaxhighlight>

Duff störte, dass diese [[Implementierung#Softwaretechnik|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:<ref name="duff83" />

<syntaxhighlight lang="c">
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);
}
}
</syntaxhighlight>

=== Erklärung ===

Die Funktion erhält beim Aufruf die Adressen eines Ausgaberegisters (<code>*to</code>) und eines Arrays im Speicher (<code>*from</code>) und die Anzahl der zu übertragenden Daten (<code>short</code> steht meist für zwei Bytes) übergeben. Sie verwendet ein ''loop unrolling'', bei dem jeweils acht Elemente ausgerollt werden.<ref>[http://www.catb.org/jargon/html/D/Duffs-device.html Eintrag ''Duff’s Device''] im [[Jargon File]] auf catb.org ''(englisch)''</ref><ref name="duff83" />

Die Zählvariable <code>n</code> enthält die Anzahl der Schleifendurchläufe (<code>count/8</code>, aufgerundet). Ist <code>count</code> '''kein''' Vielfaches von acht, so wird beim ersten Durchlauf über die [[Bedingte Anweisung und Verzweigung#Mehrfache Verzweigung|Switch-Anweisung]] ein Teil der Schleife übersprungen und nur <code>Rest(count div 8)</code> 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.<ref>[[Theodore Ts’o]] zu [https://lkml.indiana.edu/hypermail/linux/kernel/0008.2/0171.html XFree86 und Performance] im Linux Kernel Archive auf lkml.indiana.edu ''(englisch)''</ref>

== 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 ==
<references>
<ref name="duff83">
[https://www.lysator.liu.se/c/duffs-device.html ''Tom Duff on Duff’s Device''] auf lysator.liu.se (englisch)
</ref>
</references>

{{SORTIERUNG:Duffs Device}}
[[Kategorie:C (Programmiersprache)]]
[[Kategorie:C++]]

Duff’s Device - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https