Java loop efficiency

Question

Ich vergleiche die Effizienz von verschachtelten for, while und do-while-Schleifen in Java, und ich bin auf einige seltsame Ergebnisse gestoßen, die ich brauche, um zu verstehen.

public class Loops { 
    public static void main(String[] args) { 
     int L = 100000; // number of iterations per loop 
     // for loop 
     double start = System.currentTimeMillis(); 
     long s1 = 0; 
     for (int i=0; i < L; i++) { 
      for (int j = 0; j < L; j++) { 
       s1 += 1; 
      } 
     } 
     double end = System.currentTimeMillis(); 
     String result1 = String.format("for loop: %.5f", (end-start)/1000); 
     System.out.println(s1); 
     System.out.println(result1); 

     // do-while loop 
     double start1 = System.currentTimeMillis(); 
     int i = 0; 
     long s2 = 0; 
     do { 
      i++; 
      int j = 0; 
      do { 
       s2 += 1; 
       j++; 
      } while (j < L); 
     } while (i < L); 
     double end1 = System.currentTimeMillis(); 
     String result2 = String.format("do-while: %.5f", (end1-start1)/1000); 
     System.out.println(s2); 
     System.out.println(result2); 

     // while loop 
     double start2 = System.currentTimeMillis(); 
     i = 0; 
     long s3 = 0; 
     while (i < L) { 
      i++; 
      int j = 0; 
      while (j < L) { 
       s3 += 1; 
       j++; 
      } 
     } 
     double end2 = System.currentTimeMillis(); 
     String result3 = String.format("while: %.5f", (end2-start2)/1000); 
     System.out.println(s3); 
     System.out.println(result3); 
    } 
} 

Alle Schleifenzähler entsprechen jeweils 10 Milliarden; Die Ergebnisse verblüffen mich:

for-Schleife: 6,48300

do-while: 0,41200

während: 9,71500

Warum die do-while-Schleife ist so viel schneller? Diese Leistungslücke skaliert parallel zu allen Änderungen an L. Ich habe diese Schleifen unabhängig voneinander ausgeführt und sie führen das gleiche aus.

Answer 1

Ich habe den Code, den Sie bereitgestellt haben, ausgeführt und war auch überrascht, diese Unterschiede in der Leistung zu sehen. Aus Neugierde heraus begann ich zu forschen und fand heraus, dass trotz der Tatsache, dass diese Schleifen dasselbe zu tun scheinen, einige wichtige Unterschiede zwischen ihnen bestehen.

Meine Ergebnisse nach dem ersten Lauf dieser Schleifen waren:

for loop: 1.43100 
do-while: 0.51300 
while: 1.54500 

Aber wenn ich diese drei Schleifen mindestens 10mal dann die Leistung jedes dieser Schleife war so ziemlich das gleiche laufen.

for loop: 0.43200 
do-while: 0.46100 
while: 0.42900 

Der JIT in der Lage, diese Schleifen im Laufe der Zeit zu optimieren, aber es muss eine Unähnlichkeit sein, diese Schleifen verursacht eine andere Anfangsleistung haben. In der Tat gibt es tatsächlich zwei Unterschiede:

• Die do-while Schleife wenige Vergleiche als die for und while Schleifen

Zur Vereinfachung tun nehmen L = 1

