# Performance von FOR Schleifen



## Craven (2. Nov 2004)

Hallo Leute!

Neulich hab ich gelesen, daß folgende Schleife nicht gut (langsamer) ist.


```
for (int i=0;i<n.length();i++) {
...
}
```

folgendes soll schneller sein:


```
for (int i=0, s=n.length();i<s;i++){
...
}
```

das leuchtet mir ja auch durchaus ein. Allerdings hab ich keine Erfahrungswerte dazu. Vielleicht kann jemand von Euch was dazu sagen.

Vielleicht ist hier auch das richtige Forum, um mal generell über Schleifen zu reden (was ist am schnellsten?!)

Bin gespannt auf Euere Antworten

Craven


----------



## Koravel (2. Nov 2004)

Ich kann jetzt nur spekulieren:

Die erste Schleife ruft vor jedem Durchlauf die Methode length() von n auf.
(Was ist n, ein String?)
Die Zweite tut dies nur einmal, und vergleicht dann vor jedem Durchlauf i mit dem Inhalt von s.
In meinen Augen macht es Sinn, dass es schneller geht, da length() jedes Mal eingene Prozesse hat.

Aber ich denke nicht, dass man das so ohne weiteres merkt, es sei denn man arbeitet mit verschachtelten Schleifen, und/oder auf Rechnern mit beschränkten Ressourcen (Handys zum Beispiel)

Bei einem Array dürfte es keinen Unterschied machen, da dort nicht die Methode length(), sondern die Variable length abgerufen wird.

Zu Schleifen kann ich nur eins sagen (in diesem Zusammenhang):

```
int i = 0;
while(i < n.length()){
  [...]
  i++;
}
```

gibt exakt den gleichen Bytecode aus wie

```
for(int i = 0; i < n.length(); i++){
  [...]
}
```
Ergo: kein Unterschied bezüglich der Performanz.


----------



## 0xdeadbeef (2. Nov 2004)

Darum ging's ja auch nicht.

Also ein kleiner Test:


```
long t1,t2;
        int pos;
        String n = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        t1 = System.currentTimeMillis();
        for (int j=0; j<100000;j++) {        
            for (int i=0;i<n.length();i++) {
                pos = n.indexOf('z');
            } 
        }
        t2 = System.currentTimeMillis();
        System.out.println("Zeit1: " + (t2-t1));
        //
        t1 = System.currentTimeMillis();
        for (int j=0; j<100000;j++) {        
            for (int i=0,l=n.length();i<l;i++) {
                pos = n.indexOf('z');
            } 
            t2 = System.currentTimeMillis();
        }
        System.out.println("Zeit2: " + (t2-t1));
```

Ergebnis:
Zeit1: 813
Zeit2: 812

Wäre auch ein bescheidener Compiler, wenn das einen Unterschied machen würde.


----------



## dark_red (2. Nov 2004)

Wo wir gerade dabei sind, folgendes soll schneller als eine normale for-Schleife sein:

```
for (int i = 0; --i < 100;) {
    foo();
}
```

Afaik sollte ein Kompiler sowas so oder so schon optimiert haben, so dass dies keinen Unterschied mehr macht.


----------



## Illuvatar (2. Nov 2004)

Hm das würd ich mal ne Endlosschleife nennen :wink:


----------



## Guest (2. Nov 2004)

@Illuvatar
Hehe :bae:


----------



## 0xdeadbeef (2. Nov 2004)

Zum obigen Beispiel hinzufügen:


```
t1 = System.currentTimeMillis();
        for (int j=0; j<100000;j++) {        
            for (int i=n.length()-1;i>=0;i--) {
                pos = n.indexOf('z');
            } 
            t2 = System.currentTimeMillis();
        }
        System.out.println("Zeit3: " + (t2-t1));
```

Gleich schnell (im Rahmen der Meßungenauigkeit):

Zeit1: 781
Zeit2: 797
Zeit3: 781


