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

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 ?

• can you show us how are you allocating each component? – concept3d Dec 4 '13 at 20:51
• With a simple pool allocator and a Handle manager for having component reference to manage relocation of components in the pool (to keep the components contiguous in memory). – Johnmph Dec 4 '13 at 21:15
• Your example loop presumes that component updates are interleaved per-entity. In many cases it's possible to update components in bulk by component type (eg. update all rigidbody components first, then update all transforms with the finished rigidbody data, then update all rendering data with the new transforms...) - this can improve cache use for each component update. I think this type of structure is what Nick Wiggill is suggesting below. – DMGregory Dec 4 '13 at 21:17
• It's my example which is bad, in fact, it's more the "update all transforms with the finished rigid body data" system than the Physic system. But the problem stays the same, in these systems (update transform with rigid body, update rendering with transform, ...), we will need to have more than one type of component at the same time. – Johnmph Dec 4 '13 at 21:20
• Not sure if this may be relevant too? gamasutra.com/view/feature/6345/… – DMGregory Dec 5 '13 at 3:51

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.

• Just a note for anyone who might be new to C++: std::vector is basically a dynamically-resizeable array and hence is also contiguous (de facto in older C++ versions and de jure in newer C++ versions). Some implementations of std::deque are also "contiguous enough" (though not Microsoft's). – Sean Middleditch Dec 4 '13 at 18:27
• @Johnmph Quite simply: If you don't have locality of reference, you don't have anything. If two pieces of data are closely related (such as spatial and physics information), i.e. they are processed together, then you may well have to compact them as a single component, interleaved. But bear in mind then that any other logic (say, AI) that leverages that spatial data may then suffer as a result of the spatial data not being included alongside it. So it depends on what requires the most performance (perhaps physics in your case). Does that make sense? – Engineer Dec 4 '13 at 20:53
• @Johnmph yes, I totally agree with Nick it's about how they are stored in memory, if you have entity with pointers to two components that are far away in memory you don't have locality, they have to fit in a cache line. – concept3d Dec 4 '13 at 20:57
• @Johnmph: Indeed, Mick West's article assumes minimal interdependencies. So: Minimise dependencies; Replicate data along cache lines where you cannot minimise those dependencies... e.g. include Transform alongside both RigidBody and Render; and in order to fit cache lines, you may need to reduce your data atoms as much as possible... this could be achieved in part by going from floating point to fixed point (4 bytes vs 2 bytes) per decimal point value. But one way or another, no matter how you do it, your data has to fit the cache line width as concept3d noted, for maximal performance. – Engineer Dec 4 '13 at 21:20
• @Johnmph. No. Whenever you write Transform data, you simply write it to both arrays. It's not those writes you need to be worried about. Once you send off a write, it's as good as done. It's the reads, later on in the update, when you run Physics and Renderer, that must have access to all pertinent data, immediately, in a single cache line right up close and personal to the CPU. Also, if you really need it all together, then you either do further replications or you make sure physics, transform and render fit a single cache line... 64 bytes is common and is actually quite a lot of data!... – Engineer Dec 4 '13 at 21:53