rfcs
rfcs copied to clipboard
bevyengine
Eliminating blockers for Minimal Fragmenting Relationships
RFC with a focus on the technical blockers for a hypothetical minimal fragmenting relationships implementation. Less time has been spent on the summary and motivation aspects as those have been well explored by Sander's articles (example) as well as prior RFCs, PRs, discord discussions etc.
This looks great! And I think it's also a more reasonable size than #78 (which I should probably close for now). One thing I would like slightly more clarification on is the 'fragmenting' part of 'fragmenting' relationships. Even in #78, I don't think it's adequately explained. My current guess, based on context clues, is that adding relationships means that every (component, entity) acts like a new component for the archetype system, so (component, entity1), and (component, entity2) would be in two different tables, hence splitting the tables, hence fragmenting the tables, which makes iteration speed for queries slower (less predictable access patterns).
I think that's it, but wouldn't that also mean that when you don't use relations, you don't encounter any extra fragmentation, so you shouldn't see performance regressions?
Your interpretation of the "fragmenting" part is correct, I took a quick edit to make it more explicit but it could use more detail. Iteration for queries could hypothetically be slower for a set of entities that previously would have occupied the same table however if the query is only iterating dense components we can still use dense iteration and shouldn't see any regressions. One advantage we have over flecs here is we already have split storage. Since this RFC doesn't cover data on the relationships iterating targets (which are stored in the archetype not component storage) will always be dense and when we do support them we can opt for sparse storage when we don't want to impact iteration speed of dense queries that don't access the relationship.
Your also correct in that if you don't make use of relationships you won't have any increase to the fragmentation, however once you do it can increase quickly, especially if/when bevy_hierarchy uses them.
"Fragmenting"
I'd like to add some comments about "fragmenting" since that's bound to receive the most questions. We should stop calling it "fragmenting". It places too much emphasis on the potential downsides of the feature. A better description for this is "archetype level". This is a tool which can have downsides but has many desirable upsides akin to the archetype ECS model we already have.
Other implementations
I do not think this RFC or any efforts towards this feature should deviate away from an archetype level implementation and generalizing to just "an implementation of relations" would be a mistake. The other two big contenders for a relations implementation in the context of an archetypal ECS have been explored at this stage:
- Indexed
- "Non-fragmenting" (aery)
Indexed
To my knowledge there's no specific crate like aery that offers this as a standalone feature but this already exists in every other crate. Many crates have an "index" of some sort in a resource that creates relationships between entities or data stored outside the ECS. The problem with all of these is indexing is a very different data model to archetypes. This presents syncing problems and an even bigger ergonomic problems. Different data models create boundaries in your app that you have to cross every time you access data. Think getting stuff in & out of egui contexts for widgets.
Non-fragmenting
Aery was my attempt at this for my final year university project. It has less of the problems of indexed relations because it's closer to the archetype model (it just stores Entitys in components). It's serviceable for many usecases but it's very unoptimal for many more & has nowhere near the amount of query features I'd like. It originally started off as a fork of bevy but half way through I decided I didn't want it in bevy for two reasons.
- The performance problems of highly fragmented scenes can be addressed.
- A better version of "non-fragmenting" relationships can be implemented on top of archetype level relationships.
TLDR
In short it makes the most sense for an ECS relationships implementation to use the same data model as the ECS. Archetype level relationships are what we should aim for. The worst case scenario is you would have as many archetypes/tables as you have entities which is already how the vast majority of commercial games written in OO paradigms work.
The other two big contenders for a relations implementation in the context of an archetypal ECS have been explored at this stage:
There's also Flecs union relationships, which are a non-fragmenting relationships implementation that are widely used by flecs users in combination with fragmenting relationships.
A fourth non-fragmenting implementation has just finished and will land soon, which'll let you use component members as targets of relationships.
If it's useful in any way, we have some prior art on this over at Veloren that's been in use for a number of years and has proven itself under a number of different situations.
We call it the 'link system', and it's a generic framework for defining and maintaining relationships between ECS entities. It supports both 1:1 and 1:many relationships. It's the product of iterative development, and replaces several previous failed attempts at managing entity relationships.
Currently, it is used to define:
- Rider/mount relationships (like a player riding a horse)
- Volume entity riding relationships (many players sat on seats in an airship, moving through the air)
- Tethering (physics-based ropes that attach entities to one-another, or to the terrain)
I'm happy to answer any questions about it.
