È std :: deque più veloce di std :: vector per l'inserimento alla fine?

Question

ho iniziato a fare il confronto tra:

• inserimento nella parte anteriore della lista
• inserendo sul retro di un vettore
• l'inserimento nella parte anteriore di un deque

Ma poi ho notato che anche su push_back() il deque sembrava essere più veloce. Devo fare qualcosa di errato, non posso credere che un contenitore più generale possa sovraperformare un particolare.

Il mio codice utilizzando google benchmark:

#include "benchmark/benchmark.h" 
#include <deque> 
#include <vector> 

#define NUM_INS 1000 

static void BM_InsertVector(benchmark::State& state) { 
    std::vector<int> v; 
    v.reserve(NUM_INS); 
    while (state.KeepRunning()) { 
     state.PauseTiming(); 
     v.clear(); 
     state.ResumeTiming(); 
     for (size_t i = 0; i < NUM_INS; i++) 
      v.push_back(i); 
    } 
} 
BENCHMARK(BM_InsertVector); 

static void BM_InsertDeque(benchmark::State& state) { 
    std::deque<int> v; 
    while (state.KeepRunning()) { 
     state.PauseTiming(); 
     v.clear(); 
     state.ResumeTiming(); 
     for (size_t i = 0; i < NUM_INS; i++) 
      v.push_back(i); 
    } 
} 
BENCHMARK(BM_InsertDeque); 

BENCHMARK_MAIN(); 

Risultati:

Run on (1 X 2592 MHz CPU) 
2016-02-18 14:03:47 
Benchmark   Time(ns) CPU(ns) Iterations 
------------------------------------------------ 
BM_InsertVector  2820  2470  312500         
BM_InsertDeque  1872  1563  406977 

ho notato alcune differenze quando si gioca con il numero di elementi, ma deque supera sempre vettoriale.

EDIT: compilatore: gcc version 5.2.1 compilazione con: g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread

Penso che la -O3 è in realtà strumentale; quando lo spengo ottengo un po 'peggio prestazioni deque.

Answer 1

Penso che il vettore sia più lento perché si sta chiamando clear() che, a seconda dell'implementazione STL, potrebbe liberare l'archiviazione dell'array sottostante.

In questo caso, la chiamata reserve() non aiuta; e il tuo vettore viene ridimensionato continuamente, il che richiede che ogni elemento venga spostato nella nuova, più grande, memoria.

Answer 2

ci sono fondamentalmente 3 fonti di costo coinvolti in continuo aggiungendo elementi di un contenitore dinamico:

1. gestione della memoria.
2. La contabilità interna del contenitore.
3. Qualsiasi operazione che deve essere eseguita sugli elementi stessi. In particolare; qualsiasi contenitore che invalida i riferimenti all'inserimento è potenzialmente in movimento/copia elementi in giro.

Iniziamo con 1. vector mantiene chiedendo doppio della memoria, e deque assegna blocchi fissi dimensioni (deque è tipicamente implementate come una matrice di matrici, con gli array di livello inferiore essendo di dimensioni fisse). Richiedere più memoria potrebbe richiedere più tempo rispetto a chiedere di meno, ma in genere, a meno che l'heap non sia molto frammentato, chiedere un grosso pezzo tutto in una volta è il modo più veloce per ottenere un po 'di memoria. Probabilmente è più veloce allocare 1 meg una volta, quindi chiedere un kilobyte 1000 volte. Quindi sembra chiaro che vector avrà il vantaggio qui (fino a quando il contenitore è così grande da essere interessato dalla frammentazione). Tuttavia, questo non è alla fine: hai chiesto solo 1000 elementi. Ho scritto il seguente codice http://coliru.stacked-crooked.com/a/418b18ff8a81c1c0. Non è molto interessante ma fondamentalmente utilizza un allocatore banale che incrementa un globale per vedere quante allocazioni vengono eseguite.

Nel corso del benchmark, vector chiede memoria 11 volte, e deque solo 10. deque mantiene chiedendo la stessa quantità, vector chiede raddoppio quantità. Inoltre, vector deve chiamare lo free 10 volte. E deque 0. Sembra una piccola vittoria per deque.

Per la contabilità interna, vector ha un'implementazione più semplice di deque. Dopo tutto, vector è solo un array dinamico e deque è un array di matrici ed è strettamente più complesso. Quindi questa è chiaramente una vittoria per vector.

Infine, elementi sulle operazioni stesse. In deque, nulla viene mai spostato. Con vector, ogni nuova allocazione dell'heap comporta anche lo spostamento di tutti gli elementi. Probabilmente è ottimizzato per l'uso di memcpy per tipi banali, ma anche per vedere, si tratta di 10 chiamate allo memcpy per copiare interi 1,2,3,4 ... 512. Questa è chiaramente una vittoria per deque.

posso ipotizzare che a gomito fino a O3 permesso inlining molto aggressivo di molti dei codepaths più complesse in deque, riducendo il peso di 2. Ma, ovviamente, a meno che non si fa un punto di riferimento molto più dettagliata (molto attenti!), non lo saprai mai per certo.

Per lo più, questo post è per mostrare che è più complesso di un semplice contenitore specializzato rispetto a uno più generale. Farò comunque un pronostico (metto fuori il collo per essere tagliato fuori, per così dire): se aumenti il ​​numero di elementi dicendo anche un fattore 2 o 4, non vedrai più la vittoria deque. Questo perché deque creerà 2x o 4x quante allocazioni di heap, ma il vettore ne farà solo altre 1-2.

Posso anche notare che lo deque è in realtà una specie di struttura di dati dispari; è teoricamente una matrice di matrici, ma in molte implementazioni l'array ha una certa dimensione, o solo un elemento, qualunque sia il più grande. Inoltre, alcune delle sue grandi garanzie O sono assurdità. push_back è fisso solo a tempo costante, perché in C++, solo le operazioni sugli elementi stessi contano verso il grande O. Altrimenti dovrebbe essere chiaro, dal momento che è una matrice di matrici, l'array di livello superiore sarà proporzionale in dimensioni al numero di elementi già memorizzati E alla fine quell'array di primo livello finisce fuori spazio, e devi riallocarlo, spostando i puntatori O (N). Quindi non è davvero O (1) push_back.