ECS back and forth

I’ll leave this topic to a part 2 that will follow shortly.

Well, yeah, for some definitions of shortly at least. :)

Here we are with the second part of the post about sparse sets and pointer stability.
We were left saying that no policy is the best policy during iterations. Let’s see how to achieve it.

Introduction

After using the ECS architecture for a while, I’ve to say that there are some features that I’m more than willing to pay a few cpu cycles for whenever possible.
Among the others, there is pointer stability. It helps to define some things in a simple and intuitive way (such as hierarchies) and avoids the introduction of subtle bugs due to reference invalidation. It also makes it trivial to interact with third-party libraries or use your own components in external data structures of any kind.

Sparse sets and independent pools models in general are pretty good at achieving pointer stability in an elegant way. However, like everything else in computer science, this too has a cost that must be assessed from time to time.
With the last post we saw how enabling pointer stability for a type that is iterated mainly linearly isn’t that good due to the tombstone check. However, even a type worth enabling may find itself leading an iteration over multiple components (for example, because it offers the shortest pool) and therefore introducing an extra cost in the loop.

To fully remove the costs due to the tombstone check, we’ve to take a step back and start with our representation of the entity identifier.

Entity identifier

Long time ago, I talked about the fact that we can embed both the actual entity and its version in a single identifier:

How many bits do we want to reserve for one or the other is an implementation detail and I’ll stick to what EnTT does for simplicity.
With this type of identifier in mind, we can introduce two distinct and equally useful concepts: the null entity and the tombstone version. Once again, the implementation details are a matter of tastes and the following is just one of the possibilities.

The null entity is a reserved value for the entity part of an identifier:

The version doesn’t really matter for a null entity, even though one can play with the imagination to make the most of it and make good use of the countless identities of a null entity.
Similarly, the tombstone version is a reserved value for the version part of an identifier:

This time we have less freedom, as this is usually directly associated with an entity to declare it as unusable.
A fully reserved identifier would therefore be the following:

Let’s see how all these are used in combination with a sparse set.

Sparse sets and reserved values

The null entity

With this post I described a technique to reduce the cost of the lookup in a sparse set.
Briefly, the idea is that of combining the null entity (that is, an identifier with a nullified entity part) with the sparse array, so as to avoid checking the packed array during a lookup. If the element in the sparse array is null, we know for sure that there is no match in the packed array.
This is a simplified version of the resulting lookup function (it doesn’t even take in consideration the fact that the sparse array is probably paginated, as described here):

bool contains(entity_type entity) const {
    const auto index = entity_to_index(entity);
    return index < sparse.size() && sparse[index] != null;
}

As you can see, we don’t need to visit the packed array to get the position of an entity. This saves quite a lot of time during iterations, mainly because we can discard elements earlier and reduce memory accesses.
Perhaps someone has also noticed that there is a problem with this approach but we’ll leave the details for a later paragraph. For years I’ve deliberately ignored it and it has never caused any problems. On the other side, it’s also true that this problem prevents the implementation of certain features and I can finally have them now that it’s fixed upstream.

The tombstone version

In the last post I instead described how we can use tombstones in the packed array to mark elements as deleted without having to swap-and-pop them.
This, combined with pagination, allows us to have pointer stability in any case, with all that goes with it. However, it also affects our contains.
If you remember the details (I recommend rereading the previous post otherwise), an implicit list is built that visits all the entities released up to a given moment. This means that, if we find ourselves iterating a pool with tombstones, all identifiers passed to the contains can have both a special version and a potentially valid entity part.
In other words, we need to update the above function as follows:

bool contains(entity_type entity) const {
    if(entity == tombstone) return false;
    const auto index = entity_to_index(entity);
    return index < sparse.size() && sparse[index] != null;
}

Otherwise, if we want to have an early exit, we can also review the loop at the call site (forgive the pseudocode, luckily I never really had to write it):

for(auto entity: pool.packed()) {
    if(entity != tombstone && check_all_other_pools(entity)) {
        // application code here
    }
}

In both cases, we’ve an additional branch and we know it: branches should be avoided whenever possible in tight loops.
Fortunately, there also exists an alternative. The careful reader may have already noticed that we have some bits left over.

Pitfalls and wastes of a sparse array

A weak contains

Let’s take a second look at the contains function above:

