Làm thế nào để tối ưu hóa các trình biên dịch quyết định khi nào và bao nhiêu để bỏ vòng lặp?

Question

Khi trình biên dịch thực hiện tối ưu hóa vòng lặp bỏ vòng lặp, làm cách nào để xác định yếu tố nào để hủy vòng lặp hoặc có hủy bỏ toàn bộ vòng lặp không? Vì đây là một sự cân bằng hiệu suất không gian, trung bình mức độ hiệu quả của kỹ thuật tối ưu hóa này trong việc làm cho chương trình hoạt động tốt hơn như thế nào? Ngoài ra, trong những điều kiện nào được khuyến khích sử dụng kỹ thuật này (tức là một số hoạt động hoặc tính toán nhất định)?

Điều này không nhất thiết phải cụ thể đối với một trình biên dịch nhất định. Nó có thể là bất kỳ giải thích phác thảo ý tưởng đằng sau kỹ thuật này và những gì đã được quan sát thấy trong thực tế.

Answer 1

Khi trình biên dịch thực hiện tối ưu hóa tuần hoàn vòng lặp, làm cách nào để xác định yếu tố nào để bỏ vòng lặp hoặc thời tiết để hủy bỏ toàn bộ vòng lặp hay không.

tiêu thụ ngăn xếp và địa phương. số lượng lệnh. khả năng tạo/tuyên truyền tối ưu hóa dựa trên chương trình chưa được kiểm soát và được sắp xếp. cho dù kích thước vòng lặp là cố định, hoặc dự kiến ​​sẽ ở trong một phạm vi nhất định. đầu vào hồ sơ (nếu có). các hoạt động có thể được loại bỏ khỏi thân vòng lặp. v.v.

Vì đây là sự cân bằng hiệu suất không gian trung bình mức độ hiệu quả của kỹ thuật tối ưu hóa này trong việc giúp chương trình hoạt động tốt hơn?

nó phụ thuộc phần lớn vào đầu vào (chương trình của bạn). nó có thể chậm hơn (không điển hình) hoặc nó có thể nhanh hơn vài lần. viết một chương trình để chạy tối ưu và cũng cho phép trình tối ưu hóa thực hiện công việc của mình là học được.

Ngoài ra, trong điều kiện nào là nó khuyến khích để sử dụng kỹ thuật này (tức là một số hoạt động hoặc tính toán)

thường, một số lượng lớn các lần lặp trên cơ thể rất nhỏ, đặc biệt rằng đó là cành và có vị trí dữ liệu tốt.

nếu bạn muốn biết tùy chọn này có giúp ứng dụng, tiểu sử của bạn hay không.

nếu bạn cần nhiều hơn thế, bạn nên dành một chút thời gian để tìm hiểu cách viết các chương trình tối ưu, vì chủ đề khá phức tạp.

Answer 2

khi nó là (theo ý kiến ​​của tôi) tốt để cuộn một vòng lặp:

vòng lặp là ngắn và có thể tất cả các biến được sử dụng là trong thanh ghi. Sau khi các biến unrolling là 'trùng lặp' nhưng vẫn còn trong sổ đăng ký vì vậy không có bộ nhớ (hoặc cache) hình phạt.

vòng lặp (với số vòng lặp unrool không xác định) sẽ được thực thi ít nhất vài hoặc vài lần, do đó, có lý do để tải toàn bộ vòng lặp đó không được lưu vào bộ nhớ cache lệnh.

nếu vòng lặp ngắn (một hoặc chỉ vài lần giới thiệu), nó có thể rất hữu ích cho việc kiểm tra vì mã để xác định xem nó có nên được thực hiện lại hay không được thực hiện ít thường xuyên hơn.

Answer 3

Phân tích đơn giản là để đếm hướng dẫn - một vòng lặp lệnh không được kiểm tra 10 lần có 11 hướng dẫn thay vì 20 sản lượng tăng tốc 11/20. Nhưng với kiến ​​trúc vi xử lý hiện đại thì phức tạp hơn nhiều; tùy thuộc vào kích thước bộ đệm và các đặc tính của đường dẫn hướng dẫn bộ vi xử lý. Có thể ví dụ trên sẽ chạy nhanh hơn 10x thay vì 2x. Cũng có thể việc bỏ 1000x thay vì 10x sẽ chạy chậm hơn. Nếu không nhắm vào một bộ xử lý cụ thể, các trình biên dịch (hoặc các pragmas bạn viết cho chúng) chỉ là đoán.

Answer 4

Ok, trước hết, tôi không biết cách trình biên dịch tự động thực hiện như thế nào. Và tôi khá chắc chắn có ít nhất 10s nếu không phải 100s thuật toán mà trình biên dịch phải chọn.
Và có thể là trình biên dịch cụ thể.

Nhưng, tôi có thể giúp bạn tính toán hiệu quả của nó.

Chỉ cần lưu ý rằng kỹ thuật này thường không mang đến cho bạn hiệu suất tuyệt vời.
Nhưng tính toán lặp lại lặp lại và có thể cho hiệu suất phần trăm cao.
Điều này là do thường là hàm bên trong vòng lặp mất nhiều thời gian tính toán hơn kiểm tra điều kiện của vòng lặp.

Vì vậy, cho phép nói rằng chúng ta có một vòng lặp đơn giản với một hằng số, vì bạn đã quá lười biếng để làm copy-paste hoặc chỉ nghĩ nó sẽ trông tốt hơn:

for (int i = 0; i < 5; i++) 
{ 
    DoSomething(); 
} 

Ở đây bạn có int so sánh , 5 số gia tăng và Cuộc gọi DoSomethig().
Vì vậy, nếu DoSomething() tương đối nhanh, thì chúng tôi có các hoạt động .
Bây giờ nếu bạn sẽ cuộn này, bạn sẽ giảm nó xuống chỉ còn 5 hoạt động:

DoSomething(); 
DoSomething(); 
DoSomething(); 
DoSomething(); 
DoSomething(); 

Bây giờ với các hằng số đó là dễ dàng hơn, vì vậy cho phép xem làm thế nào nó sẽ làm việc với một biến:

for (int i = 0; i < n; i++) 
{ 
    DoSomething(); 
} 

Ở đây bạn có n int so sánh, n incrementations, và n DoSomethig() gọi = 3n. Bây giờ, chúng ta không thể cuộn nó hoàn toàn, nhưng chúng ta có thể cuộn nó bằng một yếu tố không đổi (cao hơn n dự kiến ​​sẽ được, chúng ta càng nên cuộn nó):

int i; 
for (i = 0; i < n; i = i+3) 
{ 
    DoSomething(); 
    DoSomething(); 
    DoSomething(); 
} 
if (i - n == 2) 
{ 
    DoSomething(); // We passed n by to, so there's one more left 
} 
else if (i - n == 1) 
{ 
    DoSomething(); //We passed n by only 1, so there's two more left 
    DoSomething(); 
} 

Bây giờ đây chúng tôi có Ở đây bạn có n/3 + 2 int so sánh, n/3 incrementations, và n DoSomethig() gọi = (1 2/3) * n.
Chúng tôi đã lưu chính mình (1 1/3) * n hoạt động. Điều này làm giảm thời gian tính toán gần một nửa.

FYI, một kỹ thuật đánh dấu gọn gàng khác được gọi là Duff's device.
Nhưng đó là trình biên dịch và ngôn ngữ thực hiện cụ thể. Có những ngôn ngữ mà điều này sẽ thực sự tồi tệ hơn.