long s1 = 0; 
for (int i=0; i < L; i++) { 
    for (int j = 0; j < L; j++) { 
     s1 += 1; 

äußeren Schleife : 0 innere Schleife: 0 innere Schleife: 1 äußeren Schleife: 1

4 Vergleiche insgesamt

int i = 0; 
long s2 = 0; 
do { 
    i++; 
    int j = 0; 
    do { 
     s2 += 1; 
     j++; 
    } while (j < L); 
} while (i < L); 

innere Schleife: 1 äußeren Schleife: 1

2 Vergleiche insgesamt

• Verschiedene erzeugt Bytecode

Zum Zwecke der weiteren Untersuchung habe ich Ihre Klasse leicht verändert, nicht die Art und Weise beeinflussen es funktioniert.

public class Loops { 
    final static int L = 100000; // number of iterations per loop 

    public static void main(String[] args) { 
     int round = 10; 
     while (round-- > 0) { 
      forLoop(); 
      doWhileLoop(); 
      whileLoop(); 
     } 
    } 

    private static long whileLoop() { 
     int i = 0; 
     long s3 = 0; 
     while (i++ < L) { 
      int j = 0; 
      while (j++ < L) { 
       s3 += 1; 
      } 
     } 
     return s3; 
    } 

    private static long doWhileLoop() { 
     int i = 0; 
     long s2 = 0; 
     do { 
      int j = 0; 
      do { 
       s2 += 1; 
      } while (++j < L); 
     } while (++i < L); 
     return s2; 
    } 

    private static long forLoop() { 
     long s1 = 0; 
     for (int i = 0; i < L; i++) { 
      for (int j = 0; j < L; j++) { 
       s1 += 1; 
      } 
     } 
     return s1; 
    } 
} 

Dann kompiliert und aufgerufen javap -c -s -private -l Loop den Bytecode zu erhalten.

Zuerst der Bytecode von doWhileLoop.

0: iconst_0  // push the int value 0 onto the stack 
    1: istore_1  // store int value into variable 1 (i) 
    2: lconst_0  // push the long 0 onto the stack 
    3: lstore_2  // store a long value in a local variable 2 (s2) 
    4: iconst_0  // push the int value 0 onto the stack 
    5: istore 4 // store int value into variable 4 (j) 
    7: lload_2  // load a long value from a local variable 2 (i) 
    8: lconst_1  // push the long 1 onto the stack 
    9: ladd  // add two longs 
    10: lstore_2  // store a long value in a local variable 2 (i) 
    11: iinc 4, 1 // increment local variable 4 (j) by signed byte 1 
    14: iload 4 // load an int value from a local variable 4 (j) 
    16: iload_0  // load an int value from a local variable 0 (L) 
    17: if_icmplt 7 // if value1 is less than value2, branch to instruction at 7 
    20: iinc 1, 1 // increment local variable 1 (i) by signed byte 1 
    23: iload_1  // load an int value from a local variable 1 (i) 
    24: iload_0  // load an int value from a local variable 0 (L) 
    25: if_icmplt 4 // if value1 is less than value2, branch to instruction at 4 
    28: lload_2  // load a long value from a local variable 2 (s2) 
    29: lreturn  // return a long value 

Nun ist die Bytecode von whileLooP:

0: iconst_0  // push int value 0 onto the stack 
    1: istore_1  // store int value into variable 1 (i) 
    2: lconst_0  // push the long 0 onto the stack 
    3: lstore_2  // store a long value in a local variable 2 (s3) 
    4: goto  26 
    7: iconst_0  // push the int value 0 onto the stack 
    8: istore 4 // store int value into variable 4 (j) 
    10: goto  17 
    13: lload_2  // load a long value from a local variable 2 (s3) 
    14: lconst_1  // push the long 1 onto the stack 
    15: ladd  // add two longs 
    16: lstore_2  // store a long value in a local variable 2 (s3) 
    17: iload 4 // load an int value from a local variable 4 (j) 
    19: iinc 4, 1 // increment local variable 4 (j) by signed byte 1 
    22: iload_0  // load an int value from a local variable 0 (L) 
    23: if_icmplt 13 // if value1 is less than value2, branch to instruction at 13 
    26: iload_1  // load an int value from a local variable 1 (i) 
    27: iinc 1, 1 // increment local variable 1 by signed byte 1 
    30: iload_0  // load an int value from a local variable 0 (L) 
    31: if_icmplt 7 // if value1 is less than value2, branch to instruction at 7 
    34: lload_2  // load a long value from a local variable 2 (s3) 
    35: lreturn  // return a long value 

Um die Ausgabe besser lesbar zu machen ich Kommentare haben anhängen beschreiben, was jeder Befehl auf dem ‪Java bytecode instruction listings basiert ist.

Wenn Sie genauer hinsehen, werden Sie sehen, dass es einen wichtigen Unterschied zwischen diesen beiden Bytecodes gibt. Die while-Schleife (das gleiche gilt für die for-Schleife) hat die if-Anweisungen (if_icmplt Anweisung) am Ende des Bytecodes definiert. Das bedeutet, dass zur Überprüfung der Exit-Bedingung der ersten Schleife ein Goto zu Zeile 26 aufgerufen werden muss und ähnlich zu Zeile 17 für die zweite Schleife.

wurde die obige Bytecode erzeugt Javac 1.6.0_45 unter Mac OS X mit

Zusammenfassung

Ich denke, die andere Menge von Vergleichen sowie die Existenz von goto Anweisungen in der while und for-Schleife Bytecode ist verantwortlich für den Leistungsunterschied zwischen diesen Schleifen.