Khi nào, nếu bao giờ, việc bỏ vòng lặp vẫn hữu ích?

Question

Tôi đã cố gắng tối ưu hóa một số mã cực kỳ hiệu suất cực kỳ quan trọng (một thuật toán sắp xếp nhanh được gọi là hàng triệu và hàng triệu lần bên trong mô phỏng monte carlo) bằng cách bỏ vòng lặp. Dưới đây là vòng lặp bên trong tôi đang cố gắng để tăng tốc độ:

// Search for elements to swap. 
while(myArray[++index1] < pivot) {} 
while(pivot < myArray[--index2]) {} 

tôi đã cố gắng để unrolling cái gì đó như:

while(true) { 
    if(myArray[++index1] < pivot) break; 
    if(myArray[++index1] < pivot) break; 
    // More unrolling 
} 


while(true) { 
    if(pivot < myArray[--index2]) break; 
    if(pivot < myArray[--index2]) break; 
    // More unrolling 
} 

Điều này làm hoàn toàn không có sự khác biệt vì vậy tôi đã thay đổi nó trở lại dưới hình thức dễ đọc hơn. Tôi đã có những trải nghiệm tương tự vào những lúc khác tôi đã cố gắng bỏ vòng lặp. Với chất lượng của các yếu tố dự báo chi nhánh trên phần cứng hiện đại, khi nào, nếu có, thì việc bỏ vòng lặp vẫn là một tối ưu hóa hữu ích?

Answer 1

Ghi vòng lặp có ý nghĩa nếu bạn có thể phá vỡ chuỗi phụ thuộc. Điều này tạo ra một CPU không theo thứ tự hoặc siêu vô hướng khả năng lên lịch cho mọi thứ tốt hơn và do đó chạy nhanh hơn.

Một ví dụ đơn giản:

for (int i=0; i<n; i++) 
{ 
    sum += data[i]; 
} 

Đây là chuỗi sự phụ thuộc của các đối số là rất ngắn. Nếu bạn nhận được một gian hàng bởi vì bạn có một bộ nhớ cache-bỏ lỡ trên mảng dữ liệu CPU không thể làm bất cứ điều gì, nhưng để chờ đợi.

Mặt khác mã này:

for (int i=0; i<n; i+=4) 
{ 
    sum1 += data[i+0]; 
    sum2 += data[i+1]; 
    sum3 += data[i+2]; 
    sum4 += data[i+3]; 
} 
sum = sum1 + sum2 + sum3 + sum4; 

có thể chạy nhanh hơn. Nếu bạn nhận được một bộ nhớ cache bỏ lỡ hoặc gian hàng khác trong một tính toán vẫn còn có ba chuỗi phụ thuộc khác mà không phụ thuộc vào gian hàng. Một CPU có thể thực hiện các lệnh này.

Answer 2

Những điều đó sẽ không tạo ra bất kỳ sự khác biệt nào vì bạn đang thực hiện cùng một số so sánh. Đây là một ví dụ tốt hơn. Thay vì:

for (int i=0; i<200; i++) { 
    doStuff(); 
} 

viết:

for (int i=0; i<50; i++) { 
    doStuff(); 
    doStuff(); 
    doStuff(); 
    doStuff(); 
} 

Thậm chí sau đó nó gần như chắc chắn sẽ không thành vấn đề nhưng bây giờ bạn đang làm 50 so sánh thay vì 200 (tưởng tượng so sánh là phức tạp hơn).

Hướng dẫn sử dụng Việc bỏ vòng lặp nói chung phần lớn là một tạo phẩm lịch sử. Đó là một danh sách ngày càng tăng của những thứ mà một trình biên dịch tốt sẽ làm cho bạn khi nó quan trọng. Ví dụ: hầu hết mọi người không bận tâm viết x << 1 hoặc x += x thay vì x *= 2. Bạn chỉ cần viết x *= 2 và trình biên dịch sẽ tối ưu hóa nó cho bạn bất cứ điều gì là tốt nhất.

Về cơ bản, càng ít cần phải đoán trước trình biên dịch của bạn.

Answer 3

