Yoshua Wuyts
In our last post we took a look at possible ways we could improve the ergonomics of Rust's refcounting APIs. In this post we'll be looking at Hashmap: how it's currently implemented, how we could optimize it further, and finally directions we could explore to enable the compiler to automatically apply these optimizations.
Disclaimer: I'm not an expert. I'm not on any team involved with const execution, nor do I hold any decision making power. This exists to share ideas and curiosities of what might be possible in Rust in the spirit of sharing posts with pals.
In 2017 Google introduced a new kind of hashmap for C++: the Swisstable hashmap. This structure uses SIMD instructions to compute hashes, which is a great match for modern computer hardware. So any improvements to the hashing algorithm would have an outsize impact on performance, and in turn resource efficiency.
In the cppcon 2017 talk on Swisstable, the authors mention that across all of Google's code, they found a non-trivial amount of time was spent computing hashes 1. Amanieu from the libs team created a Rust variant of the same algorithm for the Hashbrown crate, which has since become the default Hashmap implemention for Rust.
