Consider Removing Sparse Set Component Storage

[ElliottjPierce]

Right now, Bevy has two kinds of storage: Table and SparseSet.

Table has fast iteration speed, dense storage, and can have its exact location found per entity with just a TableId and TableRow. For each entity, we need to store a table id and row.

SparseSet has slow(er) iteration speed, sparse storage, and needs it's own Entity to "sparse set row" map. For each sparse set component, for each entity, we need to store its sparse set row.

So why use sparse set? It has one small advantage: it's much faster than tables at insertion and removal.

But, the insert and remove cost is not zero! In fact, there have already been times when even sparse set was too slow, and the best solution was to have a table component that was just an Option<MyActualComponent>. So if you don't need insert/remove speed, Table is way better, and if you are inserting/removing enough that Table isn't worth the iteration speed, even SparseSet is also too slow.

Maintenance cost of sparse set storage.

Bevy seems like it has bent over backwards to support sparse sets. For example:

• Queries have two implementations for almost everything: one really fast one for when everything is in table storage and one slow(er) one for when just one component is a sparse set.
• Query data have storage switch unions, which work great, but are another unsafe system to maintain.
• We need archetypes as a "table of tables" which is additional indirection that doesn't buy us anything unless it involves a sparse set (now that ArchetypeComponentId is being removed).
• Other types are bloated with Option<TableRow> etc that are unwrapped unsafely when we know the component is a table.
• We need to create ComponentSparseSet as bundles are created, which is overhead that isn't useful for table components.
• Any kind of component access needs some form of branching for what kind of storage it is, even though almost all components are table storage.

This isn't an exhaustive list, but it's enough to get my point across. It takes a lot of effort to maintain, test, and bench the ecs when there are two fundamentally different storages interacting.

Why I think sparse set should be removed

In my opinion, the benefits of sparse set storage are not worth this effort, not by a long shot. When is the last time you needed a sparse set component? Probably never. If you did, it was because you were inserting and removing it a lot, but a Option<MyActualComponent> table component would be faster for that anyway. The only reason you might need sparse set today is if you needed an observer/hook for when an insertion/removal happened, and you were inserting/removing very frequently.

Looking for alternatives

The only reason not to use a Option<MyActualComponent> table component when you need fast insertion/removal is because it currently has horrible UX, like not having hooks, etc. So why don't we fix that?

I would propose a new MaybeTable storage type. This could sit in the existing ThinColumn type in the existing Table type. All we would need is a MaybeUninit<FixedBitSet> on the ThinColumn (or something similar) to track which rows have the component. It would be uninit for Table components and init for MaybeTable. For iteration in queries, we would just need to ask the these columns if it has a component at a row. For normal columns, we wouldn't need to ask this, so that's 0 cost.

When inserting a MaybeTable component, we would set the row to Some if its table already has a column for it, otherwise we do a table move. When removing it, we just set it to None. When removing a normal table component, we also change its table to one that has no columns for any of the MaybeTable columns for which the row has None on that column. This is cheaper (since there's less to move) and it prevents the ecs from retaining memory that is no longer needed if the component will not be inserted on that entity again.

In general, this idea benefits from the apparent pattern that entities generally have a "kind" associated with them. For example, a 3d physics entity is unlikely to have a 2d ui widget component. There are times when an entity of the same kind has component removed/inserted without changing its kind. For example, an enemy entity may have an OnFire component inserted when the player hits it with a flame arrow, removed after 5 seconds, and inserted again with another arrow attack.

For these entity kind situations, this solution is great! Inserting and removing on an entity over and over again is fast, much faster than a sparse set. Filtering may be faster than a sparse set; it's just a fixed bit set lookup instead of chaining together archetype fetches. Iterating may be faster; again, less archetype fetches. Note that we could make this much faster by storing an Option<(IndexOfPrevious, IndexOfNext)> instead of a bit, but that linked list solution also slows down insertion/removal (but is, I would guess, still faster than the sparse set).

The only disadvantage that I can think of with this solution is that it doesn't work well for arbitrary components that are not usually inserted more than once per entity. But at that point, insertion speed is probably not as big of a factor; use table storage.

This is not the only alternative, but it's the best I've thought of. It takes entity memory from O(num_entities * num_sparse_set_components) to O(num_entities). It improves insertion/removal performance. It may usually improve iteration and filtering performance (unless it's only inserted/removed once per entity). And, the downsides are IMO unrealistic because of the entity kind pattern.

I know this is a hot take, but I do think this could improve performance and vastly simplify complexity in the ecs. I'm definitely curious if others share this opinion.