How would you move all entities from one registry to another?

bjadamson commented 6 years ago

Hello there!

I have the following use case. I'm loading levels from files in parallel, passing each thread a different instance of a registry. In the normal fork/join model, I'd like to combine/move all the entities into one registry moving forward after all levels have been loaded (I know, it seems unlikely to load all levels in memory at once but...)

Is this possible currently? How would you go about this?

skypjack commented 6 years ago

There isn't currently a clean way to do it, mainly because I've never had to do it. If you think it's a must have, issue #44 is there for you.

At a first glance, there are several ways to merge two registries:

27 and thus the branch snapshot: it's not released yet, but the API shouldn't change in future and I'm keeping it in sync with master. You can use a continuous loader and copy entities and components from a registry to the other one.
Registry::each: if you know what are the components you want to move, you can use each to iterate all the entities still in use, create their counterparts in the target registry, then copy components. It's not much different from how a continuous loader works.
Use a single registry and a bunch of mutexes, then load your levels in parallel while keeping en eye on concurrent writes. Keep in mind that different components insist on different pools, so you can parallelize loading at some extents.
Last but not least, propose a nice and clean way to do that. I'd be glad to review your proposal and eventually help it finding its way in the library. :-)

Please, let me know how you decide to work around it. It can help other users that have the same requirement.

Thank you.

skypjack commented 6 years ago

@bjadamson

I'm tempted to close the issue mainly because it's not an issue and you got an answer.
I'm closing it in a few hours if no feedback or other requests pop out.
In case, feel free to reopen the issue if you find you didn't get a proper answer.

Hoping it helped you solving the problem.

bjadamson commented 6 years ago

Hey, sorry I was away for a day out of town. Unfortunately I would have no idea what components are in each registry. My use case is that level generation is a lengthy process, so I wouldn't mind a solution like iterating over all the entities copying their components one at a time, being a serial process.

I think solving that makes sense in the library, so I'm down to investigate a good solution for this. If your down to answer a few questions that is.

Since templates are used for components, I don't think a solution here can involve iterating components. Instead, is it possible to iterate (or even just copy) the pool, tags, handlers, etc... and copy them into the destination registry? I'm thinking a solution along this manner would be most maintainable, and even flex the design of the library in a good way?

Regardless if I had to guess you would NOT want to copy over entities, instead generate new ones in the destination registry.

Something like:

// Moves all entities from a -> b
int concat_registries(registry &a, registry &b)
{
    int count = 0;
    for (auto const eid : a) {
        auto e = b.create();
        // MOVE pool maybe
        // MOVE handlers?
        // etc..?
        ++count;
    }
    return count; // number components moved
}

edit: I forgot to add, as the loop is moving pools/handlers/etc I think rewriting the Entity id in the pool (or however their linked) using the value e generated from calling b.create() would cause them to be "relinked" for lack of a better term.

skypjack commented 6 years ago

Hey, sorry I was away for a day out of town.

Not a problem. Welcome back.

Unfortunately I would have no idea what components are in each registry.

First of all, even if you don't know what your registries contain, keep in mind that you must assign types' identifiers to your components before to start loading data into your registries on different threads.
The Family class isn't thread safe. On the other side, once a type got an identifier, it is assigned with the same value no matter in what registry you use it. As an example (ra and rb are registries):

auto t0 = ra.component<AType>(); // t0 is 0
auto t1 = ra.component<AnotherType>(); // t1 is 1
// ...
rb.assign<AnotherType>(entity); // internally, rb refers to pool number 1 because AnotherType already has an identifier here

Well, components are types, so you know them at compile-time. You can easily arrange your codebase so as to avoid race conditions on a Family.

Since templates are used for components, I don't think a solution here can involve iterating components. Instead, is it possible to iterate (or even just copy) the pool, tags, handlers, etc... and copy them into the destination registry? I'm thinking a solution along this manner would be most maintainable, and even flex the design of the library in a good way?

The main problem I see here is that entity 0 from a registry shouldn't be merged with entity 0 of another registry, right?
I mean, It looks to me that what you want is a kind of append utility more than a merge. Am I wrong?

Regardless if I had to guess you would NOT want to copy over entities, instead generate new ones in the destination registry.

