How to benefit from cpu cache in a entity component system game engine?

Question

I often read in the ECS game engine documentations that is a good architecture for using cpu cache wisely.

But I can't figure how we can benefit from cpu cache.

If components are saved in an array (or a pool), in contiguous memory, it's a good way to use cpu cache BUT only if we read the components sequentially.

When we use systems, they need entities list which are list of entities that have components with specific types.

But these lists give the components in a random way, not sequentially.

So how to design a ECS to maximize the cache hit ?

EDIT :

By example, a Physic system needs an entities list for entity that has the RigidBody and Transform components (There is a pool for RigidBody and a pool for Transform components).

So its loop for updating entities will be like this :

for (Entity eid in entitiesList) {
    // Get rigid body component
    RigidBody *rigidBody = entityManager.getComponentFromEntity<RigidBody>(eid);

    // Get transform component
    Transform *transform = entityManager.getComponentFromEntity<Transform>(eid);

    // Do something with rigid body and transform component
}

The problem is that the RigidBody component of entity1 can be at the index 2 of its pool and the Tranform component of entity1 at the index 0 of its pool (because some entities can have some components and not the other and because of adding / deleting entities / components randomly).

So even if components are contiguous in memory, they are read randomly and so it will have more cache miss, no ?

Unless there is a way to prefetch the next components in the loop ?

Answer 1

Mick West's article explains the process of linearising entity component data, in full. It worked for the Tony Hawk series, years ago, on much less impressive hardware than we have today, to greatly improve performance. He basically used global, pre-allocated arrays for each distinct type of entity data (position, score and whatnot) and references each array in a distinct phase of his system-wide update() function. You can assume that the data for each entity would be at the same array index in each of these global arrays, so for instance, if the player is created first, it might have its data at [0] in each array.

Even more specific to cache optimisation, Christer Ericsson's slides for C and C++.

To give a bit more detail, you should try to use contiguous memory blocks (most easily allocated as arrays) per each type of data (e.g. position, x y and z), to ensure good locality of reference, utilising each such data block in distinct update() phases for the sake of temporal locality i.e. to ensure the cache isn't flushed via the hardware's LRU algorithm before you've reused any data you intend to reuse, within a given update() call. As you've implied, what you don't want to do is to allocate your entities and components as discrete objects via new, as data of different types on each entity instance will then be interleaved, reducing locality of reference.

If you have interdependencies between components (data) such that you absolutely cannot afford to have some data separated from it's associated data (eg. Transform + Physics, Transform + Renderer) then you may opt to replicate Transform data in both the Physics and Renderer arrays, assuring that all pertinent data fits the cache line width for each performance-critical operation.

Remember also that L2 and L3 cache (if you can assume these for your target platform) do a lot to alleviate the problems that L1 cache may suffer, such as a restrictive line width. So even on an L1 miss, these are safety nets that will most often prevent callouts to main memory, which is orders of magnitude slower than callouts to any level of cache.

Note on writing data Writing does not call out to main memory. By default, today's systems have write-back caching enabled: writing a value only writes it to cache (initially), not to main memory, so you will not be bottlenecked by this. It is only when data is requested from main memory (won't happen while it's in cache) and is stale, that main memory will be updated from cache.