Memorizzazione nella cache dell'iter iter - Buona idea o cattiva idea?

Question

In generale, è una buona idea memorizzare nella cache un iteratore finale (in particolare i contenitori STL) per motivi di efficienza e velocità? come nel seguente bit di codice:

std::vector<int> vint; 
const std::vector<int>::const_iterator end = vint.end(); 
std::vector<int>::iterator it = vint.begin(); 

while (it != end) 
{ 
    .... 
    ++it; 
} 

In quali condizioni il valore finale sarebbe stato invalidato? cancellerebbe dal contenitore causa end per essere invalidato in tutti contenitori STL o solo alcuni?

Answer 1

Nel caso semplice di vector, l'iteratore end cambia quando si aggiungono o si rimuovono elementi dal contenitore; tuttavia, di solito è più sicuro presumere che se si muta il contenitore mentre si itera su di esso, gli di tutti gli iteratori dello non sono più validi. Gli iteratori possono essere implementati in modo diverso in ogni data implementazione STL.

Per quanto riguarda la memorizzazione nella cache dell'iteratore end - è sicuramente valido per memorizzarlo nella cache, ma per scoprire se è effettivamente più veloce nel tuo caso, la soluzione migliore è quella di profilare il codice e vedere.Mentre il recupero dell'iter end da un vector è probabilmente un'implementazione rapida con una libreria e un compilatore STL recenti, I ha funzionato su progetti precedenti in cui il caching dell'iteratore end ci ha dato un notevole aumento di velocità. (Questo era su PlayStation 2, quindi prendi con un pizzico di sale.)

Answer 2

Cancellare da un contenitore su cui si sta attualmente iterando è sempre una cattiva idea. La memorizzazione nella cache effettiva del tuo iteratore finale non cambierà questo.

h.

Answer 3

Se parliamo di efficienza e velocità: il caching dell'iter iter finale non è necessario a causa dell'ottimizzazione del compilatore e dell'inlinazione.

Answer 4

Io uso spesso questo stile per contenitori iterazione:

// typedef std::vector<Person> Persons; 
Persons::iterator it = persons.begin(), end = persons.end(); 
for (; it != end; ++it) 
{ 
    Person & person = *it; 
    // ... 
} 

Cancellazione di un elemento da un vettore invalida tutti gli iteratori dopo la posizione cancellati.

Non sono sicuro degli altri tipi di contenitori. In ogni caso, penso che sarebbe sicuro assumere che tutti gli iteratori diventino invalidi dopo una cancellazione. Se hai davvero bisogno di informazioni molto specifiche, puoi sempre verificarle. Raramente ho bisogno di questo perché grazie al mio stile di codifica piuttosto conservatore.

Answer 5

In generale, non importa se si memorizza nella cache l'iteratore finale. Se ritieni che sia importante, dovresti già utilizzare un profiler sul tuo codice e riuscire a profilare entrambe le varianti. Sospetto che potrebbe differire a seconda del tipo di contenitore, ma un profilatore sarebbe l'unico modo per sapere con certezza dato il tuo compilatore, ottimizzazioni e fornitore STL.

Answer 6

In generale è una buona idea per memorizzare nella cache un iteratore fine (in particolare contenitori STL) a fini di efficienza e di velocità?

Se si utilizzano gli algoritmi del contenitore STL, la memorizzazione nella cache dell'iter iter finale avviene comunque (mentre si passa il risultato di container.end() come parametro).

Se si modifica la memoria del contenitore (inserire/rimuovere elementi) è una cattiva idea.

Inoltre, il caching per l'efficienza raramente ha molto senso: nella maggior parte dei casi la fine() è delineata dal compilatore e, quando non lo è, è molto probabile che l'efficienza non si blocchi nel risultato finale() essere messo in cache YMMV però.

Answer 7

Le regole di invalidazione (per gli iteratori) sono definite in modo molto esplicito per ogni tipo di contenitore. Trovo il sito SGI molto utile http://www.sgi.com/tech/stl/table_of_contents.html

In particolare per i vettori trovo:

[5] iteratori di un vettore vengono invalidate quando la sua memoria viene riallocata. Inoltre, l'inserimento o l'eliminazione di un elemento nel mezzo di un vettore invalida tutti gli iteratori che puntano agli elementi che seguono il punto di inserimento o di cancellazione. Ne consegue che è possibile evitare iteratori di un vettore di essere invalidati se si utilizza di riserva() per preallocare la quantità di memoria il vettore potrà mai usare, e se tutte le inserzioni e delezioni sono alla fine del vettore.