In the last installment of this series, we talked about handles/internal references in the Molecule Engine, and discussed their advantages over raw pointers and plain indices.
In a nutshell, handles are able to detect double-deletes, accesses to freed data, and cannot be accidentally freed – please read the previous blog post for all the details.
This time, we will introduce IDs or external references, which also allow us to move individual items around in memory without anybody noticing. But why would we want to do that?
The answer is quite simple: Molecule’s world/unit-management uses an entity-component-system, where each entity is defined by the components it consists of. Components are small, orthogonal pieces of data, and individual systems are responsible for handling the corresponding components. All of the components are simple PODs, and do not contain any logic or code at all; all code resides in invidivual systems.
As an example, a SkinnedMeshComponent stores various handles that refer to the mesh data, to a double-buffered vertex-buffer that contains the skinned data, and to shaders and a material. It does not contain any code, and can be mem-copied at will.
The SkinnedMeshSystem is responsible for handling the components: it owns all the components, creates and destroys them, and updates and renders them.
So why do we need to shuffle individual items in memory?
- Creating and destroying components should be an O(1) operation. If not, performance could severely deteriorate after playing for several hours, or when creating lots of components.
- Iterating over all components in order to update them should cause as few cache misses as possible. Therefore all items should be packed densely and contiguous in memory, like an array.
Clearly, those two requirements are at odds with each other. We can create and destroy components in O(1) by using a free-list, which solves our first problem. But then we cannot iterate over all components in a cache-friendly manner.
On the other hand, using a simple array fulfills our second requirement, but creating and destroying components becomes an O(N) operation if we don’t use any auxiliary data structures.
A custom data structure
As with so many progamming problems, an extra indirection will do the job.
Instead of using either a free-list or an array, we will in fact use both: a sparse array managed by a free-list, and a dense array that holds the individual components.
The sparse (outer) array stores indices into the dense (inner) array, and a generation for each item. This generation is our monotonically increasing integer that was introduced last time. The dense array stores the items contiguously in memory, just like a regular array.
Components in such an array are not referenced by handles, but by so-called IDs. An ID stores an index into the sparse array, along with the generation at the time of creation.
Let’s detail the performance characteristics of operations that need to be performed on such a data structure:
- Creating a component consists of adding a new component at the end of the dense array (O(1)), and allocating a new slot in the sparse array using an in-place free-list (O(1)). The slot stores an index into the inner array, and the user holds on to an ID that is a „smart index“ into the outer array (O(1)).
- Destroying a component means that the slot depicted by the ID needs to be returned to the free-list (O(1)), and that the component needs to be removed from the inner array. This can be done in O(1) by simply swapping the removed component with the last in the array, properly updating the corresponding index from the outer to the inner array as well.
- Accessing a component causes an additional cache-miss because of the extra indirection: we first need to access the sparse array in order to fetch the index, and retrieve the component from the inner array using that index.
- Iterating over all components is a simple for-loop over the dense array, causing the least number of cache-misses possible.
As can be seen, creation and destruction is O(1), and iterating over all components is like iterating through an ordinary array. The only drawback is the extra cache-miss for each external access to a component. Arguably, accesses from outside the individual component-systems should be far fewer than internal data accesses each frame, therefore such a data structure should be a win in almost all situations.
Additionally, if you’re careful, look-ups for certain components can be done once a frame, and the pointer to the underlying component can be cached for one frame. I would not recommend doing this, but it can be beneficial if you really need to access a thousand individual components several times each frame.
The Bitsquid Engine uses a similar data structure called the packed array, but my implementation differs from Niklas’.
In Molecule, I use IDs for referencing all kinds of components. The user only ever sees the ID, and nothing else. Hence, IDs share all the benefits with handles, and have some additional ones as well, especially in conjunction with an entity-component system: you do not need a base class for your components, because an entity can simply store an array of IDs/integers. This creates even less coupling between components and entities.
This was the last installment in the mini-series about ownership and data references, hope you enjoyed it!