After publishing part 2 of the ECS back and forth series (if you haven’t read it yet, do it now), I received several requests for further information on sparse sets. In particular, requests for more details on the grouping functionalities and on the support they can offer to different access patterns (sequential, random, …).

The grouping functionalities are a topic that can often be found online in the lines of posts or comments. To be honest, I’ve struggled to put the pieces together in the past and this is why I think it’s useful to collect all the information I gathered so far in this post.
I’m pretty sure that out there, somewhere, there’s another me going down the same road and I hope this can help him.

Introduction

As a wise boy once said in a chat where I was by chance:

50% of time you loop components, 50% you access them random, 50% is other access pattern.

Therefore, supporting a single access pattern would be limiting and that’s why there are techniques for sparse sets to allow users to decide where and how they want to access things.
Be aware that this doesn’t mean sparse sets are a one-fits-all solution to use for all your needs in terms of access patterns. However, as long as they support it elegantly, there is no reason not to use them and to squeeze the best from a sparse set.

Ironically, when you take grouping functionalities to the extreme (that is what EnTT does with its full-owning groups), this technique offers also a way to do perfect SoA (citing the words of another smart person who has contributed largely to this idea).
In the following I will try to explain what EnTT offers with its groups, how they are implemented and why these are available in different flavors (that is full-, partial- and non-owning groups), each with different features.

A quick recap

From part 2 we know how a sparse set works. The most trivial implementation when used as a pool for components is such that it is composed by three vectors:

  • The sparse array, also known as reverse array.
  • The packed array, also known as dense or direct array.
  • A component array sorted the same of the packed array.

The implementation will be in charge to keep the packed array and the component array in sync (eg whenever it swaps two elements in the packed array, it must swap the elements at the same positions also in the component array).

So far, so good. Sequential access during iterations is blazing fast for obvious reasons. Random access is fast as well thanks to the properties of the sparse set.
This gives use the best solution ever to iterate a single component and a very good approach for random access, insertion and deletion in general.

When it comes to iterate multiple components at once, that is multiple sparse sets, a pretty fast approach is that of getting the shortest one (the sparse set whose packed array is shorter), then probe the entities before to return them to the caller to test if they have assigned all the components.
The two main problems are that:

  • The two sets aren’t necessarily sorted the same. In fact, they could be ordered completely differently from each other. Sparse sets allow users to sort the items they contain and sort them in the order dictated by another sparse set is pretty fast if you know the trick to use to do that. However, this doesn’t give us the necessary guarantees anyway, although it helps to increase the performance reducing the cache misses.

  • We don’t know how many entities have both the components. What we know is that they cannot be more than the size of the shortest packed array, that’s all. In most cases it’s already enough to improve indecently the performance (imagine you’ve 200k entities still alive but only 100 of them have assigned one of the two components), but the feel is that we can do more.

This isn’t as good as it could be at a first glance, right? To be honest, it’s good enough for the majority of cases, I wouldn’t care much of it. This approach is already by far faster than most of the implementations out there and has some nice-to-have features that make it a really good solution.
However, what if we have a very critical path and we do want more on sequential access and iterations in general? Is it possible?
The answer is obviously yes. That’s what I’ve called groups (just because I’ve no idea if a name already exists and this seemed appropriate).

Groups

The idea behind the groups is straightforward. Imagine you have two sparse sets, one for the component A and one for the component B. They already contain some entities, none of which have both the components. A group for (A, B) is empty at this point:

A packed    : [e3|e7|e8|e6]
A component : [A0|A1|A2|A3]
     group ___^

B packed    : [e4|e5]
B component : [B0|B1]
     group ___^

I omitted the sparse array, because it’s pointless for the purpose of the discussion.
As you can see, the group points (whatever it means to point for a group) to the first element of the array. We can look at it as if the group pointed past the last element contained, that is no elements at all in this case. Another way of looking at it is as if it were pointing to the first available position to use to add more elements to the group.

Let’s add B to entity e7 and see how it works. When you do that, you’re guaranteed that e7 isn’t part of the group yet, mainly because it didn’t have B before.
Immediately after adding B to entity e7, the sparse sets will appear as follows:

