Hiệu suất của tan rã một vòng thành hai vòng

Question

Good Day,

Giả sử rằng bạn có một đơn giản cho vòng lặp như dưới đây ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
    //statement 2 
} 

Giả định rằng tuyên bố 1 và tuyên bố 2 là O (1). Bên cạnh các chi phí nhỏ của "bắt đầu" vòng lặp khác, sẽ phá vỡ mà cho vòng lặp thành hai (không lồng nhau, nhưng tuần tự) vòng được như nhau nhanh chóng? Ví dụ:

for(int i=0;i<10;i++) 
{ 
    //statement 1 
} 
for(int i=0;i<10;i++) 
{ 
    //statement 2 
} 

Tại sao tôi hỏi một câu hỏi ngớ ngẩn là tôi có hệ thống phát hiện va chạm (CDS) phải lặp qua tất cả các đối tượng. Tôi muốn "compartmentalize" chức năng của hệ thống CDS của tôi để tôi có thể chỉ cần gọi

cds.update(objectlist); 

thay vì phải phá vỡ hệ thống CD của tôi. (Đừng lo lắng quá nhiều về việc thực hiện CDS của tôi ... Tôi nghĩ mình biết mình đang làm gì, tôi không biết giải thích nó như thế nào, những gì tôi thực sự cần biết là nếu tôi thực hiện một hit hiệu suất lớn để lặp lại thông qua tất cả các đối tượng của tôi một lần nữa .

Answer 1

Tùy thuộc vào đơn đăng ký của bạn.

thể Nhược điểm (tách):

• dữ liệu của bạn không phù hợp với bộ nhớ cache dữ liệu L1, do đó bạn tải nó một lần cho vòng đầu tiên và sau đó tải lại nó cho vòng lặp thứ hai

Lãi thể (tách):

• vòng lặp tiếp của bạn ains nhiều biến, chia nhỏ giúp giảm bớt áp lực đăng ký/ngăn xếp và trình tối ưu hóa biến nó thành mã máy tốt hơn
• các chức năng bạn sử dụng thùng rác bộ nhớ cache L1 để bộ nhớ cache được tải trên mỗi lần lặp lại, trong khi chia tách bạn quản lý (chỉ) tại phiên đầu tiên của mỗi vòng lặp

những danh sách này chắc chắn không phải toàn diện, nhưng đã có thể cảm nhận được rằng có một sự căng thẳng giữa đang và dữ liệu. Vì vậy, rất khó cho chúng tôi để có một giáo dục/một đoán hoang dã khi chúng ta biết không.

Nghi ngờ: tiểu sử. Sử dụng callgrind, kiểm tra cache trong mỗi trường hợp, kiểm tra số lượng các lệnh được thực hiện. Đo thời gian.

Answer 2

theo như lớn-o phức tạp là có liên quan, điều này không tạo sự khác biệt nếu 1 vòng lặp là O (n), thì như vậy là giải pháp 2 vòng lặp.
như Về chi phí của một vòng lặp là khá nhỏ, chúng tôi không biết chi phí truy cập các đối tượng của bạn là gì (nếu chúng ở trong một vector, thì nó cũng khá nhỏ) , nhưng có rất nhiều điều cần cân nhắc để cung cấp câu trả lời hữu ích.

Answer 3

Bạn đang ghi chú chính xác rằng sẽ có một số chi phí hiệu năng bằng cách tạo vòng lặp thứ hai. Do đó, nó không thể "nhanh như nhau"; như chi phí này, trong khi nhỏ, vẫn còn trên cao. Tôi sẽ không cố gắng nói một cách thông minh về cách xây dựng hệ thống va chạm, nhưng nếu bạn đang cố gắng tối ưu hóa hiệu suất tốt hơn là tránh xây dựng cấu trúc điều khiển không cần thiết nếu bạn có thể quản lý nó mà không cần kéo tóc ra.

Hãy nhớ rằng tối ưu hóa sớm là một trong những điều tồi tệ nhất bạn có thể làm. Lo lắng về tối ưu hóa khi bạn có một vấn đề hiệu suất, theo ý kiến ​​của tôi.

Answer 4

Về mặt phức tạp thuật toán, chia tách các vòng không tạo ra sự khác biệt.

Xét về hiệu suất thế giới thực, các vòng lặp có thể cải thiện hiệu suất, làm xấu đi hiệu suất hoặc không có sự khác biệt - nó phụ thuộc vào hệ điều hành, phần cứng và - tất nhiên - những gì statement 1 và statement 2.

Answer 5

Với hai vòng, bạn sẽ được trả tiền cho:

• tăng kích thước mã được tạo
• 2x càng nhiều chi nhánh dự đoán
• tùy theo những gì bố trí dữ liệu của câu 1 và 2 được bạn có thể tải lại dữ liệu vào bộ nhớ cache.

Điểm cuối cùng có thể có tác động lớn trong cả hai hướng. Bạn nên đo lường như với bất kỳ tối ưu hóa perf.

Answer 6

Như đã lưu ý, sự phức tạp vẫn còn.

Nhưng trong thế giới thực, chúng tôi không thể dự đoán phiên bản nào chạy nhanh hơn. Sau đây là những yếu tố có vai trò, những người khổng lồ:

• bộ nhớ đệm dữ liệu
• Chỉ thị bộ nhớ đệm
• thực hiện đầu cơ
• dự đoán chi nhánh
• Chi nhánh mục tiêu đệm
• Số lượng đăng ký có sẵn trên CPU
• Kích thước bộ nhớ cache

(lưu ý: trên tất cả chúng, có thanh kiếm giả mạo Damocles; tất cả đều có thể xóa được và googlable)

Đặc biệt là yếu tố cuối cùng khiến đôi khi không thể biên dịch mã thực sự cho mã có hiệu suất dựa trên kích thước bộ nhớ cache cụ thể. Một số ứng dụng sẽ chạy nhanh hơn trên CPU với bộ đệm lớn, trong khi chạy chậm hơn trên bộ nhớ cache nhỏ và đối với một số ứng dụng khác, nó sẽ ngược lại.

Giải pháp:

• Hãy trình biên dịch của bạn thực hiện công việc chuyển đổi vòng lặp. Hiện đại g ++ là khá tốt trong kỷ luật đó. Một kỷ luật khác mà g ++ là tốt là vectorization tự động. Lưu ý rằng các trình biên dịch biết nhiều hơn về kiến ​​trúc máy tính hơn hầu hết mọi người.
• Gửi các tệp nhị phân khác nhau và người điều phối.
• Sử dụng cache-oblivious data structures/layouts and algorithms để điều chỉnh bộ nhớ cache mục tiêu.

Luôn luôn là một ý tưởng tốt để nỗ lực cho phần mềm thích nghi với mục tiêu, lý tưởng mà không phải hy sinh chất lượng mã. Và trước khi thực hiện tối ưu hóa thủ công, hoặc là vi mô hoặc vĩ mô, đo lường thế giới thực chạy, sau đó và chỉ sau đó tối ưu hóa.

Văn học: * Agner Fog's Guides * Intel's Guides