Replace or supplement bevy_ecs's `HashMap<TypeId, T>`s with perfect hash functions
- Dominant language
- Rust
- Stars
- 48.2k
- Forks
- 4.8k
- Avg merge
- 3d 16h
- Merged PRs (30d)
- 171
Description
## What problem does this solve or what need does it fill?
In `Components` and `Bundles`, bevy_ecs maintains TypeId keyed HashMaps to more easily map from Rust types to the target bundle component. Unfortunately this also means that these hashmaps are on the hot path for APIs like `EntityRef::get` and structural alterations like adding/removing components. We also need to do presence checks and construction on every operation as a result. This can potentially have a heavy impact on tight loops that use these operations. In particular, command application is particularly heavy with it.
## What solution would you like?
Register all Rust type-based components ahead of time, during app initialization. Use a crate like [`phf`](https://crates.io/crates/phf) to generate a perfect hash function and use it instead of a HashMap. This is a guaranteed `O(1)` lookup compared to the `O(k * alpha)` of hashbrown's implementation, and can potentially be branchless as well. This is potentially a serious usabilty regression, so more thought on how to maintain our current UX is crucial here.
Component registration is already done ahead of time during system initialization during app construction due to `Query` and `Res` system params eagerly registering their used components. However, this does not hold true for dynamic fetches like `EntityRef::get`, `EntityMut::insert`, etc. so manual calls to `App/World::init_component` might be required.
Ideally this would be done at compile time and not at runtime, but this is currently not possible without const TypeId and a way to aggregate all component types during compilation. phf claims it's capable of generating a perfect hash function for 100k elements in 0.4 seconds, so it's impact on compile times for the much smaller universe of component types should be negligible.
## What alternative(s) have you considered?
Extending the `Component` macro to generate unique `ComponentId`s at compile time instead. This is hard, if not impossible, to coordinate without IPC of some kind.
Another alternative is to use the perfect hash function and HashMap together. Building the PHF on demand, and deferring back to the HashMap when the element isn't in the PHF. This would likely result in more codgen but the happy path through the PHF should still result in the same performance gains.
Contributor guide
Research direction
Start by tracing the Components and Bundles TypeId maps through EntityRef::get, EntityMut::insert, and command application. Read the existing registration paths for Query and Res system parameters and the App/World::init_component entry points. Done means evaluating whether a phf-based lookup can preserve dynamic-fetch usability while improving the hot path, with the remaining API changes and tradeoffs documented.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- game-dev, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100