A packed    : [e3|e7|e8|e6]
A component : [A0|A1|A2|A3]
     group ___^

B packed    : [e4|e5|e7]
B component : [B0|B1|B2]
     group ___^      ^___ assign B to e7

All what is needed now is to literally move the entity e7 within the group.
To do that, we can swap the entity after the one pointed by the group with the one to which we’ve just attached the component, then advance the group. This must be done for both the sparse sets:

A packed    : [e7|e3|e8|e6] <-- swap e7 with e3
A component : [A1|A0|A2|A3]
     group ______^

B packed    : [e7|e5|e4] <-- swap e7 with e4
B component : [B2|B1|B0]
     group ______^

What if we add A to the entity e4 then? That’s easy, same operations and the group keeps growing up:

A packed    : [e7|e4|e8|e6|e3]
A component : [A1|A4|A2|A3|A0]
     group _________^

B packed    : [e7|e4|e5]
B component : [B2|B0|B1]
     group _________^

By construction, the sparse sets contain the entities that are part of the group at the top of their packed arrays, all ordered the same. We will see shortly what are the benefits due to this aspect.
However, it would be nice if this continued to be true even after removing items from a group. Fortunately, it’s easy to achieve. Whenever we remove a component from an entity that belongs to a group, we know that it’s before the one pointed out by the group itself. This is by construction. To update our implicit list of entities and components of interest, it’s enough to swap the entity that is exiting the group with the last one contained in it, then move the group (that is, it’s pointer, whatever it is) back of one step.
As an example, let’s imagine we want to remove component B from entity e7. Before to do that, we swap it with entity e4:

A packed    : [e4|e7|e3|e8|e6] <-- swap e7 with e4
A component : [A4|A1|A0|A2|A3]
     group _________^

B packed    : [e4|e7|e5]  <-- swap e7 with e4
B component : [B0|B2|B1]
     group _________^

Then we update the group so that it points to entity e7 (remember, a group points to the element past the last one that belongs to the group itself):

A packed    : [e4|e7|e3|e8|e6] <-- reduce the size of the group
A component : [A4|A1|A0|A2|A3]
     group ______^

B packed    : [e4|e7|e5] <-- reduce the size of the group
B component : [B0|B2|B1]
     group ______^

Finally, we can easily remove B from entity e7. It means usually that we want to swap the entity with the last one in the sparse set before to pop out it. This is the best way to keep the internal arrays packed. The result is:

A packed    : [e4|e7|e3|e8|e6]
A component : [A4|A1|A0|A2|A3]
     group ______^

B packed    : [e4|e5] <-- swap e7 with e5, then pop out e7 and its component
B component : [B0|B1]
     group ______^

That’s all. As we assign a component to an entity or remove it, it potentially becomes part of a group or exits it. Consequently the tail of the group is lengthened and is shortened depending on the case.
Within our sparse set we’ll still have all the entities and components tightly packed for blazing fast iterations. Furthermore, the sparse sets involved by the group will be such that the first N elements of their packed arrays also contain the entities and components of interest, ordered the same. This is kind of the best we can obtain in terms of performance, because we have in fact N arrays of the same size and all ordered the same. All what we have to do is to iterate them from the first to the last element and return everything as-is to the caller. No jumps, no indirection, no test of validity, just pick the elements and return them. That’s all.

Obviously, there is a price to pay for this, as for everything else. In this case, the creation and destruction of components is affected by a group to an extent. Nothing that you’ll really notice in real world applications probably, mainly because construction and destruction aren’t usually done along critical paths and it’s unlikely you’re to construct or destroy 1M entities or components every tick. Note also that this price is paid only when entities enter or exit a group, not all the times they are added or removed a component, like it happens with some other solutions (you’ve read part 2 of this series, right?). Therefore, the overall cost will be in general low in all cases. On the other side, as long as the choice of where to pay the price for what we want remains ours, it is up to us to decide and there is nothing better.

