Re-implement AbslHashValue for std::vector<bool> and std::bitset to
not simply defer to std::hash.

This enables hash seed randomization (a better default behavior) at
the cost of a modest slowdown for the rare case of hashing these
types. One real world benchmark had a 17% slowdown. Users that need
better performance can use std::hash or a custom data structure as the
key which would likely be faster anyway.

PiperOrigin-RevId: 949636074
Change-Id: I19b6dde7bb33427216157b5d61a0fa92da05a1a4

absl/hash/hash_benchmark.cc

diff --git a/absl/hash/hash_benchmark.cc b/absl/hash/hash_benchmark.cc
index d0ebdbc..86650b3 100644
--- a/absl/hash/hash_benchmark.cc
+++ b/absl/hash/hash_benchmark.cc
@@ -13,6 +13,7 @@
 // limitations under the License.
 
 #include <algorithm>
+#include <bitset>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
@@ -247,6 +248,12 @@
 MAKE_BENCHMARK(AbslHash, VectorDouble_10, Vector<double>(10));
 MAKE_BENCHMARK(AbslHash, VectorDouble_100, Vector<double>(100));
 MAKE_BENCHMARK(AbslHash, VectorDouble_1000, Vector<double>(1000));
+MAKE_BENCHMARK(AbslHash, VectorBool_10, Vector<bool>(10));
+MAKE_BENCHMARK(AbslHash, VectorBool_100, Vector<bool>(100));
+MAKE_BENCHMARK(AbslHash, VectorBool_1000, Vector<bool>(1000));
+MAKE_BENCHMARK(AbslHash, Bitset_10, std::bitset<10>());
+MAKE_BENCHMARK(AbslHash, Bitset_100, std::bitset<100>());
+MAKE_BENCHMARK(AbslHash, Bitset_1000, std::bitset<1000>());
 MAKE_BENCHMARK(AbslHash, FlatHashSetInt64_10, FlatHashSet<int64_t>(10));
 MAKE_BENCHMARK(AbslHash, FlatHashSetInt64_100, FlatHashSet<int64_t>(100));
 MAKE_BENCHMARK(AbslHash, FlatHashSetInt64_1000, FlatHashSet<int64_t>(1000));
@@ -294,6 +301,14 @@
                std::vector<double>(100, 1.1));
 MAKE_BENCHMARK(TypeErasedAbslHash, VectorDouble_1000,
                std::vector<double>(1000, 1.1));
+MAKE_BENCHMARK(TypeErasedAbslHash, VectorBool_10, std::vector<bool>(10, true));
+MAKE_BENCHMARK(TypeErasedAbslHash, VectorBool_100,
+               std::vector<bool>(100, true));
+MAKE_BENCHMARK(TypeErasedAbslHash, VectorBool_1000,
+               std::vector<bool>(1000, true));
+MAKE_BENCHMARK(TypeErasedAbslHash, Bitset_10, std::bitset<10>());
+MAKE_BENCHMARK(TypeErasedAbslHash, Bitset_100, std::bitset<100>());
+MAKE_BENCHMARK(TypeErasedAbslHash, Bitset_1000, std::bitset<1000>());
 MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetInt64_10,
                FlatHashSet<int64_t>(10));
 MAKE_BENCHMARK(TypeErasedAbslHash, FlatHashSetInt64_100,

absl/hash/internal/hash.h

diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index f4633ed..f68872f 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -787,41 +787,50 @@
 }
 
 // AbslHashValue special cases for hashing std::vector<bool>
-
-#if defined(ABSL_IS_BIG_ENDIAN) && \
-    (defined(__GLIBCXX__) || defined(__GLIBCPP__))
-
-// std::hash in libstdc++ does not work correctly with vector<bool> on Big
-// Endian platforms therefore we need to implement a custom AbslHashValue for
-// it. More details on the bug:
-// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531
+//
+// To achieve high performance without depending on private standard library
+// internals, we pack bits 64 at a time into uint64_t words using a fixed
+// 64-step inner loop that allows compilers to unroll bit shifts cleanly.
+//
+// This is slower than std::hash<std::vector<bool>> which can access private
+// storage directly, but more than fast enough for the very rare case of hashing
+// std::vector<bool>. In the event that higher performance is needed, a custom
+// key type is likely faster than building std::vector<bool> and hashing it,
+// otherwise users can just use std::hash as the hasher.
 template <typename H, typename T, typename Allocator>
 std::enable_if_t<is_hashable<T>::value && std::is_same_v<T, bool>, H>
 AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) {
   typename H::AbslInternalPiecewiseCombiner combiner;
-  for (const auto& i : vector) {
-    unsigned char c = static_cast<unsigned char>(i);
-    hash_state = combiner.add_buffer(std::move(hash_state), &c, sizeof(c));
+  const size_t size = vector.size();
+  size_t i = 0;
+  // Pack full 64-bit words. Fixed inner loop count enables compiler unrolling.
+  while (i + 64 <= size) {
+    uint64_t word = 0;
+    for (size_t j = 0; j < 64; ++j) {
+      word |= static_cast<uint64_t>(vector[i + j]) << j;
+    }
+    hash_state = combiner.add_buffer(
+        std::move(hash_state), reinterpret_cast<const unsigned char*>(&word),
+        sizeof(word));
+    i += 64;
   }
+  // Pack remaining bits (< 64) into the final word.
+  if (i < size) {
+    uint64_t word = 0;
+    const size_t rem = size - i;
+    for (size_t j = 0; j < rem; ++j) {
+      word |= static_cast<uint64_t>(vector[i + j]) << j;
+    }
+    hash_state = combiner.add_buffer(
+        std::move(hash_state), reinterpret_cast<const unsigned char*>(&word),
+        (rem + 7) / 8);
+  }
+  // Mix in vector.size() to distinguish vectors with trailing false/zero bits
+  // (e.g. {true} vs {true, false}) that would otherwise produce identical bit
+  // buffers.
   return H::combine(combiner.finalize(std::move(hash_state)),
-                    WeaklyMixedInteger{vector.size()});
+                    WeaklyMixedInteger{size});
 }