Yep, you got it. :-) Unfortunately, type-erasure isn't the most friendly beast when it comes to getting out data from an erased container if you don't know what's the original type.
Probably we can do it by means of a virtual method in the base sparse set. Derived one can manage to cast it to the right type and thus to copy all the components. How to map entities remains unclear so far, but I'm pretty sure there exists a clean way to do it.

skypjack commented 6 years ago

Unfortunately I would have no idea what components are in each registry.

Side note: it doesn't matter if you know exactly what components are in a registry or not.
As long as you know what components can be loaded in a registry it's enough.
Because components are types and thus compile-time stuff, it's likely that you know what components your threads could ever create. Even if you work with runtime components, they necessarily map to a type under the hood (see my example of mod made with duktape for more details) and that's the type you want to export with all its data.

In this case, you can still use a continuous loader that does exactly what you are asking for.
Just create a different loader for each registry, get a snapshot from the same registry and thus use the loader to re-create it in the target registry.
Something like this:

r1.snapshot().entities(output1).component<AType, AnotherType, MyLastType>(output1);
r2.snapshot().entities(output2).component<AType, AnotherType, MyLastType>(output2);

entt::ContinuousLoader<entt::DefaultRegistry::entity_type> l1{target};
l1.entities(input1).component<AType, AnotherType, MyLastType>(input1);

entt::ContinuousLoader<entt::DefaultRegistry::entity_type> l2{target};
l2.entities(input2).component<AType, AnotherType, MyLastType>(input2);

If r1 and r2 do not contain instances of AType or another of the types mentioned above, it's not a problem. The snapshot marks them as serialized and stores a size equal to 0, that's all.

I'm tempted to say that the continuous loader is the tool you are looking for probably. All what you need is a good archive or at least an in-memory archive. Take a look at the tests I made for it. I used a std::stringstream, Cereal C++ and the json format to do everything in memory. It's not far from what could solve your issue actually.

What about?

bjadamson commented 6 years ago

Hey, sorry for not responding. I didn't realize anything in this library wasn't thread safe... so when you mentioned Family not being thread safe I spent the past few hours trying to figure out if it was possible to change that. I haven't had a chance to seriously consider your suggestion above, it's far too many template arguments for what I would like to see in the end. That's my initial reaction anyway.

I was able to come up with a way to make Family not a static class, and still generate unique id's per type. It's threadsafe because it doesn't use static anywhere, and it's guaranteed to work by the C++ standard.

It is in my head, I'm thinking after some back and forth discussion (if you see promise in this strategy that is) I should be able to alter this work I've already done so that when your creating your registry, you can opt-into the thread safetey, as maintaining the vector is a non-zero cost that the non-threadsafe version doesn't pay for.

I'm thinking exposing a separate registry type would be how I would want to consume this in my game. Something like this:

// Internally this would be implemented to use the instanced Family() class implementation I've linked above.
entt::ThreadsafeRegistry threadsafe;

// Internally this would be implemented to use the static Family class that exists in the codebase today.
entt::DefaultRegistry default;

Given all this, I ran into one thing I don't understand I would like to ask you about. When I got this change working, one single test fails.

I don't understand this test, it's asserting that myFamilyType and yourFamilyType are the same, but I don't see how. myFamilyType comes from my_family::type< whereas yourFamilyType comes from your_family::<.

It would seem to me, that this test is backwards. Shouldn't myFamilyType and yourFamilyType be NE because they come from different family's, or am I misunderstanding the intended semantics.

Thanks again for working on this with me.

bjadamson commented 6 years ago

Because components are types and thus compile-time stuff, it's likely that you know what components your threads could ever create

Yes, I guess you could say I'm motivated to see if it's possible to have an alternative for during iteration where I can choose to use runtime memory (vector) instead of spelling out the types all the time.

I'm tempted to say that the continuous loader is the tool you are looking for probably. All what you need is a good archive or at least an in-memory archive. Take a look at the tests I made for it. I used a std::stringstream, Cereal C++ and the json format to do everything in memory. It's not far from what could solve your issue actually.

Will do, after some zzz. Thanks

skypjack commented 6 years ago

@bjadamson I'm a bit busy today, I'll give you a detailed answer as soon as possible.

and it's guaranteed to work by the C++ standard.

Meanwhile, please note that to reinterpret cast a pointer to a size_t isn't guaranteed by the standard. I can find you the wording in the working draft if you want, but this is already enough:

