2012-04-26 23 views
11

Si dice che l'iterazione attraverso un vettore (come nella lettura di tutto il suo elemento) sia più veloce dell'iterazione di un elenco, a causa della cache ottimizzata.std :: list vs std :: vector iteration

Esiste qualche risorsa sul Web che quantifica quanto influisce sulle prestazioni?

Inoltre, sarebbe meglio utilizzare un elenco personalizzato collegato, quali elementi sarebbero preallocati in modo che siano consecutivi in ​​memoria?

L'idea alla base di questo è che voglio memorizzare elementi in un certo ordine che non cambierà. Devo ancora essere in grado di inserire alcuni in fase di esecuzione nella midle velocemente, ma la maggior parte di essi sarà ancora consecutiva, perché l'ordine non cambierà.

Il fatto che gli elementi siano consecutivi hanno un impatto nella cache o perché chiamerò ancora list_element->next anziché ++list_element ma non migliora nulla?

+3

"Inoltre, sarebbe meglio utilizzare un elenco personalizzato collegato, quali elementi sarebbero preallocati in modo che siano consecutivi in ​​memoria?" intendi un vettore? –

+0

@LuchianGrigore Non sarebbe un vettore, visto che, se si desidera inserire un elemento nel mezzo, tutto ciò che si dovrebbe fare sarebbe ancora cambiare alcuni puntatori. –

+1

Il requisito principale per 'std :: list' è che l'inserimento e la rimozione di singoli elementi da qualsiasi punto della lista sia costante. Questo è incompatibile con l'avere elementi consecutivi in ​​memoria. – juanchopanza

risposta

3

I guadagni di efficienza dalla coerenza della cache dovuti alla rappresentazione compatta delle strutture di dati possono essere piuttosto drammatici.Nel caso dei vettori rispetto agli elenchi, la rappresentazione compatta può essere migliore non solo per la lettura ma anche per l'inserimento (spostamento di vettori) di elementi fino all'ordine di elementi 500K per alcune architetture particolari come dimostrato nella Figura 3 di questo articolo di Bjarne Stroustrup: (sito Editore: http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353)

http://www2.research.att.com/~bs/Computer-Jan12.pdf

Penso che se questo è un fattore critico per il programma, si dovrebbe profilo sulla vostra architettura.

1

Non so se riesco a spiegarmi bene, ma ecco la mia vista (sto pensando lungo le linee di istruzione macchina tradotto in basso :),

Vector iteratore (memoria contigua): quando si incrementa un iteratore vettore , il valore iteratore viene semplicemente aggiunto alla dimensione dell'oggetto (noto al momento della compilazione) per puntare all'oggetto successivo. Nella maggior parte delle CPU questo è qualsiasi cosa da una a tre istruzioni al massimo.

Lista iteratore (lista collegata http://www.sgi.com/tech/stl/List.html): quando si incrementa un elenco iteratore (l'oggetto appuntito), la posizione del collegamento in avanti si trova con l'aggiunta di qualche numero alla base del l'oggetto puntato e poi caricato su come il nuovo valore dell'iteratore. C'è più di un accesso alla memoria per questo ed è più lento dell'operazione di iterazione del vettore.

3

La differenza principale tra vettore e liste è che negli elementi vettoriali vengono costruiti successivamente all'interno di un buffer preallocato, mentre in un elenco gli elementi vengono costruiti uno ad uno. Di conseguenza, gli elementi di un vettore sono concessi per occupare uno spazio di memoria contiguo, mentre gli elementi di lista (a meno che alcune situazioni specifiche, come un allocatore personalizzato che funziona in quel modo) non siano garantite, e possono essere "sparse" intorno la memoria.

Ora, poiché il processore opera su una cache (che può essere fino a 1000 volte più veloce rispetto alla RAM principale) che remaps intere pagine della memoria principale, se gli elementi sono consecutivi è altamente probabile che si inserisce una stessa memoria pagina e quindi vengono spostati tutti insieme nella cache all'avvio dell'iterazione. Mentre procede, tutto avviene nella cache senza ulteriore spostamento di dati o ulteriore accesso alla RAM più lenta.

Con le liste, poiché gli elementi sono sparsi ovunque, "passare al successivo" significa fare riferimento a un indirizzo che potrebbe non essere nella stessa pagina di memoria del suo precedente, e quindi, la cache deve essere aggiornata ad ogni passo di iterazione, accedendo alla RAM più lenta ad ogni iterazione.

La differenza di prestazioni dipende molto dalla processore e sul tipo di memoria utilizzata sia per la RAM principale e la cache, e il modo in cui il std::allocator (e in definitiva operator new e malloc) sono implementati, per cui un numero generale è impossibile essere dato. (Nota: grande differenza significa RAM cattiva rispetto alla cache, ma può anche significare cattiva implementazione su liste)