Wydajność pętli Java

Question

Porównuję wydajność zagnieżdżonych pętli for, while i do-while w Javie, i natknąłem się na dziwne wyniki, które wymagają zrozumienia.

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); 
    } 
} 

Wszystkie pętle odpowiednich liczników sumują się do 10 miliardów; wyniki perplex mnie:

pętli for: 6,48300

do-while: 0,41200

natomiast: 9,71500

Dlaczego do-while więc znacznie szybciej? Luka wydajności skaluje się równolegle z każdą zmianą L. Uruchomiłem te pętle niezależnie i wykonują to samo.

Answer 1

Uruchomiłem kod, który podałeś, a także zaskoczył cię ten wzrost wydajności. Prowadzone przez ciekawość zacząłem badać i odkryłem, że pomimo tego, że te pętle robią to samo, są między nimi pewne istotne różnice.

Moje wyniki po pierwszym uruchomieniu tych pętli były:

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

Ale kiedy uruchomić te trzy pętle co najmniej 10 razy, a następnie wykonanie każdego z tych pętli był niemal tak samo.

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

JIT jest w stanie zoptymalizować te pętle w czasie, ale tam musi być jakaś odmienność przyczyną tych pętli ma inną początkową wydajność. W rzeczywistości istnieją rzeczywiście dwie różnice:

• Pętla do-while robi mniej porównań niż for i while pętli

Dla uproszczenia zakładamy, L = 1

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

zewnętrzną pętlę : 0 wewnętrzna pętla: 0 < wewnętrzna pętla: 1 zewnętrzna pętla: 1

4 porównania w całości

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

wewnętrznej pętli: 1 pętla zewnętrzna: 1

2 porównania łącznie

• Różne generowane bytecodes

W celu dalszego zbadania zmieniłem swoją klasę lekko, nie wpływając na sposób to działa.

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; 
    } 
} 

Następnie opracowano go i wywołany javap -c -s -private -l Loop uzyskać kodu bajtowego.

Najpierw kod bajtowy do dohileLoop.

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 

Teraz kodu bajtowego z 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 

Aby wyjście bardziej czytelny mam dołączania komentarzy opisujących co każda instrukcja jest oparta na ‪Java bytecode instruction listings.

Jeśli przyjrzysz się bliżej, zobaczysz, że istnieje znacząca różnica między tymi dwoma bajtami. Pętla while (tak samo jest w przypadku pętli for) ma instrukcje if (if_icmplt) zdefiniowane na końcu kodu bajtowego. Co oznacza, że ​​aby sprawdzić warunki wyjścia pierwszej pętli, należy wywołać linię goto do linii 26 i podobnie przejść do linii 17 dla drugiej pętli.

Powyższy kod bajtowy został wygenerowany przy użyciu javac 1.6.0_45 na Mac OS X.

Podsumowanie

Myślę, że inna ilość porównań oraz istnienie instrukcji goto w czasie i na pętli kodu bajtowego odpowiada za różnicę wydajności między tymi pętlami.