Robust handling of version and entity ID overflow

[emsai]

I am interested in an entity implementation that handles version overflow and maxing out entity ids more robustly.

As noted in #761, long running applications that continuously delete and create entities can run into issues with the version number associated with an entity overflowing and incorrectly causing destroyed entities to be reported as valid. The behavior when the entity ID overflows is also undefined.

Here is a potential way of eliminating the version overflow issue. For simplicity, I have described it using shared pointers for the entities, but this could be adapted to an implementation that stores the underlying data in a compact representation, using similar techniques to what is done for the registry vector. The code is just meant to give an idea of the approach and isn't intended as an actual implementation.

This implementation matches what entt does already, except that it separates the storage of the entity value from the allocation in the registry's vector, which eliminates the need for versions and issues associated with versions overflowing.

// Assume the registry has the following member variables:
std::vector<std::shared_ptr<uint32_t>> entities;
uint32_t head = std::numeric_limits<uint32_t>::max();

// Entity creation
std::shared_ptr<const uint32_t> create() {
      std::shared_ptr<uint32_t> entity;
      if (head == std::numeric_limits<uint32_t>::max()) {
               entity = std::make_shared<uint32_t>(entities.size());
               entities.push_back(entity);
      } else {
               entity = entities[head];
               uint32_t temp = head;
               head = *entities[head];
               *entities[head] = temp;
      }
      return entity;
}

// Entity destruction
void destroy() {
      uint32_t new_entity_index = *entity;
      entities[new_entity_index] = std::make_shared<uint32_t>(head);
      head = new_entity_index;
      *entity = std::numeric_limits<uint32_t>::max();
}

void is_valid(std::shared_ptr<const uint32_t> entity) {
    return *entity != std::numeric_limits<uint32_t>::max();
}

With this approach, version numbers are not needed anymore. Just one value (already reserved as null in entt) needs to be reserved to indicate that an entity is invalid. So more bits are freed up for the ID, which could help eliminate reaching the simultaneous entity ID limit as well.

Any thoughts on this approach and how feasible it would be to include in entt? Would it be possible to abstract the entity type used by the registry to accommodate this approach in addition to the existing behavior?

I would be interested in hearing about other suggestions for improving robustness as well.

[skypjack]

The behavior when the entity ID overflows is also undefined.

What do you mean exactly? Currently, it just wraps to 0. It's pretty well defined.

With this approach, version numbers are not needed anymore. Just one value (already reserved as null in entt) needs to be reserved to indicate that an entity is invalid.

There is a difference between an invalid entitiy and an entity with an updated version though. That is more or less the reason for which the version exists.
I can't really see how you would make this work without handles, as in without dynamically allocated entities. On the other hand, dynamically allocate entities would be a huge waste of cpu cycles in the vast majority of cases. Therefore, I'm a bit puzzled.

this could be adapted to an implementation that stores the underlying data in a compact representation, using similar techniques to what is done for the registry vector
[...]
Any thoughts on this approach and how feasible it would be to include in entt?

As it is (with shared pointers and whatnot), it looks technically unfeasible and a huge step back.+
However, I might change my mind if you explained in more details how one can port this implementation to something similar to what we have already.
I really can't easily fill the gap on my own, sorry.

I would be interested in hearing about other suggestions for improving robustness as well.

Entity identifiers are fully customizable already. Moreover, I'm working to make the entity storage a proper storage which also is all in all similar to that of a random component T. I think you can easily tackle the problem in one way (custom type) or the other (custom mixin) without really changing the registry.
Have you already looked into these options?

[emsai]

...which seems to assume that the (12-bit ?) version number is shared across all entity identifiers.

This is not the case. Here is an example of what actually happens:

Say that you repeatedly create a new entity and delete it, and don't do anything else. In that case, the created entity is added to the free list on deletion and reused with its version number incremented during the next creation. The version number is specific to the entity, and no other entity id values are involved. It take 4096 creations and deletions for the version number associated with this specific entity id to wrap. If you were to do this with two entities (two creations and deletions per step), then two entities would have their version number increased on each iteration.

[codylico]

so @emsai, to clarify, the issue is for external data structures that fail to keep up with the rapid deletion and creation?

[emsai]

Yes, rapid relative to the length of time that the data structures store the entity. For structures used in long running tasks, this does not need to be very fast.

[skypjack]

Is the way around this just to centralize all deletions and include updates to additional data structures that contain entities there? Or to set up the entire program in a way that there is a bound on the number of creations and deletions that can happen across entity valid checks?

The way around this is very application specific. It doesn't depend on EnTT actually.
You can for example use a 64b identifier and have way more time before an overflow or you can set up a system that cleans up invalid entites from your map from time to time.

Do you have an idea of when this change will be available?

Well, soon-ish™️ 🤷‍♂️ I'm actively working on it in my free time but it has lower priority than paid feature and things that I need at work.
In any case, it should be part of the next (non-minor) release. Dunno if you wanted to try master or just wait for a stable release.

[emsai]

Ok, thanks for the clarification, that makes sense. Good to know it is already in master, thanks for the heads up.