Component polymorphism support feature & prototype

[zheka2304]

Hello,

I'd like to introduce my work on prototype feature, that adds component polymorphism support. Such thing might seem a little controversial, so I will immediately mention two things:

• Despite not being a part of pure ECS concept, such feature can be very useful in many real world cases
• It is enabled only for certain component types at compile time, so it will not affect performance of non-polymorphic components in any way (pay only for what you use)

I already have working prototype in the experimental branch of my fork. Of course it requires some review and improvements, and some parts may not be made in a nicest way possible right now, but it is fully functional.

Here is a basic example:

struct Ticking : public entt::polymorphic {
    virtual void tick(const entt::entity) = 0;
};

class Physics : public entt::inherit<Ticking> {
    // ...
    void tick(const entt::entity e) override {
         // ...
    }
};

class AI : public entt::inherit<Ticking> {
    // ...
    void tick(const entt::entity e) override {
         // ...
    }
};


registry.emplace<Physics>(e); // emplace polymorphic component
Ticking& ticking1 = registry.get<Ticking>(e); // will return Physics as Ticking
registry.emplace<AI>(e); // emplace another polymorphic component
Ticking& ticking2 = registry.get<Ticking>(e); // will return any of two components, because they are both inherit from Ticking, which component is returned is not defined

// get iterable to iterate each component, that is inherited from Ticking, order of iteration is not defined
for (Ticking& ticking : registry.view<entt::every<Ticking>>(e).each()) {
    // ...
}

// view can also get every component instead of one
registry.view<entt::every<Ticking>>(e).each([](const entt::entity, entt::every<Ticking> every_ticking) {
    for(Ticking& ticking : every_ticking) // ...
});

// will remove EVERY component, that is inherited from Ticking
registry.remove<Ticking>(e);

You can try it yourself, it is already in the fork, along with some tests. I will appreciate any feedback about how to improve both the concept and the solution, and hope it will make it way into EnTT in the future.

Now lets dive into some details:

Problems, I try to address

Maybe the main problem, this feature solves, is accessing components without knowing their exact type. It is sometimes can be very useful to access component as some interface/base type without knowing what exactly it is (so basically this is what polymorphism is about in general, and this feature is applying this concept to ECS).

In the context of ECS it results in 2 main ideas: we should be able to access component by any of its base types and we also should be able to access all such components, attached to an entity, because there of course can be more than one. Example of this idea is already shown above, we create two component types, that implement Ticking interface and add both of them to an entity, and then we can just iterate all ticking components and do something with them (probably just call tick in this case).

Additionally, to follow "pay only for what you use" rule, such polymorphic components must be treated separately and must not affect performance of other components.

Some specs

The basic idea is simple: component can be accessed not only by its own type, but by any of its parent types. From the example above we can see, that both Physics and AI components inherit from, and so can be accessed as reference to Ticking. Here I tried to come up with a bit more formal set of rules:

1. We define polymorphic components separately from non-polymorphic, by inheriting from entt::polymorphic or entt::inherit<Parent1, Parent2, ...>. Polymorphic component can inherit only from other polymorphic components to keep them separate from non-polymorphic. With this requirement we can completely separate all logic at the compile time and preserve performance for non-polymorphic components.
2. When polymorphic component is added to entity, it can then be accessed not only by its own type, but as any of its parent types. This applies both for getting it for one entity and for iterating with a view.
3. Now for some parent type there can be several components of its child types attached to an entity. So we must be able to:
   3.1. Still get one of this components, if we just need one. This operation ideally must be as fast, as getting one non-polymorphic component. Which component will be returned cannot be specified in this case, so we just return any of them.
   3.2. Iterate over all components of this type, attached to an entity. Same as with one component, we must be able to use it both with get and with view. To achieve this, we pass entt::every<ParentType> instead of just ParentType to registry.get or registry.view, and get it back. Then we just iterate entt::every<ParentType> to get ParentType&.
   3.3. Access with entt::every must work completely similar for one and for several components.
4. Calling erase and remove must delete all components inherited from given type. This might seem a bit controversial, because in some cases we need to delete component of exactly this type, so maybe in the future separate method should be added to do such things.
5. Actions insert, get_or_emplace are deleted for polymorphic components right now, and patch is also controversial one, as they deserve separate discussion.
   ... This list will be expanded as the discussion progresses

Some implementation details

