Performance von FOR Schleifen

[Craven]

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]

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]

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]

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]

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

 

[Guest]

@Illuvatar
Hehe :bae:

 

[0xdeadbeef]

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]

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]

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

 

[Craven]

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]

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]

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

 

[dotlens]

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

 

[Bleiglanz]

wenns im java magazin steht, dann ists wahrscheinlich falsch

 

[dotlens]

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

 

[muddin]

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]

Ist überhaupt NIE sinnvoll

 

[dark_red]

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]

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!

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]

// 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]

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

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]

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]

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]

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]

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]

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...