From a0889af0a23030e6bb27c6c7241bade7e59cb763 Mon Sep 17 00:00:00 2001 From: Vitaly Goldshteyn Date: Tue, 11 Jun 2024 10:41:39 -0700 Subject: Disallow reentrance removal in `absl::erase_if`. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 --- absl/container/internal/raw_hash_set_test.cc | 28 ---------------------------- 1 file changed, 28 deletions(-) (limited to 'absl/container/internal/raw_hash_set_test.cc') diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 9b13701f..2a6ee656 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -3121,34 +3121,6 @@ TYPED_TEST(SooTest, EraseIfPartial) { } } -// 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 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(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(&frozen)}; -- cgit v1.2.3