Hai hoạt động trong một vòng lặp so với hai vòng lặp thực hiện cùng một hoạt động một vòng lặp

Question

Câu hỏi này giống hệt với số này Two loop bodies or one (result identical) nhưng trong trường hợp của tôi, tôi sử dụng Java.

Tôi có hai vòng chạy hàng tỷ lần.

int a = 188, b = 144, aMax = 0, bMax = 0; 

for (int i = 0; i < 1000000000; i++) { 
    int t = a^i; 
    if (t > aMax) 
    aMax = t;  
} 

for (int i = 0; i < 1000000000; i++) { 
    int t = b^i; 
    if (t > bMax) 
    bMax = t;  
} 

Thời gian cần để chạy hai vòng này trong máy của tôi là appr 4 giây. Khi tôi kết hợp hai vòng này thành một vòng lặp đơn và thực hiện tất cả các hoạt động trong vòng lặp đơn đó, thì nó sẽ chạy trong 2 giây. Như bạn có thể thấy các hoạt động tầm thường tạo nên nội dung vòng lặp, do đó yêu cầu thời gian không đổi.

Câu hỏi của tôi là nơi tôi nhận được cải thiện hiệu suất này?

Tôi đoán rằng nơi duy nhất có thể bị ảnh hưởng trong hai vòng riêng biệt là nó tăng i và kiểm tra nếu tôi < 1000000000 2 tỷ lần so với chỉ 1 tỷ lần nếu tôi hợp nhất các vòng với nhau. Có gì khác đang diễn ra trong đó không?

Cảm ơn!

Answer 1

Nếu bạn không chạy một giai đoạn khởi động, có thể là vòng lặp đầu tiên được tối ưu hóa và biên dịch nhưng không phải là thứ hai, trong khi khi bạn hợp nhất chúng, toàn bộ vòng lặp được hợp nhất sẽ được biên dịch. Ngoài ra, sử dụng tùy chọn server và mã của bạn, hầu hết được tối ưu hóa khi bạn không sử dụng kết quả.

Tôi đã chạy thử nghiệm dưới đây, đặt mỗi vòng lặp cũng như vòng lặp được hợp nhất theo phương pháp riêng của chúng và khởi động JVM để đảm bảo mọi thứ được biên dịch.

Kết quả (tùy chọn JVM: -server -XX:+PrintCompilation):

• vòng 1 = 500ms
• vòng 2 = 900 ms
• sáp nhập loop = 1.300 ms

Vì vậy, các vòng lặp sáp nhập là hơi nhanh hơn, nhưng không nhiều.

public static void main(String[] args) throws InterruptedException { 

    for (int i = 0; i < 3; i++) { 
     loop1(); 
     loop2(); 
     loopBoth(); 
    } 

    long start = System.nanoTime(); 

    loop1(); 

    long end = System.nanoTime(); 
    System.out.println((end - start)/1000000); 

    start = System.nanoTime(); 
    loop2(); 
    end = System.nanoTime(); 
    System.out.println((end - start)/1000000); 

    start = System.nanoTime(); 
    loopBoth(); 
    end = System.nanoTime(); 
    System.out.println((end - start)/1000000); 
} 

public static void loop1() { 
    int a = 188, aMax = 0; 
    for (int i = 0; i < 1000000000; i++) { 
     int t = a^i; 
     if (t > aMax) { 
      aMax = t; 
     } 
    } 
    System.out.println(aMax); 
} 

public static void loop2() { 
    int b = 144, bMax = 0; 
    for (int i = 0; i < 1000000000; i++) { 
     int t = b^i; 
     if (t > bMax) { 
      bMax = t; 
     } 
    } 
    System.out.println(bMax); 
} 

public static void loopBoth() { 
    int a = 188, b = 144, aMax = 0, bMax = 0; 

    for (int i = 0; i < 1000000000; i++) { 
     int t = a^i; 
     if (t > aMax) { 
      aMax = t; 
     } 
     int u = b^i; 
     if (u > bMax) { 
      bMax = u; 
     } 
    } 
    System.out.println(aMax); 
    System.out.println(bMax); 
} 

Answer 2

Dường như với tôi rằng trong trường hợp của một vòng lặp duy nhất lựa chọn JIT thể làm loop unrolling và kết quả là việc thực hiện được tốt hơn một chút

Answer 3

bạn đã sử dụng -server? Nếu không, bạn nên - JIT của khách hàng không thể dự đoán được, cũng không tốt. Nếu bạn thực sự quan tâm đến chính xác những gì đang xảy ra, bạn có thể sử dụng UnlockDiagnostic + LogCompilation để kiểm tra những gì tối ưu hóa đang được áp dụng trong cả hai trường hợp (tất cả các con đường xuống đến lắp ráp được tạo ra). Ngoài ra, từ mã bạn đã cung cấp, tôi không thể xem liệu bạn có làm nóng hay không, cho dù bạn chạy thử nghiệm một lần hay nhiều lần cho cùng một JVM, cho dù bạn đã thực hiện một vài lần chạy (các JVM khác nhau) chưa. Cho dù bạn đang tính đến tốt nhất, trung bình hay thời gian trung bình, bạn có ném ra các ngoại lệ?

Dưới đây là một liên kết tốt về chủ đề của văn bản Java vi tiêu chuẩn: http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html

Edit: Một mẹo microbenchmarking hơn, hãy cẩn thận của on-the-stack thay thế: http://www.azulsystems.com/blog/cliff/2011-11-22-what-the-heck-is-osr-and-why-is-it-bad-or-good

Answer 4

Trong ngắn hạn, CPU có thể thực hiện các hướng dẫn trong vòng lặp được hợp nhất song song, hiệu suất gấp đôi.

Vòng lặp thứ hai cũng có thể không được tối ưu hóa hiệu quả. Điều này là do vòng lặp đầu tiên sẽ kích hoạt toàn bộ phương thức được biên dịch và vòng lặp thứ hai sẽ được biên dịch mà không có bất kỳ số liệu nào có thể làm mất thời gian của vòng lặp thứ hai. Tôi sẽ đặt mỗi vòng lặp trong một phương pháp riêng biệt để đảm bảo rằng đây không phải là trường hợp.

CPU có thể thực hiện một số lượng lớn hoạt động độc lập song song (depth 10 on Pentium III and 20 in the Xeon). Một hoạt động mà nó cố gắng làm song song là một chi nhánh, sử dụng dự đoán nhánh, nhưng nếu nó không thực hiện cùng một nhánh gần như mọi lần.

tôi nghi ngờ với vòng lặp unrolling vòng lặp của bạn trông giống như sau (có thể hơn unrolling vòng lặp trong trường hợp này)

for (int i = 0; i < 1000000000; i += 2) { 
    // this first block is run almost in parallel 
    int t1 = a^i; 
    int t2 = b^i; 
    int t3 = a^(i+1); 
    int t4 = b^(i+1); 
    // this block run in parallel 
    if (t1 > aMax) aMax = t1;  
    if (t2 > bMax) bMax = t2;  
    if (t3 > aMax) aMax = t3;  
    if (t4 > bMax) bMax = t4;  
}