Allow Option<Entity> to use memory layout optimization
#3022
Comments
notverymoe
added
C-Feature
|
I know that there's an open pull request for this, but GitHub's search is so terrible that I cannot find it |
|
The only semi-related one I was able to find was relations: https://github.com/BoxyUwU/rfcs/blob/min-relations/rfcs/min-relations.md But I'll keep looking! |
|
It's #2104 |
|
Seems like a different issue, I'm specifically dealing with the representation of Entity, which that PR doesn't appear to touch |
NiklasEi
added
A-ECS
|
#1395 contains some comments pertaining to this issue |
|
Currently working on this here: Current implementation:
Currently just looking for fires/potential issues with this solution. One potential issue is that incrementing generations is more costly, as we need to do it checked and manually wrap to 1 - haven't profiled that yet though. The Edit: One fire mentioned by |
…on (#9907) # Objective - Implements change described in #3022 - Goal is to allow Entity to benefit from niche optimization, especially in the case of Option<Entity> to reduce memory overhead with structures with empty slots ## Discussion - First PR attempt: #3029 - Discord: https://discord.com/channels/691052431525675048/1154573759752183808/1154573764240093224 ## Solution - Change `Entity::generation` from u32 to NonZeroU32 to allow for niche optimization. - The reason for changing generation rather than index is so that the costs are only encountered on Entity free, instead of on Entity alloc - There was some concern with generations being used, due to there being some desire to introduce flags. This was more to do with the original retirement approach, however, in reality even if generations were reduced to 24-bits, we would still have 16 million generations available before wrapping and current ideas indicate that we would be using closer to 4-bits for flags. - Additionally, another concern was the representation of relationships where NonZeroU32 prevents us using the full address space, talking with Joy it seems unlikely to be an issue. The majority of the time these entity references will be low-index entries (ie. `ChildOf`, `Owes`), these will be able to be fast lookups, and the remainder of the range can use slower lookups to map to the address space. - It has the additional benefit of being less visible to most users, since generation is only ever really set through `from_bits` type methods. - `EntityMeta` was changed to match - On free, generation now explicitly wraps: - Originally, generation would panic in debug mode and wrap in release mode due to using regular ops. - The first attempt at this PR changed the behavior to "retire" slots and remove them from use when generations overflowed. This change was controversial, and likely needs a proper RFC/discussion. - Wrapping matches current release behaviour, and should therefore be less controversial. - Wrapping also more easily migrates to the retirement approach, as users likely to exhaust the exorbitant supply of generations will code defensively against aliasing and that defensive code is less likely to break than code assuming that generations don't wrap. - We use some unsafe code here when wrapping generations, to avoid branch on NonZeroU32 construction. It's guaranteed safe due to how we perform wrapping and it results in significantly smaller ASM code. - https://godbolt.org/z/6b6hj8PrM ## Migration - Previous `bevy_scene` serializations have a high likelihood of being broken, as they contain 0th generation entities. ## Current Issues - `Entities::reserve_generations` and `EntityMapper` wrap now, even in debug - although they technically did in release mode already so this probably isn't a huge issue. It just depends if we need to change anything here? --------- Co-authored-by: Natalie Baker <[email protected]>
|
Fixed by #9907 |
What problem does this solve or what need does it fill?
Entity currently can't be default constructed or represent a "never valid" entity. Which is extremely useful for sparse relational data structures like grids and oct/quadtrees. This is easily sidestepped via
Option<Entity>, as rust does - so there's not a hard limit here or anything of course.The issue is that Option will introduce some memory overhead, which can become significant in flatter data structures like grids.
What solution would you like?
I'd like to be allow the compiler to leverage memory layout optimization, to remove the storage overhead of
Option<Entity>. This could be done by changing eitheridorgenerationto aNonZeroU32. I'd propose thatgenerationshould be the one considered for the change, as it has less public API surface.What alternative(s) have you considered?
OptionAdditional context
In my particular case, I have "TileCoord" component and a "MultiTileCoord" component that create a relation between entities and a particular grid square. On top of that, I maintain a fixed-size grid structure that is updated as TileCoords are altered to accelerate neighbourhood queries and generate certain events (ie. neighbour changed, tile moved ontop). As a result, some of the grid squares would be empty which can't be represented with
Entityalone, so I need to utilizeOption<Entity>and incur the storage overhead.On an example 1-layer grid of 256x256, this is an overhead of about ~256KiB. This isn't a pressing issue in my case, since I'm currently using the 2nd alternative I outlined. I just thought it might be a nice space optimization to put into core.
The text was updated successfully, but these errors were encountered: