Consider compacting ComputedVisibility via bitsets

[james7132]

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

ComputedVisibility is effectively a newtype around a bool that is recomputed every frame. This representation requires a one-byte bool value and a 8-byte change tick in ECS space. This works well right now, but 7 of the 8 bits in the bool effectively go unused. A more compact representation can lead to better cache locality.

What solution would you like?

Remove ComputedVisibility as a component, and replace it with a ComputedVisibilities resource which wraps a FixedBitset. This removes the change detection overhead and uses only one bit per entity. This compact representation uses up to 72x less memory, is much more cache friendly, and reduces the fragmented iteration costs of visibility systems. The bitset would be keyed only by Entity ID, ignoring the generation to minimize memory usage. As Entities attempts to minimize holes in entity coverage, this bitset would be relatively dense. The API for such a resource could be roughly outlined as follows:

struct ComputedVisibilites {
  entities: FixedBitset,
}

impl ComputedVisibilities {
  pub fn resize(&mut self, entities: &Entities);
  pub fn clear(&mut self);
  pub fn mark_visible(&mut self, entity: Entity);
  pub fn is_visible(&self, entity: Entity);
}

As computed visibility typically follows the pattern of a once-per-frame update system, followed by the all of the extraction systems reading it in parallel, a singular resource can be used without needing additional locking.

What alternative(s) have you considered?

#3796 changes Visibility and ComputedVisibility into ZST marker components. This removes the bool entirely, but introduces further archetype fragmentation, and makes it heavier to mark certain entities as visible or not. This alternative isn't 100% incompatible with this design, as this issue only proposes changing ComputedVisibility, though using a bitset based Visibilities resource could reduce the time spent copying initial visibility state.

[james7132]

As seen with the experimentation in #4663, it does seem like this would speed up clearing the bits and improving memory locality, but the overhead of doing a bit check of every visible entity in subsequent systems potentially outweighs the benefits here.