Entt: [Feature request] Support for "double buffering" components workflow

[Paolo-Oliverio]

The kind of workflow you do swapping read from and write to component at every update.
e.g. 2 position components who act as present and past position alternatively.
In entt I naively end up with double read/write with the relative cache trashing.
I don't find any elegant way to do it without breaking DRY or do some shameless branching.

I'm guilty of not having checked the code to see how practical this could be.

[ArnCarveris]

@skypjack Maybe allow user to implement custom sparse_set for specific component via traits? This will optional advanced feature that will allow to do such things, hmm....

[Kerndog73]

Could make things easier for the user by creating a entt::buffered_sparse_set. Could allow for an arbitrary amount of buffering. To access buffered components you could use entt::buffered<Component, 0> where 0 is the index of the component. Internally, buffered_sparse_set could store either std::array<std::vector<Component>> or std::vector<std::vector<Component>>. Vector of vectors would probably be easier. We can assume that entities must have all buffered components or no buffered components so there is one sparse set and multiple component arrays. To rotate the buffers, the user would call reg.rotate<Component>().

Then it falls apart when views and groups come into the mix. I thought I had it all figured out! Ok, scrap that. One component array per sparse set. Maybe I've inspired someone to come up with a better idea?

[skypjack]

I'm guilty of not having checked the code to see how practical this could be.

Don't worry. This isn't the first time that someone pops out with such a request.
A patch to allow double buffering has been proposed a couple of months ago, but it didn't fit well with groups (as @Kerndog73 correctly reported). I don't want to expose unsafe features, mainly because I don't want to keep looking into issues of users that have errors because of them.
If you're willing to maintain your own local copy of EnTT, you can try to cherry-pick it.

In entt I naively end up with double read/write with the relative cache trashing.

Are you running systems in parallel? Otherwise I didn't get why you suffer from cache trashing.

I don't find any elegant way to do it without breaking DRY or do some shameless branching.

You can use two components (empty classes derived from the same base, aliases won't work in this case) and a function template specialized for them in your system (no need to duplicate the code if you do things correctly, don't worry). A data member having type pointer-to-member-function allows you to invoke the _right function_ each tick and you can easily update the data member without ifs (eg the function template can return the next member to invoke).
Therefore DRY principle is kept intact and you don't have shameless branching. Of course, you have an extra jump due to the pointer to member function, but you pay for it once each tick, not once for each entity, so nothing of which to worry about.
You can also use groups with a constrained type this way, so performance are guaranteed.

In fact, double buffering is possible without changes. To offer built-in support by exposing an unsafe feature isn't the best idea when you can already do it in a safe manner and in an elegant way.
I hope you got at least the basic idea.

---

@ArnCarveris

Maybe allow user to implement custom sparse_set for specific component via traits?

No need for traits here. You can already specialize the sparse set for a given component. This is the way I went to optimize for empty components. However, because of how the registry works, you must inherit from sparse_set<Entity>. The other way around would mean to sacrifice performance and I won't do it any time soon.

[Paolo-Oliverio]

Thanks to all for the feedback .@skypjack In the end your provided solution seems to be the better one in the kiss principle perspective as cherry picking something dangerous in my first days of learning this library doen't sound as a good plan, but it is surely interesting to give a look at it. About the cache trashing the idea is to be performance and multithread friendly by design ,but with soft constraints, or better, withing some other prioritative hard constraints.
Safe and cheap good pratices and principles, nothing fancy, as I'm not really having any need for speed right now. I'll be most probably gpu bound and premature optimization is always ready to kick in to bring devastation.
A bit of early bad performances helps keep the feature creep away and the journey far more interesting.

[Kerndog73]

@skypjack I think there might be a way to swap pool pointers safely.

reg.assign_pair<Component>(entity, {1, 2}, {3, 4});
// assigns entt::read<Component>
// assigns entt::write<Component>
reg.remove_pair<Component>(entity);
// remove both
reg.assign<entt::read<Component>>(entity);
// static_assert
reg.remove<entt::write<Component>>(entity);
// static_assert
reg.swap<Component>();
// swap read<Component> and write<Component> pools
reg.view<entt::read<Component>>();
// should just work without need for modification

As long as the pair of components is kept in sync and an entity never has just one of the components, it should just work right? Swapping pools should be completely transparent to views and groups so they shouldn't need to know about buffering. We should be able to assert and static_assert everything that could go wrong right?

[ArnCarveris]

@Kerndog73 Maybe this?

reg.assing<entt::readwrite<Component>>(entity, {1, 2}, {3, 4});
//reg.assing<entt::readwrite<Component>>(entity, 1, 2, 3, 4); //Hmm, maybe.
reg.remove<entt::readwrite<Component>>(entity);

reg.view<entt::readonly<Component>>();
reg.view<entt::writeonly<Component>>();

[skypjack]

@Kerndog73 @ArnCarveris

