Cache-friendly memory access in tight physics and collision loops

Question

I am writing a physics engine and having a hard time figuring out a good way to design my data storage.

The functionality that I want:

• Have a class that represents a PhysicsBody
• Have a class that represents a collision volume (Lets say a box)
• Each physics body can have one more collision volumes attached to it
• Possible to have physics body without a collision volume
• Optional: CollisionVolume without a physics body. (think Trigger Volumes)

Right now I have basically two loops. One that updates the physics bodies in the simulation. It updates their position/velocity/rotation. The second loop performs collision detection over all the collision volumes. Its just a nested for loop that checks for collisions between each pair of collision volumes. (I know it can be done better but that's a separate topic)

I know that the ideal way is to store objects in contiguous arrays.

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

Problems I found with this approach:

• Its hard to maintain PhysicsBody -> CollisionVolume relationship. For example, if I want to remove a CollisionVolume from my vector, I would swap it with the last one and pop back. Data gets moved and if I stored an index to a CollisionVolume in PhysicsBody, its no more valid.
• Anytime I destroy a PhysicsBody, the destructor will check if there was any collision volume attached to it and appropriately remove that from the Physics system as well. Problem is that a vector will make internal copies and destroy them and when that happens it will wreak havoc by removing collision volumes that weren't supposed to be removed.
• CollisionVolume is actually a base class(doesn't have to be) and other classes derive from it like boxes/spheres and what not. I could potentially not use inheritance and come up with some other complicated design, but this is something to keep in mind.

I tried hard to find a way around it but ended up storing pointers instead:

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

The best solution to minimizing cache misses that I came up with was overloading new/delete and storing these objects in a memory pool just for the physics system.

Are there any other better solutions to this? Obviously performance is key.

Answer 1

A fundamental question: In the absence of threads running and modifying data from different cores(CPUs), where do you see the need to care about cache-coherency costs?

Cache-coherency protocol is triggered only when a line gets dirtied on a core different from the reader core or vice-versa.

It appears that you actually meant cache-locality? Is that right?

With the coherency Vs. locality out of the way, here is my take:

The moment you go to the vector, you lost direct control of managing locality. You can get back some of it by having a memory pool to draw from. Still, you would have to contend with relocation associated with resize operations.

Do you know the number of elements upfront? If yes, you can do this.

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

followed by in-place new for each object from a contiguous area of memory.

myvec[i] = ...

The memory for the vector and the elements could entirely come from a single pool too. This can be achieved by passing in a custom allocator while instantiating the std::vector. Please see the following:

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