Only one thing remains to be clarified: why does EnTT then offer different types of groups?
It’s a matter of ownership. As some will have guessed, a type of component cannot belong to more than one group, because it’s not possible to induce more than one sub-set in an array (this isn’t properly true, but let’s say that it’s a good approximation if you don’t want to ruin the performance and make things more complex than what is needed). However, the possible optimizations with this tool don’t stop here and this is why EnTT offers more than one type of groups.

Full-owning groups

Full-owning groups are such that they literally own all the pools of their types of components. Therefore, they can create subsets within the packed arrays as described before.
This is the fastest group (as in fast to iterate entities and components) you can construct. For N types of components, we have N packed arrays, each of which we know to contain M elements at the top all ordered in the same way. All what is needed to iterate them is to start from the first element and return instances to the caller, a tuple at a time for M times. Just advance a bunch of pointers and return what you obtain. Cache misses are intuitively reduced to a minimum.

Partial-owning groups

What if I want to define two groups, one for components A and B, the other one for components B and C?
Ownership of B cannot be shared between two groups, so are we hopeless here? Not yet in fact, we can still give a performance boost to our iterations.

Let our first group take ownership of components A and B and therefore be a full-owning group. The second group will take then the ownership of C and will use B as a free-type, that is a type of component that takes part in the definition of the group but in whose packed array we cannot create a subset.

How does this work? It’s simple. Whenever an entity enters or exits the group, we arrange things as shown previously, this time only in the sparse set for C.
Iterations will benefit quite a lot from this. First of all, the extent of the group tells us the exact number of entities to return. Even more, we know exactly what these entities are, because the sparse set of C has them at the top of its array, ordered the same of their components. This is already a huge boost in terms of performance. To get B, instead, we will have to pay the price of the indirection, fortunately very low due to the properties of the sparse sets. However, we don’t have to test anymore entities to know if they have B because we know that they have it, being them in the group. We can then go directly to the component and return it.

Non-owning groups

The logical consequence is the case in which we have three groups: one for components A and B, one for components B and C and one for components A and C.
Oh oh. the first one is a full-owning group. The second one is a partial-owning group. Right. What about the third one instead?

This is less frequent a case, but still possible. This time, we track only the entities that deserve to belong to the group, even though we cannot create subsets in already existing arrays. Instead, we use an additional sparse set to keep the identifiers packed in an array to iterate later.
We don’t have the benefits of having all or some of the components ordered the same, but at least we know how many entities are in a group and we don’t have to test them before to get the components. Therefore, we can go directly to the instances. We have to pay the price of indirection for that, of course, but the properties of the sparse sets help to keep this price low.

Some further optimizations exist for this case tha can be applied also to the partial-owning groups. As an example, one can cache the indexes used during the first iteration to avoid the indirection later on in absence of changes.
In my experience, since we have full freedom of decision, one tends to use full-owning groups where the performance matter and non-owning groups (if necessary) along less critical paths or where the iterations aren’t the bottleneck. Therefore, these optimizations tend only to complicate the whole thing and to increase memory usage without real benefits.

Free as in free to choose

Sparse sets allow for different solutions to improve sequential access and therefore iterations, from the blazing fast full-owning and partial-owning groups to the slightly slower non-owning groups. This without considering that the model without groups already offers more than sufficient performance for the vast majority of cases.
A full-owning group is probably the best we can obtain in terms of performance with a bunch of sparse sets used as pools: packed arrays all ordered the same and of which the size is known. On the other hand, indirection pulls in a price to pay for partial-owning and non-owning groups. It’s due mainly to the fact that shared ownership isn’t possible with groups.

One of the most interesting aspects is that groups can be created on the basis of our usage patterns and the ownership model can be chosen depending on whether a query is made on a critical path or not. In fact, paths often exist along which bottlenecks aren’t in iterations on entities and components and, in these cases, one can freely decide not to use a group.
This leaves us full control unlike other more automated solutions, but also shifts the responsibility to make the right choice on the users, which is not something for everyone.

Let me know that it helped

I hope you enjoyed what you’ve read so far.

If you liked this post and want to say thanks, consider to star the GitHub project that hosts this blog. It’s the only way you have to let me know.

Thanks.