Use `IterateOverFullSlots` in `absl::erase_if` for hash table.

`EraseIf` itself is not very hot function, but I want to use that as demonstration of the speed of iteration via `IterateOverFullSlots`.

Motivation:
1. We are still going to save some resources.
2. It is the first step to implement faster `absl::c_for_each` that may give larger benefits. Will require readability considerations.

`BM_EraseIf/num_elements:1000/num_erased:0` is just iteration and it gives 60% speed up.
On smaller tables  removing all elements shows 25% speed up. Note that on small tables erasing is much faster due to cl/592272653.

```
name                                          old cpu/op   new cpu/op   delta
BM_EraseIf/num_elements:10/num_erased:0       3.41ns ± 5%  3.03ns ± 3%  -11.14%  (p=0.000 n=37+35)
BM_EraseIf/num_elements:1000/num_erased:0     6.06ns ± 3%  2.42ns ± 3%  -60.05%  (p=0.000 n=34+37)
BM_EraseIf/num_elements:10/num_erased:5       5.90ns ± 3%  4.44ns ± 4%  -24.88%  (p=0.000 n=36+37)
BM_EraseIf/num_elements:1000/num_erased:500   11.0ns ± 2%   9.2ns ± 2%  -16.60%  (p=0.000 n=35+37)
BM_EraseIf/num_elements:10/num_erased:10      8.03ns ± 3%  5.77ns ± 2%  -28.19%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000  9.00ns ± 3%  7.83ns ± 2%  -12.98%  (p=0.000 n=37+37)

name                                          old time/op          new time/op          delta
BM_EraseIf/num_elements:10/num_erased:0       3.42ns ± 5%          3.04ns ± 3%  -11.13%  (p=0.000 n=37+36)
BM_EraseIf/num_elements:1000/num_erased:0     6.07ns ± 3%          2.42ns ± 3%  -60.10%  (p=0.000 n=34+37)
BM_EraseIf/num_elements:10/num_erased:5       5.93ns ± 3%          4.45ns ± 4%  -24.89%  (p=0.000 n=36+37)
BM_EraseIf/num_elements:1000/num_erased:500   11.1ns ± 2%           9.2ns ± 2%  -16.61%  (p=0.000 n=35+37)
BM_EraseIf/num_elements:10/num_erased:10      8.06ns ± 3%          5.79ns ± 2%  -28.19%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000  9.03ns ± 3%          7.85ns ± 2%  -12.98%  (p=0.000 n=37+37)

name                                          old INSTRUCTIONS/op  new INSTRUCTIONS/op  delta
BM_EraseIf/num_elements:10/num_erased:0         19.5 ± 1%            14.9 ± 0%  -23.79%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:0       19.9 ± 0%            12.7 ± 0%  -36.20%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5         36.9 ± 1%            30.9 ± 0%  -16.47%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500     44.8 ± 0%            37.6 ± 0%  -16.06%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10        53.0 ± 1%            46.9 ± 0%  -11.61%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000    69.8 ± 0%            62.6 ± 0%  -10.32%  (p=0.000 n=36+37)

name                                          old CYCLES/op        new CYCLES/op        delta
BM_EraseIf/num_elements:10/num_erased:0         6.10 ± 7%            4.91 ± 1%  -19.49%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:0       19.4 ± 1%             7.7 ± 2%  -60.04%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5         13.9 ± 4%             9.2 ± 3%  -33.80%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500     35.5 ± 0%            29.5 ± 1%  -16.74%  (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10        20.8 ± 5%            13.5 ± 0%  -35.07%  (p=0.000 n=37+30)
BM_EraseIf/num_elements:1000/num_erased:1000    28.9 ± 0%            25.1 ± 0%  -13.06%  (p=0.000 n=37+37)
```

PiperOrigin-RevId: 642016364
Change-Id: I8be6af5916bd45fd110bb0398c3ffe932a6a083f

1 files changed, 53 insertions, 17 deletions

diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index f494fb1c..d8598725 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1222,6 +1222,8 @@ class RawHashSetLayout {
   size_t slot_offset_;
 };
 
+struct HashtableFreeFunctionsAccess;
+
 // We only allow a maximum of 1 SOO element, which makes the implementation
 // much simpler. Complications with multiple SOO elements include:
 // - Satisfying the guarantee that erasing one element doesn't invalidate
@@ -1858,8 +1860,9 @@ inline void* SlotAddress(void* slot_array, size_t slot, size_t slot_size) {
 }
 
 // Iterates over all full slots and calls `cb(const ctrl_t*, SlotType*)`.