Below a brief, yet incomplete list of problems I see with this approach:

• Pollution of the API for a side feature: I'm pretty proud of the API of EnTT to be honest, I always try to keep low pollution.

• It supports only double buffering: useless. What if I want a rollback system with 10 checkpoints? If I remember it right, @pgruenbacher wanted a three-way buffering. The only viable approach to satisfy all the requests is to support N-ways buffering, otherwise we are doing something wrong in terms of software architecture.

• Groups aren't supported out-of-the-box, at least not intuitively. They can work somehow with performance hit. A group that would guarantee to work properly is group<read<T>, write<T>>(...);, otherwise things get messed. However, this way you get components you don't want when you iterate (eg you get writable component when you want only readable one).

• It's not that easy to use it. entt::read, entt::read_write, entt::read_only, and so on. I wouldn't use it, too difficult to remember all of them and not getting wrong sooner or later. Definitely not user-friendly.

And so on, I must leave now. Sorry.
The fact is that we are trying to force into the registry a feature that one can easily design around it and apparently the latter is the only way to make it safe, feature complete and user-friendly at the same time.

@Paolo-Oliverio @ArnCarveris @Kerndog73

If you really need it and want me to go deeper in the topic, I can write a blog post on this and release a working example code somewhere (Patreon?).

[Kerndog73]

@skypjack I 90% agree with you.

The API would be polluted. The registry header is big enough as it is.

I originally wrote a comment describing abitrary buffering. It works the same except that you'd use entt::buffered<Component, 0> instead of read/write. There'd also need to be a couple of extra asserts to make sure the user gets the buffer size correct. Then I deleted the message and wrote about double buffering instead. Abitrary buffering is not that different to double buffering.

I don't really understand how groups work. I wasn't really sure if it would work with groups. Not being able to use buffered components with groups kind of sucks.

I think you might be getting what I wrote mixed up with what Arn wrote. You'd just need to remember entt::read and entt::write. The user could make type aliases if they want.

The abitrary buffering API that I came up with is horribly clumsy. Runtime asserts should be able to cover every mistake the user makes but that's the problem. There are too many mistakes that the user can make! It's a crappy API.

I don't actually need this feature. I'm just exploring ways of implementing it. If it can't be implemented safely and cleanly, it shouldn't be implemented at all. Like you said, this sort of thing should be done on the user side. It shouldn't be part of EnTT.

[skypjack]

Yeah, also sorry if I appeared rude. I got a flu and have a terrible headache. I'm not re-reading messages before to post them. Be patient. :-)

[skypjack]

@Paolo-Oliverio @Kerndog73 @ArnCarveris

As a proof of concept, I wrote a running example implementation I can use this way:

struct base { int value{}; };
struct derived_1: base {};
struct derived_2: base {};

// ...

buffered_components<entt::type_list<derived_1, derived_2>, int, char> runner;
entt::registry<> registry;

const auto entity = registry.create();
registry.assign<derived_1>(entity);
registry.assign<derived_2>(entity);
registry.assign<int>(entity);
registry.assign<char>(entity);

for(auto i = 0; i < 10; ++i) {
    runner.run(registry, [i](base &b, int, char) {
        std::cout << i << ": " << &b.value << " = " << b.value << std::endl;
        b.value = i;
    });
}

The result is intuitively the one expected for double buffering:

0: 0x602000004ed0 = 0
1: 0x602000004f30 = 0
2: 0x602000004ed0 = 0
3: 0x602000004f30 = 1
4: 0x602000004ed0 = 2
5: 0x602000004f30 = 3
6: 0x602000004ed0 = 4
7: 0x602000004f30 = 5
8: 0x602000004ed0 = 6
9: 0x602000004f30 = 7

Of course, this class works out of the box for N-ways buffering and sets no limits on the number of components returned. Moreover, components are laid out in different arrays and multithreaded stuff will benefit from this. Groups are unaware of double buffering and work like a charm in this case. A dependency function can be set to guarantee that all the components are always assigned/removed together.
Derived classes are used only to discriminate between the registry, but all what you get are references to the base class, that is what matters. Ironically, one could also set up double buffering for components without a common base with a small effort.

---

It's only a poc and it uses views under the hood. One can further refine it to use groups and to specify owned components, if any. However, it should give a grasp of what I was saying a few comments above and shows that it's easy to implement an easy-to-use solution for double buffering on top of the registry.

@pgruenbacher sorry for being summoned more than once but maybe you too can be interested.

[ArnCarveris]

@skypjack a runner of buffered_components? Hmm interesting.

[skypjack]

@ArnCarveris Yeah, put aside the names, it's just a way to forget about buffered components and make it transparent for the user.You give it a list to instantiate the class, then you refer to the base class and let the underlying type do the job for you. Just a POC but it works as expected and that's something around 30 lines of code probably, without unsafe casts or similar.