----------



## Craven (3. Nov 2004)

Tja, als Ergebnis sollte also festgehalten werden, daß es keinen Unterschied macht, wie man Schleifen schreibt, da der Compiler diese sowieso optimiert.

Danke für Euere Beiträge.

Craven


----------



## dotlens (3. Nov 2004)

wieso setzt du denn t2 in der for -schlaufe?? so wird die zeit 100'000 mal gesetzt :s


----------



## Craven (3. Nov 2004)

```
class forTest {
  public static void main (String args []) {
    long t1,t2; 
        int pos; 
        String n = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 
        // -1-
        // Normalform
        t1 = System.currentTimeMillis(); 
        for (int j=0; j<100000;j++) {        
            for (int i=0;i<n.length();i++) { 
                pos = n.indexOf('z'); 
            } 
        } 
        t2 = System.currentTimeMillis(); 
        System.out.println("Zeit1: " + (t2-t1)); 
        // -2-
        // sollte schneller sein als -1-
        t1 = System.currentTimeMillis(); 
        for (int j=0; j<100000;j++) {        
            for (int i=0,l=n.length();i<l;i++) { 
                pos = n.indexOf('z'); 
            } 
        } 
        t2 = System.currentTimeMillis(); 
        System.out.println("Zeit2: " + (t2-t1));
        // -3-
        // noch eine Möglichkeit
        t1 = System.currentTimeMillis(); 
        for (int j=0; j<100000;j++) {        
            for (int i=n.length()-1;i>=0;i--) { 
                pos = n.indexOf('z'); 
            } 
        } 
        t2 = System.currentTimeMillis(); 
        System.out.println("Zeit3: " + (t2-t1)); 
        // -4- bis xxxx
        // gibts noch weitere Möglichkeiten?!
  }
}
```


----------



## dark_red (3. Nov 2004)

Illuvatar hat gesagt.:
			
		

> Hm das würd ich mal ne Endlosschleife nennen :wink:


Jaja... War ein Fehler... müsste ein ++i sein...  

BTW... müsste der int-Wert eigentlich nicht vom kleinst möglichen Wert wieder zurück zum Grössten springen? Währe dann ja keine Endlosschleife....


----------



## CelikBlek (4. Nov 2004)

laut "java magazin" ist eine rückwärts schleife also mit i-- in der Regel schneller.


----------



## dotlens (4. Nov 2004)

steht da auch eine Begründung? macht für mich nämlich keinen sinn


----------



## Bleiglanz (4. Nov 2004)

wenns im java magazin steht, dann ists wahrscheinlich falsch


----------



## dotlens (4. Nov 2004)

lol, schreiben die immer falsche sachen, damit man weis was NICHT wahrt ist?  
*java magazin nicht kennen*


----------



## muddin (23. Nov 2004)

Hi! 
Ich glaub was mit der --i Schleife gemeint war, war folgendes:
Man lässt im Schleifenkopf die Abbruchbedingung weg
for(int i=1000;;--i)
...

Somit wird diese nicht bei jedem Schleifendurchgang geprüft, was schneller ist.
Greift man so auf ein Array zu, wird spätestens bei i = -1 eine Exception ausgelöst. Diese fängt man ab, und verlässt die Schleife
Das Problem ist nur, dass es auch seine Zeit dauert, die Exception auszulösen. Wäre also nur in größeren Schleifen sinnvoll.


mfg,

Muddin


----------



## Bleiglanz (23. Nov 2004)

Ist überhaupt NIE sinnvoll


----------



## dark_red (23. Nov 2004)

Bleiglanz hat gesagt.:
			
		

> Ist überhaupt NIE sinnvoll


So ein Kommentar ist natürlich immer wieder sehr erfrischend und lehrreich, da er ja überaus gut Begründet ist. Bitte mehr davon, währe eine Berreicherung fürs Forum!


----------



