When comparing a Rust rewrite of a C++ codebase, I noticed that Rust's default HashMap and HashSet were noticably slower than unordered_map and unordered_set. The reason is that Rust uses a hash function that has better properties, but that is a bit slower. If the performance of a HashMap is a bottleneck, one can use a simpler hash function to get the same performance as in C++. With FnvHashMap, the performance was the same as unordered_map.
Does it still provide the DoS protection SipHash offered, or does that mean that Rust is moving from secure-by-default to fastest-by-default when it comes to HashMap ? If so it's kind of a big philosophical switch.
Note that the hashbrown crate uses FxHash by default, so the second table is the fair comparison. When ported to the stdlib it will likely be changed to have SipHash as the default.
For the standard hashmap, replacing SipHash with FxHash gets you a 4x perf boost. Replacing the standard hashmap with hashbrown gets you a 2x perf boost (when you're using FxHash, there are no numbers here for when you're using SipHash but I suspect it will still be significant, if smaller)
Thanks! I just replaced FnvHashMap with hashbrown::HashMap and get a 20% overall performance improvement in my workload (which is rather HashMap-heavy).
Slightly tangential but c++ hash tables aren't even the fastest. The requirements on iterator invalidation force the use of extra allocations and indirections for separate chaining.
I've hand-rolled and/or reused hash tables that use various probing methods (removing both allocations and extra indirections) and the performance improvement is non-trivial (for my workloads anyhow).
I've been surprised by how slow the C++ standard data structures are (likely due to the need to support a lot of functionality). I once wrote a basic heap in C and tried benchmarking its performance at -O3 relative to the C++ STL heap. Was expecting mine to be slower compared to the highly optimized STL heap, but was wondering how much slower. Instead, it turned out to be 1.5-2x as fast (and this was despite freeing up memory when the underlying vector shrunk - something which the C++ vector does not do).
Never went for performance, but at the most I use `std::map<int, pointer>` (which is a RB-tree).
You can implement RQ without a hashmap.
It is only used to track the symbol number (uint32), so introducing hashing sounds a bit wasteful. You could also do a normal vector actually, but since the symbol numbers are taken from the network, that might result in a lot of reordering or pointless allocation if you are not really careful
