Data oriented design in physics engine

Question

I am new to data oriented design and I am currently developing a physics engine as a hobby project. I am really interested in data orinted design but I am not sure how to apply data oriented design to my physics engine. I am using Box2D as a reference and when I look at the source code, erin catto use linked list as a container for rigid bodies. The reason why he use linked list over array is stated here. This is what he stated at the forum

I could use an array of body pointers. That would have worse cache performance. First you have to get the array element, then the element data. I would also need some extra logic to ensure the array is big enough.

I'm not sure how I would use an array of bodies. If I resize the array, the pointers become invalid. I could return an index when you create a body, but then the array would have holes as bodies are freed. Traversing the body array would then involve extra logic to see if the body is allocated or destroyed. Also, it may be cumbersome for users to have to use an index rather than the object itself. If I return the current body pointer from the index, there will likely be many bugs where users hold onto that pointer and it becomes invalid.

Finally, when islands are created the set of bodies is likely no to be contiguous in memory.

I will add that when the physics engine do a broadphase collision detection, It will return a list of collider pairs that will most likely located randomly at memory. From what I understand, you need something like handle so the data can be moved around in memory. With handle, you only need to move the last object to the slot that holds the deleted object. Using handle over pointer will add an extra level of indirection which results in more cache misses. So is it really beneficial to store a set of rigid bodies or their components as array?

Edit: I believe there are parts of physics engine that benefit from storing rigid body using array. For example the integration phase. But I am not sure if the benefits outweight the disadvantages.

Answer 1

What you should optimize for is probably best shown in and around slide 40 of this presentation: http://www.slideshare.net/cellperformance/gdc15-code-clinic

The idea is to prevent the code from doing wasteful things with the CPU. Loading memory and then throwing it away is rather wasteful. So, naturally, you can reorder data to make better use of it. If you see a commonly used function that uses a certain set of variables, you'll want to make sure that they can be loaded on as little cache lines as possible by putting them close together and aligning them properly in memory.

With sufficiently complicated physics engines (ignoring fixed size particle system solvers), given that bodies contain lots of data and are rarely accessed sequentially, there aren't too many other optimizations to perform.

So is it really beneficial to store a set of rigid bodies or their components as array?

One extra allocation (when compared to intrusive linked lists), addition time is almost always O(1) (certain additions will trigger a resize of the array memory, but only in the beginning and can be largely avoided), removal is O(1) (when using the swap-with-last trick, since order doesn't matter), iteration requires indirection, but it doesn't happen frequently. Intrusive linked lists - O(1) addition, O(1) removal, no extra allocations, no indirection on iteration.

Intrusive linked lists look better than arrays but arrays are not far behind for this use case. Expect the performance for both to be fairly similar. The Bullet physics engine uses arrays, by the way.

P.S. Plain linked lists (like std::list) would require one more allocation for each node (since it only accepts copies of values to store, and that's not an option with physics bodies, so pointers would have to be used) and require extra indirection, so I'd recommend avoiding those.