Export of internal Abseil changes

--
58affd6378c47993f5408f7b8a8863fa5bcc2c47 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 403120541

--
27dc5d5f87bca6254585cca69058c14e0a2f3ce6 by Chris Kennelly <ckennelly@google.com>:

Prefetch while hashing.

While we may not need to access the cacheline *ctrl_ is on once we've computed the hash, we can begin to resolve the TLB required for the hashtable's heap allocation simultaneously with computing the hash value for the key.

PiperOrigin-RevId: 402954725
GitOrigin-RevId: 58affd6378c47993f5408f7b8a8863fa5bcc2c47
Change-Id: Id04297de823ad5c5a867c46065fa3a9ef0ada3dd

1 files changed, 13 insertions, 0 deletions

diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 5c5db12..47e5a22 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1446,6 +1446,7 @@ class raw_hash_set {
   void prefetch(const key_arg<K>& key) const {
     (void)key;
 #if defined(__GNUC__)
+    prefetch_heap_block();
     auto seq = probe(ctrl_, hash_ref()(key), capacity_);
     __builtin_prefetch(static_cast<const void*>(ctrl_ + seq.offset()));
     __builtin_prefetch(static_cast<const void*>(slots_ + seq.offset()));
@@ -1477,6 +1478,7 @@ class raw_hash_set {
   }
   template <class K = key_type>
   iterator find(const key_arg<K>& key) {
+    prefetch_heap_block();
     return find(key, hash_ref()(key));
   }
 
@@ -1486,6 +1488,7 @@ class raw_hash_set {
   }
   template <class K = key_type>
   const_iterator find(const key_arg<K>& key) const {
+    prefetch_heap_block();
     return find(key, hash_ref()(key));
   }
 
@@ -1856,6 +1859,7 @@ class raw_hash_set {
  protected:
   template <class K>
   std::pair<size_t, bool> find_or_prepare_insert(const K& key) {
+    prefetch_heap_block();
     auto hash = hash_ref()(key);
     auto seq = probe(ctrl_, hash, capacity_);
     while (true) {
@@ -1918,6 +1922,15 @@ class raw_hash_set {
 
   size_t& growth_left() { return settings_.template get<0>(); }
 
+  void prefetch_heap_block() const {
+    // Prefetch the heap-allocated memory region to resolve potential TLB
+    // misses.  This is intended to overlap with execution of calculating the
+    // hash for a key.
+#if defined(__GNUC__)
+    __builtin_prefetch(static_cast<const void*>(ctrl_), 0, 1);
+#endif  // __GNUC__
+  }
+
   HashtablezInfoHandle& infoz() { return settings_.template get<1>(); }
 
   hasher& hash_ref() { return settings_.template get<2>(); }