System-order-independent ECS change tracking

[cart]

The current change tracking system is very lightweight, both for event generation and consumption (which is why we can enable it by default), but it has the following problem:

schedule.run()
  System1: Change<T> query
  System2: mutates T
  world.clear_trackers()
schedule.run()
  System1: Change<T> query ... misses System2's changes

In most cases, this can be worked around via system registration order and stages, but I anticipate some cases that cannot work around this behavior, as well as general confusion from users like: "why isn't my system running ... im definitely mutating this component?"

I think it would be useful to (optionally) allow stateful "order independent" change tracking. I posted some ideas here: #54

[alice-i-cecile]

So, the current behaviour has a seriously broken edge case that seems likely to emerge in larger apps.

Suppose we have a system which relies on Changed<Foo> and mutates Bar as well as a system that does the converse. No matter which order we place them in, we will not be able to properly process both sets of changes: they'll silently vanish at the end of the frame. As your app grows, the number of possible interactions of this sort rises quadratically, and you can also get larger loops with the same issue.

Pulling from #54, there seem to be a few options.

1. Current behavior, which is problematic for the reason given above.
2. Double-buffering. Somewhat inelegant, makes handling more complex and duplicates data. The requirement to check whether the last frame's entities are still valid (from ECS Change Events #54) seems like a red herring to me: there's no guarantee that they're valid even when only looking within the same frame.
3. Stateful queries with modified generations.
4. Track on a per-system basis whether each change has been consumed by it. Like 6, but heavier. Does allow dynamically changing the set of systems more safely though. (I think this is the same as "For systems with a Changed query, identify systems with &mut T after and track changes that occur" from ECS Change Events #54). Like 6. but much heavier. Does allow for dynamically changing systems more safely though.
5. Manual clearing of changes. This is really onerous and hard to maintain, and probably will end up with most users running into the problems above in their own implementation. Could be handy for certain types of deferrable cleanup systems I guess?
6. Ensure that changes hang around for "exactly" one frame, by tagging the changes with the system that caused them, then cleaning them up after that system runs in the next frame. Because these changes require reading the resource / component in question, I think that we guarantee that the order WRT all other relevant systems stays consistent between passes. The new "system label" tech that Ratys is working on would work well for this, or the existing SystemID may work.

Edit: Apparently #6 is called a "ring buffer", which should help with finding prior art on efficient implementations.

[fopsdev]

i'm pretty sure i've read something about a "Changed"-queue and the system gets called over and over again until its empty.
But i could be completely wrong and i sadly don't remember where i picked this up...

that should kinda solve it?

[alice-i-cecile]

I can see the value in a self-recursing queue of Changed objects that @fopsdev, but I'm not sure it's a great fit here.

The self-recursing Changed queue seems hard to fit in:

• we would need to repeatedly run every system across all stages that takes a Changed. That would result in some very strange ordering, making it harder to reason about the logic flow, and avoiding double-counting would be hard
• the list of Changed components here are never actually consumed under the current model, in order to ensure that they can be used by multiple orthogonal systems. This is the critical distinction :) Your model works better for a proper event stream; changing this change tracking to use an event model requires a lot more manual handling WRT re-emitting events if you're not done with them and so on
• possibility of accidentally writing emergent infinite loops, or just very long ones that cause lag spikes

[mockersf]

How about firing events at the end of a frame before clearing the marker bits?

• for order dependent change detection within a frame, use query filter Changed
• for change from last frame, react to events ComponentEvent::Changed<Component>(Entity) (not sure this type signature would work but it would be nice)

It could potentially be a large number of events

[alice-i-cecile]

How about firing events at the end of a frame before clearing the marker bits

I don't think this gets around the shortcomings of event-based change detection: namely, that you can't elegantly have several consumers of them. If you have two or more systems that come before your change-generating system, your first system will eat the event and the second one never encounters the event.

A simple double-buffer, where we keep around two copies of Changed, one for the current frame and one for the last seems like a strictly better version of this. But I'm still nervous about the complexity and fragility of actually working with it.

With a double-buffer, there's no way of knowing whether we already processed this change in the last time step, resulting in double-processing of changes that occured in preceding systems. To get around this, we could only process certain events that occured in the last time step, but then you can't handle antecedent systems and your code breaks again if the change-generating system gets moved.

You could bypass this by attaching a unique ID to each changed, but then you're left with the overhead of tracking which change has been seen in every change-detecting system, which is a giant mess and probably very costly.

I'm increasingly convinced that solution 6., a ring-buffer, is the only feasible way to handle this. All of the other solutions seem to introduce either subtle logic bugs or require very manual, fragile change detection ala events, which are prone to reintroduce those exact same logic bugs when our end users try to handle the changes on their own.

[mockersf]

namely, that you can't elegantly have several consumers of them

But you can, by having an event reader local to your system it will keep its own track of which events it read and let other systems read them too

I think a ring buffer has the same issue as a double buffer, you'll have to check that the entity still exists if you try to use it in the next frame

[alice-i-cecile]

But you can, by having an event reader local to your system it will keep its own track of which events it read and let other systems read them too

Ah cool, I was mistaken on exactly how Bevy's event handling works then. That involves keeping track of a seperate list per system though right?

I think a ring buffer has the same issue as a double buffer, you'll have to check that the entity still exists if you try to use it in the next frame

The issue I raised in my previous comment is distinct from this :) The entities-potentially-not-existing issue raised by you (and cart in his original comments) isn't unique to ring buffers or double buffers. It actually crops up in our current Changed implementation in 0.4. Entities can be deleted mid-frame via commands: they're processed at the end of each stage, so you can easily try to access an entity that no longer exists if you're just operating off the Changed list.

