Hiệu suất của vector :: size(): nó có nhanh như đọc một biến không?

Question

Tôi đã tính toán rộng rãi trên một vectơ lớn các số nguyên. Kích thước vectơ không thay đổi trong quá trình tính toán. Kích thước của vector thường được truy cập bởi mã. Nói chung nhanh hơn là gì: sử dụng chức năng vector::size() hoặc sử dụng hằng số trợ giúp vectorSize để lưu trữ kích thước của véc-tơ? Tôi biết rằng trình biên dịch thường có thể nội tuyến chức năng size() khi thiết lập cờ trình biên dịch thích hợp, tuy nhiên, làm cho nội tuyến hàm là thứ mà trình biên dịch có thể làm nhưng không thể bị ép buộc.

Answer 1

Câu hỏi vui.

Vì vậy, điều gì sẽ xảy ra?Vâng, nếu bạn gỡ lỗi với gdb bạn sẽ thấy một cái gì đó giống như biến 3 thành viên (tên không chính xác):

• _M_begin: con trỏ đến phần tử đầu tiên của mảng động
• _M_end: con trỏ một quá khứ yếu tố cuối cùng của mảng động
• _M_capacity: con trỏ một quá khứ yếu tố cuối cùng có thể được lưu trữ trong mảng động

việc thực hiện vector<T,Alloc>::size() do đó thường giảm xuống còn:

return _M_end - _M_begin; // Note: _Mylast - _Myfirst in VC 2008 

Giờ đây, có 2 điều cần xem xét khi liên quan đến việc tối ưu hóa thực tế càng tốt:

• chức năng này sẽ được inlined? Có lẽ: Tôi không có nhà văn biên dịch, nhưng nó là một cược tốt kể từ khi chi phí của một cuộc gọi chức năng sẽ lùn thời gian thực tế ở đây và kể từ khi nó được templated chúng tôi có tất cả các mã có sẵn trong các đơn vị dịch
• kết quả sẽ được lưu trữ (ví dụ: loại có một biến địa phương giấu tên): nó cũng có thể được, nhưng bạn sẽ không biết trừ khi bạn tháo rời các mã được tạo

Nói cách khác:

• Nếu bạn lưu trữ các size mình, có là một cơ hội tốt, nó sẽ nhanh như trình biên dịch có thể nhận được ...
• nhưng bạn tiếp xúc với xác tàu bảo trì: nếu đột nhiên bạn sửa đổi vectơ và không cập nhật biến;)?

Dù sao đi chăng nữa, tôi thực sự nghi ngờ nó đáng giá. Đó là tối ưu hóa vi mô ở mức tốt nhất và không mang lại nhiều cải thiện.

Answer 2

Khi tôi hiểu đặc điểm kỹ thuật C++ năm 1998, vector<T>::size() mất thời gian không đổi, không phải thời gian tuyến tính. Vì vậy, câu hỏi này có thể tóm tắt cho dù đó là nhanh hơn để đọc một biến địa phương hơn gọi một chức năng mà rất ít công việc.

do đó tôi muốn khẳng định rằng lưu trữ của size() trong một biến địa phương sẽ tăng tốc độ chương trình của bạn bởi một lượng nhỏ, vì bạn sẽ chỉ gọi là chức năng (và do đó số lượng nhỏ liên tục của thời gian cần thiết để vector của bạn thực thi) một lần thay vì nhiều lần.

Answer 3

Trong mọi lần triển khai tôi đã thấy vector::size() thực hiện phép trừ end() và begin(), tức là không nhanh như đọc biến.

Khi triển khai véc tơ, người triển khai phải chọn lựa nhanh nhất, end() hoặc size(), tức là lưu số lượng phần tử được khởi tạo hoặc con trỏ/vòng lặp vào phần tử sau phần tử được khởi tạo lần cuối. Nói cách khác; lặp lại bằng cách sử dụng trình lặp.

Nếu bạn lo lắng về hiệu suất size(), hãy viết chỉ mục của bạn dựa trên vòng lặp như thế này;

for (size_t i = 0, i_end = container.size(); i < i_end; ++i){ 
// do something performance critical 
} 

Answer 4

Bạn có thể viết cho mình một hàm cho vòng lặp của bạn và gọi nó qua số std::for_each. Nó lặp lại cho bạn, và sau đó câu hỏi của bạn trở thành tranh luận. Tuy nhiên, bạn đang giới thiệu một cuộc gọi hàm (có thể hoặc có thể không nhận được nội tuyến) cho mỗi vòng lặp lặp lại, vì vậy bạn nên cấu hình tốt nhất nếu bạn không nhận được hiệu suất mà bạn mong đợi.

Answer 5

Hiệu suất của vector :: size(): là nó nhanh như đọc một biến?

Có thể là không.

Liệu nó có vấn đề

Có lẽ không.

Trừ khi công việc bạn đang thực hiện cho mỗi lần lặp lại là rất nhỏ (như một hoặc hai hoạt động số nguyên), chi phí sẽ không đáng kể.

Answer 6

Luôn nhận hồ sơ về đơn đăng ký của bạn trước khi xem loại tối ưu hóa vi mô này. Hãy nhớ rằng ngay cả khi nó thực hiện phép trừ, trình biên dịch vẫn có thể dễ dàng tối ưu hóa nó theo nhiều cách sẽ làm mất đi bất kỳ tổn thất hiệu năng nào.

Answer 7

tôi luôn luôn lưu vector.size() trong một biến địa phương (Chỉ khi vector.size() không thay đổi trong vòng lặp for!).
Tại sao? Bởi vì gọi nó trên mỗi lần lặp lại và lưu nó trong một biến cục bộ nhanh hơn rất nhiều. Đó là những gì tôi đã trải nghiệm trong các ứng dụng của mình.
Tôi không thể cung cấp cho bạn bất kỳ số thực nào, nhưng nó tạo ra sự khác biệt đáng chú ý.

Và đối với tất cả những người phàn nàn về tối ưu hóa vi mô:
Khi bạn viết một vòng lặp lớn, bạn có đơn giản (chỉ để vui) chèn một phép trừ không cần thiết trong đó? Không, bạn không.

Tại sao bạn không chỉ cần cấu hình nó? Một vector lớn và std :: thời gian sẽ làm tốt.