Wrappers (or containers, don't know, which name is better)

Main idea here is to store polymorphic components inside wrappers/containers (polymorphic_component_container<Component>). These wrappers are able to store component value of exactly given type and reference list to other components. They have storage for component value, list of references to other components and 2 bits for flags to store its state.

Wrapper has methods for value construction/destruction, adding/removing references to other components from reference list and for getting reference to one component or entt::every to iterate all of them. When constructing a value, wrapper adds reference to this value into all wrappers for parent component types, when destructing - it will remove all this references. So it requires registry and entity to access those wrappers for parent types.

Polymorphic components reference each other by pointer, so stable pointer is required, in_place_delete is true for all polymorphic types, and empty type optimization is also disabled, because wrappers are never empty.

Changes in basic_storage

Because polymorphic components are stored in wrappers and accessed in a slightly different way, separate basic_storage and iterator implementations are created for them. It changes implementation of get, emplace, erase and remove and also adds hidden methods for polymorphic_component_container like emplace_ref and erase_ref.

I have also added get_as<T> (and similar) methods for all basic_storage implementations and similar as<T> methods for storage iterators. The purpose of those is resolving entt::every (and maybe some other type modifiers in the future). For non-polymorphic storage those methods are completely similar to get/operator*, they actually just call them with an extra static_assert, so no performance overhead here.

And here comes an uglier part: emplace and erase now require registry for polymorphic storage, so right now they are just passed as an additional parameter, that is ignored for non-polymorphic component storages. Again, no performance overhead here, as the registry parameter is just optimized out, but the whole idea of such inverse dependence is pretty nasty. It is another open discussion on how to implement this in a more elegant way.

Changes in basic_view

Here things are simpler: I use get_as<T>/as<T> methods I have created in storage and storage iterators to just forward everything in a right way. Because all of these methods are basically same as get/operator* used before for non-polymorphic types, no overhead is expected for them.

There is also some changes to get unwrap entt::every to get storages for required component, but these are fully resolved at compile time.

Changes in basic_registry

Only changes here are passing registry to emplace/erase/remove and unwrapping entt::every for views.

Dive into polymorphic_component_container implementation

As was said before, polymorphic_component_container aka polymorphic component wrapper can store both component value and reference list. In a very basic implementation it can be done like this (and also thinking of it in this way may help a lot):

template<typename Component>
struct polymorphic_component_container {
    std::optional<Component> value;
    std::vector<Component&> refs;
};

But when I came to thinking about erase implementation the following problem kicked in. When erasing component, we must also erase all components listed in refs (those are child types). When deleting component, it must delete all of its references from parent wrappers, so we must know exact types of components in refs to do it or come up with another way. My idea was to store pointer to 'deleter' function along with component reference, such deleter will be placed when reference is added and called, when it is required to erase component by its reference. So wrapper implementation should look like this:

template<typename Component>
struct polymorphic_component_container {
    struct component_ref {
        Component& ref;
        void* deleter;
    };
    std::optional<Component> value;
    std::vector<component_ref> refs;
};

Now lets move on to real implementation. It does not use std::vector nor std::optional. Instead it has data - buffer for component value or at least one pointer and uintptr_t pointer, which can store pointer to one reference or pointer to list, depending on wrapper state. And to store wrapper state I use a solution with some pointer hacks - I rely on memory alignment, so 2 bits of pointer are always zero and can be used to store the state (it is achieved by aligning entt::inherit by at least 4 bytes). This saves us one memory access when getting reference to the component and also sizeof(pointer) bytes of memory per wrapper, that would be otherwise added by padding. I thought it was worth it, so there is a lot of strange stuff going on inside wrapper, but if you consider this an overkill I of course will rethink it.

Now lets look on the possible storage states: there are 2 bits, 2 flags that are mostly independent of each other, 1st flag - if wrapper has a value, 2nd flag - if wrapper has a reference list. Describing whole implementation here would take forever, I will try to do it separately, so here are some important notes:

• There is always a value or a reference stored directly inside the wrapper, so one component reference can be always accessed without any indirection and looking into list. If nothing is stored, wrapper is deleted.
• When wrapper has list, it stores all the references, owned by this wrapper, including reference to the value inside this wrapper (if in has one), so iterating the list does not require extra logic.
• When wrapper contains only one reference or only value, it does not allocate a list (and also it deallocates a list, if only one reference/value remains)
• Lists are allocated via component_ref_list_page_source to optimize many small memory allocations of the same size, required for them. Note: right now template of component_ref_list_page_source depends only on underlying allocator type, but maybe it should instead be instantiated per component type (the page size must be reduced greatly in this case).

I am planning to clean up, and move some of this logic out of the wrapper class to abstract underlying memory layout a bit, right now the solution is messy.

...Implementation details are also to be expanded

[skypjack]

Hi, I see that your branch has 10 changed files with 2,170 additions and 112 deletions.
My first suggestion is to provide the reader with a walkthrough of your work and reasoning. Otherwise, it may take a while before getting a feedback.
Another thing that helps to focus on your proposal is to clearly define the goals of this work. Polymorphism support is somewhat vague. A list of use cases and problems you're trying to address would help on the other hand. Otherwise, agani, it may take a while before knowing what this code adds to the whole picture.

That being said, let's start with scratching the surface though. A bunch of questions/doubts after a quick glance:

• The fact that both page_size and in_place_delete depend on the polymorphic nature of a type is really odd to me in terms of design. Why is it required at all?
• The sparse set doesn't know about the registry class today and and I'd rather stick with this approach.
• How does this affect the view perf? I see many changes but I can't easily figure out if they add up for the non-polymorphic case.

I won't go into the details of storage.hpp and component.hpp right away, mainly because they are very huge and with many changes. I'm a little short in time today. 😅
Something that looks odd is the storage specialization for is_polymorphic_component_v<Type>. I don't get why being a polymorphic type should affect the storage type.

As I was reading your proposal, I thought of a much less impactful implementation to support polymorphic types. It would also fit with an upcoming feature, literally entering the same design.
However, I'd like more details about your work and it would be really helpful if you could guide me through it as suggested at the beginning. It might just be enough with a clean up already but I really struggle to grasp all the details from the code alone, sorry.

[zheka2304]

Thanks for your reply! I will write in details about ideas and implementation and put it in the heading comment for easier access as soon as possible.

And also here is a brief response for your first questions:

• Polymorphic components are stored in wrappers inside the storage, and reference each other by pointer, so they must have stable pointer and also prevent empty type optimization. page_size is zero for empty type components, so polymorphic check was added to prevent this for empty, but polymorphic types. in_place_delete is an overkill, because it was duplicated in entt::inherit, I will clean it up.
• When polymorphic component is added, it adds its reference into all parent type storages, and when it is removed, it must delete all those references. So the idea that it requires registry to get those storages. Making duplicate emplace/remove methods for storages and sparse sets to pass registry were the fast way to do it, but I admit it is an ugly one and must be refactored. Even when I was writing it I have already decided to discuss it with you, because you will suggest the best way to solve this problem.
• I haven't yet tested two versions of the library (with and without my changes) side by side. But the whole idea here was to separate all the logic at compile time, so logic for non-polymorphic components stays completely the same. All alternative methods, that were added, contain additional logic only for polymorphic components types, for non-polymorphic they just have additional unused parameters or wrap a call to another function. It should all be optimized out completely, when it is inlined.
• And for the storage: as was mentioned earlier, polymorphic components are stored inside wrappers, so they can hold both value and references to other components. These wrappers require separate logic for access, especially for handling entt::every. I first started with making this logic inside original storage class, but it quickly became a complete mess with a lot of if constexpr(is_polymorphic), so it seems making separate class for polymorphic components is just a cleaner solution.

[zheka2304]

I have added a lot of details into the heading comment, and will add more with progression of this discussion. Those should help to dive into what I am trying to achieve, and how this whole thing even works (or, at least, how its supposed to work). If some parts are incorrect or unclear, please, notify me and I will rewrite them.

[skypjack]

That's great. Thank you very much. I'll try to go through it as soon as possible.
Sorry if it takes a while but it's really a lot of stuff to read and digest before moving on. 🙂

A quick question (and sorry if it sounds stupid but I still have to dig into your explanation).
Do I get it correctly that the whole thing doesn't apply to types for which the user doesn't have the control?
For example, imagine a third party hierarchy aimed to create UIs (cough coff Qt coff cough). I can't put its graphic items in my registry because I can't make them inherit from entt::polymorphic, is it correct?
Please, also ignore for a moment the fact that probably it doesn't even make sense to put these objects in the registry. It's just to provide an example. 😅

[Innokentiy-Alaytsev]

I'm not sure how physics libraries work, but if they have some sort of shape hierarchy, then it might be an example of non-extensible third-party class as well. From what I understand, having physics-related components is somewhat common.

[zheka2304]

It is a good question, right now there are no way to declare hierarchy for third-party components. However it seems possible to add alternative way of declaring hierarchy separately from the classes. entt::inherit is just a template to form type_list of all parent types for given component type, and nothing stops such list from being created outside the component type itself. The only difficulty may be in hidden relation between entt::inherit and hacks in wrapper implementation.

[skypjack]

I'm trying to wrap my head around the implementation details. A bit at a time.
I'm not sure I get them correctly though. Please, correct me if I'm wrong.

Let's suppose there are 3 pools for types T1, T2 and T3. All these types derive from a common base B (polymorphic and inherit and all the rest, that part is pretty clear and I'll drop a bunch of questions/doubts later on probably 🙂).
When I add an instance of T2, what happens is that a wrapper is created within its pool while another two wrappers are also created in the pools for T1 and T3? All these wrappers have the size of 🤔 B plus a pointer?
I think I don't get what Component is here:

template<typename Component>
struct polymorphic_component_container;

That is, if it's the base type or the final type. This also makes it difficult to understand how this type is used.
Can you elaborate a little further on this point? Thanks!

[zheka2304]

I suppose, you have hierarchy like this:

    B
+---|---+
|   |   |
T1  T2  T3

When you add component T2, it adds references to itself into all parent pools (B in this case), so you following structure:

pool T2: T2        // stores value of newly created T2
pool B : T2&       // stores no value, but has a reference to T2 value in T2 pool
// pools T1, T3 are empty

So T2 can be accessed both as T2 and as B.

When you add, for example T1, you will get the following:

pool T1: T1              // stores value of newly created T1
pool T2: T2              // still stores a value of T2
pool B : [T1&, T2&]      // still stores no value, but now has both reference to T2 value in T2 pool and T1 value in T1 pool
// pool T3 is still empty

Returning to your question about Component template parameter - it is a exact (not parent or child) type, that this wrapper can store by value. Only one value can be stored per wrapper, as there is only one component of this exact type can be attached to a single entity.

When attached to an entity, component (lets assume it is T2) is first put into corresponding pool of T2 into the wrapper for the same type, and then it will go through all of its parents and add reference to itself.

Hope this will help a bit.

[skypjack]

Hope this will help a bit.