[mockersf]

Ah cool, I was mistaken on exactly how Bevy's event handling works then. That involves keeping track of a seperate list per system though right?

Each system only keeps a counter. There is a Res event list that is a double buffer, and a Local event reader that counts how many events was read by a system (example). implementation is quite nice and easy to read, and I think without risk of playing same event twice in a reader.

[alice-i-cecile]

Here are my thoughts as I start to do some more concrete design work on these proposals, looking at component flags as our lens.

Component flags are essentially metadata, attached to a single entity-component unit of data.

Desiderata

1. Component flags are set whenever a specific action occurs.
2. Component flags only exist for valid entities.
3. There should be no (or very little) performance cost for components that aren't tracking these changes.
4. The performance cost of using a flagged component should be reasonably low.
5. The amount of memory used to store flags must not increase over time.
6. A component flag should be able to be detected by any other system, independent of their relative location in our scheduling graph.
7. A component flag should be able to be detected by the system that set it on the next tick.
8. Each component should be detected exactly once by every other system.
9. External users should be able to easily add more component flags of their own.

I would say that overhead on non-flagged components should weigh at about 10 times more than overhead on flagged components, as most components will be unflagged.

6. and 7. are distinct criteria here, since I'm not sure that 7 should be true.

System-ordering properties

In general, the order in which systems run is neither deterministic nor linear. At first blush, this would seem to make hitting property 8 very challenging: if our systems are running in an unpredictable order, how can we be sure that a single flag always persists exactly long enough to be seen once and no more by each relevant system? If the order was fully unconstrained, for any fixed persistence window, the change may be seen 0, 1 or 2 times by another system.

We could get around this by storing a list of SystemID for each component flag (or conversely, store a matrix of entities x component flags for every system), checking to ensure that each system x component flag interaction is handled exactly once before resetting our component flag. This requires a great deal of memory and checking though, especially as our number of systems grows.

But, any valid schedule has two much stronger properties:

1. Systems which write to a particular entity-component follow a total order. We always know whether one writing system occurs.
2. Systems that read a particular component follow a partial order, constrained by the systems that write to that component. We always know which two component-writing systems a component-reading system occurs between.

This property is fundamental to how games in Bevy should work, rather than a quirk in the current scheduler. Without it, your behavior is fundamentally not reproducible, as you could get data-processing operations happening out of order.

As I try to show in my next comment, we can use these properties to persist our component flags for "exactly one tick". If we hang on to our component flags until the next time the originating system is run, they will have been seen by every other relevant system (that reads or writes to the associated entity-component) precisely once.

This leads us to another constraint when considering property 9: any system which can write component flags must have write-access to the described entity-component. Similarly, any system which reads component-flags must have read-access to the described entity-component. This makes sense: component flags are essentially a type-agnostic extension of the data contained in every component. We need to wait for changes to them to resolve before we can be confident in using them.

[alice-i-cecile]

A simple "one tick" component flag proposal

1. Store component flags as an Option<SystemId>. If this is None, the component flag is not set. If it is Some, then the component flag was most recently set by the recorded system.
2. Whenever some action occurs on the entity-component unit of data in question, set the system flag, marking it with the the current SystemId, overwriting any previous state.
3. When entering a system (or exiting, based on your feeling on property 7 above), wipe all component flags who match the SystemId of the current system.
4. When entity-components are deleted (including when entities are despawned), remove all associated component flags.

And that's it! We're guaranteed to see each change exactly once for all other relevant system because of the total order given in the post above: component flags can only be set (either through overwriting or erasing) in systems that have write-access to the entity-component in question.

If we overwrite it with a newer flag, we're still processing that data when we should, and not wasting any effort (because we need to process the longer lifetime for the fresher system).

Notes

• this costs us a little bit of memory: we need to store a SystemID, rather than just a single bit. We could probably compress this by only considering systems with write access to the component in question, defining a total order, then decoding it when needed.
• If you have said numeric total order, you can swap to a tick-tock cycle to more quickly assess whether a flag should be reset, based on the system number being called, rather than having to traverse by SystemId
• I'm not sure how this works with the current DerefMut magic that's currently used by Changed: there may need to be some refactoring
• Ideally we can factor out this behavior, so then it's only occurring for the components that have an appropriate marker in at least one system's parameters
• You'll obviously want to use this same behavior for Resources as well :) Changing Events to work using this style of queue may also be desirable
• If not all systems are running every tick, this behavior gets a little wonky. Changes can persist for longer than they should while a system is sleeping, and if a system is asleep it can miss changes. The tick-tock variant solves this first problem nicely, and is probably better
• You also need to account for writes made via Commands (caught by @mockersf)

[alice-i-cecile]

To expand on the tick-tock system mentioned above:

1. Generate your total order over the systems that can write to the flagged component.
2. Assign each of these systems a system_time in sequence, stored as a small unsigned integer.
3. Every pass of our game loop is either a tick or a tock. On a tick, the system's system_time is recorded as the base system num; on a tock, add 1/2 your integer size to the base. This gives us a nice circular measure of time.
4. In each system, for each tracked component that we have write access to, wipe all component flags that were set between the last time the current system ran, and the current system_time.

(This idea was courtesy of @alercah).

Rather than having to traverse through these component flags one at a time like in the SystemID based proposal, store component flags that are set in their own data structure, always adding new flags to the end of the current list. When you need to reset flags, you can simply slice off the start, found by either a search or recording how many were added and how many were overwritten each time they're modified.

I'm not sure if that optimization would be net positive; I worry that it would make filtering queries slower, since the flags wouldn't be stored aligned.