bool contains(entity_type entity) const {
    const auto index = entity_to_index(entity);
    return index < sparse.size() && sparse[index] != null;
}

This works fine as long as you’ve control over all storage objects. However, it also has a problem.
Briefly, if we pass an identifier for an entity with version N and the set contains that entity with version M, we are still returned true.

No one has even noticed this problem in years of EnTT but think what sneaky errors it could cause if users were managing their own pools.
Even more (but this time I’ll leave this for a future article), think about what features we could implement if there were a strict control also on the version (still without having to access the packed array, so as not to lose performance).

Wasted bits

In the sparse array we put either the position of the entity inside the packed array or a null entity (once converted to its underlying type).
Since the entity part of an identifier uses only the first N bits, we know that we cannot have more than N elements in a set. Moreover, an index won’t grow beyond the first N bits. Finally, we also know that the null entity occupies only the entity part of an identifier.

Did you notice anything? Indeed, the version part of an identifier is unused inside the sparse array.
We’re literally wasting a handful of bits on each entity when these could be so useful to us instead.

And finally came the version

I think at this point it’s obvious how having the version of an entity inside the sparse array can solve many problems, not only with regard to pointer stability.
Also, it seems clear to me that there is room for it, so let’s connect the dots.

The rules to follow are few and simple:

• Whenever you put the null entity in a slot of the sparse array, combine it with the tombstone version (that is, use your reserved identifier).

• In all other cases, slots must contain values such that their entity part is the index of the element in the packed array while their version part is the actual version of that element.

This is an image that should give you a rough idea of what I’m saying:

Once this is done, a single change to the contains function will fix both of the above problems (again, I’m ignoring the pagination of the sparse array for simplicity here, therefore expect a slightly more elaborated implementation from real world cases):

bool contains(entity_type entity) const {
    const auto index = entity_to_index(entity);
    return (index < sparse.size()) && ((~null & entity) ^ sparse[index]) < null;
}

How does this thing work? Let’s try to figure it out by examples.

Case: valid identifier

For valid identifiers, (~null & entity) returns the version part of the entity. As a consequence, ((~null & entity) ^ sparse[index]) returns a value that is less than null when the two versions match and higher than null otherwise.
There are two cases in which the two versions don’t match:

• The entity isn’t part of the set and therefore the version set in the sparse array is the tombstone version.

• The entity in the sparse set has a different version from the one provided for the check.

From what we can see, we’ve already solved all our problems with entity versions and the contains function doesn’t even need to access the packed array. After all, this was our goal, right?
So far, so good. Let’s see what happens in all other cases now.

Case: null entity

This is trivial. entity_to_index(null) returns an index that is always higher than sparse.size().
Therefore, null entities are rejected in all cases as it ought to be, no matter what.

Case: tombstone version.

In this case, (~null & entity) returns the tombstone version.
On the other hand, the entity part of our identifier can identify (by mistake) an element that is either part of the set or not.

If the element is actually part of the set, ((~null & entity) ^ sparse[index]) returns a value that is greater than null (once converted to an integral value). Therefore, the resulting value is false.
This is due to the fact that we’re combining a tombstone version with a valid version and the two will differ at least for a bit.

The other case around is slightly more interesting instead. Remember that we put a null entity with a tombstone version in the sparse array when the element isn’t part of the set. This means that ((~null & entity) ^ sparse[index]) will return null while the whole expression evaluates to false.
This is due to the fact that the two versions will match while the entity part of the identifier is actually null.

In other words, the test always fails for a tombstone version.

No policy is the best policy

If it’s true that pointer stability is a super nice feature, it’s also true that no policy is the best policy when it comes to iterating entities and components.
We’ve finally messed up both our sparse set and our contains function, completely removing the tombstone check (or rather, embedding it inside our check in a hopefully less expensive form). At this point, the caller as well as the sparse set can ignore whether or not we are using tombstones and always perform the same test.
Even more, by playing with tombstone versions and null entities we’ll also be able to introduce new modes in addition to pointer stability while maintaining the contains function fully agnostic.

I’m pretty sure that the solution presented here is neither the only nor the best possible one but it’s still a solution.
Unfortunately I’m not that smart, but I more than willingly accept suggestions to refine or replace this stuff, so get in on it!

Now we just have to talk about what allows us to do having solved the problem of checking the versions inside the contains function… maybe next time? :)

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 that you appreciate my work.

Thanks.