std :: vector :: penalizzazione delle prestazioni di riserva

Question

inline void add(const DataStruct& rhs) { 
    using namespace boost::assign; 
    vec.reserve(vec.size() + 3); 
    vec += rhs.a, rhs.b, rhs.c; 
} 

La funzione di cui sopra è stato eseguito per circa 17000 volte e ha eseguito (per quanto posso vedere. C'era qualche trasformazione coinvolti) circa 2 magnitudini peggio con la chiamata per vector :: reserve.

Ho sempre avuto l'impressione che la riserva possa accelerare push_back anche per valori piccoli, ma questo non sembra vero e non riesco a trovare alcun ovvio motivo per cui non dovrebbe essere così. Si riserva di impedire la definizione della funzione? La chiamata a size() è troppo costosa? Questo dipende dalla piattaforma? Proverò a codificare un piccolo benchmark per confermarlo in un ambiente pulito.

Compiler: gcc (GCC) 4.4.2 con -g -O2

Answer 1

implementazione GCC di reserve() assegnerà esatto numero di elementi, mentre push_back() crescerà buffer interno in modo esponenziale, raddoppiando, in modo che si sta sconfiggendo la crescita esponenziale e forzare la riallocazione/copia su ogni iterazione. Esegui il test sotto ltrace o valgrind e visualizza il numero di chiamate malloc().

Answer 2

Utilizzare solo riserva se si sa in anticipo quanto luogo userà.

Reserve avrà bisogno di tutta la vostra copia vettore ...

Se fate una push_back e il vettore è troppo piccolo, allora farà una riserva (vec.size() * 2).

Se non sai in anticipo quanto grande sarà il tuo vettore e se hai bisogno di un accesso casuale, considera l'uso di std :: deque.

Answer 3

Si utilizza solo reserve() se si conosce in anticipo il numero di elementi. In questo caso lo spazio reserve() per tutti gli elementi contemporaneamente.

Altrimenti basta usare push_back() e fare affidamento sulla strategia predefinita: riallocerà in modo esponenziale e ridurrà notevolmente il numero di riallocazioni a un costo di consumo di memoria leggermente subottimale.

Answer 4

Sposta la riserva all'esterno dell'aggiunta.

Ogni volta che invochi "aggiungi", stai prenotando almeno 3 elementi in più. A seconda dell'implementazione del vettore, questo potrebbe aumentare quasi tutte le volte che si chiama "aggiungi". Ciò causerebbe sicuramente la differenza di prestazioni che descrivi.

Il modo corretto di utilizzare riserva è qualcosa di simile:

vec.reserve(max*3); 
for(int i=0; i<max; i++) 
    add(i); 

Answer 5

Se hai profilato il codice, scommetto che vedresti che + = È molto veloce, il problema è che la riserva ti sta uccidendo. Dovresti davvero usare la riserva solo quando hai una certa conoscenza di quanto grande sarà il vettore. Se riesci a indovinare in anticipo, fai una riserva, altrimenti vai con il push_back predefinito.

Answer 6

Quando std :: vector deve riallocarlo, aumenta la dimensione di allocazione di N * 2, dove n è la dimensione corrente. Ciò si traduce in un numero logaritmico di reallocs al crescere del vettore.

Se invece lo std :: vector ha aumentato lo spazio allocato di una quantità costante, il numero di realloc crescerebbe linearmente man mano che il vettore aumenta.

Quello che hai fatto è essenzialmente far crescere il vettore di una quantità costante 3, che significa crescita lineare. La linearità è ovviamente peggiore di quella logaritmica, specialmente con grandi numeri.

Generalmente, l'unica crescita migliore di logaritmica è costante. Questo è il motivo per cui il comitato degli standard ha creato il metodo di riserva. Se puoi evitare tutti i reallocs (costanti), avrai un rendimento migliore del comportamento logaritmico predefinito.

Detto questo si può prendere in considerazione i commenti di Herb Sutter circa preferendo std :: deque sopra vettore www.gotw.ca/gotw/054.htm