## bygones (23. Nov 2004)

dark_red hat gesagt.:
			
		

> Bleiglanz hat gesagt.:
> 
> 
> 
> ...


Exception sind, wie der Name es auch impliziert - Ausnahmen.. und als diese sollte man sie auch betrachten und behandeln. Ein Abbruchbedingung nur über das Werfen einer Exception ist unsinnig (ob weniger performant denk ich, weiß nicht genau)...

 ???:L oder habe ich die Ironie nicht mitbekommen  :roll:


----------



## Bleiglanz (23. Nov 2004)

```
// For1 = "schlecht, weil jedesmal"
// 
for(int i=0;i<arr.length;i++)
{
   arr[i]=i;
}

   12:  astore_1
   13:  iconst_0
   14:  istore_2
   15:  goto    25
   18:  aload_1
   19:  iload_2
   20:  iload_2
   21:  iastore
   22:  iinc    2, 1
   25:  iload_2
   26:  aload_1
   27:  arraylength // tatsächlich innerhalb der Schleife!!!
   28:  if_icmplt       18
   31:  return


// For2 = "gut, weil nur einmal"
for(int i=0,len=arr.length;i<len;i++)
{
   arr[i]=i;
}

   12:  astore_1
   13:  iconst_0
   14:  istore_2
   15:  aload_1
   16:  arraylength // nur einmal vorher
   17:  istore_3
   18:  goto    28
   21:  aload_1
   22:  iload_2
   23:  iload_2
   24:  iastore
   25:  iinc    2, 1
   28:  iload_2
   29:  iload_3
   30:  if_icmplt       21
   33:  return
```
Eigentlich sollte also die gute Variante schneller sein, weil 
nicht nur der arraylength Befehl eingespart wird, sondern auch ein holen
des arrays eingespart wird (das gebraucht wird, um arraylength
überhaupt auszuführen). Wer jetzt glaubt dass das irgendwie relevant ist, der 
ist vollkommen auf dem Holzweg und soll mal schnell 5 Millionen java.util.Date 
auf seinem Rechner erzeugen.

Es würde mich wundern, wenn es jemand schafft, diesen 
Performancegewinn durch geeignete Benchmarks tatsächlich explizit 
nachzuweisen


Zum Thema "Exceptions als Mittel der Programmsteuerung" 
oder "Performancegewinn durch Endlosschleifen mit Exceptions":

Sowas verhindert (lt. Sun) alle JIT Optimierungen, ist schlechter Stil,
man kann natürlich im entsprechenden Programmblock keine ArrayIndexOutOfBounds 
Exception mehr finden - weil man sie für das Schleifenende hält usw.

Irgendwo hab ich mal ein interessantes Paper über einen Test von Sun gelesen,
bei dem mit verschiedenen JVMs (von IBM, Sun, Bea) verglichen wurde - dabei war der
Code mit "Exceptionsteuerung" fast immer LANGSAMER!


----------



## Sky (23. Nov 2004)

muddin hat gesagt.:
			
		

> Hi!
> Ich glaub was mit der --i Schleife gemeint war, war folgendes:
> Man lässt im Schleifenkopf die Abbruchbedingung weg
> for(int i=1000;;--i)
> ...



D.h. Du willst nen try-catch-Block in die Schleife legen? Das ist kompletter Wahnsinn, jedenfalls, wenn es um Performance geht!!! Denn ein try-catch-Block in einer Schleife ist langsamer als eine Abbruchbedingung! Vor allem sollte man m.E. komplizierte Berechnungen für den End-Wert vor die Schleife legen.

Also lieber:

```
int ende = berechneWasKompliziertes() * 7 + ( nochMehrAufwand()*3);
for ( int i = 1000; i > ende; i-- ) {
  ...
}
```

als: 


```
for ( int i = 1000; i > (berechneWasKompliziertes() * 7 + ( nochMehrAufwand()*3)); i-- ) {
  ...
}
```


