diff options
author | 2023-01-07 09:57:55 -0800 | |
---|---|---|
committer | 2023-01-07 09:58:34 -0800 | |
commit | 74eee2aff683cc7dcd2dbaa69b2c654596d8024e (patch) | |
tree | 5b03779c56b9dcf7358bd9cc85f428238032b36c /absl/hash | |
parent | e160c5f534fead21162c8951d4cfc975d0377896 (diff) |
Replace absl::Hash for inputs from 9 to 16 bytes according to AlphaZero findings
PiperOrigin-RevId: 500401844
Change-Id: I6d0909a8e395c914861dd034824a34737a52d71f
Diffstat (limited to 'absl/hash')
-rw-r--r-- | absl/hash/BUILD.bazel | 1 | ||||
-rw-r--r-- | absl/hash/CMakeLists.txt | 1 | ||||
-rw-r--r-- | absl/hash/internal/hash.h | 20 |
3 files changed, 19 insertions, 3 deletions
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index 4a95f054..a0db919b 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel @@ -43,6 +43,7 @@ cc_library( "//absl/container:fixed_array", "//absl/functional:function_ref", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", "//absl/strings", "//absl/types:optional", diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt index 0514c296..f99f35bc 100644 --- a/absl/hash/CMakeLists.txt +++ b/absl/hash/CMakeLists.txt @@ -25,6 +25,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::bits absl::city absl::config absl::core_headers diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index dbdc2050..ccf4cc1a 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -49,6 +49,7 @@ #include "absl/hash/internal/city.h" #include "absl/hash/internal/low_level_hash.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/string_view.h" #include "absl/types/optional.h" @@ -1052,7 +1053,7 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { uint64_t most_significant = low_mem; uint64_t least_significant = high_mem; #endif - return {least_significant, most_significant >> (128 - len * 8)}; + return {least_significant, most_significant}; } // Reads 4 to 8 bytes from p. Zero pads to fill uint64_t. @@ -1183,9 +1184,22 @@ inline uint64_t MixingHashState::CombineContiguousImpl( } v = Hash64(first, len); } else if (len > 8) { + // This hash function was constructed by the ML-driven algorithm discovery + // using reinforcement learning. We fed the agent lots of inputs from + // microbenchmarks, SMHasher, low hamming distance from generated inputs and + // picked up the one that was good on micro and macrobenchmarks. auto p = Read9To16(first, len); - state = Mix(state, p.first); - v = p.second; + uint64_t lo = p.first; + uint64_t hi = p.second; + // Rotation by 53 was found to be most often useful when discovering these + // hashing algorithms with ML techniques. + lo = absl::rotr(lo, 53); + state += kMul; + lo += state; + state ^= hi; + uint128 m = state; + m *= lo; + return static_cast<uint64_t>(m ^ (m >> 64)); } else if (len >= 4) { v = Read4To8(first, len); } else if (len > 0) { |