On many platforms (an exception is systems with segmented addressing) std::size_t can safely store the value of any non-member pointer, in which case it is synonymous with std::uintptr_t.

On many platforms it works but there are exceptions, it means no guarantees. Therefore your version of the family class is quite a breaking change that could cause problems on some platforms. I'm sorry.

Side note: did you star the project on GitHub? I'm going to delete all my comments and never ever help you again because of that otherwise!!! If you read a promise in it, that is... :-D

skypjack commented 6 years ago

@bjadamson I'm kind of stupid. Since C++11 static initialization is guaranteed to be thread safe:

Dynamic initialization of a block-scope variable with static storage duration orthread storage duration is performed the first time control passes through its declaration; such a variable is considered initialized upon the completion of its initialization. [...] If control enters the declaration concurrently while the variable is being initialized, the concurrent execution shall wait for completion of the initialization.

Plus a note at the end of the page about deadlocks during initialization.

The Family class isn't thread safe as it is, but it's enough to make a couple of changes to that class to turn it in a thread safe tool without introducing vectors or risky/unsafe features.
Probably during the week I can push everything upstream.

This way, for you are loading levels in different registries, you shouldn't have problems anymore.
You'll need synchronization only while merging all the registries in one, but you cannot really avoid it without a bunch of mutexes all around the library and I'd prefer not to introduce them. Use a mutex to protect the target registry instead and merge one registry at a time. I don't think performance would be much better in the other case at the end of the day.

Will do, after some zzz. Thanks

Let me know if it works for you. As far as I can see, this is the sole point still open out of our discussion. Am I wrong?
If it's not a viable solution, I can arrange to define a merge utility for runtime registries maybe in a few days. The good news is that I've already in mind a way to go.
Unfortunately I cannot give you a schedule anyway because I'm working on it for free in my free time.

bjadamson commented 6 years ago

The Family class isn't thread safe as it is, but it's enough to make a couple of changes to that class to turn it in a thread safe tool without introducing vectors or risky/unsafe features. Probably during the week I can push everything upstream.

Awesome! Yeah using a mutex around the destination mutex in the meantime is no problem, it's really great this ended up being useful.

Side note: did you star the project on GitHub? I'm going to delete all my comments and never ever help you again because of that otherwise!!! If you read a promise in it, that is... :-D

Uhh yep... sure did... totally star'd the project this WHOLE time... yup definitely..!!

skypjack commented 6 years ago

Yeah, I thought about it and both a thread safe family and a merge utility for the registry seem feasible other than useful.
Thank you for the suggestion. Hoping you are not stuck behind this feature. It will be upstream soon hopefully.

skypjack commented 6 years ago

This version of the Family class probably works as expected when used with different threads:

template<typename...>
class Family {
    static std::atomic<std::size_t> identifier;

    template<typename...>
    static std::size_t family() noexcept {
        static const std::size_t value = identifier.fetch_add(1);
        return value;
    }

public:
    using family_type = std::size_t;

    template<typename... Type>
    static family_type type() noexcept {
        return family<std::decay_t<Type>...>();
    }
};

template<typename... Types>
std::atomic<std::size_t> Family<Types...>::identifier{};

Static initialization is guaranteed to be thread safe and identifier is zero-initialized because it's a static variable. std::atomic and fetch_add should do the rest within the family member function in case it's accessed concurrently on different specializations. The concurrent access of the same specialization is safe as well because (again) static initialization is thread safe since C++11.
I don't see major flaws. Any advice your side?

The advantage over the std::vector based solution is that it doesn't have to use a vector (quite obvious) nor to iterate it each time. Moreover atomic operations and thus operations that can rely on locks under the hood where the hw doesn't support us are limited to the first call for each specialization. Because of this, performance hits are avoided at all.

What about?

skypjack commented 6 years ago

@bjadamson

I tried to develop a Registry::merge member function, but it's not that easy as I thought initially:

What if a tag (single instance component) is assigned to entities in both the registries? Obviously, we cannot have it assigned to more than one entity after the merge.
Without knowing the types of the components, we cannot use the Pool template class and thus we cannot keep updated the internal data structures used for persistent views. Because of this, after a merge the registry can be in an incorrect state and there is no way to fix it.
Apparently, there isn't a way to do it without specifying components unless we use a dynamic_cast internally. I'm trying to avoid it all the ways if possible. I'm not a fan of dynamic_casts.

