„Loop unrolling“ – Versionsunterschied

Loop unrolling ist eine Optimierung, die die Laufzeit eines Programms beschleunigt, auf Kosten seiner Größe.

Dabei wird versucht, Schleifen derart umzuwandeln, dass die Schleifenbedingungen seltener oder gar nicht mehr überprüft werden. Im Idealfall entfallen dadurch auch die Zählvariablen.

Moderne Compiler Entrollen Schleifen bei Bedarf automatisch, so dass diese Technik nicht mehr von Hand angewandt werden muss.

Idee

Bei einer Schleife muss in jedem Durchlauf die sogenannte Schleifenbedingung geprüft werden. Gerade bei Schleifen mit sehr kleinen Rumpf kann diese Prüfung einen verhältnismäßig großen Anteil der Laufzeit ausmachen.

for (int i=0; i<8; ++i)
    dest[i] = src[i];

Eine solche Schleife besteht nur aus wenigen Anweisungen: Kopieren, Erhöhen des Zählers, Prüfen der Bedingung und Sprung. Somit verbringt der Prozessor etwa die Hälfte der Zeit nur mit Kontrollanweisungen.

Die naheliegende Lösung ist, mehr Anweisungen in den Schleifenrumpf zu packen. Dadurch sinkt die Anzahl der ausgeführten Kontrollanweisungen.

Damit ein Compiler eine Schleife entrollen kann, muss

• die Anzahl der Schleifendurchläufe bereits bei der Übersetzung bekannt sein oder
• es müssen Kontrollanweisungen eingefügt werden um eine nur teilweise entrollte Schleife korrekt auszuführen.

Die Schleife kann nur teilweise entrollt werden, bspw. wenn sie sehr oft durchlaufen werden muss oder die genaue Anzahl der Durchläufe unbekannt ist.

Ein einzelner „Abroll“-Schritt verdoppelt die Anzahl der Kopierbefehle im Schleifenrumpf, dadurch halbiert sich die Anzahl der Durchläufe und damit auch die der Vergleiche:

for (int i=0; i<8; ++i) {
    dest[i] = src[i];
    ++i;
    dest[i] = src[i];
}

Oder auch vollständig:

dest[0] = src[0];
dest[1] = src[1];
dest[2] = src[2];
dest[3] = src[3];
dest[4] = src[4];
dest[5] = src[5];
dest[6] = src[6];
dest[7] = src[7];

Vorteile

• Die Ausführungszeit verkürzt sich, da weniger Kontrollanweisungen ausgeführt werden.
• Wenn die Schleife komplett entrollt werden kann, entfällt das Zählen und die zugehörigen Variablen.
• Besseres Pipelining.
• Weniger Branches im Programmablauf.

Nachteile

• Die Größe des Programms wächst, da die Anzahl der Instruktionen steigt.
• Beim manuellen Entrollen verschlechtert sich die Lesbarkeit des Quelltextes.

Siehe auch

• Duff’s Device