Thomas Kramer

IT-COW | Januar 2012

Loop Unrolling

By Administrator at Januar 26, 2012 08:45
Filed Under: Algorithmen, Java, Programmierung allgemein

Über ein Forum habe ich etwas von einer Optimierungs-Technik namens Loop Unrolling (Schleifen ausrollen) erfahren, welche zur Performance-Optimierung eines Programmes gehört.

 

Auf Wikipedia ist ein guter Artikel dazu, die Erklärung hier bringt es auf den Punkt:

 

"Statt eine Funktion einmal pro Schleifendurchlauf auszuführen wird sie z.B. acht mal nacheinander ausgeführt und somit die Schleifendurchläufe um den selben Faktor verkürzt."

 

Auf dieser Seite findet sich eine weitere Erwähnung, nachfolgend habe ich es einmal in Eclipse/Java selbst getestet:

 

public class Loop_unrolling {
   
      public static void main(String[] args)
      {
            long completeTimeBefore;
            long completeTimeAfter;
            long completeTimeDiff;
            int i=0;
            int[] array = new int[1000000];
           
            /* erster Test */
         
            completeTimeBefore = System.currentTimeMillis();
            for (i=0; i<1000000; i++) /* eine Million Durchläufe gemäß Schleifenkopf */
            {
              array[i] = 0;
            }           
            completeTimeAfter = System.currentTimeMillis();     
            completeTimeDiff   = completeTimeAfter - completeTimeBefore;
            System.out.println(i + " Instruktionen in der Schleife ausgeführt.");           
            System.out.println(completeTimeDiff + " ms Zeit benötigt ohne Loop-Unrolling.\n");
           
            /* nächster Test */
           
            completeTimeBefore = System.currentTimeMillis();
            i = 0;          
            for (int a=0; a<100000; a++) /* 100.000 Durchläufe gemäß Schleifenkopf, dafür je 10 Instruktionen */
            {
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
                array[i++] = 0;
            }
            completeTimeAfter = System.currentTimeMillis();     
            completeTimeDiff   = completeTimeAfter - completeTimeBefore;
            System.out.println(i + " Instruktionen in der Schleife ausgeführt.");           
            System.out.println(completeTimeDiff + " ms Zeit benötigt mit partiellem Loop-Unrolling.\n");           

            /* nächster Test */
           
            int iterations = 1000000;
            /* Rest */
            int left = iterations % 8;
            /* 8er Durchläufe */
            int nLoop = iterations - left;
           
            completeTimeBefore = System.currentTimeMillis();
            for (i=0; i<nLoop; i+=8)
            {             
                array[i] = 0;
                array[i+1] = 0;
                array[i+2] = 0;
                array[i+3] = 0;
                array[i+4] = 0;
                array[i+5] = 0;
                array[i+6] = 0;
                array[i+7] = 0;
            }
           
            /* Rest abarbeiten, in diesem Fall 0 */          
            while (i<iterations)
            {
                array[i++] = 0;                           
            }
           
            completeTimeAfter = System.currentTimeMillis();     
            completeTimeDiff   = completeTimeAfter - completeTimeBefore;
            System.out.println(i + " Instruktionen in der Schleife ausgeführt.");           
            System.out.println(completeTimeDiff + " ms Zeit benötigt mit partiellem Loop-Unrolling.\n");                      
      }
}

 

Meine Ergebnisse:

 

Fall 1:

Eine Million Durchläufe mit je einem Array-Zugriff.

1.000.000 Instruktionen in der Schleife ausgeführt.
5 ms Zeit benötigt ohne Loop-Unrolling.


Fall 2:

100.000 Durchläufe mit je 10 Array-Zugriffen - Array-Index jeweils um eins erhöht.
1.000.000 Instruktionen in der Schleife ausgeführt.
3 ms Zeit benötigt mit partiellem Loop-Unrolling.

 

Fall 3:

125.000 Durchläufe mit je 8 Array-Zugriffen - Array-Index jeweils um 1-7 erhöht; Schleifendurchlauf in 8er-Schritten.
1.000.000 Instruktionen in der Schleife ausgeführt.
2 ms Zeit benötigt mit partiellem Loop-Unrolling.

 

Mal ist Fall 2 schneller als 3, umgekehrt oder beide gleich schnell gewesen - aber immer ist Fall 1 ganz ohne Loop Unrolling am langsamsten gewesen. Gemäß avanzu.de sollte addieren um mehr als eins (Fall 3) mehr Rechenzeit benötigen als einfaches Inkrementieren um eins (Fall 2), aber das konnte ich somit nicht bestätigen - das liegt bei diesen niedrigen Werten aber möglicherweise auch an der Messungenauigkeit (oder der Java-JIT-Compiler nimmt im Gegensatz zu PHP automatische Optimierungen vor, das wäre auch eine Möglichkeit).

 

Im Studium wurde diese Optimierung-Technik übrigens nicht erwähnt. Nun ist auch klar warum Herr Gaußmann manchen seiner Suchalgorithmen-Varianten das Suffix unrolled im Namen gegeben hat. Diesen Link mit Binär-Tricks wollte ich mir auch nochmal in diesem Zusammenhang notieren. Modulo-Rechnung binär durchzuführen ist einfach und bekannt, aber da finden sich auch weitere Tricks.

 

Auf dieser Seite gibt es eine Menge weiterer Tipps zur Performance-Optimierung von Java-Programmen, wenn auch mit vielen redundanten Erwähnungen. Loop Unrolling bzw. Schleifen ausrollen wird auch öfter erwähnt. Interessant fand ich auch dass der Java-Garbage Collector vor Zeitmessungen gezielt aufgerufen werden sollte: "Call system.gc() before every timing run to minimize inconsistent results due to garbage collection in the middle of a run."

 

Weiterhin notieren wollte ich mir folgende Aussagen: "The architecture and algorithms of your program are much more important than any low-level optimizations you might perform.", "Choosing the best algorithm or data structure for a particular task is one of the keys to writing high-performance software.". Kurz gesagt ist die Wahl des richtigen Algorithmus wichtiger als Low-Level-Optimierungen.

 

Monats-Liste