The funny part is that all of these are more or less the same problems encountered while I was working to the save/restore functionality and that's why users must specify what components they want to serialize in a snapshot.
Something like this:

registry.snapshot().entities(archive)..component<Position, Velocity, Whatever>(archive);

Probably the first suggestion is something you should consider for the merge, for it's an already existent way to do it that is both safe and clean. Did you try it?

ArnCarveris commented 6 years ago

Implementing space concept, should help to solve level loading problem.

skypjack commented 6 years ago

@bjadamson

Honestly, if I was you I'd use something like the following snippet (with a thread safe family, of course):

template<typename... Component, typename Entity>
void merge(entt::Registry<Entity> &src, entt::Registry<Entity> &dst) {
    std::unordered_map<Entity, Entity> ref;

    auto component = [&](auto view) {
        using component_type = typename decltype(view)::raw_type;

        view.each([&](auto entity, const auto &component) {
            if(ref.find(entity) == ref.cend()) {
                ref.emplace(entity, dst.create(component));
            } else {
                dst.template assign<component_type>(ref[entity], component);
            }
        });
    };

    using accumulator_type = int[];
    accumulator_type accumulator = { 0, (component(src.template view<Component>()), 0)... };
    (void)accumulator;
}

// ...

merge<AComponent, AnotherComponent, AndSoOn>(src, dst);

It's probably the safest way to do it. Because of how EnTT works internally, unfortunately it's hard to define a merge utility that isn't aware of the components you want to merge.
The other way around is to use save/restore utilities, but it's far slower than this.

Let me know what you think about it. I don't know if I can do much more for this issue.

skypjack commented 6 years ago

@ArnCarveris I'm not sure spaces can solve this problem. If he's loading levels on different threads, it's risky to load them in different spaces of a same registry. Concurrent threads can slow down a lot the one that owns the registry and he still needs a merge utility if it isn't the main thread that owns the target registry.

ArnCarveris commented 6 years ago

@skypjack In case of that space instance is isolated, you create empty instance of spaces, then set atomic loading flag, pass to thread that do job, when it finishes, unsets loading flag, done.

skypjack commented 6 years ago

Branch issue_45 is ready to merge with master. Can I do something else for this issue? @bjadamson

bjadamson commented 6 years ago

I was away again, my apologies.

What if a tag (single instance component) is assigned to entities in both the registries? Obviously, we cannot have it assigned to more than one entity after the merge.

Hmm that's interesting about the duplicate TAG case. In my usecase, I can work around this by making those entities not tagged and keep developing. Would a try version deem acceptable to add?

something like:

enum class ConcatenateResult
{
    TAG_PRESENT_IN_BOTH_REGISTRIES,
    PERSISTENT_VIEWS_IN_USE,
    ...
    SUCCESS
};

enum class MergeResult
{
    TAG_PRESENT_IN_BOTH_REGISTRIES,
    PERSISTENT_VIEWS_IN_USE,
    ...
    SUCCESS
};

ConcatenateResult try_concatenate(Registry &a, Registry &b);
MergeResult try_merge(Registry &a, Registry &b);

In my use case, I can simply edit my data files to not indicate an entity in the second file has the same tag, and keep developing.

Without knowing the types of the components, we cannot use the Pool template class and thus we cannot keep updated the internal data structures used for persistent views. Because of this, after a merge the registry can be in an incorrect state and there is no way to fix it.

In my use case, I don't have any persistent views. I'm simply starting up the game, and generating levels in parallel passing each highlevel function it's own Entity reference.

Apparently, there isn't a way to do it without specifying components unless we use a dynamic_cast internally. I'm trying to avoid it all the ways if possible. I'm not a fan of dynamic_casts.

Understood. Could you speak a little about the cause? In either case, for me, this being a utility function, I wouldn't mind a dynamic cast when using one of these utilities. It certainly won't be happening during my core game loop.

