Hypothetical and factual archetypes: unifying our data access checks

[alice-i-cecile]

While working on bevyengine/bevy-website#222, @cart point out that the mental model I use for determining "can two queries be used in the same system" is not the same as our actual implementation.

As of Bevy 0.5 (and almost certainly Bevy 0.6), we check for data conflicts in two different ways. This overview is meant for someone who already has a basic sense of how the internals work; check out the linked PR for a longer explanation.

Factual conflicts

Factual conflicts arise between systems which conflict on actual, instantiated bits of data: typically entities.
Right now, this logic is only used for parallel scheduling.

The basic algorithm is fairly straightforward.

1. Each entity belongs to an archetype, corresponding to its unique set of components.
2. These archetypes are subdivided into archetype-components, corresponding to a single component type within that archetype.
3. When a system is checked to see if it can be run, it requests access to all of the data that it needs (in terms of archetype-components), based on its system parameters. Systems can only run if all of the data that they need is unlocked.
4. When a system starts all of the archetype-components that it has write-access to are locked until the system completes.

This is simple, fast, and maximally parallel: we can't (efficiently) divide our data any further.

Hypothetical conflicts

Hypothetical conflicts arise when two systems / system parameters / queries could conflict, given a hypothetical entity with the correct set of components.

We are concerned with hypothetical conflicts when detecting execution-order ambiguities, and when checking for incompatible system parameters. The reason for this is fairly simple: strange panics in the middle of running your game because an unusual entity was created is Bad UX.

However, accurately computing whether two system parameters could conflict (our base case) is less straightforward.
We immediately see that we can restrict our analysis to archetypes, rather than particular entities: entities with the same set of components will have identical properties for the concerns we care about.

Naively, we could use the exact same approach as we do for factual conflicts, but build out every 2**n_components combination, "run" the first system, and check if the second conflicts. Obviously, this is a terrible algorithm. But, it would work, and provides a baseline!

Current algorithm

Under the hood, the existing code doesn't reason about things in terms of "hypothetical archetype-component accesses". Instead, it does something different, and reaches the same conclusions.

1. Check for unfiltered conflicts, on a per-component basis. This conflicts if the same component is accessed, and at least one of the access-levels is write.
2. Then, filtered accesses are checked. The critical logic is that if one access has a Without, and the other has a With (or requests the data normally), the queries are always compatible.

Conceptual algorithm

As described in the new book PR, I use a different algorithm, much more closely linked to the approach we use for factual conflicts.

1. Examine which archetypes a query could access.
2. Refine these into archetype-components.
3. If there are overlapping archetypes-components, check if the data accesses conflict.

Equivalency

These two algorithms aim to accomplish the same goal, and produce identical results. Why?

The unfiltered case is trivial: the maximally conflicting archetype is the archetype with all components. Then, we can perform one-component-at-a-time comparison of accesses, as done in both algorithms.

Things get more interesting when we move to filtered accesses.

It turns out that Without is (currently) the only way to transform conflicting access patterns (on the component-level) into non-conflicting ones. This makes sense: if we can jump to the maximal archetype if no queries exist, adding more data accesses isn't going to take anything away.

We can only go from a conflict to not-a-conflict if and only if we have a Without in one data access, matched by a With on the other. This splits the archetypes into two disjoint sets, causing the hypothetical archetype-component accesses to no longer conflict.

Conclusions

As I've hopefully convinced you by now, the existing algorithm for hypothetical data conflicts is equivalent to the proposed one, and is closely related to the algorithm we use for factual data conflicts.

This matters because:

1. It's a clearer, more principled way to teach this feature of Bevy.
2. It opens the door to alternative approaches to implementing these checks, and possibly a partial unification of the code base.
3. It allows us to clearly reason about extensions to these systems, such as Archetype Invariants #1481.

[cart]

I'm pretty sure I like the angle here / in the new book content. "hypothetical vs factual" conflicts is a useful framing from a high level, although I think the original framing is more approachable for determining conflicts in practice because the algorithm can be easily summed up / understood from two succinct sentences: "If two Queries both access the same component and one or both of them mutates the component, they will conflict. This conflict can be avoided if one of the Queries adds a Without filter for one or more of the components in the other Query." I think the basic learning path should cover quick functional descriptions of SystemParam conflicts within a system, why we need to fail in those cases, and quick functional descriptions of ways to fix conflicts. Additional theory and descriptions (especially anything containing set theory, "disjoint proofs", "hypothetical vs factual" conflict distinctions, etc) should probably be hidden behind an "advanced" section.

[alice-i-cecile]

I think the basic learning path should cover quick functional descriptions of SystemParam conflicts within a system, why we need to fail in those cases, and quick functional descriptions of ways to fix conflicts. Additional theory and descriptions (especially anything containing set theory, "disjoint proofs", "hypothetical vs factual" conflict distinctions, etc) should probably be hidden behind an "advanced" section.

Yep, that's exactly the approach I took :) The "how do I fix this stupid error" overview is brief, and in the ECS chapter where we discuss queries.

[cart]

Brilliant ❤️

[cart]

Thanks for putting in the time + rigor here!

[alice-i-cecile]

I'm glad you like it! I'm excited to see if this can yield a reasonable algorithm for archetype invariants (far) down the line.