Ghi vòng lặp hoàn toàn phụ thuộc vào kích thước sự cố của bạn. Nó hoàn toàn phụ thuộc vào thuật toán của bạn có thể giảm kích thước thành các nhóm nhỏ hơn của công việc. Những gì bạn đã làm ở trên không giống như vậy. Tôi không chắc chắn nếu một mô phỏng Monte Carlo có thể được unrolled.

Kịch bản tốt cho việc bỏ vòng lặp sẽ xoay hình ảnh. Vì bạn có thể xoay các nhóm công việc riêng biệt. Để làm được điều này, bạn sẽ phải giảm số lần lặp lại.

Answer 4

Bất kể dự đoán nhánh nào trên phần cứng hiện đại, hầu hết các trình biên dịch đều thực hiện việc bỏ vòng lặp cho bạn.

Nó sẽ là đáng giá để tìm ra bao nhiêu tối ưu hóa trình biên dịch của bạn làm cho bạn.

Tôi tìm thấy Felix von Leitner's presentation rất khai sáng về chủ đề này. Tôi khuyên bạn nên đọc nó. Tóm tắt: Trình biên dịch hiện đại rất thông minh, vì vậy việc tối ưu hóa bằng tay hầu như không bao giờ hiệu quả.

Answer 5

Việc bỏ vòng lặp vẫn hữu ích nếu có nhiều biến cục bộ cả trong và với vòng lặp. Để sử dụng lại những thanh ghi đó thay vì lưu một thanh ghi cho chỉ mục vòng lặp.

Trong ví dụ của bạn, bạn sử dụng số lượng nhỏ các biến cục bộ, không sử dụng quá mức thanh ghi.

So sánh (đến cuối vòng lặp) cũng là một hạn chế lớn nếu so sánh là nặng (tức là không test hướng dẫn), đặc biệt nếu nó phụ thuộc vào chức năng bên ngoài.

Việc bỏ vòng lặp giúp tăng nhận thức của CPU về dự đoán chi nhánh, tuy nhiên, điều đó cũng xảy ra.

Answer 6

Theo như tôi hiểu nó, trình biên dịch hiện đại đã cuộn vòng nơi thích hợp - một ví dụ là gcc, nếu được thông qua các cờ tối ưu hóa nó hướng dẫn cho biết họ sẽ:

cuộn vòng số có của lặp có thể được xác định tại thời gian biên dịch hoặc khi truy cập vào vòng lặp .

Vì vậy, trên thực tế, có khả năng trình biên dịch của bạn sẽ thực hiện các trường hợp nhỏ nhặt cho bạn. Đó là vào bạn do đó để đảm bảo rằng càng nhiều càng tốt của các vòng của bạn là dễ dàng cho trình biên dịch để xác định bao nhiêu lần lặp sẽ là cần thiết.

Answer 7

Dò vòng lặp, cho dù là mở khóa tay hay không biên dịch, thường có thể phản tác dụng, đặc biệt với các CPU x86 gần đây (Core 2, Core i7). Tóm lại: chuẩn mã của bạn có và không có vòng lặp unrolling trên bất cứ CPU nào bạn định triển khai mã này.

Answer 8

Cố gắng mà không biết không phải là cách để làm điều đó.
Loại này có chiếm tỷ lệ cao trong tổng thời gian không?

Tất cả việc bỏ vòng lặp không làm giảm chi phí vòng lặp của tăng/giảm, so sánh với điều kiện dừng và nhảy. Nếu những gì bạn đang làm trong vòng lặp mất nhiều chu kỳ chỉ dẫn hơn bản thân vòng lặp, bạn sẽ không thấy nhiều cải thiện về tỷ lệ phần trăm.

Here's an example of how to get maximum performance.

Answer 9

Ghi vòng lặp có thể hữu ích trong trường hợp cụ thể. Lợi ích duy nhất không bỏ qua một số bài kiểm tra! Bạn có thể ngạc nhiên thực sự hữu ích như thế nào (bạn có thể dễ dàng nhận được 10% tăng tốc trên hầu hết các vòng thậm chí với -O3) bằng cách tích cực unrolling.

Như đã nói trước đó, nó phụ thuộc rất nhiều vào vòng lặp và trình biên dịch và thử nghiệm là cần thiết. Thật khó để thực hiện một quy tắc (hoặc trình biên dịch heuristic cho unrolling sẽ là hoàn hảo)