-// NOTE: no erasure from this table allowed during Callback call.
-template <class SlotType, class Callback>
+// If kAllowRemoveReentrance is false, no erasure from this table allowed during
+// Callback call. This mode is slightly faster.
+template <bool kAllowRemoveReentrance, class SlotType, class Callback>
 ABSL_ATTRIBUTE_ALWAYS_INLINE inline void IterateOverFullSlots(
     const CommonFields& c, SlotType* slot, Callback cb) {
   const size_t cap = c.capacity();
@@ -1882,18 +1885,25 @@ ABSL_ATTRIBUTE_ALWAYS_INLINE inline void IterateOverFullSlots(
     --ctrl;
     --slot;
     for (uint32_t i : mask) {
-      cb(ctrl + i, slot + i);
+      if (!kAllowRemoveReentrance || ABSL_PREDICT_TRUE(IsFull(ctrl[i]))) {
+        cb(ctrl + i, slot + i);
+      }
     }
     return;
   }
   size_t remaining = c.size();
   while (remaining != 0) {
     for (uint32_t i : GroupFullEmptyOrDeleted(ctrl).MaskFull()) {
-      cb(ctrl + i, slot + i);
+      if (!kAllowRemoveReentrance || ABSL_PREDICT_TRUE(IsFull(ctrl[i]))) {
+        cb(ctrl + i, slot + i);
+      }
       --remaining;
     }
-    slot += Group::kWidth;
     ctrl += Group::kWidth;
+    if (kAllowRemoveReentrance && *(ctrl - 1) == ctrl_t::kSentinel) {
+      break;
+    }
+    slot += Group::kWidth;
   }
 }
 
@@ -2430,6 +2440,7 @@ class raw_hash_set {
 
   class iterator : private HashSetIteratorGenerationInfo {
     friend class raw_hash_set;
+    friend struct HashtableFreeFunctionsAccess;
 
    public:
     using iterator_category = std::forward_iterator_tag;
@@ -2736,7 +2747,7 @@ class raw_hash_set {
     size_t offset = cap;
     const size_t shift =
         is_single_group(cap) ? (PerTableSalt(control()) | 1) : 0;
-    IterateOverFullSlots(
+    IterateOverFullSlots</*kAllowRemoveReentrance=*/false>(
         that.common(), that.slot_array(),
         [&](const ctrl_t* that_ctrl,
             slot_type* that_slot) ABSL_ATTRIBUTE_ALWAYS_INLINE {
@@ -3411,6 +3422,8 @@ class raw_hash_set {
   friend struct absl::container_internal::hashtable_debug_internal::
       HashtableDebugAccess;
 
+  friend struct absl::container_internal::HashtableFreeFunctionsAccess;
+
   struct FindElement {
     template <class K, class... Args>
     const_iterator operator()(const K& key, Args&&...) const {
@@ -3521,7 +3534,7 @@ class raw_hash_set {
   inline void destroy_slots() {
     assert(!is_soo());
     if (PolicyTraits::template destroy_is_trivial<Alloc>()) return;
-    IterateOverFullSlots(
+    IterateOverFullSlots</*kAllowRemoveReentrance=*/false>(
         common(), slot_array(),
         [&](const ctrl_t*, slot_type* slot)
             ABSL_ATTRIBUTE_ALWAYS_INLINE { this->destroy(slot); });
@@ -3866,7 +3879,8 @@ class raw_hash_set {
     }
     // We only do validation for small tables so that it's constant time.
     if (capacity() > 16) return;
-    IterateOverFullSlots(common(), slot_array(), assert_consistent);
+    IterateOverFullSlots</*kAllowRemoveReentrance=*/false>(
+        common(), slot_array(), assert_consistent);
 #endif
   }
 
@@ -4030,19 +4044,41 @@ class raw_hash_set {
                 key_equal{}, allocator_type{}};
 };
 
+// Friend access for free functions in raw_hash_set.h.
+struct HashtableFreeFunctionsAccess {
+  template <class Predicate, typename Set>
+  static typename Set::size_type EraseIf(Predicate& pred, Set* c) {
+    if (c->empty()) {
+      return 0;
+    }
+    if (c->is_soo()) {
+      auto it = c->soo_iterator();
+      if (!pred(*it)) {
+        return 0;
+      }
+      c->destroy(it.slot());
+      c->common().set_empty_soo();
+      return 1;
+    }
+    size_t num_deleted = 0;
+    IterateOverFullSlots</*kAllowRemoveReentrance=*/true>(
+        c->common(), c->slot_array(), [&](const ctrl_t* ctrl, auto* slot) {
+          if (pred(Set::PolicyTraits::element(slot))) {
+            c->destroy(slot);
+            EraseMetaOnly(c->common(), static_cast<size_t>(ctrl - c->control()),
+                          sizeof(*slot));
+            ++num_deleted;
+          }
+        });
+    return num_deleted;
+  }
+};
+
 // Erases all elements that satisfy the predicate `pred` from the container `c`.
 template <typename P, typename H, typename E, typename A, typename Predicate>
 typename raw_hash_set<P, H, E, A>::size_type EraseIf(
     Predicate& pred, raw_hash_set<P, H, E, A>* c) {
-  const auto initial_size = c->size();
-  for (auto it = c->begin(), last = c->end(); it != last;) {
-    if (pred(*it)) {
-      c->erase(it++);
-    } else {
-      ++it;
-    }
-  }
-  return initial_size - c->size();
+  return HashtableFreeFunctionsAccess::EraseIf(pred, c);
 }
 
 namespace hashtable_debug_internal {