Excessive CPU cycles in bevy_ecs::entity::Entities::alloc_at_without_replacement

[fickle scroll]

Hello Bevy community. This is my first time using bevy for a serious project so I apologize if I'm lacking some basic knowledge to a potentially simple question.

I've been stress testing my game and found some reproducible strange behavior. I start the game and spawn about 80,000 entities linearly over 4 seconds. I don't see any frame rate drops until I have around 70,000 entities. Those all despawn over the next 4 seconds and I know have less than 10 entities alive. I immediatly start spawning entities via the same process again but now my frames drop aggressively when there are only 10,000-20,000 entities in the game. There are zero changes and new systems running between the trials. One simply happens after the other. This is reproducible 100% of the time.

I have attached a flamegraph. The weapons::update::update_projectile time taken is expected, but the majority of time is spent in bevy_ecs::entity::Entities::alloc_at_without_replacement. I'm not sure if this is expected or what is going on? I did some googling and was unable to find anything and I lack the knowledge on the internals of Bevy to understand when this method should be running.

I'm happy to provide any more information that may be useful! Thank you for taking the time to read this!

[rich yarrow]

At a glance, I'm not entirely sure myself. Can you share a code snippet of how you are spawning and despawning? If you are using insert_or_spawn_batch, try it with spawn_batch instead. See if that helps?

[fickle scroll]

Thanks for checking it out! I updated to spawn_batch but that did not cause any changes to the perfomance issue.

I spawn projectiles in one system:

fn handle_commands(
    mut event_reader: EventReader<Command>,
    mut weapons: ResMut<Weapons>,
    mut commands: Commands,
) {
    let mut projectiles_to_spawn = Vec::with_capacity(500);
    for command in event_reader.read() {
        match command {
            Command::RegisterProjectile((weapon_id, projectile_ptr, projectile_id)) => {
                if projectiles_to_spawn.len() < 500 {
                    if let Some(bundle) =
                        weapons.register_projectile(*weapon_id, *projectile_ptr, *projectile_id)
                    {
                        projectiles_to_spawn.push(bundle);
                    }
                }
            }
            // Three other cases that don't spawn projectiles
        }
    }

    if !projectiles_to_spawn.is_empty() {
        commands.spawn_batch(projectiles_to_spawn);
    }
}

I despawn projectiles in one system:

fn update_projectiles(
    mut projectiles_query: Query<(Entity, &mut Projectile, &mut Transform, &HitBox)>,
    player_transform_query: Query<&Transform, (With<Player>, Without<Projectile>)>,
    enemy_query: EnemyQuery,
    mut weapons: ResMut<Weapons>,
    mut event_writer: EventWriter<Command>,
    frame_id: Res<FrameCount>,
    time: Res<Time<Virtual>>,
    mut commands: Commands,
    world: Res<World>,
) {
    if let Ok(player_transform) = player_transform_query.get_single() {
        let delta_seconds = time.delta_secs();
        let mut event_writer_vec = vec![];
        for (entity, mut projectile, mut transform, hitbox) in projectiles_query.iter_mut() {
            projectile.alive_for += Duration::from_secs_f32(time.delta_secs());
            if projectile.alive_for > Duration::from_secs(5) {
                commands.entity(entity).despawn();
            } else if transform.translation.x < 0.
                || transform.translation.x > world.width as f32
                || transform.translation.y < 0.
                || transform.translation.y > world.height as f32
            {
                commands.entity(entity).despawn();
            } else {
                if weapons.update_projectile(
                    &*projectile,
                    &mut transform,
                    &mut event_writer_vec,
                    &player_transform,
                    &enemy_query,
                    frame_id.0,
                    delta_seconds,
                ) {
                    commands.entity(entity).despawn();
                }
            }
        }
        event_writer.send_batch(event_writer_vec);
    }
}

[rich yarrow]

Sorry I stepped away for a bit. An updated flame graph with spawn_batch would be helpful. insert_or_spawn_batch has a linear search in it to try to re-use the same endity id. I think this can be faster if it keeps storage from being fragmented, but since you're more impacted by spawn speed spawn_batch is the better choice. I'm no expert, but looking at the source, I think I have some idea of what's happening to make even spawn_batch too slow.

When you spawn the first 80,000 entities, all it has to do is create a new entity id. Then you despawn them, putting each entity id into a vec to reuse. But the order of the vector is not necessarily the order of the entity ids, I don't think, especially if they are spread over different archetypes (maybe by having different bundles per projectile in your case). Anyway, when you go to respawn them, it starts popping ids off the re-use queue, but it has to update some metadata information too, which lives in a separate vec in order of entity id. So now, you're ping-ponging between different regions of memory, which the cache is not happy about. Those cache misses cause the performance drag. I think.

I could always be wrong. This is just a guess on my part. You could test it by calculating all the entities you want to despawn earlier and sorting them by their index. I don't think it would be enough to just sort the one's you despawn each frame probably, but you could try that as a start. Hopefully, that all makes sense. If this fixes your issue or improves it, let me know, and I might find time to make a PR to prevent those cache misses.

[rich yarrow]

Looking at this again (cuz now you have me curious), I'm not so sure the cache misses are the only thing harming performance here. Could you provide another flame graph with spawn_batch? Just to make sure there isn't anything weird in the render world too, could you try without putting meshes or anything on the projectile bundles?

[fickle scroll]

Thanks for looking into it and sorry for the delay. Will have this to you today!

[fickle scroll]

Here is a flamegraph where I removed the Sprite component from my projectiles. This completely fixed the frame drops.

I was able to spawn 90,000 projectiles with no frame drops, let them despawn, and then spawn another 90,000 projectiles without any drops in frames. For reference here is the component I removed from my projectile entity:

            Sprite {
                image: atlas_info.image.clone_weak(),
                custom_size: Some(Vec2::new(
                    atlas_info.sprite_dimensions.0 as f32,
                    atlas_info.sprite_dimensions.1 as f32,
                )),
                texture_atlas: Some(TextureAtlas {
                    layout: atlas_info.layout.clone_weak(),
                    index: 0,
                }),
                ..default()
            },

atlas_info holds both the image Handle and TextureAtlas layout and I clone weak references to it every time I spawn a projectile. I am happy to provide more code or anything you might find useful.

Thanks for looking into this!

[rich yarrow]

Beautiful. It looks like something in the render world uses insert_or_spawn_batch then, which has that pesky linear search I mentioned. That would be the problem. As long as you don't go from a huge amount of entities to very little and back again quite so rapidly in practice, you should be good. Still, I'll reach out to some ECS guys and see if we can get rid of the linear search altogether.

[orchid adder]

@fickle scroll tracked in https://github.com/bevyengine/bevy/issues/18054, and we've identified a root cause and a fix 🙂

[fickle scroll]

Wow absolutely incredible thank you so much team!

I'm going to mark this as resolved! Genuinely incredible work thank you for your time and glad my issue was able to help improve Bevy!