Loop unrolling

Loop unrolling (manchmal auch Loop unwinding), das „Strecken zyklischer Rechenpläne“^[1] oder „Strecken einer Schleife“^[2], ist eine Optimierungsmethode, die die Laufzeit eines Computerprogramms auf Kosten der Größe seiner Programmdatei beschleunigen kann.^[3] Dabei wird eine Schleife

• entweder durch eine äquivalente Schleife ersetzt, die mehrere Kopien des Schleifenrumpfes enthält und dafür eine geringere Anzahl an Durchläufen hat,
• oder komplett aufgelöst, indem der Schleifenrumpf so oft aneinandergereiht wird, wie die ursprüngliche Anzahl Durchläufe war.

Dadurch wird die Schleifenbedingung seltener oder gar nicht mehr überprüft. Es wird ferner oft ermöglicht, anschließend weitere Optimierungen des (entrollten) Schleifenrumpfes durchzuführen. Die Anzahl der Kopien des ursprünglichen Schleifenrumpfes wird Abrollfaktor (englisch unroll factor) genannt.^[4][5]

Moderne Compiler versuchen Schleifen automatisch zu entrollen, falls auf Geschwindigkeit optimiert werden soll.^[6][7] Ist bekannt, auf welcher Architektur genau ein Programm später ausgeführt wird, kann eine manuelle Optimierung jedoch überlegen sein.^[8]

Kommen die Wiederholungen durch Selbst-Aufrufe (Rekursionen) zustande, lassen sich durch Vervielfältigung des Prozedurrumpfes Prozeduraufrufe und -rücksprünge einsparen. In solchen Fällen spricht man von Recursion unrolling.

1. ↑ Rutishauser, Heinz: Automatische Rechenplanfertigung bei programmgesteuerten Rechenmaschinen. In: Mitteilungen aus dem Institut für angewandte Mathematik an der ETH Zürich. Birkhäuser, 1961, abgerufen am 6. Januar 2019. 
2. ↑ Bauer, F.L.; Wössner, H.: Algorithmische Sprache und Programmentwicklung. 2. Auflage. Springer, Berlin/Heidelberg/New York 1984, ISBN 3-540-12962-6, S. 287. 
3. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen ullman77.
4. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen muchnick.
5. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen intel_opt_man.
6. ↑ Intel C++ Compiler XE 13.0 User and Reference Guides: O
7. ↑ GCC 4.7.2 Manual: Optimization Options
8. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen amd2002.