template<typename... Component, typename Entity>
void merge(entt::Registry<Entity> &src, entt::Registry<Entity> &dst) {
    std::unordered_map<Entity, Entity> ref;
    auto component = [&](auto view) {
        using component_type = typename decltype(view)::raw_type;

        view.each([&](auto entity, const auto &component) {
            if(ref.find(entity) == ref.cend()) {
                ref.emplace(entity, dst.create(component));
            } else {
                dst.template assign<component_type>(ref[entity], component);
            }
        });
    };

    using accumulator_type = int[];
    accumulator_type accumulator = { 0, (component(src.template view<Component>()), 0)... };
    (void)accumulator;
}

// ...

merge<AComponent, AnotherComponent, AndSoOn>(src, dst);

This would work, but I would really love to not specify the components. It's a big amount of friction having to specify my components in a second place.

Thank you for all the work you've put into this so far. I really appreciate it.

skypjack commented 6 years ago

In my use case, I don't have any persistent views. I'm simply starting up the game, and generating levels in parallel passing each highlevel function it's own Entity reference.

Just out of curiosity, can I ask you why you use more than one registries for this? It looks a lot like the bootstrap of your game, wouldn't a single registry work fine in this case?

This would work, but I would really love to not specify the components. It's a big amount of friction having to specify my components in a second place.

BTW, not all components, only those used in the source registry are fine. However I see why it's annoying for you.

bjadamson commented 6 years ago

Just out of curiosity, can I ask you why you use more than one registries for this? It looks a lot like the bootstrap of your game, wouldn't a single registry work fine in this case?

Certainly. Level generation takes a lot of time, specifically when generating an area I'm generating many dungeons, each with multiple levels. A single registry means that each level in the dungeon must be generated synchronously. I would like to speed up my generation loop, and using multiple registries allows me to pass a different registry instance to each thread. A single registry means I need to introduce concurrency, which ruins the performance gained through the parallelism I put in the first place.

The alternative I believe would be to define a custom data structure, and fill that in. That would cause me to define my component types in two places. Using multiple registries gets me the parallelism and doesn't force me to define all my ~~entities~~ components in a template argument list anywhere. All without concurrency, well minus the join loop at the end.

bjadamson commented 6 years ago

BTW, not all components, only those used in the source registry are fine. However I see why it's annoying for you.

Ah, yes. However my original definition of which components are in which registry ultimately comes at runtime from reading a save file. The components themselves are simple structs defined in header files, but which ones are in which level aren't known until the savefiles are read.

skypjack commented 6 years ago

A single registry means I need to introduce concurrency, which ruins the performance gained through the parallelism I put in the first place. [...] All without concurrency, well minus the join loop at the end.

