diff options
author | Fangrui Song <i@maskray.me> | 2024-06-19 10:30:13 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-06-19 10:30:13 -0700 |
commit | fb17bbce80cf76ce1a31eff463f451f626bc36b5 (patch) | |
tree | ddcc0415c422b0ed2b56670526f5514f8459c938 | |
parent | 58d7a6e0e6361871442df956bb88798ce602b09d (diff) | |
download | llvm-fb17bbce80cf76ce1a31eff463f451f626bc36b5.zip llvm-fb17bbce80cf76ce1a31eff463f451f626bc36b5.tar.gz llvm-fb17bbce80cf76ce1a31eff463f451f626bc36b5.tar.bz2 |
[DenseMap] Update combineHashValue
`combineHashValue` is a custom bit mixer from 2008
(5fc8ab6d187aefbf1d2cbd36e191e675b14db8f6) used for std::pair and
std::tuple. It has a long dependency chain and slow. Replace it with
a simply multiply-xorshift style hash using a constant from
splitmix64[1]. abseil-cpp and carbon also use this style, but with
uint128 to probably get a lower avalanche bias. We don't use uint128 for
MSVC portability.
Measured time to compute [0,1000000000) values on an i7-11850H:
* old: 1.163s
* new: 0.427s
[1]: https://jonkagstrom.com/tuning-bit-mixers/index.html
Pull Request: https://github.com/llvm/llvm-project/pull/95970
-rw-r--r-- | llvm/include/llvm/ADT/DenseMapInfo.h | 24 |
1 files changed, 13 insertions, 11 deletions
diff --git a/llvm/include/llvm/ADT/DenseMapInfo.h b/llvm/include/llvm/ADT/DenseMapInfo.h index c405f74..7e1525a 100644 --- a/llvm/include/llvm/ADT/DenseMapInfo.h +++ b/llvm/include/llvm/ADT/DenseMapInfo.h @@ -23,20 +23,22 @@ namespace llvm { +namespace densemap::detail { +// A bit mixer with very low latency using one multiplications and one +// xor-shift. The constant is from splitmix64. +inline uint64_t mix(uint64_t x) { + x *= 0xbf58476d1ce4e5b9u; + x ^= x >> 31; + return x; +} +} // namespace densemap::detail + namespace detail { /// Simplistic combination of 32-bit hash values into 32-bit hash values. -static inline unsigned combineHashValue(unsigned a, unsigned b) { - uint64_t key = (uint64_t)a << 32 | (uint64_t)b; - key += ~(key << 32); - key ^= (key >> 22); - key += ~(key << 13); - key ^= (key >> 8); - key += (key << 3); - key ^= (key >> 15); - key += ~(key << 27); - key ^= (key >> 31); - return (unsigned)key; +inline unsigned combineHashValue(unsigned a, unsigned b) { + uint64_t x = (uint64_t)a << 32 | (uint64_t)b; + return (unsigned)densemap::detail::mix(x); } } // end namespace detail |