Improve Performance of Entities::alloc_at

[ElliottjPierce]

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.

[alice-i-cecile]

We should start by adding a benchmark specifically stressing this. The exact pattern from the user of "spawn 100k entities, despawn most of them, try spawning more" is really suitable for creating a microbenchmark that we can use to measure regressions against this.

[ElliottjPierce]

We should start by adding a benchmark specifically stressing this.

I'm on it!

[alice-i-cecile]

Aha! This code, where we're spawning specific entities, seemed highly unusual to me. With the advent of the retained rendering world, this shouldn't ever be needed. Going up the call stack, the offending methods only look to be called by insert_or_spawn_batch, which #18035 removes our internal usage of.

[alice-i-cecile]

I think that the right fix immediately is going to be to get some form of 18035 merged. Long-term, I think we should just remove this functionality completely, rather than risk slowing down any of the much more important paths.

[ElliottjPierce]

Long-term, I think we should just remove this functionality completely.

100% agree here. IDK where alloc_at would really be necessary. I'll get some benchmarks in shortly and defer to you for the solution.

[cart]

I believe that if the use cases in the renderer are removed all current motivating use cases will be gone. However the ability to claim a range of entities that remains invalid until they are made valid is the type of thing that might come up again (and in those cases, being able to "spawn into" the entities to make them valid does make sense). That being said, I'm not opposed to removing this now given its general "weirdness factor" and performance implications. No need to worry about a future that might never come.

If we plan on removing support for this, we should also look into some of the "invalid checks" in Entities. Iirc we added additional checking to support this scenario, and we might be able to simplify / optimize some things. Worth digging up the PRs that introduced those changes.

[alice-i-cecile]

However the ability to claim a range of entities that remains invalid until they are made valid is the type of thing that might come up again (and in those cases, being able to "spawn into" the entities to make them valid does make sense).

Agreed here: I think that there's a decent chance that we end up wanting this functionality in some form for niche, performance sensitive things. Most of the applications I've seen for entity partitioning seem like they overlap heavily with multi-world scenarios, and given the relative intuitiveness of multi-world I'd prefer to push in that direction for now.

[ElliottjPierce]

given the relative intuitiveness of multi-world I'd prefer to push in that direction for now.

Music to my ears. After 0.16, I am curious what y'all would think of #17937 too, but I don't want to get ahead of myself.

However the ability to claim a range of entities that remains invalid until they are made valid is the type of thing that might come up again.

If I were personally designing this feature from scratch, I would reach for either entity partitioning/multi-world OR some system to disable or mark as invalid an entity without despawning it. That would keep entity allocation fast and simple and may cut down on archetype changes. Just a thought.

But like y'all said, we should cross that bridge when/if we come to it.

[alice-i-cecile]

As a note, we have entity disabling coming in Bevy 0.16, and live on main :)