Some confusing about Sparse Set

[ysysimon]

I recently discovered this library and read a series of blogs by the author, I learn a lot from it, This is invaluable to a programmer.

But I also had some confusing about Sparse Set.

As far as I understand, sparse set is used in entt by:

• Store registered entities in the registry, But this seems odd since this would seem to only be sufficient for sparse arrays? Is entt::storage<void> used in the registry to store entities?
• Storing components in a component pool, Are components stored directly in the dense array of the sparse set?

I also read that an entt::null entity is an entity whose identifier part is invalid, This is used in a sparse array of a component pool's sparse set to indicate that this entity does not have this component (avoid to test dense array ), But if the identifier part is occupied by entt::null, how to implement the implicit linked list for identifier recycling?

And entt::tombstone is a version part invalid that is used to ensure pointer stability in dense arrays of sparse sets of component pools, But if it is stored in the dense array, where are the components stored? If entt::tombstone is not stored in a dense array, but in a sparse array, then its identifier part originally indicates which entity is the tombstone, and now the position in the sparse array has already indicated this? And there is still no place left for the implicit linked list (the identifier part should store entt::null)? However, if stored in a sparse array, iterating over a dense array will not be able to distinguish and skip invalid tombstone components?

[skypjack]

I think this is better suited for a discussion. Converting it.

[ysysimon]

I just noticed that github has a feature called discussion... 🤣

[skypjack]

Is entt::storage used in the registry to store entities?

No, EnTT uses a specialization of the storage class for the entities. That is, when the entity type and the component type are the same. See here for further details.

Are components stored directly in the dense array of the sparse set?

Uhm 🤔 it depends of what you mean. The library derives from the plain sparse set and adds yet another packed array on top of it. See here and the storage.hpp file in general for all implementation details.

This is used in a sparse array of a component pool's sparse set to indicate that this entity does not have this component [...] But if the identifier part is occupied by entt::null, how to implement the implicit linked list for identifier recycling?

You're mixing apples and pears. Recycling an identifier is something that entity storage does. Component storage types aren't interested in recycling any identifiers. So, yeah, null is used to speed up component checks. As for entities, I recommend studying the above storage specialization instead. Identifiers are never deleted. Their list is partitioned instead.

And entt::tombstone is a version part invalid that is used to ensure pointer stability in dense arrays of sparse sets of component pools, But if it is stored in the dense array, where are the components stored?

Components: nowhere. If the i-th position contains a tombstone in the sparse set, then the memory chunk to store the component is empty in the storage class. Uninitialized memory, available for next reuse.
See here for example. We swap-and-pop by default. However, we just invoke destroy the object when pointer stability is enabled. Memory is retained and managed accordingly.

If entt::tombstone is not stored in a dense array, but in a sparse array [...] And there is still no place left for the implicit linked list (the identifier part should store entt::null)?

The tombstone is in the packed array. Again, you're confusing the entity storage with the component one.

[ysysimon]

That is to say, entt::null and entt::tombstone are only in the component storage because they are used to speed up the verification of whether an entity has a component and maintain pointer stability.
While entity storage does not have them. Instead, they are replaced by an implicit linked list in the sparse array to speed up identifier recycling.

[skypjack]

Instead, they are replaced by an implicit linked list in the sparse array to speed up identifier recycling.

This part is wrong.

The implicit linked list is in the component storage and tracks the tombstones when pointer stability is enabled. This list is embedded in the packed array and you can literally walk all empty slots with it. As you can guess, it helps to recycle available elements before pushing back new ones.
Sparse arrays never contain embedded lists instead. I don't even know what they could be used for actually.

The entity storage is just a sparse set with an index that points to a random position N in the packed array. All elements before N are entities still in use. All other elements are entities returned by the user that we can recycle after incrementing the version.

[ysysimon]

Instead, they are replaced by an implicit linked list in the sparse array to speed up identifier recycling.

This part is wrong.

The implicit linked list is in the component storage and tracks the tombstones when pointer stability is enabled. This list is embedded in the packed array and you can literally walk all empty slots with it. As you can guess, it helps to recycle available elements before pushing back new ones. Sparse arrays never contain embedded lists instead. I don't even know what they could be used for actually.

The entity storage is just a sparse set with an index that points to a random position N in the packed array. All elements before N are entities still in use. All other elements are entities returned by the user that we can recycle after incrementing the version.

I thought that when using registry.create();, the previously destroyed entities would be used first, so we need to maintain an implicit linked list in the sparse array of the entity storage to find the recycled entities. I read this from ur blog

[skypjack]

This is how the previous version worked, yes. The non sparse set based version.
Entities have their own storage now. You can get it as: registry.storage<entt::entity>().
The latter doesn't use implicit lists. Instead, it partitions the packed array of the sparse set.
Previously destroyed entities are used first as before in any case. What changed are the implementations details.