fix: Only instantiate RawTable's reserve functions once #204
Conversation
This file contains 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
added 2 commits
September 29, 2020 13:44
...per key-value. Each of the previous closures would cause an entirely new reserve/resize function to be instantiated. By using this trick (which std uses for iterator adaptors), we always get a single instantiatiation per key (modulo the insert_with_hasher method).
Amanieu
reviewed
Sep 30, 2020
src/map.rs
Outdated
| @@ -664,8 +687,7 @@ where | |||
| #[cfg_attr(feature = "inline-more", inline)] | |||
| pub fn reserve(&mut self, additional: usize) { | |||
| let hash_builder = &self.hash_builder; | |||
| self.table | |||
| .reserve(additional, |x| make_hash(hash_builder, &x.0)); | |||
| self.table.reserve(additional, make_hasher(hash_builder)); | |||
There was a problem hiding this comment.
Suggested change
| self.table.reserve(additional, make_hasher(hash_builder)); | |
| self.table.reserve(additional, make_hasher(&self.hash_builder)); |
The let above was only needed because the closure would otherwise capture all of self instead of just the hash_builder field.
Amanieu
reviewed
Sep 30, 2020
src/map.rs
Outdated
| @@ -1974,16 +2002,16 @@ impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> { | |||
| S: BuildHasher, | |||
| { | |||
| let hash_builder = self.hash_builder; | |||
src/map.rs
Outdated
| /// Ensures that a single closure type across uses of this which, in turn prevents multiple | ||
| /// instances of any functions like RawTable::reserve from being generated | ||
| #[cfg_attr(feature = "inline-more", inline)] | ||
| fn equivalent_single<Q, K>(k: &Q) -> impl Fn(&K) -> bool + '_ |
There was a problem hiding this comment.
This should probably be called equivalent and the other one should be renamed to equivalent_key.
|
Thanks! @bors r+ |
|
📌 Commit 5e11d32 has been approved by |
|
☀️ Test successful - checks-travis |
bors
added a commit
that referenced
this pull request
Jan 26, 2021
Reduce the amount of llvm IR instantiated This works to improve the generated code in a similar way to #204 , however it is entirely orthogonal to it but also far more invasive. The main change here is the introduction of `RawTableInner` which is contains all the fields that `RawTable` has but without being parameterized by `T`. Methods have been moved to this new type in parts or their entirety and `RawTable` forwards to these methods. For this small test case with 4 different maps there is a reduction of the number of llvm lines generated by -17% (18088 / 21873 =0.82695560737) . ```rust fn main() { let mut map1 = hashbrown::HashMap::new(); map1.insert(1u8, ""); map1.reserve(1000); let mut map2 = hashbrown::HashMap::new(); map2.insert(1i16, ""); map2.reserve(1000); let mut map3 = hashbrown::HashMap::new(); map3.insert(3u16, ""); map3.reserve(1000); let mut map4 = hashbrown::HashMap::new(); map4.insert(3u64, ""); map4.reserve(1000); dbg!(( map1.iter().next(), map2.iter().next(), map3.iter().next(), map4.iter().next() )); } ``` The commits are almost entirely orthogonal (except the first which does the main refactoring to support the rest) and if some are not desired they can be removed. If it helps, this PR could also be split up into multiple. For most commitst I don't expect any performance degradation (unless LLVM stops inlining some function as it is now called more), but there are a couple of commits that does slow parts down however these should only be in the cold parts of the code (for instance, panic handling).
This was referenced Mar 15, 2021
bors
pushed a commit
to rust-lang-ci/rust
that referenced
this pull request
Mar 16, 2021
Includes rust-lang/hashbrown#204 and rust-lang/hashbrown#205 (not yet merged) which both server to reduce the amount of IR generated for hashmaps. Inspired by the llvm-lines data gathered in rust-lang#76680
bors
added a commit
to rust-lang-ci/rust
that referenced
this pull request
Mar 18, 2021
feat: Update hashbrown to instantiate less llvm IR Includes rust-lang/hashbrown#204 and rust-lang/hashbrown#205 (not yet merged) which both serve to reduce the amount of IR generated for hashmaps. Inspired by the llvm-lines data gathered in rust-lang#76680 (cc `@Julian-Wollersberger)`
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
...per key-value.
Each of the previous closures would cause an entirely new reserve/resize
function to be instantiated. By using this trick (which std uses for
iterator adaptors), we always get a single instantiatiation per key
(modulo the insert_with_hasher method).