Am allerbesten ist natürlich, wenn das Ende '0' ist, weil der Vergleich mit '0' besonders schnell ist (hab ich irgendwo bei sun gelesen). Also so:

```
for ( int i = 1000; i > 0; i-- ) {
  ...
}
```


----------



## Bleiglanz (23. Nov 2004)

> Denn ein try-catch-Block in einer Schleife ist langsamer als eine Abbruchbedingung!


bist du sicher? 

Es gibt ja immer zwei geläufige  Meinungen zum Thema:

"Das Betreten eines try-Blocks ist kostenlos"

und

"try-catch kostet soviel Performance, das ist schlimm"

Beide Ansichten sind falsch und führen zu viel dämlichen Code - in 99% aller Fälle sind nämlich alle diese Überlegungen für die Katz


----------



## muddin (24. Nov 2004)

Moin!

Hab gestern die Schleifenvarianten mit der Exception, --i, i++ getestet, und muss sagen, dass bei 10000000 Schleifendurchgängen der Unterschied aller Varianten so gering ist, dass er im Rahmen der Messungenauigkeit liegt.

mfg,

Muddin


----------



## dark_red (24. Nov 2004)

Nun ja... war ja eigentlich zu erwarten. 

Also... packt eure Profiler aus und optimiert richtig  Btw... kennt jemand einen guten freien Profiler? Komerziell gibt es einige nette Produkte, aber freies habe noch nicht gefunden.


----------



## Bleiglanz (24. Nov 2004)

> Hab gestern die Schleifenvarianten mit der Exception, --i, i++ getestet, und muss sagen, dass bei 10000000 Schleifendurchgängen der Unterschied aller Varianten so gering ist, dass er im Rahmen der Messungenauigkeit liegt.


Etwas anderes hätte micht auch gewundert. Wenn man ein paar Statements in der Schleife hat, dann erdrückt das die winzige Bedingungsabfrage; ist der Inhalt leer, wird das ganze möglicherweise vom JIT wegoptimiert!

In Wahrheit ist das alles völlig egal; als Programmierer muss man sein Gehirn eben mit Gewalt so konditionieren, dass man nicht ständig über läppische "Performance"-Fragen nachdenkt


----------



## Bleiglanz (25. Nov 2004)

Abschliessende Bemerkung (for the record)

Nur weils mich selbst interessiert hat, habe ich auch mal versucht zu Benchmarken (1000 Widerholungen von jeweils 15000000 Schleifendurchläufen)

good: ist die variante mit for(int i=0, len=arr.length;..)
bad: ist die variante mit for(int i=0; i<arr.length;
ex: ist die exception gesteuerte variante

angegeben sind die kumulierten Zeiten in ms

wenn schleifen nicht in funktionsaufrufen
good=139601
bad=145122
ex=139371

wenn schleifen in funktionsaufrufen (braucht man fürs profiling, ist ja schon unglaublich, dass das einen unterschied macht; offenbar wurde der good-loop per inline optimiert? komisch wenn man innerhalb der funktion misst!)

good=139245 ms
bad=156527 ms
ex=152766 ms

dann kann man nämlich auch profilen
mit  java -Xrunhprof:cpu=samples,gc_okay=n LoopShootout

CPU SAMPLES BEGIN (total = 196098) Thu Nov 25 10:45:53 2004
rank   self  accum   count trace method
   1 35.25% 35.25%   69133    13 LoopShootout.exceptionloop
   2 32.59% 67.85%   63917     8 LoopShootout.badloop
   3 31.73% 99.58%   62229    11 LoopShootout.goodloop
   4  0.16% 99.74%     315    17 java.io.FileOutputStream.writeBytes

Schaut so aus, als ob der goodloop der beste wäre, aber wenn ich mit einem Taschenrecher 

139 Sekunden / 15000000

ausrechnen würde...


----------

