Use HashTable in DynamicMap and fix bug in remove#15158
Merged
alice-i-cecile merged 6 commits intobevyengine:mainfrom Sep 30, 2024
Merged
Use HashTable in DynamicMap and fix bug in remove#15158alice-i-cecile merged 6 commits intobevyengine:mainfrom
HashTable in DynamicMap and fix bug in remove#15158alice-i-cecile merged 6 commits intobevyengine:mainfrom
Conversation
MrGVSV
approved these changes
Sep 11, 2024
Member
MrGVSV
left a comment
There was a problem hiding this comment.
Looks good to me! This is certainly better than just hoping there's no hash collision haha.
And like we talked about on Discord, I think that get_at should be removed (not necessarily in this PR), so I'm not too concerned about that.
pablo-lua
approved these changes
Sep 24, 2024
Contributor
pablo-lua
left a comment
There was a problem hiding this comment.
Thumbs up, no collisions
fb632a9 to
e784a46
Compare
robtfm
pushed a commit
to robtfm/bevy
that referenced
this pull request
Oct 4, 2024
…5158) # Objective - `DynamicMap` currently uses an `HashMap` from a `u64` hash to the entry index in a `Vec`. This is incorrect in the presence of hash collisions, so let's fix it; - `DynamicMap::remove` was also buggy, as it didn't fix up the indexes of the other elements after removal. Fix that up as well and add a regression test. ## Solution - Use `HashTable` in `DynamicMap` to distinguish entries that have the same hash by using `reflect_partial_eq`, bringing it more in line with what `DynamicSet` does; - Reimplement `DynamicMap::remove` to properly fix up the index of moved elements after the removal. ## Testing - A regression test was added for the `DynamicMap::remove` issue. --- Some kinda related considerations: the use of a separate `Vec` for storing the entries adds some complications that I'm not sure are worth. This is mainly used to implement an efficient `get_at`, which is relied upon by `MapIter`. However both `HashMap` and `BTreeMap` implement `get_at` inefficiently (and cannot do so efficiently), leading to a `O(N^2)` complexity for iterating them. This could be removed in favor of a `Box<dyn Iterator>` like it's done in `DynamicSet`.
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
5 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
DynamicMapcurrently uses anHashMapfrom au64hash to the entry index in aVec. This is incorrect in the presence of hash collisions, so let's fix it;DynamicMap::removewas also buggy, as it didn't fix up the indexes of the other elements after removal. Fix that up as well and add a regression test.Solution
HashTableinDynamicMapto distinguish entries that have the same hash by usingreflect_partial_eq, bringing it more in line with whatDynamicSetdoes;DynamicMap::removeto properly fix up the index of moved elements after the removal.Testing
DynamicMap::removeissue.Some kinda related considerations: the use of a separate
Vecfor storing the entries adds some complications that I'm not sure are worth. This is mainly used to implement an efficientget_at, which is relied upon byMapIter. However bothHashMapandBTreeMapimplementget_atinefficiently (and cannot do so efficiently), leading to aO(N^2)complexity for iterating them. This could be removed in favor of aBox<dyn Iterator>like it's done inDynamicSet.