Accelerate change detection by redundantly storing change ticks

[alice-i-cecile]

What problem does this solve or what need does it fill?

Currently, change detection is an O(n) operation, where n is the number of components in matching archetypes.

In cases where large amount of change detection must be performed (such as for networking), this check can become a bottleneck.

What solution would you like?

Redundantly store change detection data at two additional levels:

1. At the component-type level (the Column).
2. At the archetype level.

Then, when checking for changes to a component, check at the component level, then the archetype level, then the individual component level, breaking early at each step if no recent changes have been detected.

What alternative(s) have you considered?

Only implement one or none of these redundant storages. Evaluating this change will require much more robust change detection benchmarks, see #4883.

Additional context

This will likely be cleaned up by #4809, as these optimizations only make sense for components. Related to #4882, which could further configure this behavior.

This idea was originally discussed by @DJMcNab and @PROMETHIA-27's; I'm just writing it up :)

[cart]

It is worth calling out that this would involve more data flow (passing pointers to each new level's mutation tracker to each Mut<T>), writing to each level on each mutation, etc.

However naively, this will be unsafe (as there can be multiple writes to components within an archetype). We could use atomics to avoid stepping on toes / make this safe.

So while this extra hierarchy will allow us to skip checks during Changed<T> iteration, it will increase the cost of mutation (and generating Mut<T> pointers). It is unclear to me if this is worth it in practice.

Currently, change detection is an O(n) operation, where n is the number of matching archetypes.

This isn't right. It is O(n), where n is the total number of component instances.

[cart]

Worth exploring this idea, but I'm guessing the extra work to maintain the hierarchies will generally be "not worth it", given that change detection is enabled by default. Maybe this should be configurable per-component (probably defaulting to the current non-hierarchical-per-entity-component tracking by default).

[alice-i-cecile]

This isn't right. It is O(n), where n is the total number of component instances.

Fixed. This was just a typo 😅

[alice-i-cecile]

@james7132 points out that we reduce coordination overhead by doing this pessimistically, by effectively mirroring the Mut structure at the archetype and column level. Whenever these larger storages are mutably dereferenced in any form, update their change ticks.

This will be somewhat less granular, but as false positives are fine, I think that this is a better tradeoff than plumbing the information back up.

[DJMcNab]

https://github.com/DJMcNab/bevy/tree/filter_shortcut is a pre-existing prototype of this. It didn't seem to be a significant regression in my unscientific tests, but we don't have great benchmarks for this.

[alice-i-cecile]

More discussion on how we could tangibly achieve this: https://discord.com/channels/691052431525675048/749335865876021248/1205274375842955365.

Consider the following design from @james7132.

for archetype in matched_archetypes {
   let mut changed = false;
   for fetch in archetype {
       if F::matches_entity(fetch) {
          // do mutation
          changed = true;
       }
   }
   if changed {
       archetype.update_tick();
   }
}

If F::matches_entity is always true, the branch is eliminated and the compiler can then just lift the changed = true out of the inner loop.

To handle Query::get and other methods that access a single entity, we'll probably need to put it into the Drop impl for the fetches.

@maniwani has another proposal:

for archetype in matched_archetypes {
   if archetype.has_fine_grained_change_detection(component_id) {
       // iterate entities, construct `Mut` with entity's `UnsafeCell<Tick>`
   } else if archetype.has_changed(component_id) {
       // iterate entities, construct `Mut` with archetype's `UnsafeCell<Tick>`
   }
}