Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

implement FromEntitySetIterator #17513

Merged
merged 5 commits into from
Jan 24, 2025
Merged

implement FromEntitySetIterator #17513

merged 5 commits into from
Jan 24, 2025

Conversation

Victoronz
Copy link
Contributor

@Victoronz Victoronz commented Jan 23, 2025 •
edited
Loading

Objective

Some collections are more efficient to construct when we know that every element is unique in advance.
We have EntitySetIterators from #16547, but currently no API to safely make use of them this way.

Solution

Add FromEntitySetIterator as a subtrait to FromIterator, and implement it for the EntityHashSet/hashbrown::HashSet types.
To match the normal FromIterator, we also add a EntitySetIterator::collect_set method.
It'd be better if these methods could shadow from_iter and collect completely, but rust-lang/rust#89151 is needed for that.

While currently only HashSets implement this trait, future UniqueEntityVec/UniqueEntitySlice functionality comes with more implementors.

Because HashMaps are collected from tuples instead of singular types, implementing this same optimization for them is more complex, and has to be done separately.

Showcase

This is basically a free speedup for collecting EntityHashSets!

pub fn collect_milk_dippers(dippers: Query<Entity, (With<Milk>, With<Cookies>)>) {
    dippers.iter().collect_set::<EntityHashSet>();
    // or
    EntityHashSet::from_entity_set_iter(dippers);
}

@Victoronz Victoronz added C-Feature A new feature, making something new possible A-ECS Entities, components, systems, and events C-Performance A change motivated by improving speed, memory usage or compile times D-Straightforward Simple bug fixes and API improvements, docs, test and examples S-Needs-Review Needs reviewer attention (from anyone!) to move forward labels Jan 23, 2025
@BenjaminBrienen BenjaminBrienen added S-Ready-For-Final-Review This PR has been approved by the community. It's ready for a maintainer to consider merging it D-Unsafe Touches with unsafe code in some way and removed S-Needs-Review Needs reviewer attention (from anyone!) to move forward labels Jan 23, 2025
SpecificProtagonist
SpecificProtagonist suggested changes Jan 23, 2025
View reviewed changes
Copy link
Contributor

@SpecificProtagonist SpecificProtagonist left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hmm… this is slower for me:

let mut world = World::new();
for _ in 0..1_000_000 {
    world.spawn_empty();
}
let mut query = world.query::<Entity>();
for _ in 0..10 {
    query.iter(&world).collect::<EntityHashSet>();
}

gives me

  Time (mean ± σ):      81.1 ms ±   0.9 ms    [User: 56.1 ms, System: 24.5 ms]
  Range (min … max):    80.0 ms …  83.7 ms    36 runs

while doing the same with collect_set gives

  Time (mean ± σ):     221.8 ms ±   4.3 ms    [User: 108.1 ms, System: 112.2 ms]
  Range (min … max):   217.2 ms … 231.5 ms    13 runs

This seems to be because it doesn't use size_hint. With that fixed it improves to

  Time (mean ± σ):      79.1 ms ±   2.3 ms    [User: 54.8 ms, System: 23.9 ms]
  Range (min … max):    77.7 ms …  92.1 ms    37 runs

or slightly faster than the standard collect (the spawning part of this benchmark takes about 26ms, with this PR improving the iter/collect part from ~49ms to ~47ms). Not a huge difference :/

crates/bevy_ecs/src/entity/entity_set.rs Outdated Show resolved Hide resolved
crates/bevy_ecs/src/entity/hash_set.rs Outdated Show resolved Hide resolved
Victoronz and others added 2 commits January 23, 2025 23:01
@Victoronz @SpecificProtagonist
Apply suggestions from code review
35cc4ba 
Use size hint in the HashSet FromEntitySetIterator impls

Co-authored-by: SpecificProtagonist <vincentjunge@posteo.net>
@Victoronz
use bevy_platform_support
939140f
@Victoronz
Copy link
Contributor Author

good catch!
I was going to perf test it after to check, but it does seem to be a rather small gain :P
Judging from indexmap-rs/indexmap#200, it seems the return type in the implementation does make this somewhat slower than it could be, but it is still an improvement nonetheless.

@Victoronz
Copy link
Contributor Author

slightly faster than the standard collect (the spawning part of this benchmark takes about 26ms, with this PR improving the iter/collect part from ~49ms to ~47ms). Not a huge difference :/

What system/compilation settings did you use to bench this?

@Victoronz
Copy link
Contributor Author

I've also changed the for loop into a fold, since internal iteration is known to generate bit better code.
Might not/probably does not have an impact for simple/common iterators though.

@alice-i-cecile alice-i-cecile added this pull request to the merge queue Jan 24, 2025
Merged via the queue into bevyengine:main with commit 94a238b Jan 24, 2025
28 checks passed
@Victoronz Victoronz mentioned this pull request Jan 26, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@SpecificProtagonist SpecificProtagonist SpecificProtagonist requested changes

@Bleachfuel Bleachfuel Bleachfuel approved these changes

@BenjaminBrienen BenjaminBrienen BenjaminBrienen approved these changes

Assignees
No one assigned
Labels
A-ECS Entities, components, systems, and events C-Feature A new feature, making something new possible C-Performance A change motivated by improving speed, memory usage or compile times D-Straightforward Simple bug fixes and API improvements, docs, test and examples D-Unsafe Touches with unsafe code in some way S-Ready-For-Final-Review This PR has been approved by the community. It's ready for a maintainer to consider merging it
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
5 participants
@Victoronz @SpecificProtagonist @BenjaminBrienen @Bleachfuel @alice-i-cecile