Entities::alloc_at and alloc_at_without_replacement currently have performance issues. See this conversation for the full background.

When and why is it slow?

Both these functions currently have a linear search through the pending list to try to find and remove the requested entity. When there are lots of pending entities, this is very slow.

See also the source.

Practical Impact

In the conversation mentioned above, a user was spawning waves of sprite projectiles. Each wave was ~90,000 entities and was spawned and desawned over 8 seconds, repeating for each wave. This lead to measurable frame drops because, on the second wave, the render world was using alloc_at_without_replacement with 90,000 entities in the pending list. For massive, wave oriented games, this is a big deal.

Solution

Add a field to EntityMeta that stores the index of the entity in the pending list if it is fee. This will remove the linear search and fix the problem.

Downside: EntityMeta will be bigger, so less of them can fit in cache. This is relevant to lots of very hot paths.

Alternatives

We could try to keep the pending list small by not storing tail entities. For example, if there are 16 entries in meta and entities of index 8-15 are in the pending list, we could remove them since their pending nature could be implied by shortening meta. But this gives extra overhead and can be ruined by keeping just one high-index entity around.

We could also try to pack the index of the entity in the pending list into some other fields of EntityMeta. Maybe table_row or something, but that looses/invalidates other information about the entity. If anyone has a way of doing this without dropping some information, this would be an ideal solution.

Finally, we could sort the pending list after Entities::flush. This could let us change the linear search to a binary search, but keeping the sorted invariance may have additional overhead.