Bản sao nhanh của `std :: vector <std :: uint8_t>`

Question

Tôi có một số std::vector<std::uint8_t>, cần được sao chép. Điều này được thực hiện đơn giản bằng cách gọi hàm tạo bản sao.

Kết quả lược tả của tôi cho thấy rằng việc triển khai Microsoft Visual C++ (msvc100), sử dụng std::uninitialized_copy nội bộ. Điều này sao chép từng phần tử một. Trong trường hợp này, một bản sao tối ưu hơn có thể được thực hiện bằng cách sao chép toàn bộ các khối bộ nhớ cùng một lúc (như memcpy có thể làm).

Nói cách khác, đây có thể là một tối ưu hóa đáng kể. Có cách nào để buộc các vector để sử dụng một phương pháp tối ưu hóa như vậy?

Lưu ý: Tôi đã thử sử dụng std::basic_string<std::uint8_t> và ứng dụng hoạt động tốt hơn nhưng có sự cố khác.

Answer 1

Dựa trên các giải pháp được đề xuất, tôi quyết định đặt cùng một điểm chuẩn nhỏ.

#include <cstdint> 
#include <cstring> 
#include <ctime> 
#include <iostream> 
#include <random> 
#include <vector> 

using namespace std; 

int main() 
{ 
    random_device seed; 
    mt19937 rnd(seed()); 
    uniform_int_distribution<uint8_t> random_byte(0x00, 0xff); 

    const size_t n = 512 * 512; 

    vector<uint8_t> source; 
    source.reserve(n); 
    for (size_t i = 0; i < n; i++) source.push_back(random_byte(rnd)); 

    clock_t start; 
    clock_t t_constructor1 = 0; uint8_t c_constructor1 = 0; 
    clock_t t_constructor2 = 0; uint8_t c_constructor2 = 0; 
    clock_t t_assign = 0;  uint8_t c_assign = 0; 
    clock_t t_copy = 0;   uint8_t c_copy = 0; 
    clock_t t_memcpy = 0;  uint8_t c_memcpy = 0; 

    for (size_t k = 0; k < 4; k++) 
    { 
    start = clock(); 
    for (size_t i = 0; i < n/32; i++) 
    { 
     vector<uint8_t> destination(source); 
     c_constructor1 += destination[i]; 
    } 
    t_constructor1 += clock() - start; 

    start = clock(); 
    for (size_t i = 0; i < n/32; i++) 
    { 
     vector<uint8_t> destination(source.begin(), source.end()); 
     c_constructor2 += destination[i]; 
    } 
    t_constructor2 += clock() - start; 

    start = clock(); 
    for (size_t i = 0; i < n/32; i++) 
    { 
     vector<uint8_t> destination; 
     destination.assign(source.begin(), source.end()); 
     c_assign += destination[i]; 
    } 
    t_assign += clock() - start; 

    start = clock(); 
    for (size_t i = 0; i < n/32; i++) 
    { 
     vector<uint8_t> destination(source.size()); 
     copy(source.begin(), source.end(), destination.begin()); 
     c_copy += destination[i]; 
    } 
    t_copy += clock() - start; 

    start = clock(); 
    for (size_t i = 0; i < n/32; i++) 
    { 
     vector<uint8_t> destination(source.size()); 
     memcpy(&destination[0], &source[0], n); 
     c_memcpy += destination[i]; 
    } 
    t_memcpy += clock() - start; 
    } 

    // Verify that all copies are correct, but also prevent the compiler 
    // from optimising away the loops 
    uint8_t diff = (c_constructor1 - c_constructor2) + 
       (c_assign - c_copy) + 
       (c_memcpy - c_constructor1); 

    if (diff != 0) cout << "one of the methods produces invalid copies" << endl; 

    cout << "constructor (1): " << t_constructor1 << endl; 
    cout << "constructor (2): " << t_constructor2 << endl; 
    cout << "assign:   " << t_assign << endl; 
    cout << "copy    " << t_copy << endl; 
    cout << "memcpy   " << t_memcpy << endl; 

    return 0; 
} 

Tại máy tính của tôi, biên soạn cho x64 với msvc100, tối ưu hóa đầy đủ, điều này sẽ cho kết quả như sau:

constructor (1): 22388 
constructor (2): 22333 
assign:   22381 
copy    2142 
memcpy   2146 

Kết quả là khá rõ ràng: std::copy Thực hiện cũng như std::memcpy, trong khi cả nhà thầu và assign là một đơn đặt hàng có cường độ chậm hơn. Tất nhiên, các con số và tỷ lệ chính xác phụ thuộc vào kích thước vectơ, nhưng kết luận cho msvc100 là hiển nhiên: như suggested by Rapptz, sử dụng std::copy.

Chỉnh sửa: kết luận không rõ ràng đối với các trình biên dịch khác. Tôi đã thử nghiệm tại 64-bit Linux là tốt, với kết quả sau cho Clang 3.2

constructor (1): 530000 
constructor (2): 560000 
assign:   560000 
copy    840000 
memcpy   860000 

GCC 4.8 cho kết quả tương tự.Đối với GCC trên Windows, memcpy và copy hơi chậm hơn so với các nhà xây dựng và assign, mặc dù sự khác biệt nhỏ hơn. Tuy nhiên, kinh nghiệm của tôi là GCC không tối ưu hóa tốt trên Windows. Tôi đã thử nghiệm msvc110 là tốt, và kết quả tương tự như msvc100.

Answer 2

Câu trả lời này không dành riêng cho msvc100.

Nếu bạn sử dụng các nhà xây dựng bản sao giống như trong

std::vector<uint8_t> newVect(otherVect); 

đối tượng cấp phát của otherVect phải được sao chép (và sử dụng) là tốt, mà cần nhiều nỗ lực để có được nó performant trong việc thực hiện STL.

Nếu bạn chỉ muốn sao chép nội dung của otherVect, sử dụng

std::vector<uint8_t> newVect(otherVect.begin(), otherVect.end()); 

trong đó sử dụng bộ cấp phát mặc định cho newVect.

Một khả năng khác là

std::vector<uint8_t> newVect; nevVect.assign(otherVect.begin(), otherVect.end()); 

Tất cả trong số họ (bao gồm cả constuctor bản sao khi otherVect sử dụng bộ cấp phát mặc định) nên đun sôi xuống một memmove/memcpy trong việc thực hiện STL tốt trong trường hợp này. Cẩn thận, rằng vectơ khác có chính xác kiểu phần tử giống nhau (không phải là 'char' hoặc 'int8_t') như newVect.

Sử dụng phương pháp của thùng chứa thường hoạt động hiệu quả hơn so với sử dụng thuật toán chung, do đó, kết hợp vector :: resize() và std :: copy() hoặc memmove()/memcpy() sẽ là công việc nếu nhà cung cấp không tối ưu hóa vùng chứa đầy đủ.