Accesso alla memoria compatibile con la cache in fisica ristretta e loop di collisione

Question

Sto scrivendo un motore fisico e ho difficoltà a trovare un buon modo per progettare l'archiviazione dei dati.

La funzionalità che voglio:

• avere una classe che rappresenta un PhysicsBody
• avere una classe che rappresenta un volume di collisione (diciamo una scatola)
• Ogni organismo fisica può avere un altro volumi di collisione collegati ad esso
• È possibile avere un corpo fisico senza volume di collisione
• Opzionale: CollisionVolume senza un corpo fisico. (pensa a Trigger Volumes)

In questo momento ho fondamentalmente due cicli. Uno che aggiorna i corpi fisici nella simulazione. Aggiorna la loro posizione/velocità/rotazione. Il secondo ciclo esegue il rilevamento delle collisioni su tutti i volumi di collisione. È solo un ciclo annidato per il controllo delle collisioni tra ogni coppia di volumi di collisione. (So ​​che può essere fatto meglio ma questo è un argomento separato)

So che il modo ideale è quello di memorizzare gli oggetti in matrici contigue.

std::vector<PhysicsBody> m_bodies; 
std::vector<CollisionVolume> m_colliders; 

problemi che ho trovato con questo approccio:

• La sua difficile da mantenere PhysicsBody -> rapporto CollisionVolume. Ad esempio, se voglio rimuovere un CollisionVolume dal mio vettore, lo cambierò con l'ultimo e tornerò indietro. I dati vengono spostati e se ho memorizzato un indice su CollisionVolume in PhysicsBody, non è più valido.
• Ogni volta che distruggo un PhysicsBody, il distruttore controllerà se vi è un eventuale volume di collisione collegato e rimuoverlo in modo appropriato anche dal sistema Physics. Il problema è che un vettore produrrà copie interne e le distruggerà e quando ciò accadrà causerà il caos rimuovendo i volumi di collisione che non avrebbero dovuto essere rimossi.
• CollisionVolume è in realtà una classe base (non deve essere) e altre classi derivano da essa come scatole/sfere e cosa no. Potrei potenzialmente non usare l'ereditarietà e trovare qualche altro design complicato, ma questo è qualcosa da tenere a mente.

Ho cercato di trovare un modo intorno ad esso, ma ha finito per memorizzare i puntatori invece:

std::vector<PhysicsBody*> m_bodies; 
std::vector<CollisionVolume*> m_colliders; 

La soluzione migliore per la cache riducendo al minimo non trova che mi è venuta è stata sovraccarico new/delete e la conservazione di questi oggetti in un pool di memoria solo per il sistema fisico.

Esistono altre soluzioni migliori? Ovviamente le prestazioni sono fondamentali.

Answer 1

Una domanda fondamentale: in assenza di thread in esecuzione e modifica di dati da diversi core (CPU), dove si vede la necessità di preoccuparsi dei costi di coerenza della cache?

Il protocollo di coerenza della cache viene attivato solo quando una linea viene sporcata su un nucleo diverso dal nucleo del lettore o viceversa.

Sembra che in realtà si intendesse la cache-locality? È giusto?

Con la coerenza vs. località fuori mano, ecco la mia risposta:

Nel momento in cui vai al vettore, hai perso il controllo diretto della gestione della località. Puoi recuperarne una parte disponendo di un pool di memoria. Tuttavia, dovresti fare i conti con il riposizionamento associato alle operazioni di ridimensionamento.

Conosci il numero di elementi in anticipo? Se sì, puoi farlo.

vector<T> myVec; 
myVec.reserve(NUM_ELEMS); 

seguito da un nuovo posto per ogni oggetto da un'area contigua di memoria.

myvec[i] = ... 

La memoria per il vettore e gli elementi potrebbe provenire interamente da un singolo pool. Questo può essere ottenuto passando in un allocatore personalizzato durante l'istanziazione di std :: vector. Vedere il seguente:

• Custom allocator in std::vector
• https://github.com/johannesthoma/mmap_allocator

Answer 2

Un modo semplice per evitare di perdere i blocchi di località e di memoria fusibile MEM insieme per colpire meglio la cache è quello di mantenere semplicemente gli elementi di fisica rimosse al il vettore per evitare di invalidare gli indici, ma contrassegnarli come removed in modo da poter recuperare quegli spazi vuoti negli inserimenti successivi.

Qui, se si vuole percorrere l'intero percorso di creazione del proprio contenitore, è davvero utile se si desidera ancora richiamare i distruttori su questi oggetti rimossi per capire come vengono implementati i contenitori STL utilizzando "posizionamento nuovo" e invocazioni manuali del distruttore per evitare di richiedere cose come un operatore di assegnazione per il tipo T.

È inoltre possibile inviarli a un elenco di indici liberi da recuperare ogniqualvolta si inserisce uno nuovo, o ancora più veloce, trattare uno di questi elementi come unione a un puntatore elenco, ad esempio:

union PhysicsNode 
{ 
    PhysicsBody body; 
    PhysicsNode* next_free; 
}; 
PhysicsNode* free_physics_nodes; 

Lo stesso vale per il nodo di collisione . In questo caso, stai trattando questo PhysicsNode come se fosse un PhysicsBody quando è "occupato" e come un nodo di elenco collegato singolarmente quando è "libero" o "libero" da recuperare.

Purtroppo si cerca di affrontare il problema a questo livello spesso ha si scherzi con meccanismi orientata agli oggetti di design, costruttore e distruttore, ecc

Quindi, quando si desidera che questo tipo di efficienza insieme a tutta la programmazione orientata agli oggetti goodies, questo è il momento in cui potresti essere tentato di risolvere questo problema, fondamentalmente allo stesso modo, a livello di allocatore di memoria.

Answer 3

Vorrei sottolineare le differenze significative nel modello di dati se si prevede di utilizzare il motore vettoriale (GPU) per il calcolo o meno. Il tipico layout dei dati segue OOP e si chiama Array-of-Structures. Per utilizzare un motore vettoriale di qualche tipo, i dati devono essere riorganizzati in Structure-of-Arrays. Altro su argomento dalla Intel

https://software.intel.com/en-us/articles/creating-a-particle-system-with-streaming-simd-extensions