Hiệu suất vòng lặp Java

Question

Tôi so sánh hiệu quả của các vòng lặp lồng nhau trong khi và trong khi thực hiện trong Java và tôi đã gặp một số kết quả lạ mà tôi cần trợ giúp để hiểu.

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

Tất cả các vòng tương ứng đều tính tổng 10 tỷ; kết quả làm rối tôi:

vòng lặp for: 6,48300

do-while: 0,41200

khi: 9,71500

Tại sao là do-while loop rất nhiều nhanh hơn? Khoảng cách hiệu suất này quy mô song song với bất kỳ thay đổi nào đối với L. Tôi đã chạy các vòng lặp này một cách độc lập và chúng hoạt động giống nhau.

Answer 1

Tôi đã chạy mã bạn đã cung cấp và cũng rất ngạc nhiên khi thấy những khác biệt này về hiệu suất. Dẫn đầu bởi sự tò mò, tôi bắt đầu điều tra và phát hiện ra rằng thực sự mặc dù những vòng này dường như đang làm điều tương tự có một số khác biệt quan trọng giữa chúng.

kết quả của tôi sau khi chạy đầu tiên của các vòng là:

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

Nhưng khi tôi chạy ba vòng ít nhất 10 lần sau đó hiệu suất của mỗi người trong các vòng lặp đã được khá nhiều giống nhau.

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

JIT có thể tối ưu hóa các vòng này theo thời gian, nhưng phải có một số khác biệt khiến các vòng lặp này có hiệu suất ban đầu khác nhau. Trong thực tế có thực sự là hai sự khác biệt:

• Vòng lặp do-while đang làm so sánh ít hơn for và while vòng

Để đơn giản giả định L = 1

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

vòng ngoài : 0 vòng lặp bên trong: 0 vòng lặp bên trong: 1 ngoài vòng: 1

4 so sánh trong tổng

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

vòng lặp bên trong: 1 vòng ngoài: 1

2 so sánh trong tổng số

• bytecode tạo khác nhau

Với mục đích nghiên cứu thêm Tôi đã thay đổi lớp học của bạn một chút, không ảnh hưởng đến cách nó hoạt động.

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

Sau đó biên dịch và gọi javap -c -s -private -l Loop để nhận mã byte.

Đầu tiên mã byte của 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 

Bây giờ bytecode của 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 

Để làm cho đầu ra dễ đọc hơn tôi đã thêm ý kiến ​​mô tả những gì từng giảng dạy không dựa trên ‪Java bytecode instruction listings.

Nếu bạn nhìn kỹ hơn, bạn sẽ thấy rằng có sự khác biệt quan trọng giữa hai bytecode này. Vòng lặp while (điều này cũng đúng cho vòng lặp for) có câu lệnh if (if_icmplt lệnh) được xác định ở cuối bytecode. Có nghĩa là để kiểm tra điều kiện thoát của vòng đầu tiên, một goto đến dòng 26 phải được gọi và tương tự như một goto đến dòng 17 cho vòng lặp thứ hai.

Các bytecode trên được tạo ra sử dụng javac 1.6.0_45 trên Mac OS X.

Tóm tắt

Tôi nghĩ rằng số tiền khác nhau so sánh cộng với sự tồn tại của hướng dẫn goto trong thời gian và vòng lặp for bytecode chịu trách nhiệm về sự khác biệt hiệu suất giữa các vòng lặp này.