C++ lặp & tối ưu hóa vòng lặp

Question

Tôi nhìn thấy rất nhiều C++ mã mà trông như thế này:

for(const_iterator it = list.begin(), 
    const_iterator ite = list.end(); 
    it != ite; ++it) 

Trái ngược với phiên bản ngắn gọn hơn:

for(const_iterator it = list.begin(); 
    it != list.end(); ++it) 

Sẽ có bất kỳ sự khác biệt về tốc độ giữa hai công ước này? Naively đầu tiên sẽ hơi nhanh hơn kể từ list.end() chỉ được gọi một lần. Nhưng kể từ khi iterator là const, nó có vẻ như trình biên dịch sẽ kéo thử nghiệm này ra khỏi vòng lặp, tạo ra lắp ráp tương đương cho cả hai.

Answer 1

tôi sẽ chỉ đề cập đến cho các hồ sơ mà C++ nhiệm vụ tiêu chuẩn mà gọi begin() và end() trên bất kỳ loại container (có thể là vector, list, map vv) phải chỉ hằng số thời gian. Trong thực tế, các cuộc gọi này gần như chắc chắn sẽ được đưa vào một so sánh con trỏ duy nhất nếu bạn biên dịch với các tối ưu hóa được bật. Lưu ý rằng bảo lãnh này không nhất thiết phải giữ thêm các "container" do nhà cung cấp cung cấp mà không thực sự tuân thủ các yêu cầu chính thức là một container được đưa ra trong chương 23 của tiêu chuẩn (ví dụ: danh sách được liên kết đơn slist) .

Answer 2

Đầu tiên có thể sẽ luôn nhanh hơn, nhưng nếu bạn nghĩ điều này sẽ tạo sự khác biệt, luôn luôn cấu hình trước tiên để xem nhanh hơn và bao nhiêu.

Trình biên dịch có lẽ sẽ có thể nội tuyến cuộc gọi đến end() trong cả hai trường hợp, mặc dù nếu end() đủ phức tạp, nó có thể chọn không đặt nội tuyến nó. Tuy nhiên, tối ưu hóa chính là liệu trình biên dịch có thể thực hiện loop-invariant code motion hay không. Tôi sẽ đặt ra rằng trong hầu hết các trường hợp, trình biên dịch không thể chắc chắn rằng giá trị của end() sẽ không thay đổi trong vòng lặp của vòng lặp, trong trường hợp đó nó không có lựa chọn nào khác ngoài gọi end() sau mỗi lần lặp.

Answer 3

Tôi sẽ chọn tùy chọn súc tích và dễ đọc nhất. Đừng cố gắng để đoán thứ hai trình biên dịch và tối ưu hóa nó có thể thực hiện. Hãy nhớ rằng phần lớn mã của bạn sẽ hoàn toàn không ảnh hưởng đến hiệu suất tổng thể, do đó, chỉ khi điều này nằm trong phần hiệu suất quan trọng của mã, bạn nên dành thời gian để lập hồ sơ và chọn một đại diện nguồn hiệu quả phù hợp.

Với tham chiếu cụ thể về ví dụ của bạn, phiên bản đầu tiên tạo sao chép của trình lặp vòng end(), gọi bất kỳ mã nào chạy cho hàm tạo bản sao của đối tượng trình lặp. Các container STL thường chứa các hàm nội tuyến end(), do đó trình biên dịch có nhiều cơ hội để tối ưu hóa phiên bản thứ hai ngay cả khi bạn không cố gắng trợ giúp nó. Cái nào là tốt nhất? Đo chúng.

Answer 4

Về lý thuyết, trình biên dịch có thể tối ưu hóa phiên bản thứ hai vào phiên bản đầu tiên (giả sử rằng vùng chứa không thay đổi trong vòng lặp, rõ ràng).

