[C++] Raggruppare dati per evitare cache faults

[-Ivan-]

Sono nuovamente dietro a leggere libri, implemetare alcune tecniche che sto studiando e sudare come un maiale .
Ora mi trovo a dover implementare dei semplici alberi binari. Nel libro che sto leggendo, a un certo punto dice:

"L'implementazione memorizza i nodi in un singolo blocco di memoria. Questo evita la possibilità che i nodi possano essere memorizzati in posti differenti causando problemi con la cache ed una esecuzione lenta".
(tradotto malamente dall'inglese ma il concetto è quello)

C'era già un riferimento a questo fatto all'inizio del capitolo dove parla dei problemi relativi allo swap tra cache e memoria quando capita un cache fault, mostrando quanto questo possa far degradare le prestazioni.

Io nè all'università nè dopo di essa ho mai considerato questo tipo di problematica e non sono abituato a ragionare sulla compattezza dei dati forse perchè non ne ho mai avuto il bisogno.
Ora vorrei sapere innanzitutto in quale modo in C++ posso creare una struttura dati che, quando richiesta dal programma, sia caricata in cache completamente senza quindi causare continui cache fault durante l'esecuzione dell'algoritmo. Mi viene da pensare se non ricordo male che se memorizzo i nodi dentro un array (un vector in c++) questo dovrebbe funzionare bene allo scopo mentre ovviamente una lista concatenata no. Ma esistono anche altri modi? Qualche struttura speciale?

[pabloski]

Per le strutture dati, tutto quello che memorizza i dati in zone di memoria contigue, diminuisce il numero di cache miss.

Quindi array al posto di liste, ridurre l'uso di malloc, new e compagnia, loop unrolling, ecc...

Però, in generale, affrontare questi problemi è compito del compilatore e del sistema operativo. Aiutarli non fa male, ma è assai poco pratico e molto oneroso.

[-Ivan-]

Ok grazie, lo terrò a mente. Per ora penso che memorizzerò i nodi all'interno di un array.

[pabloski]

Originariamente inviato da -Ivan-

Ok grazie, lo terrò a mente. Per ora penso che memorizzerò i nodi all'interno di un array.

un'array di struct?

[-Ivan-]

No sarebbe un array di instanze di una classe, ho bisogno di modellare i nodi in un certo modo e mi servono anche dei metodi.

[WarDuck]

C'è da dire che anche se allochi i nodi in maniera "sparsa", dunque non avendo località spaziale (anche se non è necessariamente detto), hai comunque quella temporale nel caso degli alberi binari, perché spesso quando ricerchi un elemento all'interno di un albero binario accedi cmq ai nodi intermedi e quelli vengono tipicamente cachati.

Usare una struttura di dimensioni fissate è la soluzione migliore a patto che non sia troppo grande e che il pattern di accesso preveda un accesso simil-sequenziale.

Ad esempio una hash-table da questo punto di vista è la peggior struttura dal punto di vista del caching.

Nel caso degli array il vantaggio è dato dal fatto che viene fatto prefetch sui dati nelle locazioni vicine e quindi se lo scorri linearmente puoi avere dei vantaggi nel caso in cui l'array sia di piccole dimensioni.

Ovviamente c'è da considerare sempre il delay dovuto all'allocazione, per questo motivo tipicamente in software ad alte prestazioni si tende ad allocare memoria in batch, però queste cose sono solo da considerarsi nell'ambito di programmi realmente specifici o real-time per cui devono esistere limiti sul tempo di processamento e l'allocazione rappresenta effettivamente il collo di bottiglia.

[-Ivan-]

Originariamente inviato da WarDuck

C'è da dire che anche se allochi i nodi in maniera "sparsa", dunque non avendo località spaziale (anche se non è necessariamente detto), hai comunque quella temporale nel caso degli alberi binari, perché spesso quando ricerchi un elemento all'interno di un albero binario accedi cmq ai nodi intermedi e quelli vengono tipicamente cachati.

Usare una struttura di dimensioni fissate è la soluzione migliore a patto che non sia troppo grande e che il pattern di accesso preveda un accesso simil-sequenziale.

Ad esempio una hash-table da questo punto di vista è la peggior struttura dal punto di vista del caching.

Nel caso degli array il vantaggio è dato dal fatto che viene fatto prefetch sui dati nelle locazioni vicine e quindi se lo scorri linearmente puoi avere dei vantaggi nel caso in cui l'array sia di piccole dimensioni.

Ovviamente c'è da considerare sempre il delay dovuto all'allocazione, per questo motivo tipicamente in software ad alte prestazioni si tende ad allocare memoria in batch, però queste cose sono solo da considerarsi nell'ambito di programmi realmente specifici o real-time per cui devono esistere limiti sul tempo di processamento e l'allocazione rappresenta effettivamente il collo di bottiglia.

Grazie della spiegazione, siccome sono gnurante ti chiedo...cosa intendi per allocare memoria in batch?

Io l'array che memorizza i nodi dell'albero a dire la verità lo utilizzo molto per avere accesso diretto ai vari elementi, non lo scorro in modo sequenziale. Comunque riguardo all'esercizio che sto facendo c'è un sorgente su internet che poi mi andrò a vedere, prima volevo scrivere la mia versione, poi le cose sbagliate me le studierò a posteriori.

L'ambito è quello delle intelligenze artificiali per videogiochi dunque effettivamente si tratta di algoritmi che vengono rieseguiti ad ogni frame in contesti real time. Penso sia questo il motivo per cui ci si pone in modo così forte il problema di avere una certa compattezza dei dati per migliorare le prestazioni, infatti nei lavori che ho fatto in precedenza difficilmente si arrivava a discutere questioni di questa natura.

[nico159]

IMHO c'è solo un ottimo riferimento a questo:
http://www.akkadia.org/drepper/cpumemory.pdf
Scritto dal mantainer della glibc

Una buona introduzione al problema la si ha con questo talk:
http://channel9.msdn.com/Events/Build/2013/4-329

[-Ivan-]

Originariamente inviato da nico159

IMHO c'è solo un ottimo riferimento a questo:
http://www.akkadia.org/drepper/cpumemory.pdf
Scritto dal mantainer della glibc

Una buona introduzione al problema la si ha con questo talk:
http://channel9.msdn.com/Events/Build/2013/4-329

Grazie, mi interessano tantissimo queste cose relative anche all'architettura dei computer.

[WarDuck]

Originariamente inviato da -Ivan-

Grazie della spiegazione, siccome sono gnurante ti chiedo...cosa intendi per allocare memoria in batch?

Intendo dire che anziché fare N allocazioni piccole, ne puoi fare 1 di dimensioni molto grandi e gestire da te lo spazio per gli oggetti.

Tra l'altro in C++ è presente il così detto "placement new" che consente di creare oggetti in aree di memoria già allocate:

http://en.wikipedia.org/wiki/Placement_syntax

Ovviamente gli oggetti così allocati vanno gestiti a modo, non esiste un placement delete perché si presume che l'area di memoria per l'oggetto in questione venga gestita manualmente (ad esempio potrebbe essere deallocata tutta in una volta sola alla fine del programma).

[||ElChE||88]

Originariamente inviato da WarDuck

Ovviamente gli oggetti così allocati vanno gestiti a modo, non esiste un placement delete perché si presume che l'area di memoria per l'oggetto in questione venga gestita manualmente (ad esempio potrebbe essere deallocata tutta in una volta sola alla fine del programma).

placement delete non serve perché al contrario del costruttore il distruttore lo si può gia chiamare esplicitamente.

[marco.r]

Originariamente inviato da -Ivan-

Ora vorrei sapere innanzitutto in quale modo in C++ posso creare una struttura dati che, quando richiesta dal programma, sia caricata in cache completamente senza quindi causare continui cache fault durante l'esecuzione dell'algoritmo. Mi viene da pensare se non ricordo male che se memorizzo i nodi dentro un array (un vector in c++) questo dovrebbe funzionare bene allo scopo mentre ovviamente una lista concatenata no. Ma esistono anche altri modi? Qualche struttura speciale?

Non occorre necessariamente utilizzare un array. La cosa piu' semplice e' allocare un "pezzo" di memoria grezza e poi utilizzarlo per tirarci fuori i singoli oggetti. Se sono tutti dello stesso tipo allora e' equivalente ad un array, ma in generale puoi utilizzare la tecnica per strutture dati eterogenee.
Non e' l'unica tecnica da usare; altre due regole molto semplici per aiutare la cache sono
* Accessi temporalmente vicini dovrebbero accedere memoria fisicamente vicina. Il caso migliore e' quando riesci ad accedere la memoria "linearmente" nel qual caso riesci a sfruttare anche il prefetch
* Utilizzare meno memoria. Sembra banale, ma e' importante da tenere in mente. Una lista concatenata consumera' molta piu' memoria di un array in quanto devi memorizzare anche i puntatori. Nel caso di interi vuol dire che meta' della memoria (e quindi della cache) va via per memorizzare puntatori.