Perché la localizzazione della cache è importante per le prestazioni dell’array?

Nel seguente blog c’è una dichiarazione sul vantaggio degli array rispetto alle liste concatenate:

Gli array hanno una migliore localizzazione della cache che può fare una grande differenza nelle prestazioni.

Cosa significa? Non capisco come la localizzazione della cache possa offrire un enorme vantaggio in termini di prestazioni.

Vedi la mia risposta sulla località spaziale e temporale .

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.

Considerare i seguenti possibili layout di memoria per i data un array e l’elenco collegato l_data di strutture di grandi dimensioni

 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 effettuare il loop di questo array, il primo accesso a ffff 0000 richiederebbe l’accesso alla memoria per il recupero (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 la lista collegata, 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, diciamo 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.

In genere, quando si utilizza un array si accede agli elementi vicini l’uno all’altro. Ciò è particolarmente vero quando si accede a un array in sequenza.

Quando accedi alla memoria, ne vengono memorizzati alcuni blocchi a vari livelli. La localizzazione cache si riferisce alla probabilità che le operazioni successive siano nella cache e quindi siano più veloci. In un array, si massimizzano le possibilità di accesso sequenziale degli elementi nella cache.

Con gli elenchi, per controesempio, non vi è alcuna garanzia che gli elementi che appaiono sequenzialmente nell’elenco siano effettivamente disposti l’uno vicino all’altro in memoria. Ciò significa meno hit della cache e prestazioni degradate.