Polymorphism vs cache-friendliness

Question

How can we combine inheritance-based polymorphism with spatial cache friendly data structures? In a simple game engine we usually have some base Entity class which is inherited from to implement the various distinct game entities. These entities are then stored by pointer in a large array of some kind, which is iterated over for updating, rendering and so on.

However this leads to bad performance because entities will be randomly scattered throughout memory. One way I thought of to fix this problem is to have a separate array for each entity type, for example:

Goblin goblins[100];
Human humans[100];
Demon demons[100]; 
Entity* entities[300]; 

My question is: Is there a more elegant solution than that? The separate arrays approach requires rewriting the core functions of the engine itself every time I want to add or remove an entity type in the game implementation. I'm looking for a general solution which doesn't care about what the subclassed entity types are as long as they inherit from a common ancestor.

Answer 1

I wouldn't do that, as you'd complicate things unnecessarily. Keep a single generic list of entities and compact toward the beginning of the array every so often. That way you will get far fewer cache misses (unlikely you'll eliminate them altogether unless you make your dataset sufficiently small). It's also bad form to type various species as you have there; you should just be using Entity, composed of components describing differences between the species. Favour composition over inheritance.

Compaction means updating entity indices everywhere in memory; otherwise you face broken links.

Look into cache-oblivious algorithms to understand how to achieve best cache performance, but note that not every problem is suited to eliminating cache misses entirely. Key is to minimise them.

P.S. If you haven't wrapped your head around implementing Entity-Component Systems yet, you'd do well not to worry about optimising cache any time too soon. Work on the basics first - long road.

Answer 2

If the costs of dynamic dispatch/indirect function calls and optimization barriers are genuinely too great and exhibit a tendency to degrade spatial locality, then the straightforward solution is model your design at a less granular level.