Perché è così lento che scorre su una grande lista std ::?

Question

Come suggerisce il titolo, ho avuto problemi con un mio programma in cui ho usato uno std :: list come stack e anche per scorrere su tutti gli elementi dell'elenco. Il programma stava prendendo troppo tempo quando le liste sono diventate molto grandi.

Qualcuno ha una buona spiegazione per questo? È un comportamento stack / cache?

(Risolto il problema cambiando gli elenchi in std :: vector e std :: deque (una straordinaria struttura di dati tra l'altro) e all'improvviso tutto è andato molto più veloce)

EDIT: non sono uno sciocco e non accedo agli elementi in mezzo alle liste. L'unica cosa che ho fatto con gli elenchi è stata quella di rimuovere / aggiungere elementi alla fine / inizio e di scorrere tra tutti gli elementi dell'elenco. E ho sempre usato gli iteratori per scorrere l'elenco.

Answer 1

Le liste hanno una terribile (inesistente) località cache. Ogni nodo è una nuova allocazione di memoria e può essere ovunque . Quindi ogni ogni volta che segui un puntatore da un nodo al successivo, salti in un posto nuovo, non correlato, in memoria. E sì, questo fa male un po 'le prestazioni. Una mancata cache può essere di due ordini di grandezza più lenta di un colpo di cache. In un vettore o deque, praticamente ogni accesso sarà un colpo alla cache. Un vettore è un singolo blocco contiguo di memoria, quindi l'iterazione su di esso è più veloce che otterrai. Un deque è costituito da diversi blocchi di memoria più piccoli, quindi introduce occasionalmente la mancanza della cache, ma saranno comunque rari e l'iterazione sarà ancora molto veloce poiché si ottengono principalmente hit della cache.

Un elenco contiene quasi tutte le mancate cache. E le prestazioni faranno schifo.

In pratica, un elenco collegato non è quasi mai la scelta giusta dal punto di vista delle prestazioni.

Modifica : Come ha sottolineato un commento, un altro problema con le liste è la dipendenza dai dati. A una CPU moderna piace sovrapporre le operazioni. Ma non può farlo se l'istruzione successiva dipende dal risultato di questo.

Se stai iterando su un vettore, non c'è problema. Puoi calcolare l'indirizzo successivo da leggere al volo, senza mai dover controllare in memoria. Se stai leggendo l'indirizzo x ora, l'elemento successivo si troverà all'indirizzo x + sizeof (T) dove T è il tipo di elemento. Quindi non ci sono dipendenze lì, e la CPU può iniziare a caricare immediatamente l'elemento successivo, o quello successivo, mentre continua a elaborare un elemento precedente. In questo modo, i dati saranno pronti per noi quando ne avremo bisogno, e questo aiuta ulteriormente a mascherare il costo di accesso ai dati nella RAM.

In un elenco, dobbiamo seguire un puntatore dal nodo i al nodo i + 1 e fino a quando i + 1 è stato caricato, non sappiamo nemmeno dove cercare i + 2 . Abbiamo una dipendenza dai dati, quindi la CPU è costretta a leggere i nodi uno alla volta e non può iniziare a leggere i nodi futuri in anticipo, perché non sa ancora dove si trovano.

Se un elenco non fosse stato privo di cache, questo non sarebbe stato un grosso problema, ma dal momento che stiamo ricevendo molti errori nella cache, questi ritardi sono costosi.

Answer 2

È a causa della grande quantità di errori nella cache che si ottengono quando si utilizza un elenco. Con un vettore gli elementi circostanti sono memorizzati nella cache dei processori.

Answer 3

Dai un'occhiata al seguente threadoverflowflow .

Answer 4

Lì è un problema di cache: tutti i dati nel vettore sono archiviati in un blocco contiguo e ogni elemento della lista è allocato separatamente e può capitare di essere archiviato in un luogo di memoria abbastanza casuale, il che porta a più cache cache. Tuttavia, scommetto che incontri uno dei problemi descritti nelle altre risposte.

Answer 5

La semplice risposta è perché iterare su un vettore non è affatto iterare, sta solo cominciando dalla base di un array e leggendo gli elementi uno dopo l'altro.

Vedo che questo è contrassegnato C ++, non C, ma poiché fanno la stessa cosa sotto le copertine vale la pena sottolineare che è possibile aggiungere elementi all'inizio e alla fine di un array allocandolo arbitrariamente grande, e realloc () ing e memmove () ing tra 2 array companion se e quando si esaurisce lo spazio. Molto veloce.

Il trucco per aggiungere elementi all'inizio di un array è di distorcere l'inizio logico dell'array facendo avanzare il puntatore nell'array all'inizio e quindi eseguendo il backup quando si aggiungono elementi in primo piano. (anche il modo in cui viene implementato uno stack)

Allo stesso modo, è possibile creare C per supportare sottoscrizioni negative.

C ++ fa tutto questo per te con la classe STL vettoriale, ma vale comunque la pena ricordare cosa sta succedendo sotto le copertine.

Answer 6

[Modifica: sto corretto. std :: list non ha un operatore []. Siamo spiacenti.]

È difficile distinguerlo dalla tua descrizione, ma sospetto che stavi tentando di accedere agli elementi in modo casuale (ad esempio, per indice):

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

Invece di usare gli iteratori:

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

Entrambi " vector " & Amp; & Quot; deque " sono bravi ad accedere casualmente, quindi entrambi si comporteranno adeguatamente per quei tipi --- O (1) in entrambi i casi. Ma "quot" " non è buono in caso di accesso casuale. L'accesso all'elenco per indice richiederebbe O (n ^ 2) tempo, rispetto a O (1) quando si utilizzano iteratori.