summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2023-12-19 10:19:12 -0800
committerGravatar Copybara-Service <copybara-worker@google.com>2023-12-19 10:20:04 -0800
commit46223c8620c98be44628037e0a21c56182bf4f64 (patch)
tree2d45061b25240c4b03821669196548477ffaa778 /absl
parent78c2f64873cdff76f6790413b98ed47937b7f2c4 (diff)
Refactor `EraseMetaOnly` to speed up single group tables.
PiperOrigin-RevId: 592272653 Change-Id: I895c5786555227bdc88ab0a4cce8cf5ba65222a1
Diffstat (limited to 'absl')
-rw-r--r--absl/container/internal/raw_hash_set.cc35
-rw-r--r--absl/container/internal/raw_hash_set.h5
-rw-r--r--absl/container/internal/raw_hash_set_test.cc17
3 files changed, 42 insertions, 15 deletions
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc
index 6bc5f7bd..9f8ea519 100644
--- a/absl/container/internal/raw_hash_set.cc
+++ b/absl/container/internal/raw_hash_set.cc
@@ -221,26 +221,35 @@ void DropDeletesWithoutResize(CommonFields& common,
common.infoz().RecordRehash(total_probe_length);
}
-void EraseMetaOnly(CommonFields& c, ctrl_t* it, size_t slot_size) {
- assert(IsFull(*it) && "erasing a dangling iterator");
- c.decrement_size();
- const auto index = static_cast<size_t>(it - c.control());
+static bool WasNeverFull(CommonFields& c, size_t index) {
+ if (is_single_group(c.capacity())) {
+ return true;
+ }
const size_t index_before = (index - Group::kWidth) & c.capacity();
- const auto empty_after = Group(it).MaskEmpty();
+ const auto empty_after = Group(c.control() + index).MaskEmpty();
const auto empty_before = Group(c.control() + index_before).MaskEmpty();
// We count how many consecutive non empties we have to the right and to the
// left of `it`. If the sum is >= kWidth then there is at least one probe
// window that might have seen a full group.
- bool was_never_full = empty_before && empty_after &&
- static_cast<size_t>(empty_after.TrailingZeros()) +
- empty_before.LeadingZeros() <
- Group::kWidth;
-
- SetCtrl(c, index, was_never_full ? ctrl_t::kEmpty : ctrl_t::kDeleted,
- slot_size);
- c.set_growth_left(c.growth_left() + (was_never_full ? 1 : 0));
+ return empty_before && empty_after &&
+ static_cast<size_t>(empty_after.TrailingZeros()) +
+ empty_before.LeadingZeros() <
+ Group::kWidth;
+}
+
+void EraseMetaOnly(CommonFields& c, size_t index, size_t slot_size) {
+ assert(IsFull(c.control()[index]) && "erasing a dangling iterator");
+ c.decrement_size();
c.infoz().RecordErase();
+
+ if (WasNeverFull(c, index)) {
+ SetCtrl(c, index, ctrl_t::kEmpty, slot_size);
+ c.set_growth_left(c.growth_left() + 1);
+ return;
+ }
+
+ SetCtrl(c, index, ctrl_t::kDeleted, slot_size);
}
void ClearBackingArray(CommonFields& c, const PolicyFunctions& policy,
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 3b3c5aa3..b7295c84 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1788,7 +1788,7 @@ void ClearBackingArray(CommonFields& c, const PolicyFunctions& policy,
bool reuse);
// Type-erased version of raw_hash_set::erase_meta_only.
-void EraseMetaOnly(CommonFields& c, ctrl_t* it, size_t slot_size);
+void EraseMetaOnly(CommonFields& c, size_t index, size_t slot_size);
// Function to place in PolicyFunctions::dealloc for raw_hash_sets
// that are using std::allocator. This allows us to share the same
@@ -2871,7 +2871,8 @@ class raw_hash_set {
// This merely updates the pertinent control byte. This can be used in
// conjunction with Policy::transfer to move the object to another place.
void erase_meta_only(const_iterator it) {
- EraseMetaOnly(common(), it.control(), sizeof(slot_type));
+ EraseMetaOnly(common(), static_cast<size_t>(it.control() - control()),
+ sizeof(slot_type));
}
// Resizes table to the new capacity and move all elements to the new
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index ab3b8f9f..fe000742 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -653,6 +653,23 @@ TEST(Table, InsertCollisionAndFindAfterDelete) {
EXPECT_TRUE(t.empty());
}
+TEST(Table, EraseInSmallTables) {
+ for (int64_t size = 0; size < 64; ++size) {
+ IntTable t;
+ for (int64_t i = 0; i < size; ++i) {
+ t.insert(i);
+ }
+ for (int64_t i = 0; i < size; ++i) {
+ t.erase(i);
+ EXPECT_EQ(t.size(), size - i - 1);
+ for (int64_t j = i + 1; j < size; ++j) {
+ EXPECT_THAT(*t.find(j), j);
+ }
+ }
+ EXPECT_TRUE(t.empty());
+ }
+}
+
TEST(Table, InsertWithinCapacity) {
IntTable t;
t.reserve(10);