Changes bevy would need for flecs-like fragmenting relations

[maniwani]

Was asked to document this somewhere.

For people wanting to implement flecs-like fragmenting relations in bevy, currently bevy_ecs isn't well-equipped to efficiently handle an arbitrarily large number of archetypes. This is a quick summary of changes that I think will fix that and let someone trial an implemantion.

Improve Worst-Case Query Construction Time

Constructing and updating queries involves iterating all archetypes (that the query has not yet seen). A more efficient solution would be for the Archetypes structure to have a HashMap<ComponentId, HashMap<ArchetypeId, ArchetypeComponentInfo>>. Then queries can simply iterate their components and find the intersection of their archetypes.

This map would also enable removing archetypes when a particular relation can no longer exist.

Improve Worst-Case Access Iteration Time

Access is the main primitive used to check queries and systems for conflicts at runtime. Internally, it makes use of FixedBitSet instances (I assume because they're very small). Iterating a FixedBitSet is much faster than iterating a simple Vec<bool> when the 1s (true values) are sparse. But that iteration time will grow linearly with the number of (archetype, component) pairs that exist, not just the ones that match.

I don't know at what point FixedBitSet would start to fall behind, but my suggestion would be replace those FixedBitSets with HashSets.

Edit: To greatly reduce the number of matched elements, queries and systems could ignore the "target" of any relation pair and only look at the "relation kind". In other words, their Access would have an ArchetypeComponentId for (archetype, relation kind). That would limit parallelism, but it might be worth the tradeoff.

Telling Relation Pairs and Entities Apart

If our relations are identified as (entity.index(), entity.index()) pairs like in flecs, we might have to change the underlying bit pattern of Entity to have a way to reliably tell them apart from pairs. The simplest form of this would be a flag bit, with flag == 0 meaning entity and flag == 1 meaning pair.

Naively, this would reduce the hypothetical maximum number of entities from 4 billion to 2 billion. That isn't a big deal, but it might be avoidable. Entity and target indices could continue to use the full u32 range if the "relation kind" is restricted to component ids and we arbitrarily limit component ids to a smaller range of indices.

[ 1 ][ 31 ] (entity => generation, pair => 1st index)
  ^
 MSB (flag)

[ 1 ][ 31 ] (entity => index, pair => 2nd index)
  ^
 MSB (unused, always zero)

However, if there's no need for untyped methods, we can maybe avoid the flag bit.

Components as Entities

The last change is making ComponentId values use indices from the Entity address space. This has nothing to do with performance, but it would let components take advantage of everything we have for normal entities.

We would need to modify World::init_component<T> to account for this by spawning an Entity to represent T.

One other thing we might want is to do is reserve a nice power-of-two number of Entity values upfront for normal components (maybe 256?). That way, we can still use a Vec for most of them, with a HashMap for the bulk of the relation pairs. Might still be premature optimization at this point, though.

[james7132]

One potential alternative to FixedBitset and HashSet<usize> are compressed bitsets (roaring and tinyset). Like HashSet it's size scales with the total member count instead of the maximum member value, and like FixedBitset it still can use bitmasking as an efficient dense iterator. The tradeoff is that they tend to be less efficient for small bitsets (small maximum value, dense distribution), which has historically been the case for Access. However, if we're looking to use fragmenting relations, their use may be more compelling.

[maniwani]

I dunno if Access using FixedBitSet was motivated by a specific issue or was just an opportunistic choice to save space, but I do agree that if a system matched a lot of archetypes HashSet<usize> could get pretty big.

[maniwani]

Sander also suggested that if it becomes a problem, we could have Access ignore the "target" of the pairs, and conflict on the "relation kind" only. It would limit parallelism but reduce the amount of ArchetypeComponentIds we'd have to care about.

Edit: Also if we could somehow not care about ZST components (currently we have to because each "instance" still has its own ComponentTicks).

[james7132]

One thing that isn't mentioned is how this will impact archetypal query iteration. Dense iteration will likely still remain unchanged, but higher archetype fragmentation will negatively affect any query with a sparse set component in it.

[iiYese]

how this will impact archetypal query iteration

Is the "this" here referring to the introduced archetype fragmentation from a fragmenting relations impl?
Or the outlined changes to support fragmenting relations?

[james7132]

The introduced archetype fragmentation. Increasing the number of matched archetypes for archetypal iteration will in incur the cost of switching archetypes more often. This increases overhead for the same amount of work.

[iiYese]

The unused MSB flag in the target portion of the relation pair could be used to indicate wildcard targets. The actual ID portion could then be used to store the ID to a "rule" entity? If we were to go about rules in that fashion.

Rules allow expressing relations in terms of relations for those who don't know prolog.
likes(Alice, anyone) :- likes(anyone, Alice). says "Alice likes anyone if they like Alice".