Copia veloce di `std :: vector <std :: uint8_t>`

Question

Ho uno std::vector<std::uint8_t>, che deve essere duplicato. Questo viene fatto semplicemente chiamando il costruttore di copie.

I risultati del mio profilo mostrano che l'implementazione Microsoft Visual C++ (msvc100) utilizza internamente std::uninitialized_copy. Questo copia ogni elemento uno per uno. In questo caso, una copia più ottimizzata può essere eseguita copiando interi blocchi di memoria contemporaneamente (come può fare memcpy).

In altre parole, questa potrebbe essere una significativa ottimizzazione. C'è un modo per forzare il vettore ad utilizzare un metodo così ottimizzato?

Nota: ho provato a utilizzare std::basic_string<std::uint8_t> e ha prestazioni migliori, ma presenta altri problemi.

Answer 1

Sulla base delle soluzioni suggerite, ho deciso di mettere insieme un piccolo punto di riferimento.

#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; 
} 

A mio PC, compilato per x64 con msvc100, completamente ottimizzato, questo produce il seguente output:

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

I risultati sono chiari: std::copy può competere con std::memcpy, mentre entrambi i costruttori e assign sono un ordine di grandezza più lento. Naturalmente i numeri esatti e le proporzioni dipendono dalla dimensione del vettore, ma la conclusione per msvc100 è ovvia: come suggested by Rapptz, utilizzare std::copy.

Modifica: la conclusione non è ovvia per altri compilatori. Ho testato a 64-bit Linux pure, con il seguente risultato per Clang 3,2

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

GCC 4.8 dà un risultato simile.Per GCC su Windows, memcpy e copy erano leggermente più lenti dei costruttori e assign, sebbene la differenza fosse inferiore. Tuttavia, la mia esperienza è che GCC non ottimizza molto bene su Windows. Ho provato anche msvc110 e i risultati erano simili a msvc100.

Answer 2

Questa risposta non è specifica per msvc100.

se si utilizza il costruttore di copia come in

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

oggetto allocatore del otherVect deve essere copiato (e utilizzato) pure, che ha bisogno di più gli sforzi per farlo performante per l'attuazione STL.

Se si desidera solo per copiare i contenuti di otherVect, utilizzare

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

che utilizza l'allocatore di default per newVect.

Un'altra possibilità è

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

Tutti loro (compreso il constuctor copia quando otherVect utilizza l'allocatore di default) dovrebbe ridursi a un memmove/memcpy in una buona implementazione STL in questo caso. Fai attenzione, che otherVect ha esattamente lo stesso tipo di elemento (non ad esempio 'char' o 'int8_t') come newVect.

L'utilizzo del metodo del contenitore è generalmente più performante rispetto all'utilizzo di algoritmi generici, quindi una combinazione di vector :: resize() e std :: copy() o anche memmove()/memcpy() sarebbe un work-around, se il venditore non ha ottimizzato sufficientemente il contenitore.