New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
std: hash_map: optimize isFree/isTombstone #10562
std: hash_map: optimize isFree/isTombstone #10562
Conversation
- Add an `Metadata.isFree` helper method. - Implement `Metadata.isTombstone` and `Metadata.isFree` with `@bitCast` then comparing to a constant. I assume `@bitCast`-then-compare is faster than the old method because it only involves one comparison, and doesn't require bitmasking. - Summary of benchmarked changes (`gotta-go-fast`, run locally, compared to master): - 3/4 of the hash map benchmarks used ~10% fewer cycles - The last one (project Euler) shows 4% fewer cycles.
I would have expected the optimizer to catch this simplification! |
It's not quite equivalent, the old check of |
Restructuring I too was surprised that the compiler didn't handle that optimization (i.e. combining comparisons of a packed struct's fields) automatically. |
- Add an `Metadata.isFree` helper method. - Implement `Metadata.isTombstone` and `Metadata.isFree` with `@bitCast` then comparing to a constant. I assume `@bitCast`-then-compare is faster than the old method because it only involves one comparison, and doesn't require bitmasking. - Summary of benchmarked changes (`gotta-go-fast`, run locally, compared to master): - 3/4 of the hash map benchmarks used ~10% fewer cycles - The last one (project Euler) shows 4% fewer cycles.
- Add an `Metadata.isFree` helper method. - Implement `Metadata.isTombstone` and `Metadata.isFree` with `@bitCast` then comparing to a constant. I assume `@bitCast`-then-compare is faster than the old method because it only involves one comparison, and doesn't require bitmasking. - Summary of benchmarked changes (`gotta-go-fast`, run locally, compared to master): - 3/4 of the hash map benchmarks used ~10% fewer cycles - The last one (project Euler) shows 4% fewer cycles.
Optimize
HashMap
.Metadata.isFree
helper method (not an optimization, just for clarity).Metadata.isTombstone
andMetadata.isFree
with@bitCast
then comparing to a constant. I assume@bitCast
-then-compare is faster than the old method because it only involves one comparison, and doesn't require bitmasking.gotta-go-fast
, run locally, compared to master):Benchmarks- Measurements are from running the
gotta-go-fast
benchmarks locally on my laptop.available
: Measures current master (a couple weeks out of date, but there haven't been any changes to hash_map in that time).pre-available-fix
: Prior to the std: count hash_map tombstones as available #10337 fix.available-faster
: Not actually faster. Measures the (now reverted) std: optimize hash_map probe loop condition #10350.is-free-tomb-bitcasts
: This PR.And I experimented a few other optimizations that didn't pan out -- see here for all the data.
cc: @jorangreef @Sahnvour