Did you measure it? I mean, as far as I can see you are only creating entities (Registry::create) and components (Registry::assign), no destroy, no remove at all (correct me if I'm wrong). Constructing entities and components are pretty fast operations. If you create mutexes on a per type basis around a registry instead of a one-fits-all mutex for the whole registry to use during the merge, I'm not that sure that using multiple registries is faster than using a single registry.

In other terms, have you had a chance with something along this line?

struct RegistryWrapper {
    using entity_type = typename entt::DefaultRegistry::entity_type;

    RegistryWrapper(entt::DefaultRegistry &registry): registry{registry} {}

    entity_type create() noexcept {
        // protect the entities array of the registry to avoid concurrent access
        // because std::vector doesn't give guarantees on concurrent writes
        std::lock_guard<std::mutex> guard(entities);
        return registry.create();
    }

    template<typename Component, typename... Args>
    Component & assign(entity_type entity, Args&&... args) {
        // force the creation of a pool for the type, does nothing if it already exists
        // again, it's due to the fact that std::vector bla bla bla :-)
        reserve.lock();
        registry.reserve<Component>(0)
        reserve.unlock();
        // protect the pool of components of the given type, do not lock the
        // other ones (it's enough because of how a registry works internally)
        std::lock_guard<std::mutex> guard(components[registry.component<Component>()]);
        return registry.assign<Component>(entity, std::forward<Args>(args)...);
    }

private:
    entt::DefaultRegistry &registry;
    // put here a proper number, as long as it's
    // greater than the number of components you have
    std::vector<std::mutex> components{100};
    std::mutex reserve;
    std::mutex entities;
}

Not tested, I wrote it out of my head, but it should give you a grasp of what I mean.
Please, let me know what you think about it. Thanks.

skypjack commented 6 years ago

@bjadamson

Here is a way to do what you want with what the registry has already to offer.
I didn't test it, but I hope it's enough to give you a grasp of the idea. Feel free to ask if you want more details.
I covered only create and assign because it looks to me it's all what you need. Anyway it's pretty easy to extend once you got how it works.

Of course, you can use it with more than one thread and you don't have to give any list of components in any case, that is something on which you insisted more than once. :-)

Here it is:

template<typename Entity>
class RegistryToMerge: private entt::Registry<Entity> {
    template<typename Component>
    static void proto(std::unordered_map<Entity, Entity> &ref, entt::Registry<Entity> &src, entt::Registry<Entity> &dst) {
        src.template view<Component>().each([&](auto entity, const auto &component) {
            if(ref.find(entity) == ref.cend()) {
                ref[entity] = dst.create();
            }

            dst.template assign<Component>(ref[entity], component);
        });
    }

public:
    using entt::Registry<Entity>::create;

    template<typename Component, typename... Args>
    Component & assign(Entity entity, Args&&... args) {
        const auto type = this->template component<Component>();

        if(!(type < merge_fns.size())) {
            merge_fns.resize(type+1, nullptr);
        }

        merge_fns[type] = &proto<Component>;
        return entt::Registry<Entity>::template assign<Component>(entity, std::forward<Args>(args)...);
    }

    void merge(entt::Registry<Entity> &dst) {
        std::unordered_map<Entity, Entity> ref;
        entt::Registry<Entity> &src = *this;

        for(auto &&fn: merge_fns) {
            if(fn) {
                fn(ref, src, dst);
            }
        }
    }

private:
    using merge_fn_type = void(*)(std::unordered_map<Entity, Entity> &, entt::Registry<Entity> &, entt::Registry<Entity> &);
    std::vector<merge_fn_type> merge_fns;
};

It's just a kind of wrapper of a registry that stores aside a bunch of functions to use to merge it on request.
Note that this works fine only with the changes on branch issue_45 (the thread-safe family).

As a side note, I prefer not to put the merge functionality directly into the registry. The main reason is that it's not that safe unless we accept to increase memory usage to store erased functions like in the example above. However, I prefer to avoid consuming memory for a feature that can be easily implemented externally and isn't a desiderata in general.
In other terms, I don't want other users to pay for something they don't want. Even more if those that are interested can easily do it with an utility class like this one.

Hoping you are on the same line and the snippet above works for you.
Please, let me know. I want you to solve your problem and enjoy using EnTT in any case. ;-)

skypjack commented 6 years ago

@bjadamson

Changes from branch issue_45 are now on master. Considering the previous comment that provides you with an external tool to use the way you asked, I think I cannot do much more for this issue.
Let me know if I can help you further or we can close it. Thank you.

skypjack commented 6 years ago

Hi @bjadamson ,

I'm not sure you're still following this thread. To sum up:

Upstream is now a thread safe version of the Family class.
Above is a POC of a class derived from entt::Registry that can be used to solve your problem without using multiple registries.
Above is a POC of a class derived from entt::Registry that can be used to solve your problem using multiple registries to be merged together. It does the job under the hood and it doesn't require to be explicit about the components to merge, as requested.

From my point of view, the issue can be closed.
Feel free to reopen it if you find you didn't get a proper answer.

zhmt commented 4 years ago

we can use a thread-safe registry as a transfer station . Registry R1(runs in thread1) copy entity E1 to R2(transfer station,thread-safe), then R3(runs in thread3) copy E1 from R2 . Not transfer all, transfer by entity id.

Another way is : every thread holding a RegistryToMerge using as queue. All transfering entity will be put into RegistryToMerge of destitnation thread.

skypjack / entt

How would you move all entities from one registry to another? #45

27 and thus the branch `snapshot`: it's not released yet, but the API shouldn't change in future and I'm keeping it in sync with `master`. You can use a continuous loader and copy entities and components from a registry to the other one.

skypjack / entt

How would you move all entities from one registry to another? #45

27 and thus the branch snapshot: it's not released yet, but the API shouldn't change in future and I'm keeping it in sync with master. You can use a continuous loader and copy entities and components from a registry to the other one.

27 and thus the branch `snapshot`: it's not released yet, but the API shouldn't change in future and I'm keeping it in sync with `master`. You can use a continuous loader and copy entities and components from a registry to the other one.