Trong thực tế, tôi đã tìm thấy một số trường hợp tương tự khi lập hồ sơ mã thời gian quan trọng mà trình biên dịch của tôi đã hoàn toàn thất bại trong việc hoist tính toán bất biến trong điều kiện vòng lặp. Vì vậy, trong khi phiên bản ngắn gọn hơn một chút là tốt trong hầu hết trường hợp, tôi không dựa vào trình biên dịch làm những điều hợp lý với nó cho một trường hợp mà tôi thực sự quan tâm đến hiệu suất.

Answer 5

Bạn có thể làm cho phiên bản đầu tiên ngắn gọn hơn và tận dụng tốt nhất của cả hai:

for(const_iterator it = list.begin(), ite = list.end(); 
    it != ite; ++it) 

T.B. Các trình vòng lặp không phải là const, chúng là các trình vòng lặp tới một tham chiếu const. Có một sự khác biệt lớn.

Answer 6

Hai phiên bản không giống nhau. Trong phiên bản thứ hai, nó so sánh biến lặp với list.end() mọi lúc và những gì list.end() đánh giá có thể thay đổi trong suốt vòng lặp. Bây giờ tất nhiên, bạn không thể sửa đổi list thông qua const_iterator it; nhưng không có gì ngăn chặn mã bên trong vòng lặp từ các phương thức gọi trực tiếp trên list trực tiếp và biến đổi nó, có thể (tùy thuộc vào loại cấu trúc dữ liệu list là) thay đổi trình lặp kết thúc.Do đó, nó có thể không chính xác trong một số trường hợp để lưu trữ trình lặp kết thúc trước, bởi vì điều đó có thể không còn là trình lặp kết thúc đúng theo thời gian bạn nhận được nó.

Answer 7

Tôi luôn ưu tiên cái đầu tiên. Mặc dù với chức năng nội tuyến, tối ưu hóa trình biên dịch và kích thước container tương đối nhỏ hơn (trong trường hợp của tôi nó thường là tối đa 20-25 mục) nó thực sự không tạo ra bất kỳ sự khác biệt lớn nào về hiệu suất.

const_iterator it = list.begin(); 
const_iterator endIt = list.end(); 

for(; it != endIt ; ++it) 
{//do something 
} 

Nhưng gần đây tôi đang sử dụng nhiều hơn std::for_each bất cứ nơi nào có thể. Vòng lặp tối ưu hóa của nó giúp làm cho mã trông dễ đọc hơn hai loại khác.

std::for_each(list.begin(), list.end(), Functor()); 

Tôi sẽ chỉ sử dụng vòng lặp khi không thể sử dụng vòng lặp std::for_each. (ví dụ: std::for_each không cho phép bạn ngắt vòng trừ khi ngoại lệ được ném).

Answer 8

Aah, mọi người dường như đang dự đoán. Mở mã của bạn trong trình gỡ rối & bạn sẽ thấy rằng các cuộc gọi để bắt đầu(), kết thúc() vv mọi thứ được tối ưu hóa. Không cần phải sử dụng phiên bản 1. Thử nghiệm với trình biên dịch Visual C++ fullopt.

Answer 9

Hãy xem xét ví dụ sau:

for (const_iterator it = list.begin(); it != list.end(); ++list) 
{ 
    if (moonFull()) 
     it = insert_stuff(list); 
    else 
     it = erase_stuff(list); 
} 

trong trường hợp này, bạn cần phải gọi list.end() trong vòng lặp, và trình biên dịch sẽ không tối ưu hóa mà đi.

Các trường hợp khác mà trình biên dịch có thể chứng minh rằng kết thúc() luôn trả về cùng một giá trị, tối ưu hóa có thể diễn ra.

Nếu chúng ta đang nói về STL container, hơn tôi nghĩ rằng bất kỳ trình biên dịch tốt có thể tối ưu hóa nhiều kết thúc() cuộc gọi khi nhiều cuộc gọi end() là không cần thiết cho logic lập trình. Tuy nhiên, nếu bạn có vùng chứa tùy chỉnh và việc triển khai kết thúc() không thuộc cùng một đơn vị dịch, thì việc tối ưu hóa sẽ phải xảy ra tại thời gian liên kết. Tôi biết rất ít về tối ưu hóa thời gian liên kết, nhưng tôi sẽ đặt cược hầu hết các liên kết sẽ không thực hiện tối ưu hóa như vậy.

