In che modo std :: vector è più veloce di un array semplice?

Question

Mi sono imbattuto in questo mentre confrontavo un buffer circolare. Qualcuno può spiegare come un vettore std: riesce a sovraperformare una matrice semplice in questa istanza?

#include <iostream> 
#include <vector> 

struct uint_pair { 
    unsigned int a, b; 
    uint_pair (unsigned int x = 0, unsigned int y = 0) : a(x), b(y) {} 
}; 

struct container { 
    unsigned int pos; 

#ifdef USE_VECTOR 
    std::vector<uint_pair> data; 
    container() : pos(0) { data.resize(16); } 
#else 
    uint_pair data[16]; 
    container() : pos(0) {} 
#endif 

    void add(uint_pair val) { 
     data[++pos % 16] = val; 
    } 
}; 

int main() { 
    container c; 
    for (unsigned int i = 0; i < 1000000000; i++) c.add(uint_pair{i, i}); 
    std::cout << c.data[0].a << " " << c.data[0].b << std::endl; 
} 

Questi sono i risultati che sto ottenendo con GCC (simile con Clang):

g++ -o bench -std=c++0x -Os main.cpp -D'USE_VECTOR' 
real 0m8.757s 
user 0m8.750s 
sys  0m0.002s 

g++ -o bench -std=c++0x -Os main.cpp 
real 0m9.215s 
user 0m9.209s 
sys  0m0.002s 

Answer 1

Ecco come è possibile eliminare la differenza. Invece della vostra add, utilizzare una funzione come questa:

void set(unsigned int x, unsigned int y) { 
    ++pos; 
    data[pos % 16].a = x; 
    data[pos % 16].b = y; 
} 

chiamato in questo modo:

for (unsigned int i = 0; i < 1000000000; i++) c.set(i, i); 

Questo fa esattamente la stessa cosa come la tua, ma evita la creazione di semanticamente un oggetto temporaneo. Sembra che quando usi un vettore, il compilatore sia maggiormente in grado di ottimizzare il provvisorio.

$ g++-4.8 -o bench -std=c++11 -Os main.cpp -DUSE_VECTOR 
$ time ./bench 
999999999 999999999 

real 0m0.635s 
user 0m0.630s 
sys 0m0.002s 

$ g++-4.8 -o bench -std=c++11 -Os main.cpp 
$ time ./bench 
999999999 999999999 

real 0m0.644s 
user 0m0.639s 
sys 0m0.002s 

Sulla mia macchina sia set e add metodi cedono prestazioni identiche con vettori. Solo la matrice mostra una differenza. Per dare ulteriore credito all'ottimizzazione, se si compila con -O0, allora il metodo array è leggermente più veloce (ma entrambi oltre 10x più lenti rispetto a -Os).

Questo non spiega perché il il compilatore tratta questi due in modo diverso. Dopotutto, un vettore è supportato da un array. Inoltre, un std::array si comporta in modo identico al tuo array in stile C.

Answer 2

Un problema riguarda il posizionamento del membro "pos" nella struttura.

Per il c-array, ricordare che è memorizzato in modo contiguo nella memoria adiacente al membro "pos". Quando i dati vengono trasferiti nell'array c, devono essere impartite istruzioni aggiuntive per spostarsi nella struttura oltre il membro "pos". Tuttavia, la scrittura sul vettore non rende tale limitazione poiché la sua memoria si trova altrove.

Per aumentare le prestazioni, assicurarsi che i dati più aggiornati siano nella parte anteriore di una linea della cache.

Edit:

Per ottenere c-array per eseguire velocemente come il vettore, il c-array deve essere allocato su 8 limiti di byte su una macchina a 64 bit. Quindi, qualcosa di simile a:

uint_pair* data; 
unsigned int pos; 

container() : pos(0) { 
    std::size_t bufSize = sizeof(uint_pair) * 17; 
    void* p = new char[bufSize]; 
    p = std::align(8, sizeof(uint_pair), p, bufSize); 
    data = reinterpret_cast<uint_pair*>(p); 
} 

Con una funzione leggermente modificata aggiuntivo:

void add(unsigned int x, unsigned int y) { 
    auto& ref = data[pos++ % 16]; 
    ref.a = x; 
    ref.b = y; 
} 

Il c-array Ora i tempi:

real 0m0.735s 
user 0m0.730s 
sys  0m0.002s 

E lo std :: vector:

real 0m0.743s 
user 0m0.736s 
sys  0m0.004s 

La libreria standard implemente rs stanno tirando fuori tutto per te :)

Answer 3

Sembra che il compilatore C++ 11 generi un codice migliore per il vettore a causa dell'operatore = (valore di riferimento). In primo luogo, nel compilatore C++ 03 array semplice due volte più veloce del vettore. In secondo luogo, non ci sono differenze se si utilizza il set vuoto (unsigned int x, unsigned int y) suggerito da Adam.

codice Assembler per il vettore

.L49: 
leal (%rdi,%rax), %esi 
andl $15, %esi 
leaq (%rdx,%rsi,8), %rsi 
movl %eax, (%rsi) 
movl %eax, 4(%rsi) 
incq %rax 
cmpq $1000000000, %rax 
jne .L49 

per matrice piana

.L3: 
movl 12(%rsp), %edx 
incl %edx 
movl %edx, 12(%rsp) 
andl $15, %edx 
leaq 12(%rsp,%rdx,8), %rdx 
movl %eax, 4(%rdx) 
movl %eax, 8(%rdx) 
incl %eax 
cmpl $1000000000, %eax 
jne .L3