[Paolo-Oliverio]

@skypjack this looks good it made me think about a trail effect implementation using a fixed ring buffer for old sampled position, so tried to figure out how to implement it with this api and there are things I don't understand, not provided in the example.Naturally you can implement the trail effect without the buffered feature it is just an example.
Can you access an arbitrary buffered value or all at the same time? e.g. to build the actual poly trail or to smooth out the samples.
How do you rotate manually?As it seems that the run function rotates by itself, but I may want to advance it over time(e.g you may rotate samples after some amount of time is passed or after some distance is traveled).
I think you may also want to know the index of the actual head.

[skypjack]

@Paolo-Oliverio that's exactly the point, the registry cannot offer an API for all the cases and you've mentioned yet another few ones in your comment. This is why I suggest to implement it as an external tool.
The example code does rotate automatically each time you invoke run, but it's a line of code you can move in a dedicated function to call after N ms if you prefer. You're the only one that knows the requirements of your piece of code. Of course, current type is easy to retrieve as well.

[Paolo-Oliverio]

ok so a full general solution seems to be out of scope and possibly in the end not even a tool you end up using in a real use case where if you need to squeeze up to the last cycle you can probably end up quickly with an ad hoc solution solution with the actual Api.

[skypjack]

A full general solution built on top of the registry is theoretically possible. I'm not that sure the final API won't be a bit ugly tho. If you limit the implementation to your needs, it will be probably easier to work with and to maintain. I developed it in around an hour after a few failed attempts, so I don't expect it will take longer than half a day to implement something more complex.
A built-in solution offered by the registry doesn't fit well with some other features like groups, unless you are fine with unsafe and risky things or you go with an approach that resembles the one I used. The former case is something I won't even take in consideration. In the latter case, as it always happened with EnTT, if you can easily implement it your side and a built-in solution doesn't give you more performance or any other benefit, I prefer not to integrate it directly with the registry for several reasons.

Probably I'll write a blog post or a patreon post about that. It seems you're not the only one interested in the topic after all.

[pgruenbacher]

@Paolo-Oliverio here's what I did https://github.com/skypjack/entt/pull/171
I just do a pointer swap on the two components I want to double-buffer. ReadPosition and WritePosition. I just make sure that ReadPosition and WritePosition components are only created through my agent prototype and are destroyed together. It probably works fine with groups too, though I haven't tested. The main reason the PR is denied is that pointer swapping can obviously go wrong for a new user of the library. If i want to do triple buffer, I just do something like this

    _registry.swap<C1, C2>();
    _registry.swap<C3, C2>();

where C1,C2,C3 can be something like prevposition, readposition, writeposition which allows me to interpolate animations betwen prevposition and readposition while writeposition is occuring in separate thread

my way is pretty KISS, and it lets me decide on buffering later. E.g. if i think my agents need to double-buffer their height but I already have a Height component set everywhere, all I do is throw in a WriteHeight component into the prototype factory and I can swap, withou having to worry about refactoring evertying besides where the height component is being written to.

[After Reading the wall of text above]. yea my way is better. if you do a group view, just make sure the group includes all the buffered components and you're good to go I'm pretty sure.... I still need to test that but idk why it wouldn't work.

[pgruenbacher]

oh nvm groups def don't work with my swapping. it must be because the group has its own pointers to the component pools that it mantains... but i don't use groups at the moment anyways, and if I really need them I'll just try to see if I can have the group swap its pointers as well...

TEST(Registry, TripleBufferGroup) {

    struct C1 {int value;};
    struct C2 {int value;};
    struct C3 {int value;};
    struct OtherComp {};

    Registry reg;

    auto group = reg.group<C1, C2, C3>();

    auto proto = entt::prototype(reg);
    proto.set<C1>(1);
    proto.set<C2>(2);
    proto.set<C3>(3);

    for (int i = 0; i < 20; ++i) {
        if (i % 10 == 0) {
            // orphan
            reg.create();
        } else if (i % 4 == 0) {
            // entity with 1 other comp
            auto id = reg.create();
            reg.assign<OtherComp>(id);
        } else if (i % 6 == 0) {
            // entity with buffered comps and 1 other comp
            auto id = proto.create();
            reg.assign<OtherComp>(id);
        } else {
            // entity with buffered comps
            proto.create();
        }
    }

    for (auto ent : group) {
        ASSERT_EQ(group.get<C1>(ent).value, 1);
    }
    for (auto ent : reg.view<C1>()) {
        ASSERT_EQ(reg.get<C1>(ent).value, 1);
    }
    reg.swap<C1, C2>();
    for (auto ent : reg.view<C1>()) {
        ASSERT_EQ(reg.get<C1>(ent).value, 2);
    }
    // ah yes... fails here....
    for (auto ent : group) {
        ASSERT_EQ(group.get<C1>(ent).value, 2);
    }
}