implement EntityIndexMap/Set#17449
Merged
alice-i-cecile merged 2 commits intobevyengine:mainfrom Jan 24, 2025
Merged
Conversation
alice-i-cecile
approved these changes
Jan 20, 2025
alice-i-cecile
added
A-ECS
Member
|
As discussed on Discord, we should adopt #17447 to apply to the |
Contributor
Author
|
Note: this currently only includes slicing via deref. It'd put this PR well over a thousand lines to add the wrappers for those as well, so I'll do that as a follow-up. |
BenjaminBrienen
approved these changes
Jan 20, 2025
BenjaminBrienen
added
S-Ready-For-Final-Review
Member
|
Actually, before I merge this, can you say a bit more on the motivation here? Adding code like this isn't free, and we don't have any internal users currently. |
alice-i-cecile
added
S-Waiting-on-Author
Contributor
Author
Fair, I've added some more extensive motivation. |
alice-i-cecile
added
S-Ready-For-Final-Review
mrchantey
pushed a commit
to mrchantey/bevy
that referenced
this pull request
Feb 4, 2025
…evyengine#17450) # Objective Noticed while doing bevyengine#17449, I had left these `DerefMut` impls in. Obtaining mutable references to those inner iterator types allows for `mem::swap`, which can be used to swap an incorrectly behaving instance into the wrappers. ## Solution Remove them!
mrchantey
pushed a commit
to mrchantey/bevy
that referenced
this pull request
Feb 4, 2025
# Objective We do not have `EntityIndexMap`/`EntityIndexSet`. Usual `HashMap`s/`HashSet`s do not guarantee any order, which can be awkward for some use cases. The `indexmap` versions remember insertion order, which then also becomes their iteration order. They can be thought of as a `HashTable` + `Vec`, which means fast iteration and removal, indexing by index (not just key), and slicing! Performance should otherwise be comparable. ## Solution Because `indexmap` is structured to mirror `hashbrown`, it suffers the same issue of not having the `Hasher` generic on their iterators. bevyengine#16912 solved this issue for `EntityHashMap`/`EntityHashSet` with a wrapper around the hashbrown version, so this PR does the same. Hopefully these wrappers can be removed again in the future by having `hashbrown`/`indexmap` adopt that generic in their iterators themselves!
github-merge-queue bot
pushed a commit
that referenced
this pull request
Mar 17, 2025
# Objective Continuation of #17449. #17449 implemented the wrapper types around `IndexMap`/`Set` and co., however punted on the slice types. They are needed to support creating `EntitySetIterator`s from their slices, not just the base maps and sets. ## Solution Add the wrappers, in the same vein as #17449 and #17589 before. The `Index`/`IndexMut` implementations take up a lot of space, however they cannot be merged because we'd then get overlaps. They are simply named `Slice` to match the `indexmap` naming scheme, but this means they cannot be differentiated properly until their modules are made public, which is already a follow-up mentioned in #17954.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Objective
We do not have
EntityIndexMap/EntityIndexSet.Usual
HashMaps/HashSets do not guarantee any order, which can be awkward for some use cases.The
indexmapversions remember insertion order, which then also becomes their iteration order.They can be thought of as a
HashTable+Vec, which means fast iteration and removal, indexing by index (not just key), and slicing!Performance should otherwise be comparable.
Solution
Because
indexmapis structured to mirrorhashbrown, it suffers the same issue of not having theHashergeneric on their iterators. #16912 solved this issue forEntityHashMap/EntityHashSetwith a wrapper around the hashbrown version, so this PR does the same.Hopefully these wrappers can be removed again in the future by having
hashbrown/indexmapadopt that generic in their iterators themselves!