Spawning child entities is extremely slow

[aevyrie]

Bevy version

0.15, has existed for as long as constructing Parent and Children has been locked down.

What you did

Attempt to optimize spawning large batches of children in a custom command for big_space.

What went wrong

Profiling shows that applying system commands dominates system time. Spawning 320k entities took 31s.

The problem appears to be that even when spawning a brand new entity, bevy is doing reparenting checks for every child when its Parent component is added, and again for every child when the children are added to the parent entity's Children component. These checks are completely unnecessary - the entities are new and cannot yet exist in the hierarchy.

By doing some transmute shenanigans, I was able to see what a niave solution would look like if I could simply construct the Parent and Children entities myself. The performance improvement was stark: what previously took 31s now took 83ms.

I was also able to work around this without unsafe by using reflection to construct a Parent and Children, bypassing the private constructors.

[aevyrie]

I had a lot of trouble replicating this performance issue on main, and it turned out to be that it only happens in a specific, non-obvious case. When an entity has no other children, and you spawn a bunch of children, this is fast. If that entity already had other children, you start to run into accidentally quadratic scaling.

The fix is to recognize that when the children we are adding to an entity have just been spawned, we can skip all of these checks. There is no way for the hierarchy to become malformed, because these entities are brand new. In the linked benchmark, the 1 million entity case was projected to take 7.5 hours, but completes in 111ms with fixes.

[aevyrie]

Another note: the linked PR doesn't fully fix this issue, it only resolves one set of cases that are easy to optimize for (and common). In the case where an entity is not new, adding this as a child still scales exponentially after the change. This is because to check if an entity already exists, bevy currently does a linear scan of a vector, which scales linearly with the length of the vector. Instead, we should probably be using a hashmap once the vector is large enough to spill onto the heap. This would make these checks constant time.

[cart]

As a heads up, if we land something in the "non-fragmenting relations" category (which I have an incoming PR for), that would fully resolve this. I'm not opposed to landing your optimizations first though, in the interest of ensuring some form of improvement lands in the next release.

[aevyrie]

"non-fragmenting relations"

What does this mean? The relations live in a central store or something? It's still possible for these optimizations to be missed, unless I'm missing something.

Edit: #16920

After skimming this, it still appears possible to hit the same performance issue, it completely depends on the implementation. I don't see how the design would prevent this from happening.

[cart]

After skimming this, it still appears possible to hit the same performance issue, it completely depends on the implementation. I don't see how the design would prevent this from happening.

You're right it isn't inherent to the space. My particular implementation does not suffer from the problem. The Parent(Entity) component is the "single source of truth" and the Children component is just a reflection of the children's Parent state. Component lifecycle hooks on Parent are used to update the Children component. Because the only way to update children is through the Parent component lifecycle, there is no way to introduce duplicates, so we don't need to check for dupes on spawn. Children just blissfully insert into their parent's Children collection.

Normal per-child removal does still require a scan to find the entity. But with the new on_despawn hook I've added we can skip the scan per-entity on despawn by clearing the children list early.

[aevyrie]

Thanks for the details, that all makes sense.