Answer 10

1. Lấy mẫu trong điều kiện căng thẳng và xem bạn có đang ở ** mã này thường xuyên ***.
   Nếu không, nó không quan trọng.

2. Nếu bạn đang có, hãy xem xét việc tháo gỡ hoặc thực hiện một bước.
   Đó là cách bạn có thể biết cái nào nhanh hơn.

Bạn phải cẩn thận với những người lặp này.
Chúng có thể được tối ưu hóa thành mã máy đẹp, nhưng thường là chúng không đủ, và trở thành heo con thời gian.

** (Nơi "trong" nghĩa thực sự trong đó, hoặc được gọi từ nó.)

*** (Nơi "thường" có nghĩa là một tỷ lệ đáng kể thời gian.)

thêm: Không chỉ xem bao nhiêu lần mỗi giây mã được thực hiện. Nó có thể là 1.000 lần một giây và vẫn sử dụng ít hơn 1% thời gian.

Cũng đừng mất thời gian. Có thể mất một phần nghìn giây và vẫn sử dụng ít hơn 1% thời gian.

Bạn có thể nhân hai, để có ý tưởng tốt hơn, nhưng điều đó chỉ hoạt động nếu chúng không quá sai lệch.

Sampling the call stack sẽ cho bạn biết nếu nó sử dụng một tỷ lệ phần trăm thời gian đủ cao cho vấn đề.

Answer 11

Trình biên dịch có thể tối ưu hóa giá trị thứ hai thành giá trị đầu tiên, nhưng giả định rằng hai giá trị này tương đương, tức là kết thúc() thực sự là không đổi. Một vấn đề có vấn đề hơn một chút là trình biên dịch có thể không thể suy ra rằng trình lặp kết thúc là hằng số do có thể có răng cưa. Tuy nhiên, giả sử rằng lời gọi kết thúc() được gạch chân, sự khác biệt chỉ là tải bộ nhớ.

Lưu ý rằng điều này giả định rằng trình tối ưu hóa được bật. Nếu trình tối ưu hóa không được kích hoạt, như thường được thực hiện trong các bản dựng gỡ lỗi, thì công thức thứ hai sẽ liên quan đến các cuộc gọi hàm N-1. Trong các phiên bản hiện tại của Visual C++, các bản dựng gỡ lỗi cũng sẽ phát sinh các lần truy cập bổ sung do chức năng kiểm tra prolog/epilog và các trình lặp gỡ lỗi nặng hơn. Vì vậy, trong mã nặng STL, mặc định cho trường hợp đầu tiên có thể ngăn chặn mã không bị chậm tương đối trong các bản dựng gỡ lỗi.

Chèn và loại bỏ trong vòng lặp là một khả năng, như những người khác đã chỉ ra, nhưng với kiểu vòng lặp này, tôi thấy khó xảy ra. Đối với một điều, các thùng chứa dựa trên nút - danh sách, tập hợp, ánh xạ - không làm mất hiệu lực kết thúc() trên một trong hai thao tác. Thứ hai, tăng iterator thường xuyên đã được di chuyển trong vòng lặp để tránh các vấn đề huỷ bỏ hiệu lực:

 
    // assuming list -- cannot cache end() for vector 
    iterator it(c.begin()), end(c.end()); 
    while(it != end) { 
     if (should_remove(*it)) 
      it = c.erase(it); 
     else 
      ++it; 
    }

Vì vậy, tôi xem xét một vòng lặp mà tuyên bố để gọi end() vì lý do đột biến-trong-loop và vẫn có ++ nó trong tiêu đề vòng lặp để nghi ngờ.