-#else
-// When not working around the libstdc++ bug above, we still have to contend
-// with the fact that std::hash<vector<bool>> is often poor quality, hashing
-// directly on the internal words and on no other state.  On these platforms,
-// vector<bool>{1, 1} and vector<bool>{1, 1, 0} hash to the same value.
-//
-// Mixing in the size (as we do in our other vector<> implementations) on top
-// of the library-provided hash implementation avoids this QOI issue.
-template <typename H, typename T, typename Allocator>
-std::enable_if_t<is_hashable<T>::value && std::is_same_v<T, bool>, H>
-AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) {
-  return H::combine(std::move(hash_state),
-                    std::hash<std::vector<T, Allocator>>{}(vector),
-                    WeaklyMixedInteger{vector.size()});
-}
-#endif
 
 // -----------------------------------------------------------------------------
 // AbslHashValue for Ordered Associative Containers
@@ -959,28 +968,44 @@
 // AbslHashValue for Other Types
 // -----------------------------------------------------------------------------
 
-// AbslHashValue for hashing std::bitset is not defined on Little Endian
-// platforms, for the same reason as for vector<bool> (see std::vector above):
-// It does not expose the raw bytes, and a fallback to std::hash<> is most
-// likely faster.
-
-#if defined(ABSL_IS_BIG_ENDIAN) && \
-    (defined(__GLIBCXX__) || defined(__GLIBCPP__))
 // AbslHashValue for hashing std::bitset
 //
-// std::hash in libstdc++ does not work correctly with std::bitset on Big Endian
-// platforms therefore we need to implement a custom AbslHashValue for it. More
-// details on the bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531
+// To achieve high performance without depending on private standard library
+// internals, we pack bits 64 at a time into uint64_t words using a fixed
+// 64-step inner loop that allows compilers to unroll bit shifts cleanly.
+//
+// This is slower than std::hash<std::bitset> which can access private storage
+// directly, but more than fast enough for the very rare case of hashing
+// std::bitset. In the event that higher-performance is needed, users can just
+// use std::hash as the hasher.
 template <typename H, size_t N>
 H AbslHashValue(H hash_state, const std::bitset<N>& set) {
   typename H::AbslInternalPiecewiseCombiner combiner;
-  for (size_t i = 0; i < N; i++) {
-    unsigned char c = static_cast<unsigned char>(set[i]);
-    hash_state = combiner.add_buffer(std::move(hash_state), &c, sizeof(c));
+  size_t i = 0;
+  // Pack full 64-bit words. Fixed inner loop count enables compiler unrolling.
+  while (i + 64 <= N) {
+    uint64_t word = 0;
+    for (size_t j = 0; j < 64; ++j) {
+      word |= static_cast<uint64_t>(set[i + j]) << j;
+    }
+    hash_state = combiner.add_buffer(
+        std::move(hash_state), reinterpret_cast<const unsigned char*>(&word),
+        sizeof(word));
+    i += 64;
+  }
+  // Pack remaining bits (< 64) into the final word.
+  if (i < N) {
+    uint64_t word = 0;
+    const size_t rem = N - i;
+    for (size_t j = 0; j < rem; ++j) {
+      word |= static_cast<uint64_t>(set[i + j]) << j;
+    }
+    hash_state = combiner.add_buffer(
+        std::move(hash_state), reinterpret_cast<const unsigned char*>(&word),
+        (rem + 7) / 8);
   }
   return H::combine(combiner.finalize(std::move(hash_state)), N);
 }
-#endif
 
 // -----------------------------------------------------------------------------