Context: FxHash is a non-cryptographic hash used in the Rust compiler. It affects performance a lot. Different people were looking for a faster(*) hash for years(https://nnethercote.github.io/2021/12/08/a-brutally-effective-hash-function-in-rust.html), without success, and it looks like this recently changed!
(*): faster in this contex is a balance between “hash is fast to compute” and “the result is random enough such that there are few collisions in hash tables”.
Do I read it correctly that compile-times improved by avg +0.28%?
You do, except that it is instruction count. If you feel that 0.28% is not much, it helps to keep in mind that twenty successive improvements of 0.28% make for more than a 5% total reduction of instruction count.
You are reading it correctly, with the caveats that it’s the average across the benchmark crates used by the rustc-perf project and the measure is the number of instructions run.
The low hanging fruit in rustc performance improvements have mostly been picked (nnethercote and the rest of the perf team are doing great work) and finding new ones is getting very hard, but even “small” ones like these compound over time! I had a lot of fun looking for and contributing a few micro-optimizations in rustc myself, but it’s been ages since I’ve found anything worth doing.
I see, thanks for the explanation and the context. There’s definitely a limit of things that can be optimized without deep refactors (hash function is nice because it can be swapped out easily, it has a simple interface, etc. ).
The thing I’m wondering about is: is this improvement within expectation of the devs? I couldn’t find a breakdown of how much time/instructions are spent hashing things. Especially since we’re counting instructions, it should be possible to instrument all the basic blocks belonging to the hash function. This should give you an improvement ceiling.
Good question, I don’t know! If I recall correctly the move to FxHash made a sizeable difference in its time though.
I’m not sure how to read this, either. But I think that’s the default instructions:u (instructions executed) metric, while cycles:u (CPU cycles spent) is down ~3%. Some descriptions of the metrics here https://internals.rust-lang.org/t/what-is-perf-rust-lang-org-measuring-and-why-is-instructions-u-the-default/9815
Edit: Yeah I don’t know what I’m looking at, there’s a totally different set of tests for cycles:u and that 3% might reflect a different change.
This looks a lot like Knuth’s multiplicative hashing (TAOCP section 6.4).
This is mostly a polynomial hash and a multiplicative hash is a polynomial hash, so that’s not too surprising :)
A multiplicative hash is one where you multiply the input by some value (often something that approximates 2^64 divided by some irrational number). A polynomial hash is one where you multiply powers of the input by various coefficients and sum the result.
Knuth’s version has a shift at the end, but that’s for range reduction, not for the hash itself.
See this (slightly wrong/misleading, but still useful) article for more info: https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ (For details on why it’s a bit wrong, check out the hacker news thread about it).