Yeah, definitely. Thank you a lot.
The first question that pops to my mind is the following: isn't it an issue when it comes to multithreading?
The design of EnTT makes it possible to add and remove (but even sort) components in parallel. In this case, if I decided to store aside a hierarchy like that of Qt where all items inherit from a QObject or QWidget type, multithreading the access to their pools isn't an option anymore.
Do I get it correctly? Standalone and fully independent pools are kinda expected most of the times.

[zheka2304]

Yes, it limits multithreading for polymorphic components, which share a parent, because accesses to these components will also affect shared parent pool. Only pools, related to separate hierarchies can be accessed in parallel. However I think it is expected, that components, that are somehow related to each other, are not safe to access from different threads.

[skypjack]

This is a contrived point imho.
When I access them from the base, I think you're right, I expect to lock all pools in a sense.
However, if I want to access all buttons and all labels in parallel, I can't really see why I can't (I mean, as an user).
I'm accessing different explicit types that are stored in different pools from what I know. Imagine what kind of bugs one could introduce in a codebase by changing the hierarchy definition when all systems are multithreaded already.
That's pretty risky and makes the use of this feature rather limited probably. Food for thoughts anyway.

[zheka2304]

Yes, I see, from this perspective this issue seems much scarier. From the first glance it seems impossible to make viable polymorphic component implementation with safe multithreaded access for intersecting hierarchy, while keeping whole idea of EnTT unchanged and without introducing some kind of hidden locks/atomics, which of course is not viable too.

The one idea is accessing all child pools while trying to get component by its base type, instead of adding references to parent pools. This way it will be safe to modify different pools, because this modifications will not touch their shared parent pool. But in this way get and iterate operations will be extremely slow and will require a lot of random memory access. So this is not an option.

I think the possible solution from design perspective could be adding some sort of compile time guards, when you can maybe declare what components you will access from which thread (I am not sure, how exactly this will look, it is just my first idea). This will require additional declaration, but it will not compile, in case of conflicts. This may also help with non-polymorphic components, to guard same types from being accessed from different threads.

[Innokentiy-Alaytsev]

Hope this will help a bit.

Yeah, definitely. Thank you a lot. The first question that pops to my mind is the following: isn't it an issue when it comes to multithreading? The design of EnTT makes it possible to add and remove (but even sort) components in parallel. In this case, if I decided to store aside a hierarchy like that of Qt where all items inherit from a QObject or QWidget type, multithreading the access to their pools isn't an option anymore. Do I get it correctly? Standalone and fully independent pools are kinda expected most of the times.

In the particular case of Qt, all QObject-based types are expected to only be used through pointer so storing them by value in a pool will be a bit complicated. On the other hand, storing pointers won't work with polymorphic storage because pointer types are not directly related through inheritance.

It has little to nothing to do with the proposal, just something to keep an eye on: sometimes you shouldn't store things by value by design.