Disallow reentrance removal in `absl::erase_if`.
Predicates should generally have no side effects since we do not guarantee the order or quantity for the calls.
In this change we forbid one specific side effect: modification of the table we are iterating over.
As a positive effect we have performance improvements (less computations and less branches).
```
name old cpu/op new cpu/op delta
BM_EraseIf/num_elements:10/num_erased:0 3.02ns ± 2% 2.79ns ± 3% -7.44% (p=0.000 n=35+37)
BM_EraseIf/num_elements:1000/num_erased:0 2.41ns ± 5% 2.05ns ± 4% -14.88% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5 4.40ns ± 3% 4.22ns ± 3% -4.19% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500 9.16ns ± 4% 9.13ns ± 3% ~ (p=0.307 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10 5.77ns ± 3% 5.50ns ± 4% -4.62% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000 7.84ns ± 3% 7.77ns ± 3% -0.94% (p=0.006 n=37+35)
name old time/op new time/op delta
BM_EraseIf/num_elements:10/num_erased:0 3.02ns ± 2% 2.79ns ± 3% -7.48% (p=0.000 n=35+36)
BM_EraseIf/num_elements:1000/num_erased:0 2.41ns ± 5% 2.05ns ± 4% -14.89% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5 4.42ns ± 3% 4.23ns ± 3% -4.22% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500 9.18ns ± 4% 9.15ns ± 3% ~ (p=0.347 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10 5.79ns ± 3% 5.52ns ± 4% -4.61% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000 7.87ns ± 3% 7.79ns ± 3% -0.95% (p=0.007 n=37+35)
name old INSTRUCTIONS/op new INSTRUCTIONS/op delta
BM_EraseIf/num_elements:10/num_erased:0 14.9 ± 0% 12.9 ± 0% -13.46% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:0 12.7 ± 0% 10.3 ± 0% -18.76% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5 30.9 ± 0% 28.9 ± 0% -6.48% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:500 37.6 ± 0% 35.3 ± 0% -6.33% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:10 46.9 ± 0% 44.9 ± 0% -4.27% (p=0.000 n=37+37)
BM_EraseIf/num_elements:1000/num_erased:1000 62.6 ± 0% 60.2 ± 0% -3.80% (p=0.000 n=37+36)
name old CYCLES/op new CYCLES/op delta
BM_EraseIf/num_elements:10/num_erased:0 4.91 ± 1% 4.11 ± 1% -16.35% (p=0.000 n=36+35)
BM_EraseIf/num_elements:1000/num_erased:0 7.74 ± 2% 6.54 ± 2% -15.54% (p=0.000 n=37+37)
BM_EraseIf/num_elements:10/num_erased:5 9.18 ± 3% 8.45 ± 3% -7.88% (p=0.000 n=37+35)
BM_EraseIf/num_elements:1000/num_erased:500 29.5 ± 1% 29.3 ± 1% -0.82% (p=0.000 n=36+37)
BM_EraseIf/num_elements:10/num_erased:10 13.5 ± 1% 12.6 ± 0% -7.06% (p=0.000 n=33+34)
BM_EraseIf/num_elements:1000/num_erased:1000 25.1 ± 0% 24.9 ± 0% -0.90% (p=0.000 n=37+35)
```
PiperOrigin-RevId: 642318040
Change-Id: I78a4a5a9a5881db0818225f9c7c153c562009f66
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index d859872..c63b60e 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1902,6 +1902,9 @@
ctrl += Group::kWidth;
if (kAllowRemoveReentrance && *(ctrl - 1) == ctrl_t::kSentinel) {
break;
+ } else {
+ assert((remaining == 0 || *(ctrl - 1) != ctrl_t::kSentinel) &&
+ "element was erased from hash table unexpectedly");
}
slot += Group::kWidth;
}
@@ -4061,7 +4064,7 @@
return 1;
}
size_t num_deleted = 0;
- IterateOverFullSlots</*kAllowRemoveReentrance=*/true>(
+ IterateOverFullSlots</*kAllowRemoveReentrance=*/false>(
c->common(), c->slot_array(), [&](const ctrl_t* ctrl, auto* slot) {
if (pred(Set::PolicyTraits::element(slot))) {
c->destroy(slot);
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 9b13701..2a6ee65 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -3121,34 +3121,6 @@
}
}
-// Test that we are allowed to erase during the callback in erase_if.
-// TODO(b/345744331): Consider to change behavior to disallow erasure in the
-// callback.
-TYPED_TEST(SooTest, EraseIfReentry) {
- for (int size = 0; size < 100; ++size) {
- SCOPED_TRACE(absl::StrCat(size));
- TypeParam t;
- std::vector<int64_t> expected;
- for (int i = 0; i < size; ++i) {
- t.insert(i);
- if (i % 4 == 1 || i % 4 == 2) {
- expected.push_back(i);
- }
- }
- auto pred = [&](const auto& x) {
- auto value = static_cast<int64_t>(x);
- int64_t group = value / 4;
- t.erase(group * 4);
- if (value % 4 == 3) {
- return true;
- }
- return false;
- };
- absl::container_internal::EraseIf(pred, &t);
- ASSERT_THAT(t, testing::UnorderedElementsAreArray(expected));
- }
-}
-
TEST(Table, EraseBeginEndResetsReservedGrowth) {
bool frozen = false;
BadHashFreezableIntTable t{FreezableAlloc<int64_t>(&frozen)};
