Rollforward "Make slot_array to assume large table to optimize large raw_hash_set operations." PiperOrigin-RevId: 991865689 Change-Id: I5372af702835c492cecda67f8efd30a9c7637f68
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 0a72ee3..810bc25 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -821,7 +821,7 @@ template <bool kSooEnabled> void* SingleSlotAddress(CommonFields& c) { - return kSooEnabled ? c.soo_data() : c.slot_array(/*capacity=*/1); + return kSooEnabled ? c.soo_data() : c.single_non_soo_slot(); } template <bool kSooEnabled> @@ -854,7 +854,7 @@ if (c.is_small()) { if (!c.empty()) { static_assert(kMaxSmallCapacity == 1); - policy.destroy_slot(&c, c.slot_array(/*capacity=*/1)); + policy.destroy_slot(&c, c.single_non_soo_slot()); } } else { DestroySlots(c, policy.slot_size, policy.destroy_slot); @@ -994,7 +994,8 @@ size_t FindNewPositionsAndTransferSlots( CommonFields& common, const PolicyFunctions& __restrict policy, ctrl_t* old_ctrl, void* old_slots, size_t old_capacity) { - void* new_slots = common.slot_array(common.capacity()); + void* new_slots = common.is_small() ? common.single_non_soo_slot() + : common.slot_array(common.capacity()); const void* hash_fn = policy.hash_fn(common); const size_t slot_size = policy.slot_size; const size_t seed = common.seed().seed(); @@ -1421,6 +1422,7 @@ ABSL_ATTRIBUTE_NOINLINE size_t DecodeAndInsertImpl( CommonFields& c, const PolicyFunctions& __restrict policy, const ProbedItem* start, const ProbedItem* end, void* old_slots) { + ABSL_SWISSTABLE_ASSERT(!c.is_small()); const HashtableCapacity new_capacity = c.capacity_impl(); void* new_slots = c.slot_array(new_capacity.capacity()); @@ -1459,9 +1461,10 @@ ABSL_ATTRIBUTE_NOINLINE size_t ProcessProbedMarkedElements( CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* old_ctrl, void* old_slots, size_t start) { - size_t old_capacity = PreviousCapacity(c.capacity()); + const size_t new_capacity = c.capacity(); + const size_t old_capacity = PreviousCapacity(new_capacity); const size_t slot_size = policy.slot_size; - void* new_slots = c.slot_array(c.capacity()); + void* new_slots = c.slot_array(new_capacity); size_t total_probe_length = 0; const void* hash_fn = policy.hash_fn(c); auto hash_slot = policy.hash_slot; @@ -1760,7 +1763,7 @@ ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); constexpr size_t kOldCapacity = 1; constexpr size_t kNewCapacity = NextCapacity(kOldCapacity); - void* old_slots = common.slot_array(kOldCapacity); + void* old_slots = common.single_non_soo_slot(); // old_slots == old_ctrl in case of capacity == 1. ctrl_t* old_ctrl = static_cast<ctrl_t*>(old_slots); @@ -1895,7 +1898,7 @@ if (common.empty()) { IncrementSmallSizeNonSoo(common, policy); // Compute before `RecordInsertMissCold` to avoid reloading `control_`. - void* res = common.slot_array(/*capacity=*/1); + void* res = common.single_non_soo_slot(); // Call NOINLINE function to move infoz instructions out of line. if (common.has_infoz()) { ReportInsertMissToInfozAndComputeHash(common, /*probe_length=*/0, @@ -2148,7 +2151,9 @@ const size_t old_capacity = common.capacity(); ctrl_t* const old_ctrl = common.control(); - void* const old_slots = common.slot_array(old_capacity); + void* const old_slots = IsSmallCapacity(old_capacity) + ? common.single_non_soo_slot() + : common.slot_array(old_capacity); const size_t old_blocked_element_count = common.blocked_element_count(); const size_t slot_size = policy.slot_size; @@ -2276,8 +2281,10 @@ ABSL_SWISSTABLE_ASSERT(common.has_infoz()); return; } + // Reducing from large capacity to SOO. ABSL_SWISSTABLE_ASSERT(slot_size <= sizeof(HeapOrSoo)); ABSL_SWISSTABLE_ASSERT(policy.slot_align <= alignof(HeapOrSoo)); + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(cap)); HeapOrSoo tmp_slot; size_t begin_offset = FindFirstFullSlot(0, cap, common.control()); policy.transfer_n( @@ -2333,7 +2340,7 @@ const void* other_slot = other_capacity <= soo_capacity ? other.soo_data() : IsSmallCapacity(other_capacity) - ? other.slot_array(other_capacity) + ? other.single_non_soo_slot() : SlotAddress(other.slot_array(other_capacity), FindFirstFullSlot(0, other_capacity, other.control()), slot_size);
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index a942d0b..d6b7496 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1105,9 +1105,14 @@ // `Group::kWidth`-width probe window starting from any control byte. constexpr size_t NumClonedBytes() { return Group::kWidth - 1; } +// Returns the number of control bytes including cloned assuming large table. +constexpr size_t NumControlBytesForLargeTable(size_t capacity) { + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(capacity)); + return capacity + 1 + NumClonedBytes(); +} // Returns the number of control bytes including cloned. constexpr size_t NumControlBytes(size_t capacity) { - return IsSmallCapacity(capacity) ? 0 : capacity + 1 + NumClonedBytes(); + return IsSmallCapacity(capacity) ? 0 : NumControlBytesForLargeTable(capacity); } // Returns the size in bytes table with given capacity use to store GrowthInfo. @@ -1301,13 +1306,17 @@ // Note: we can't use slots() because Qt defines "slots" as a macro. // Returns pointer to the slots of a table with explicit capacity that must be // equal to the actual capacity of the table. - // Capacity is often known at compile time or already in register with some - // ABSL_ASSUME conditions. We require passing it explicitly to eliminate - // branches inside of NumControlBytes in majority of cases. + // Table must be large. void* slot_array(size_t capacity) const { ABSL_SWISSTABLE_ASSERT(capacity == this->capacity()); + ABSL_ASSUME(capacity > kMaxSmallCapacity); ctrl_t* ctrl = control(); - return ctrl + NumControlBytes(capacity); + return ctrl + NumControlBytesForLargeTable(capacity); + } + // Returns pointer to the single slot of a table with capacity 1. + void* single_non_soo_slot() const { + ABSL_SWISSTABLE_ASSERT(capacity() == 1); + return control(); } // The number of filled slots. @@ -3938,9 +3947,7 @@ } slot_type* single_slot() { ABSL_SWISSTABLE_ASSERT(is_small()); - return SooEnabled() - ? soo_slot() - : to_slot(common().slot_array(/*capacity=*/1)); + return SooEnabled() ? soo_slot() : to_slot(common().single_non_soo_slot()); } const slot_type* single_slot() const { return const_cast<raw_hash_set*>(this)->single_slot();
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 3b799c3..2ae8023 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -82,8 +82,8 @@ return std::forward<C>(c).common(); } template <typename C> - static auto GetSlots(const C& c) -> decltype(c.slot_array(c.capacity())) { - return c.slot_array(c.capacity()); + static auto GetSlots(C& c) -> decltype(c.slot_array(c.capacity())) { + return c.is_small() ? c.single_slot() : c.slot_array(c.capacity()); } template <typename C> static size_t CountTombstones(const C& c) {