Proposal: Refcounted Double Linked Lists for version objects

[CharlesJQuarra]

This might not be useful for everyone, but I thought to write it down in case it might have interesting applications

The problem with incremental counters for versions in Entity identifiers is that for long-running programs (like, if Entt/ECS is used to implement an online game server), they might wrap around and result in false alive tests.

The optimization opportunity is that many version numbers might have no entities pointing to them, and that all the functionality provided by versioning can presumably exist with a reduced set of Version identifiers. The only important invariants for versions is that:

1. they are well-ordered
2. that they remain alive as long as all past Entity references that point to it

These can be easily achieved by implementing the Version objects as DL lists with a refcount of Entity references. Whenever it is detected that no one holds an Entity reference point to a given Version object, the object is removed.

If one is confident the number of alive versions in a program will remain limited, one might replace a pointer to a version object as the version identifier, with an index in the actual array of pointers

Any feedback on the above is welcome.

[codylico]

Two thoughts come to mind:

• Worst-case: one entity per version, all versions used up: Is there a way to handle version identifier selection in this case?
• New version selection: How does this scheme select new version identifiers, given that a version object, once removed, "takes" its identifier with it? Do the pointers to object (for example, Version* ptr;) become the de-facto version identifier?

Forgive me if I'm missing something obvious.

[skypjack]

Converted the issue to a discussion since it seems better suited.
I'm not sure I fully get what you're proposing though. The basic idea would be to not embed the version into the entity identifier. Instead, you want to associate to every identifier a linked list of available versions that get recycled when the ref counter reaches 0 but that can also stay alive indefinitely, so that it would be normal to have multiple versions of the same entity around?

[skypjack]

Any performance results? From a quick glance, it seems way more expensive than the basic implementation.

[CharlesJQuarra]

I have some free time to try debugging the issues with the PR. However after looking at the code I'm still confused about the assertion at sparse_set.hpp:518, it happens while trying to do registry.insert(std::begin(entities), std::end(entities), 42). The error seems to suggest the entities cannot be distinguished from null or tombstone values.

I was considering this approach: declare inside entt_traits two more constexpr calls called construct_null and construct_tombstone that resolve to internal::entt_traits implementation. For all types except those that need a long lived version, the specialization should resolve to the same entt_traits::construct(entt_traits::entity_mask, entt_traits::version_mask) call, but in my case, I could provide separate reserved instances so that they will not evaluate equal to normal entities

Is this semantically consistent with how you are using and defining nulls/tombstones?

[skypjack]

🤔 null entities and tombstones are interleaved with normal entities more often than not. For example, to track holes within stable pools, there is an implicit list in the packed array that exploits the entity part of an identifier to store the next position and set the tombstone as a version. Therefore, not sure if isolating the construct function addresses all uses.

[CharlesJQuarra]

so if I understand correctly, the null is a reserved entity section, and the tombstone is a reserved version section? I'm not clear how does the engine distinguish between nulls from tombstones when iterating on an array, if both resolve to the same Entity value

[skypjack]

There are both a null entity and a tombstone version around. EnTT doesn't really need to distinguish between them and actually it doesn't even want to. When the library encounters an identifier, it can check if it's a null entity, if it has a tombstone version and/or if both are valid. In most of the cases, the library is only interested in one or the other. However, there are some optimizations that rely on both of them being valid for an identifier.

[emsai]

I am also interested in more robust handling of the version numbers. I have started a general discussion related to this and proposed another approach here: #875.