Nel seguente blog v'è una dichiarazione circa il vantaggio di array su liste concatenate:Perché la localizzazione della cache è importante per le prestazioni dell'array?
Gli array hanno una migliore località della cache che può fare una bella differenza in termini di prestazioni.
Che cosa significa? Non capisco come la localizzazione della cache possa offrire un enorme vantaggio in termini di prestazioni.
Vedere la risposta about spatial and temporal locality.
In particolare, gli array sono blocchi di memoria contigui, quindi blocchi di grandi dimensioni verranno caricati nella cache al primo accesso. Questo rende relativamente veloce l'accesso agli elementi futuri dell'array. Gli elenchi collegati, d'altra parte, non sono necessariamente in blocchi contigui di memoria e potrebbero portare a più errori di cache, il che aumenta il tempo necessario per accedervi.
Considerate i seguenti layout di memoria possibili per una serie data e lista collegata l_data di grandi struct
Address Contents | Address Contents
ffff 0000 data[0] | ffff 1000 l_data
ffff 0040 data[1] | ....
ffff 0080 data[2] | ffff 3460 l_data->next
ffff 00c0 data[3] | ....
ffff 0100 data[4] | ffff 8dc0 l_data->next->next
| ffff 8e00 l_data->next->next->next
| ....
| ffff 8f00 l_data->next->next->next->next
Se volessimo scorrere questo array, il primo accesso a ffff 0000 richiederebbe noi per andare a memoria recuperare (un'operazione molto lenta nei cicli della CPU). Tuttavia, dopo il primo accesso, il resto dell'array si troverebbe nella cache e gli accessi successivi sarebbero molto più rapidi. Con l'elenco collegato, il primo accesso a ffff 1000 richiederebbe anche di andare in memoria. Sfortunatamente, il processore memorizzerà nella cache la memoria che circonda direttamente questa posizione, ad esempio fino a ffff 2000. Come puoi vedere, questo in realtà non cattura nessuno degli altri elementi della lista, il che significa che quando andremo ad accedere a l_data->next, dovremo nuovamente andare in memoria.
Si noti che la località degli elenchi collegati può essere migliorata mediante l'uso di un pool di memoria. Ma hai ancora il problema che i "prossimi" puntatori occupano uno spazio extra. – paddy
@paddy è un buon punto perché spesso questo è il modo in cui sono implementati gli elenchi collegati – brc
Ora ho capito cosa significa "Cache mancante nella lista collegata". – AKS
In genere, quando si utilizza un array si accede agli elementi vicini. Ciò è particolarmente vero quando si accede a un array in sequenza.
Quando si accede alla memoria, un blocco di esso viene memorizzato nella cache a vari livelli. Località cache si riferisce alla probabilità che le operazioni successive si trovino nella cache e quindi siano più veloci. In un array, si massimizzano le possibilità di accesso sequenziale degli elementi nella cache.
Con le liste, per controesempio, non è possibile garantire che gli elementi che appaiono in sequenza nell'elenco siano effettivamente disposti l'uno vicino all'altro in memoria. Ciò significa meno hit della cache e prestazioni degradate.
Tuttavia, ciò dipende molto dal processore e dall'architettura della memoria. Le CPU progettate per la programmazione orientata agli oggetti, ad esempio, di solito non si preoccupano della localizzazione, semplicemente perché dalla * definizione * di "object-oriented" non si può garantire comunque la località. –
Se capisci come funziona [cache] (http://en.wikipedia.org/wiki/Locality_of_reference), capirai anche 1) "La località di riferimento" è una buona cosa e 2) l'accesso ai dati dagli array è in genere più probabile avere una buona "località" rispetto all'accesso agli stessi dati da un elenco. – paulsm4
Una cosa che vale la pena notare è che mentre questo è vero, un elenco collegato singolarmente con un allocatore contiguo può essere un'enorme risorsa, principalmente perché il trasferimento di elementi da un contenitore a un altro implica solo la logica del puntatore. Se si osserva il layout di memoria di questi, tuttavia, è contiguo e si presenta come un array con solo collegamenti al prossimo elemento dell'array, e quindi è ancora cache-friendly (almeno fino a quando l'elenco è tutto riorganizzato). –