Vòng unrolling & tối ưu hóa

Question

Với mã:

for (int i = 0; i < n; ++i) 
{ 
    A(i) ; 
    B(i) ; 
    C(i) ; 
} 

Và phiên bản tối ưu hóa:

for (int i = 0; i < (n - 2); i+=3) 
{ 
    A(i) 
    A(i+1) 
    A(i+2) 
    B(i) 
    B(i+1) 
    B(i+2) 
    C(i) 
    C(i+1) 
    C(i+2) 
} 

Cái gì là không rõ ràng với tôi: đó là tốt hơn? Tôi không thể thấy bất cứ thứ gì hoạt động nhanh hơn bằng phiên bản khác. Am i thiếu cái gì ở đây ?

Tất cả tôi thấy là mỗi hướng dẫn là tùy thuộc vào hướng dẫn trước, có nghĩa là tôi cần phải chờ mà các hướng dẫn trước sẽ kết thúc để bắt đầu một sau khi ...

Cảm ơn

Answer 1

Ở chế độ xem cấp cao của ngôn ngữ, bạn sẽ không thấy tối ưu hóa. Việc tăng tốc độ đến từ những gì trình biên dịch làm với những gì bạn có.

Trong trường hợp đầu tiên, đó là một cái gì đó như:

LOCATION_FLAG; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

Trong thứ hai đó là một cái gì đó như:

LOCATION_FLAG; 
DO_SOMETHING; 
DO_SOMETHING; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

Bạn có thể thấy trong trường hợp thứ hai, chi phí xét nghiệm và nhảy duy nhất là 1 lệnh cho mỗi 3. Đầu tiên là 1 lệnh cho mỗi 1; vì vậy nó xảy ra thường xuyên hơn rất nhiều. Vì vậy, nếu bạn có bất biến, bạn có thể dựa vào (một mảng mod 3, để sử dụng ví dụ của bạn) thì nó hiệu quả hơn để giải phóng vòng lặp vì lắp ráp bên dưới được viết trực tiếp hơn.

Answer 2

Vâng, cho dù mã này là "tốt hơn" hoặc "tồi tệ" hoàn toàn phụ thuộc vào việc triển khai của A, B và C, giá trị của n bạn mong đợi, trình biên dịch bạn đang sử dụng và phần cứng nào bạn đang chạy.

Thông thường lợi ích của việc bỏ vòng lặp là chi phí thực hiện vòng lặp (tức là tăng i và so sánh nó với n) bị giảm. Trong trường hợp này, có thể được giảm theo hệ số 3.

Answer 3

Việc bỏ vòng lặp được sử dụng để giảm số bước nhảy & hướng dẫn chi nhánh có khả năng làm cho vòng lặp nhanh hơn nhưng sẽ làm tăng kích thước của tệp nhị phân. Tùy thuộc vào việc triển khai và nền tảng, có thể nhanh hơn.

Answer 4

Miễn là các hàm A(), B() và C() không sửa đổi cùng một tập dữ liệu, câu thứ hai cung cấp nhiều tùy chọn song song hơn.

Trong phiên bản đầu tiên, ba hàm có thể chạy đồng thời, giả sử không có sự phụ thuộc lẫn nhau. Trong phiên bản thứ hai, tất cả ba chức năng có thể được chạy với cả ba bộ dữ liệu cùng một lúc, giả sử bạn có đủ các đơn vị thực hiện để làm như vậy và một lần nữa, không có sự phụ thuộc lẫn nhau.

Answer 5

Nói chung không phải là một ý tưởng tốt để cố gắng "sáng tạo" tối ưu hóa, trừ khi bạn có bằng chứng khó khăn rằng bạn sẽ tăng, bởi vì nhiều lần bạn có thể sẽ đưa ra một sự xuống cấp. Thông thường cách tốt nhất để có được bằng chứng như vậy là với một trình bày tốt. Tôi sẽ kiểm tra cả hai phiên bản của mã này với một hồ sơ để xem sự khác biệt.

Ngoài ra, nhiều lần lặp unrolling isnt rất protable, như đã đề cập trước đó, nó phụ thuộc nhiều vào nền tảng, trình biên dịch vv

Bạn bổ sung có thể chơi với các tùy chọn trình biên dịch. Một tùy chọn gcc thú vị là "-floop-optimization", bạn sẽ tự động nhận được với trình biên dịch "-O, -O2, -O3 và -Os"

EDIT Ngoài ra, hãy xem trình biên dịch "-funroll-loops" Tùy chọn.