Optimize GrowthInfo storage for small capacities. GrowthInfo now occupies only one byte for tables with capacity up to 127. This reduces memory overhead for smaller hash tables. We store 1 byte "cache" of growth info. For small tables <= 127 capacity it will be all we store. For larger tables we will store additional 7 bytes of growth info. This way the hottest path just unconditionally access 1 byte growth info. Once in 128 inserts, we will fall into "slow path". There we will learn that there are more growth_info available. We will insert the element and set "cache" byte to 127. Most commonly 1 byte of growth info will be placed into the padding. 1. 1-byte growth info for tables upto 127. 2. 1 byte would fit into padding. With `NumClonedBytes` we allocate `capacity + 16` bytes of control block. 3. `Capacity->ControlBytes` examples: `3->19`, `7->23`, `15->31`, `31->47`. 4. On ARM we have 7 cloned bytes: `3->11`, `7->15`, `15->23`, `31->39` 5. Alignment is typically at least 4, so we almost always can fit 1 byte in the padding. For 32 bit systems we will use 64 bits for growth info for big tables. PiperOrigin-RevId: 927299043 Change-Id: I679f7e7d35b8773359b8f2861f5b37d98085be7d
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 5a2c08a..69a411d 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -14,6 +14,7 @@ #include "absl/container/internal/raw_hash_set.h" +#include <algorithm> #include <atomic> #include <cassert> #include <cstddef> @@ -279,8 +280,133 @@ "hash table was modified unexpectedly"); } +// NOTE: we don't use structure with bit fields for GrowthInfo because for +// correctness we rely on the lower bound being the most significant byte. + +// Returns the increment that needs to be added to the packed full growth info +// in order to increase lower bound by lower_bound_increment and increase +// overflow growth left by overflow_increment. +constexpr uint64_t GetPackedIncrement(uint64_t lower_bound_increment, + uint64_t overflow_increment) { + return (lower_bound_increment << GrowthInfoAccessor::kLowerBoundShift) + + overflow_increment; +} + +// Returns the increment that needs to be added to the packed full growth info +// in order to increase lower bound by overflow_to_lower_bound_size and +// decrease overflow growth left by overflow_to_lower_bound_size. +constexpr uint64_t GetRebalanceIncrement( + uint64_t overflow_to_lower_bound_size) { + return GetPackedIncrement(overflow_to_lower_bound_size, + 0u - overflow_to_lower_bound_size); +} + +// Returns the number of elements left to grow in the full growth info. +constexpr uint64_t GetOverflowGrowthLeftFromPacked( + uint64_t packed_full_growth_info) { + constexpr uint64_t kFullGrowthMask = + (uint64_t{1} << GrowthInfoAccessor::kLowerBoundShift) - 1; + return packed_full_growth_info & kFullGrowthMask; +} + +// Returns the GrowthInfoLowerBound object containing the information +// about minimum growth left. +constexpr GrowthInfoLowerBound GetGrowthInfoLowerBoundFromPacked( + uint64_t packed_full_growth_info) { + return GrowthInfoLowerBound(packed_full_growth_info >> + GrowthInfoAccessor::kLowerBoundShift); +} + +// Returns the number of elements left to grow in the lower bound. +constexpr uint64_t GetGrowthLeftLowerBoundFromPacked( + uint64_t packed_full_growth_info) { + return GetGrowthInfoLowerBoundFromPacked(packed_full_growth_info) + .GetGrowthLeft(); +} + +// Returns the total number of elements left to grow in the full growth info. +// Assumes that the table has capacity > kMaxGrowthLeftLowerBound. +uint64_t GetGrowthLeftTotalBigCapacity(void* full_growth_info) { + uint64_t packed_full_growth_left = little_endian::Load64(full_growth_info); + return GetOverflowGrowthLeftFromPacked(packed_full_growth_left) + + GetGrowthLeftLowerBoundFromPacked(packed_full_growth_left); +} + } // namespace +void GrowthInfoAccessor::InitGrowthLeftNoDeleted(size_t growth_left, + size_t capacity) { + if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + *growth_info_lower_bound_ = static_cast<uint8_t>(growth_left); + } else { + uint64_t lower_bound = + (std::min)(uint64_t{growth_left}, + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + little_endian::Store64( + full_growth_info_ptr(), + GetPackedIncrement(lower_bound, growth_left - lower_bound)); + } +} + +GrowthInfoLowerBound GrowthInfoAccessor::RebalanceGrowthLeftLowerBound( + size_t capacity) { + auto growth_left_lower_bound = GetGrowthInfoLowerBound(); + if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound || + // For tables with deleted slots, we often call rebalance even if + // we have growth left in the lower bound. + growth_left_lower_bound.HasDeletedAndGrowthLeft()) { + return growth_left_lower_bound; + } else { + return RebalanceGrowthLeftLowerBoundLargeCapacity(); + } +} + +size_t GrowthInfoAccessor::GetGrowthLeftTotalSlow(size_t capacity) const { + if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + return GetGrowthLeftLowerBound(); + } else { + return GetGrowthLeftTotalBigCapacity(full_growth_info_ptr()); + } +} + +ABSL_ATTRIBUTE_NOINLINE GrowthInfoLowerBound +GrowthInfoAccessor::RebalanceGrowthLeftLowerBoundLargeCapacity() { + void* full_growth_info = full_growth_info_ptr(); + uint64_t packed_full_growth_info = little_endian::Load64(full_growth_info); + uint64_t overflow_growth_left = + GetOverflowGrowthLeftFromPacked(packed_full_growth_info); + uint64_t lower_bound_growth_left = + GetGrowthLeftLowerBoundFromPacked(packed_full_growth_info); + uint64_t overflow_to_lower_bound_size = + (std::min)(overflow_growth_left, + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound - + lower_bound_growth_left); + packed_full_growth_info += + GetRebalanceIncrement(overflow_to_lower_bound_size); + little_endian::Store64(full_growth_info, packed_full_growth_info); + auto result = GetGrowthInfoLowerBoundFromPacked(packed_full_growth_info); + ABSL_SWISSTABLE_ASSERT(result.HasNoDeleted() == + GetGrowthInfoLowerBound().HasNoDeleted()); + ABSL_SWISSTABLE_ASSERT( + (result.GetGrowthLeft() > 0 || + GetGrowthLeftTotalBigCapacity(full_growth_info_ptr()) == 0) && + "rebalance may return 0 only if we have absolutely no growth left"); + return result; +} + +void GrowthInfoAccessor::OverwriteFullAsEmpty() { + if (GetGrowthLeftLowerBound() < + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + ++(*growth_info_lower_bound_); + } else { + constexpr uint64_t kIncrement = GetPackedIncrement( + /*lower_bound_increment=*/0, /*overflow_increment=*/1); + void* const full_growth_info = full_growth_info_ptr(); + little_endian::Store64( + full_growth_info, little_endian::Load64(full_growth_info) + kIncrement); + } +} + void ConvertDeletedToEmptyAndFullToDeleted(ctrl_t* ctrl, size_t capacity) { ABSL_SWISSTABLE_ASSERT(ctrl[capacity] == ctrl_t::kSentinel); ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity)); @@ -299,12 +425,10 @@ namespace { -void ResetGrowthLeft(GrowthInfo& growth_info, size_t capacity, size_t size) { - growth_info.InitGrowthLeftNoDeleted(CapacityToGrowth(capacity) - size); -} - -void ResetGrowthLeft(CommonFields& common) { - ResetGrowthLeft(common.growth_info(), common.capacity(), common.size()); +void ResetGrowthLeft(GrowthInfoAccessor growth_info, size_t capacity, + size_t occupied_elements) { + growth_info.InitGrowthLeftNoDeleted( + CapacityToGrowth(capacity) - occupied_elements, capacity); } // Finds guaranteed to exists empty slot from the given position. @@ -517,7 +641,8 @@ } // Prepare insert for the new element. PrepareInsertCommon(common); - ResetGrowthLeft(common); + ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); + ResetGrowthLeft(common.growth_info(), capacity, common.size()); FindInfo find_info = find_first_non_full(common, new_hash); SetCtrlInLargeTable(common, find_info.offset, H2(new_hash), slot_size); common.infoz().RecordInsertMiss(new_hash, find_info.probe_length); @@ -700,8 +825,7 @@ c.set_size_to_zero(); ABSL_SWISSTABLE_ASSERT(c.capacity() > policy.soo_capacity()); ResetCtrl(c, policy.slot_size, blocked_element_count); - ResetGrowthLeft(c); - c.growth_info().OverwriteManyEmptyAsFull(blocked_element_count); + ResetGrowthLeft(c.growth_info(), c.capacity(), blocked_element_count); ABSL_SWISSTABLE_ASSERT(c.blocked_element_count() == blocked_element_count); c.infoz().RecordStorageChanged(0, c.capacity()); } else { @@ -905,9 +1029,9 @@ common.generate_new_seed(has_infoz); ResetCtrl(common, slot_size, blocked_element_count); - if (HasGrowthInfoForCapacity(new_capacity)) { - GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted( - CapacityToGrowth(new_capacity) - blocked_element_count); + if (GrowthInfoSizeForCapacity(new_capacity) > 0) { + ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, + blocked_element_count); } if (ABSL_PREDICT_FALSE(has_infoz)) { @@ -966,6 +1090,7 @@ AssertFullSoo(common, policy); const size_t slot_size = policy.slot_size; void* alloc = policy.get_char_alloc(common); + constexpr size_t kTableSize = 1; HashtablezInfoHandle infoz; bool has_infoz = false; @@ -990,11 +1115,11 @@ InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots, has_infoz); - ResetGrowthLeft(common); + ResetGrowthLeft(common.growth_info(), new_capacity, kTableSize); if (has_infoz) { common.set_has_infoz(); common.set_infoz(infoz); - infoz.RecordStorageChanged(common.size(), new_capacity); + infoz.RecordStorageChanged(kTableSize, new_capacity); } } @@ -1296,9 +1421,13 @@ } ProbedItem* OverflowBufferStart() const { + ABSL_SWISSTABLE_ASSERT(!kGuaranteedFitToBuffer && + "OverflowBufferStart should not be called when " + "kGuaranteedFitToBuffer is true."); // We reuse GrowthInfo memory as well. - return AlignToNextItem(control_ - ControlOffset(/*has_infoz=*/false, - /*has_growth_info=*/true)); + return AlignToNextItem( + control_ - ControlOffset(/*has_infoz=*/false, + NextCapacity(kMaxLocalBufferOldCapacity))); } // Encodes item when previously allocated buffer is full. @@ -1529,7 +1658,8 @@ /*blocked_element_count=*/0); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); - GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2); + GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2, + kNewCapacity); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportSingleGroupTableGrowthToInfoz(common, infoz, new_hash); @@ -1542,8 +1672,9 @@ size_t GrowToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_hash) { - ABSL_SWISSTABLE_ASSERT(common.growth_left() == 0); const size_t old_capacity = common.capacity(); + ABSL_SWISSTABLE_ASSERT( + common.growth_info().GetGrowthLeftTotalSlow(old_capacity) == 0); ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(old_capacity)); @@ -1729,22 +1860,27 @@ size_t PrepareInsertLargeSlow(CommonFields& common, const PolicyFunctions& __restrict policy, size_t hash) { - const GrowthInfo growth_info = common.growth_info(); - ABSL_SWISSTABLE_ASSERT(!growth_info.HasNoDeletedAndGrowthLeft()); - if (ABSL_PREDICT_TRUE(growth_info.HasNoGrowthLeftAndNoDeleted())) { + GrowthInfoAccessor growth_info = common.growth_info(); + const size_t cap = common.capacity(); + GrowthInfoLowerBound growth_info_lower_bound = + growth_info.RebalanceGrowthLeftLowerBound(cap); + if (ABSL_PREDICT_TRUE( + growth_info_lower_bound.HasNoGrowthLeftAndNoDeleted())) { // Table without deleted slots (>95% cases) that needs to be resized. - ABSL_SWISSTABLE_ASSERT(growth_info.HasNoDeleted() && - growth_info.GetGrowthLeft() == 0); return GrowToNextCapacityAndPrepareInsert(common, policy, hash); } - if (ABSL_PREDICT_FALSE(growth_info.HasNoGrowthLeftAssumingMayHaveDeleted())) { + if (ABSL_PREDICT_FALSE( + growth_info_lower_bound.HasNoGrowthLeftAndHaveDeleted())) { // Table with deleted slots that needs to be rehashed or resized. return RehashOrGrowToNextCapacityAndPrepareInsert(common, policy, hash); } - // Table with deleted slots that has space for the inserting element. + // Covers two cases: + // 1. Table with deleted slots that has space for the inserting element. + // 2. Table without deleted slots that has space and GrowthInfoView was + // rebalanced. FindInfo target = find_first_non_full(common, hash); PrepareInsertCommon(common); - common.growth_info().OverwriteControlAsFull(common.control()[target.offset]); + growth_info.OverwriteControlAsFull(common.control()[target.offset]); SetCtrlInLargeTable(common, target.offset, H2(hash), policy.slot_size); common.infoz().RecordInsertMiss(hash, target.probe_length); return target.offset; @@ -1880,7 +2016,7 @@ common, policy, old_ctrl, old_slots, old_capacity); (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, has_infoz, old_blocked_element_count); - if (HasGrowthInfoForCapacity(new_capacity)) { + if (GrowthInfoSizeForCapacity(new_capacity) > 0) { ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, common.size()); } @@ -1928,7 +2064,8 @@ PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); - GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2); + GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2, + kNewCapacity); common.generate_new_seed(/*has_infoz=*/false); const h2_t soo_slot_h2 = H2(policy.hash_slot( policy.hash_fn(common), common.soo_data(), common.seed().seed())); @@ -2066,6 +2203,7 @@ } ReserveTableToFitNewSize(common, policy, size); + const size_t blocked_element_count = common.blocked_element_count(); auto infoz = common.infoz(); ABSL_SWISSTABLE_ASSERT(other.capacity() > soo_capacity); const size_t cap = common.capacity(); @@ -2087,7 +2225,7 @@ common.maybe_increment_generation_on_insert(); }); common.increment_size(size); - common.growth_info().OverwriteManyEmptyAsFull(size); + ResetGrowthLeft(common.growth_info(), cap, size + blocked_element_count); } void ReserveTableToFitNewSize(CommonFields& common, @@ -2104,7 +2242,9 @@ ABSL_SWISSTABLE_ASSERT(!common.empty() || cap > policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(cap > 0); const size_t max_size_before_growth = - IsSmallCapacity(cap) ? cap : common.size() + common.growth_left(); + IsSmallCapacity(cap) + ? cap + : common.size() + common.growth_info().GetGrowthLeftTotalSlow(cap); if (new_size <= max_size_before_growth) { return; } @@ -2118,15 +2258,16 @@ Group::NonIterableBitMaskType mask_empty, FindInfo target_group) { ABSL_SWISSTABLE_ASSERT(!common.is_small()); - const GrowthInfo growth_info = common.growth_info(); + GrowthInfoAccessor growth_info = common.growth_info(); // When there are no deleted slots in the table // and growth_left is positive, we can insert at the first // empty slot in the probe sequence (target). - if (ABSL_PREDICT_FALSE(!growth_info.HasNoDeletedAndGrowthLeft())) { + if (ABSL_PREDICT_FALSE( + !growth_info.GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft())) { return PrepareInsertLargeSlow(common, policy, hash); } PrepareInsertCommon(common); - common.growth_info().OverwriteEmptyAsFull(); + growth_info.OverwriteEmptyAsFull(); target_group.offset += mask_empty.LowestBitSet(); target_group.offset &= common.capacity(); SetCtrl(common, target_group.offset, H2(hash), policy.slot_size); @@ -2150,11 +2291,13 @@ absl::FunctionRef<size_t(size_t)> recompute_hash) { // NOLINTNEXTLINE(misc-static-assert) ABSL_SWISSTABLE_ASSERT(SwisstableGenerationsEnabled()); - if (common.should_rehash_for_bug_detection_on_insert()) { + const size_t cap = common.capacity(); + const size_t growth_left = common.growth_info().GetGrowthLeftTotalSlow(cap); + // As an optimization, we avoid calling ShouldRehashForBugDetection if we + // will end up rehashing anyways. + if (growth_left > 0 && common.should_rehash_for_bug_detection_on_insert()) { // Move to a different heap allocation in order to detect bugs. - const size_t cap = common.capacity(); - ResizeAllocatedTableWithSeedChange( - common, policy, common.growth_left() > 0 ? cap : NextCapacity(cap)); + ResizeAllocatedTableWithSeedChange(common, policy, cap); hash = recompute_hash(common.seed().seed()); std::tie(target_group, mask_empty) = find_first_non_full_group(common, hash);
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index affe395..478a55c 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -59,9 +59,13 @@ // struct BackingArray { // // Sampling handler. This field isn't present when the sampling is // // disabled or this allocation hasn't been selected for sampling. -// HashtablezInfoHandle infoz_; -// // The number of elements we can insert before growing the capacity. -// size_t growth_left; +// HashtablezInfoHandle infoz_; // optional +// // Additional number that can be added to growth_left_lower_bound. +// // Only stored for tables with large capacities. +// uint8_t growth_left_overflow[7]; // optional +// // The minimum number of elements we can insert before growing the +// // capacity. +// uint8_t growth_left_lower_bound; // // Control bytes for the "real" slots. // ctrl_t ctrl[capacity]; // // Always `ctrl_t::kSentinel`. This is used by iterators to find when to @@ -921,78 +925,149 @@ // which will recompute this value as a side-effect. // // See also `CapacityToGrowth()`. -class GrowthInfo { +// +// GrowthInfo is stored as 1 or 8 bytes at the beginning of the backing array. +// For capacity <= kMaxGrowthLeftLowerBound we store single byte, otherwise we +// store 8 bytes. Byte before the first control byte for all tables is always +// used to store GrowthInfoLowerBound. That helps to avoid any branching in the +// hottest code accessing GrowthInfo. GrowthInfoLowerBound has 7 bits to store +// the growth left and 1 bit to store whether the table has any deleted slots. +// For capacity > kMaxGrowthLeftLowerBound we use another 7 bytes to store the +// full GrowthInfo. GrowthInfo for capacity > kMaxGrowthLeftLowerBound is stored +// as uint64_t in little endian encoding. Most significant 8 bits (last byte in +// little endian encoding) contains GrowthInfoLowerBound. +class GrowthInfoAccessor; + +// One byte encoding of lower bound GrowthInfo. +// It encodes number of growth left from 0 to kMaxGrowthLeftLowerBound and +// whether the table has any deleted slots. +class GrowthInfoLowerBound { public: - // Leaves data member uninitialized. - GrowthInfo() = default; + static constexpr uint8_t kGrowthLeftMask = 0x7Fu; + static constexpr uint8_t kDeletedBit = 0x80u; + static constexpr uint64_t kMaxGrowthLeftLowerBound = 127; + static_assert(kMaxGrowthLeftLowerBound == kGrowthLeftMask); - // Initializes the GrowthInfo assuming we can grow `growth_left` elements - // and there are no kDeleted slots in the table. - void InitGrowthLeftNoDeleted(size_t growth_left) { - growth_left_info_ = growth_left; - } - - // Overwrites single full slot with an empty slot. - void OverwriteFullAsEmpty() { ++growth_left_info_; } - - // Overwrites single empty slot with a full slot. - void OverwriteEmptyAsFull() { - ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() > 0); - --growth_left_info_; - } - - // Overwrites several empty slots with full slots. - void OverwriteManyEmptyAsFull(size_t count) { - ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() >= count); - growth_left_info_ -= count; - } - - // Overwrites specified control element with full slot. - void OverwriteControlAsFull(ctrl_t ctrl) { - ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() >= - static_cast<size_t>(IsEmpty(ctrl))); - growth_left_info_ -= static_cast<size_t>(IsEmpty(ctrl)); - } - - // Overwrites single full slot with a deleted slot. - void OverwriteFullAsDeleted() { growth_left_info_ |= kDeletedBit; } + explicit constexpr GrowthInfoLowerBound(uint8_t growth_left) + : growth_left_(growth_left) {} // Returns true if table satisfies two properties: // 1. Guaranteed to have no kDeleted slots. // 2. There is a place for at least one element to grow. - bool HasNoDeletedAndGrowthLeft() const { - return static_cast<std::make_signed_t<size_t>>(growth_left_info_) > 0; + constexpr bool HasNoDeletedAndGrowthLeft() const { + return static_cast<int8_t>(growth_left_) > 0; + } + + // Returns true if table satisfies two properties: + // 1. May have kDeleted slots (kDeletedBit == 1). + // 2. There is a place for at least one element to grow. + constexpr bool HasDeletedAndGrowthLeft() const { + return growth_left_ > kDeletedBit; } // Returns true if the table satisfies two properties: // 1. Guaranteed to have no kDeleted slots. // 2. There is no growth left. - bool HasNoGrowthLeftAndNoDeleted() const { return growth_left_info_ == 0; } + constexpr bool HasNoGrowthLeftAndNoDeleted() const { + return growth_left_ == 0; + } - // Returns true if GetGrowthLeft() == 0, but must be called only if - // HasNoDeleted() is false. It is slightly more efficient. - bool HasNoGrowthLeftAssumingMayHaveDeleted() const { - ABSL_SWISSTABLE_ASSERT(!HasNoDeleted()); - return growth_left_info_ == kDeletedBit; + // Returns true if GetGrowthLeft() == 0 and HasNoDeleted() is false. + // It is slightly more efficient. + constexpr bool HasNoGrowthLeftAndHaveDeleted() const { + return growth_left_ == kDeletedBit; } // Returns true if table guaranteed to have no kDeleted slots. - bool HasNoDeleted() const { - return static_cast<std::make_signed_t<size_t>>(growth_left_info_) >= 0; + constexpr bool HasNoDeleted() const { + return (growth_left_ & kDeletedBit) == 0; } - // Returns the number of elements left to grow. - size_t GetGrowthLeft() const { return growth_left_info_ & kGrowthLeftMask; } + // Returns the minimum number of elements left to grow. + // Use GrowthInfoView::GetGrowthLeftTotal() to get the total number of + // elements left to grow. For tables with capacity <= + // kMaxGrowthLeftLowerBound, this is the same as GetGrowthLeftTotal(). + constexpr uint8_t GetGrowthLeft() const { + return growth_left_ & kGrowthLeftMask; + } private: - static constexpr size_t kGrowthLeftMask = ((~size_t{}) >> 1); - static constexpr size_t kDeletedBit = ~kGrowthLeftMask; - // Topmost bit signal whenever there are deleted slots. - size_t growth_left_info_; + uint8_t growth_left_; }; -static_assert(sizeof(GrowthInfo) == sizeof(size_t), ""); -static_assert(alignof(GrowthInfo) == alignof(size_t), ""); +// GrowthInfo is stored in the backing array, and this class provides a simple +// interface to access and modify it. +class GrowthInfoAccessor { + public: + // GrowthInfoLowerBound is stored in the most significant 8 bits of the + // full growth info. + static constexpr uint64_t kLowerBoundShift = 64 - 8; + + explicit GrowthInfoAccessor(void* control) + : growth_info_lower_bound_(reinterpret_cast<uint8_t*>(control) - 1) {} + + // Initializes the GrowthInfo assuming we can grow `growth_left` elements + // and there are no kDeleted slots in the table. + void InitGrowthLeftNoDeleted(size_t growth_left, size_t capacity); + + // Returns a GrowthInfoLowerBound object containing the information + // about minimum growth left. + // It guarantees that GetGrowthLeft() will be > 0 if GetGrowthLeftTotal() > 0. + // It may optionally borrow some growth left from the full_growth_info. + GrowthInfoLowerBound RebalanceGrowthLeftLowerBound(size_t capacity); + + // Overwrites single full slot with an empty slot. + void OverwriteFullAsEmpty(); + + // Overwrites single empty slot with a full slot. + // Must be called when GetGrowthLeftLowerBound() > 0. + void OverwriteEmptyAsFull() { + ABSL_SWISSTABLE_ASSERT(GetGrowthLeftLowerBound() > 0); + --(*growth_info_lower_bound_); + } + + // Overwrites specified control element with full slot. + // Must be called when GetGrowthLeftLowerBound() >= IsEmpty(ctrl). + void OverwriteControlAsFull(ctrl_t ctrl) { + ABSL_SWISSTABLE_ASSERT(GetGrowthLeftLowerBound() >= + static_cast<size_t>(IsEmpty(ctrl))); + *growth_info_lower_bound_ -= static_cast<size_t>(IsEmpty(ctrl)); + } + + // Overwrites single full slot with a deleted slot. + void OverwriteFullAsDeleted() { + *growth_info_lower_bound_ |= GrowthInfoLowerBound::kDeletedBit; + } + + // Returns a GrowthInfoLowerBound object containing the information + // about minimum growth left. + GrowthInfoLowerBound GetGrowthInfoLowerBound() const { + return GrowthInfoLowerBound(*growth_info_lower_bound_); + } + + // Returns the minimum number of elements left to grow. + size_t GetGrowthLeftLowerBound() const { + return GetGrowthInfoLowerBound().GetGrowthLeft(); + } + + // The number of slots we can still fill without needing to rehash. + // Hot code paths should try to work with + // growth_info().GetGrowthLeftLowerBound() instead. + size_t GetGrowthLeftTotalSlow(size_t capacity) const; + + private: + void* full_growth_info_ptr() const { return growth_info_lower_bound_ - 7; } + + GrowthInfoLowerBound RebalanceGrowthLeftLowerBoundLargeCapacity(); + + // Pointer to the GrowthInfoLowerBound data. + // For large capacities, 7 bytes before this pointer is used to store + // the full growth info. + // NOTE: using a pointer here can result in the compiler being forced to + // assume aliasing can happen. So in hot code paths, we try to work with + // GrowthInfoLowerBound directly + uint8_t* growth_info_lower_bound_; +}; // Returns the number of "cloned control bytes". // @@ -1006,20 +1081,26 @@ return IsSmallCapacity(capacity) ? 0 : capacity + 1 + NumClonedBytes(); } -// Returns whether table with the given capacity has a GrowthInfo. -constexpr bool HasGrowthInfoForCapacity(size_t capacity) { - return !IsSmallCapacity(capacity); +// Returns the size in bytes table with given capacity use to store GrowthInfo. +// Returns 0 for small tables that doesn't store GrowthInfo. +constexpr size_t GrowthInfoSizeForCapacity(size_t capacity) { + if (IsSmallCapacity(capacity)) { + return 0; + } + return capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound + ? sizeof(uint8_t) + : sizeof(uint64_t); } // Computes the offset from the start of the backing allocation of control. // infoz and growth_info are stored at the beginning of the backing array. -constexpr size_t ControlOffset(bool has_infoz, bool has_growth_info) { +constexpr size_t ControlOffset(bool has_infoz, size_t capacity) { if (ABSL_PREDICT_FALSE(has_infoz)) { - // We always allocate GrowthInfo for sampled tables to allow branchless - // access to infoz pointer. - return sizeof(HashtablezInfoHandle) + sizeof(GrowthInfo); + // We always allocate 8 bytes of growth info for sampled tables to allow + // branchless access to infoz pointer. + return sizeof(HashtablezInfoHandle) + sizeof(uint64_t); } - return has_growth_info ? sizeof(GrowthInfo) : 0; + return GrowthInfoSizeForCapacity(capacity); } // Returns the offset of the next item after `offset` that is aligned to `align` @@ -1034,8 +1115,7 @@ explicit RawHashSetLayout(size_t capacity, size_t slot_size, size_t slot_align, bool has_infoz, size_t blocked_element_count) - : control_offset_( - ControlOffset(has_infoz, HasGrowthInfoForCapacity(capacity))), + : control_offset_(ControlOffset(has_infoz, capacity)), generation_offset_(control_offset_ + NumControlBytes(capacity)), slot_offset_( AlignUpTo(generation_offset_ + NumGenerationBytes(), slot_align)), @@ -1129,11 +1209,8 @@ // Returns a reference to the GrowthInfo object stored immediately before // `control`. -inline GrowthInfo& GetGrowthInfoFromControl(ctrl_t* control) { - auto* gl_ptr = reinterpret_cast<GrowthInfo*>(control) - 1; - ABSL_SWISSTABLE_ASSERT( - reinterpret_cast<uintptr_t>(gl_ptr) % alignof(GrowthInfo) == 0); - return *gl_ptr; +inline GrowthInfoAccessor GetGrowthInfoFromControl(ctrl_t* control) { + return GrowthInfoAccessor(control); } // CommonFields hold the fields in raw_hash_set that do not depend @@ -1260,19 +1337,10 @@ } bool is_small() const { return inline_data_.is_small(); } - // The number of slots we can still fill without needing to rehash. - // This is stored in the heap allocation before the control bytes. - // TODO(b/289225379): experiment with moving growth_info back inline to - // increase room for SOO. - size_t growth_left() const { return growth_info().GetGrowthLeft(); } - - GrowthInfo& growth_info() { - ABSL_SWISSTABLE_ASSERT(HasGrowthInfoForCapacity(capacity())); + GrowthInfoAccessor growth_info() const { + ABSL_SWISSTABLE_ASSERT(GrowthInfoSizeForCapacity(capacity()) > 0); return GetGrowthInfoFromControl(control()); } - GrowthInfo growth_info() const { - return const_cast<CommonFields*>(this)->growth_info(); - } bool has_infoz() const { return inline_data_.has_infoz(); } void set_has_infoz() { @@ -1286,8 +1354,7 @@ reinterpret_cast<uintptr_t>(control()) % alignof(size_t) == 0); ABSL_SWISSTABLE_ASSERT(has_infoz()); return reinterpret_cast<HashtablezInfoHandle*>( - control() - ControlOffset(/*has_infoz=*/true, - HasGrowthInfoForCapacity(capacity()))); + control() - ControlOffset(/*has_infoz=*/true, capacity())); } HashtablezInfoHandle infoz() { @@ -1302,9 +1369,6 @@ if constexpr (!SwisstableGenerationsEnabled()) { return false; } - // As an optimization, we avoid calling ShouldRehashForBugDetection if we - // will end up rehashing anyways. - if (growth_left() == 0) return false; return CommonFieldsGenerationInfo:: should_rehash_for_bug_detection_on_insert(capacity()); } @@ -1329,7 +1393,11 @@ // Formula is valid because MaxCapacityWithBlockedElements is less than // group width. On erase for single group tables, we always increment the // growth left. - return CapacityToGrowth(cap) - size() - growth_left(); + ABSL_SWISSTABLE_ASSERT(cap <= + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + return CapacityToGrowth(cap) - size() - + // We can use lower bound here because capacity is small. + growth_info().GetGrowthLeftLowerBound(); } // The size of the backing array allocation. @@ -1725,9 +1793,12 @@ ctrl_t* new_ctrl, size_t new_capacity); -// growth_info (which is a size_t) is stored with the backing array. +// The HashtablezInfoHandle is stored before the control bytes. +// NOTE: The growth_info is also stored before the backing array, but it doesn't +// have alignment requirements. For small tables it is 1 byte, for larger tables +// it is 8 bytes, but we use unaligned load. constexpr size_t BackingArrayAlignment(size_t align_of_slot) { - return (std::max)(align_of_slot, alignof(GrowthInfo)); + return (std::max)(align_of_slot, alignof(HashtablezInfoHandle)); } // Iterates over all full slots and calls `cb(const ctrl_t*, void*)`. @@ -3737,26 +3808,7 @@ private: friend struct RawHashSetTestOnlyAccess; - // The number of slots we can still fill without needing to rehash. - // - // This is stored separately due to tombstones: we do not include tombstones - // in the growth capacity, because we'd like to rehash when the table is - // otherwise filled with tombstones: otherwise, probe sequences might get - // unacceptably long without triggering a rehash. Callers can also force a - // rehash via the standard `rehash(0)`, which will recompute this value as a - // side-effect. - // - // See `CapacityToGrowth()`. - size_t growth_left() const { - return common().growth_left(); - } - - GrowthInfo& growth_info() { - return common().growth_info(); - } - GrowthInfo growth_info() const { - return common().growth_info(); - } + GrowthInfoAccessor growth_info() const { return common().growth_info(); } // Prefetch the heap-allocated memory region to resolve potential TLB and // cache misses. This is intended to overlap with execution of calculating the
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 59492ab..fbc33c6 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -105,129 +105,420 @@ // Convenience function to static cast to ctrl_t. ctrl_t CtrlT(int i) { return static_cast<ctrl_t>(i); } -// Enables sampling with 1 percent sampling rate and -// resets the rate counter for the current thread. -void SetSamplingRateTo1Percent() { - SetHashtablezEnabled(true); - SetHashtablezSampleParameter(100); // Sample ~1% of tables. - // Reset rate counter for the current thread. - TestOnlyRefreshSamplingStateForCurrentThread(); +TEST(RawHashSetLayout, SmallCapacity) { + { + SCOPED_TRACE("capacity=1 no alignment after generation"); + constexpr size_t kSlotSize = 1; + RawHashSetLayout layout(1, kSlotSize, /*slot_align=*/1, + /*has_infoz=*/false, /*blocked_element_count=*/0); + EXPECT_EQ(layout.control_offset(), 0); + EXPECT_EQ(layout.slot_offset(), NumGenerationBytes()); + EXPECT_EQ(layout.alloc_size(), NumGenerationBytes() + kSlotSize); + } + { + SCOPED_TRACE("capacity=1 with alignment after generation"); + constexpr size_t kSlotSize = 8; + constexpr size_t kAlignment = 4; + RawHashSetLayout layout(1, kSlotSize, kAlignment, + /*has_infoz=*/false, /*blocked_element_count=*/0); + EXPECT_EQ(layout.control_offset(), 0); + EXPECT_EQ(layout.slot_offset(), NumGenerationBytes() == 0 ? 0 : kAlignment); + EXPECT_EQ(layout.alloc_size(), layout.slot_offset() + kSlotSize); + } } -// Disables sampling and resets the rate counter for the current thread. -void DisableSampling() { - SetHashtablezEnabled(false); - SetHashtablezSampleParameter(1 << 16); - // Reset rate counter for the current thread. - TestOnlyRefreshSamplingStateForCurrentThread(); +void VerifyMiddleSizeTableLayout(size_t capacity, size_t slot_size, + size_t slot_align, bool has_infoz, + size_t blocked_element_count, + size_t padding = 0) { + SCOPED_TRACE(testing::Message() + << "capacity: " << capacity << " slot_size: " << slot_size + << " slot_align: " << slot_align << " has_infoz: " << has_infoz + << " blocked_element_count: " << blocked_element_count + << " padding: " << padding); + ASSERT_GT(capacity, 1); + ASSERT_LE(capacity, GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, + blocked_element_count); + EXPECT_EQ(layout.control_offset(), 1); // 1 byte for growth_info + size_t expected_slot_offset = + capacity + NumClonedBytes() + 1 + /*growth*/ 1 + NumGenerationBytes(); + EXPECT_LT(padding, slot_align); + EXPECT_EQ((expected_slot_offset + padding) % slot_align, 0); + expected_slot_offset += padding; + EXPECT_EQ(layout.slot_offset(), expected_slot_offset); + size_t allocated_values = capacity - blocked_element_count; + EXPECT_EQ(layout.alloc_size(), + expected_slot_offset + allocated_values * slot_size); } -TEST(GrowthInfoTest, GetGrowthLeft) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(5); - EXPECT_EQ(gi.GetGrowthLeft(), 5); - gi.OverwriteFullAsDeleted(); - EXPECT_EQ(gi.GetGrowthLeft(), 5); +TEST(RawHashSetLayout, MiddleSize) { + VerifyMiddleSizeTableLayout(/*capacity=*/3, /*slot_size=*/4, + /*slot_align=*/4, /*has_infoz=*/false, + /*blocked_element_count=*/1, + /*padding=*/NumGenerationBytes() == 0 ? 0 : 3); + VerifyMiddleSizeTableLayout(/*capacity=*/7, /*slot_size=*/4, + /*slot_align=*/4, /*has_infoz=*/false, + /*blocked_element_count=*/1, + /*padding=*/NumGenerationBytes() == 0 ? 0 : 3); + VerifyMiddleSizeTableLayout(/*capacity=*/127, /*slot_size=*/8, + /*slot_align=*/8, /*has_infoz=*/false, + /*blocked_element_count=*/3, + /*padding=*/NumGenerationBytes() == 0 ? 0 : 7); } -TEST(GrowthInfoTest, HasNoDeleted) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(5); - EXPECT_TRUE(gi.HasNoDeleted()); - gi.OverwriteFullAsDeleted(); - EXPECT_FALSE(gi.HasNoDeleted()); +#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) +TEST(RawHashSetLayout, SmallWithInfoZ) { + { + SCOPED_TRACE("capacity=1 no alignment after generation"); + RawHashSetLayout layout(1, /*slot_size=*/1, /*slot_align=*/1, + /*has_infoz=*/true, /*blocked_element_count=*/0); + EXPECT_EQ(layout.control_offset(), + // growth_info is always 8 bytes for sampled tables. + 8 + sizeof(HashtablezInfoHandle)); + EXPECT_EQ(layout.slot_offset(), + layout.control_offset() + NumGenerationBytes()); + EXPECT_EQ(layout.alloc_size(), layout.slot_offset() + 1); + } + { + constexpr size_t kSlotSize = 8; + constexpr size_t kAlignment = 8; + constexpr size_t kCapacity = 3; + RawHashSetLayout layout(kCapacity, /*slot_size=*/kSlotSize, + /*slot_align=*/kAlignment, + /*has_infoz=*/true, /*blocked_element_count=*/0); + EXPECT_EQ(layout.control_offset(), + // growth_info is always 8 bytes for sampled tables. + 8 + sizeof(HashtablezInfoHandle)); + size_t expected_slot_offset = + layout.control_offset() + kCapacity + NumClonedBytes() + 1 + + /*padding+generation*/ (sizeof(HashtablezInfoHandle) == 4 ? 1 : 5); + EXPECT_EQ(expected_slot_offset % kAlignment, 0); + EXPECT_EQ(layout.slot_offset(), expected_slot_offset); + EXPECT_EQ(layout.alloc_size(), + expected_slot_offset + kCapacity * kSlotSize); + } +} +#endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) + +void VerifyLargeTableLayout(size_t capacity, size_t slot_size, + size_t slot_align, bool has_infoz, + size_t blocked_element_count) { + SCOPED_TRACE(testing::Message() + << "capacity: " << capacity << " slot_size: " << slot_size + << " slot_align: " << slot_align << " has_infoz: " << has_infoz + << " blocked_element_count: " << blocked_element_count); + ASSERT_GT(capacity, GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, + blocked_element_count); + EXPECT_EQ(layout.control_offset(), + has_infoz ? 8 + sizeof(HashtablezInfoHandle) : 8); + size_t expected_slot_offset = layout.control_offset() + capacity + + NumClonedBytes() + 1 + /*padding+generation*/ 1; + EXPECT_EQ(expected_slot_offset % slot_align, 0); + EXPECT_EQ(layout.slot_offset(), expected_slot_offset); + EXPECT_EQ( + layout.alloc_size(), + expected_slot_offset + (capacity - blocked_element_count) * slot_size); +} + +TEST(RawHashSetLayout, Large) { + VerifyLargeTableLayout(/*capacity=*/255, /*slot_size=*/8, /*slot_align=*/8, + /*has_infoz=*/false, /*blocked_element_count=*/5); +#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) + VerifyLargeTableLayout(/*capacity=*/1023, /*slot_size=*/8, /*slot_align=*/8, + /*has_infoz=*/true, /*blocked_element_count=*/2); +#endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) +} + +class GrowthInfoAllocator { + public: + explicit GrowthInfoAllocator(size_t capacity) { + if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + SanitizerPoisonMemoryRegion(control_.data(), 7); + } + SanitizerPoisonMemoryRegion(control_.data() + 8, 1); + } + + GrowthInfoAccessor* operator->() { return &growth_info_; } + + private: + // We allocate on heap since ASAN fails to detect access to poisoned memory + // on stack. + std::vector<ctrl_t> control_ = + std::vector<ctrl_t>(9, /*garbage*/ ctrl_t::kSentinel); + GrowthInfoAccessor growth_info_ = GrowthInfoAccessor(control_.data() + 8); +}; + +TEST(GrowthInfoViewTest, GetGrowthLeft) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 5); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), 5); + growth_info->OverwriteFullAsDeleted(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 5); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), 5); +} + +TEST(GrowthInfoViewTest, HasNoDeleted) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + EXPECT_TRUE(growth_info->GetGrowthInfoLowerBound().HasNoDeleted()); + growth_info->OverwriteFullAsDeleted(); + EXPECT_FALSE(growth_info->GetGrowthInfoLowerBound().HasNoDeleted()); // After reinitialization we have no deleted slots. - gi.InitGrowthLeftNoDeleted(5); - EXPECT_TRUE(gi.HasNoDeleted()); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + EXPECT_TRUE(growth_info->GetGrowthInfoLowerBound().HasNoDeleted()); } -TEST(GrowthInfoTest, HasNoDeletedAndGrowthLeft) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(5); - EXPECT_TRUE(gi.HasNoDeletedAndGrowthLeft()); - gi.OverwriteFullAsDeleted(); - EXPECT_FALSE(gi.HasNoDeletedAndGrowthLeft()); - gi.InitGrowthLeftNoDeleted(0); - EXPECT_FALSE(gi.HasNoDeletedAndGrowthLeft()); - gi.OverwriteFullAsDeleted(); - EXPECT_FALSE(gi.HasNoDeletedAndGrowthLeft()); +TEST(GrowthInfoViewTest, HasNoDeletedAndGrowthLeft) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + EXPECT_TRUE( + growth_info->GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft()); + growth_info->OverwriteFullAsDeleted(); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft()); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/0, kCapacity); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft()); + growth_info->OverwriteFullAsDeleted(); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft()); // After reinitialization we have no deleted slots. - gi.InitGrowthLeftNoDeleted(5); - EXPECT_TRUE(gi.HasNoDeletedAndGrowthLeft()); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + EXPECT_TRUE( + growth_info->GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft()); } -TEST(GrowthInfoTest, HasNoGrowthLeftAndNoDeleted) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(1); - EXPECT_FALSE(gi.HasNoGrowthLeftAndNoDeleted()); - gi.OverwriteEmptyAsFull(); - EXPECT_TRUE(gi.HasNoGrowthLeftAndNoDeleted()); - gi.OverwriteFullAsDeleted(); - EXPECT_FALSE(gi.HasNoGrowthLeftAndNoDeleted()); - gi.OverwriteFullAsEmpty(); - EXPECT_FALSE(gi.HasNoGrowthLeftAndNoDeleted()); - gi.InitGrowthLeftNoDeleted(0); - EXPECT_TRUE(gi.HasNoGrowthLeftAndNoDeleted()); - gi.OverwriteFullAsEmpty(); - EXPECT_FALSE(gi.HasNoGrowthLeftAndNoDeleted()); +TEST(GrowthInfoViewTest, HasNoGrowthLeftAndNoDeleted) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/1, kCapacity); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndNoDeleted()); + growth_info->OverwriteEmptyAsFull(); + EXPECT_TRUE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndNoDeleted()); + growth_info->OverwriteFullAsDeleted(); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndNoDeleted()); + growth_info->OverwriteFullAsEmpty(); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndNoDeleted()); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/0, kCapacity); + EXPECT_TRUE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndNoDeleted()); + growth_info->OverwriteFullAsEmpty(); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndNoDeleted()); } -TEST(GrowthInfoTest, OverwriteFullAsEmpty) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(5); - gi.OverwriteFullAsEmpty(); - EXPECT_EQ(gi.GetGrowthLeft(), 6); - gi.OverwriteFullAsDeleted(); - EXPECT_EQ(gi.GetGrowthLeft(), 6); - gi.OverwriteFullAsEmpty(); - EXPECT_EQ(gi.GetGrowthLeft(), 7); - EXPECT_FALSE(gi.HasNoDeleted()); +TEST(GrowthInfoViewTest, OverwriteFullAsEmpty) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + growth_info->OverwriteFullAsEmpty(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 6); + growth_info->OverwriteFullAsDeleted(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 6); + growth_info->OverwriteFullAsEmpty(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 7); + EXPECT_FALSE(growth_info->GetGrowthInfoLowerBound().HasNoDeleted()); } -TEST(GrowthInfoTest, OverwriteEmptyAsFull) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(5); - gi.OverwriteEmptyAsFull(); - EXPECT_EQ(gi.GetGrowthLeft(), 4); - gi.OverwriteFullAsDeleted(); - EXPECT_EQ(gi.GetGrowthLeft(), 4); - gi.OverwriteEmptyAsFull(); - EXPECT_EQ(gi.GetGrowthLeft(), 3); - EXPECT_FALSE(gi.HasNoDeleted()); +TEST(GrowthInfoViewTest, OverwriteEmptyAsFull) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + growth_info->OverwriteEmptyAsFull(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 4); + growth_info->OverwriteFullAsDeleted(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 4); + growth_info->OverwriteEmptyAsFull(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 3); + EXPECT_FALSE(growth_info->GetGrowthInfoLowerBound().HasNoDeleted()); } -TEST(GrowthInfoTest, OverwriteControlAsFull) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(5); - gi.OverwriteControlAsFull(ctrl_t::kEmpty); - EXPECT_EQ(gi.GetGrowthLeft(), 4); - gi.OverwriteControlAsFull(ctrl_t::kDeleted); - EXPECT_EQ(gi.GetGrowthLeft(), 4); - gi.OverwriteFullAsDeleted(); - gi.OverwriteControlAsFull(ctrl_t::kDeleted); +TEST(GrowthInfoViewTest, OverwriteControlAsFull) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/5, kCapacity); + growth_info->OverwriteControlAsFull(ctrl_t::kEmpty); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 4); + growth_info->OverwriteControlAsFull(ctrl_t::kDeleted); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 4); + growth_info->OverwriteFullAsDeleted(); + growth_info->OverwriteControlAsFull(ctrl_t::kDeleted); // We do not count number of deleted, so the bit sticks till the next rehash. - EXPECT_FALSE(gi.HasNoDeletedAndGrowthLeft()); - EXPECT_FALSE(gi.HasNoDeleted()); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft()); + EXPECT_FALSE(growth_info->GetGrowthInfoLowerBound().HasNoDeleted()); } -TEST(GrowthInfoTest, HasNoGrowthLeftAssumingMayHaveDeleted) { - GrowthInfo gi; - gi.InitGrowthLeftNoDeleted(1); - gi.OverwriteFullAsDeleted(); - EXPECT_EQ(gi.GetGrowthLeft(), 1); - EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); - gi.OverwriteControlAsFull(ctrl_t::kDeleted); - EXPECT_EQ(gi.GetGrowthLeft(), 1); - EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); - gi.OverwriteFullAsEmpty(); - EXPECT_EQ(gi.GetGrowthLeft(), 2); - EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); - gi.OverwriteEmptyAsFull(); - EXPECT_EQ(gi.GetGrowthLeft(), 1); - EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); - gi.OverwriteEmptyAsFull(); - EXPECT_EQ(gi.GetGrowthLeft(), 0); - EXPECT_TRUE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); +TEST(GrowthInfoViewTest, HasNoGrowthLeftAndHaveDeleted) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/1, kCapacity); + growth_info->OverwriteFullAsDeleted(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 1); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndHaveDeleted()); + growth_info->OverwriteControlAsFull(ctrl_t::kDeleted); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 1); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndHaveDeleted()); + growth_info->OverwriteFullAsEmpty(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 2); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndHaveDeleted()); + growth_info->OverwriteEmptyAsFull(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 1); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndHaveDeleted()); + growth_info->OverwriteEmptyAsFull(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 0); + EXPECT_TRUE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndHaveDeleted()); +} + +TEST(GrowthInfoViewTest, HasNoGrowthLeftAndHaveDeletedReturnFalseIfNoDeleted) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/0, kCapacity); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasNoGrowthLeftAndHaveDeleted()); +} + +TEST(GrowthInfoViewTest, HasDeletedAndGrowthLeft) { + constexpr size_t kCapacity = 7; + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/1, kCapacity); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasDeletedAndGrowthLeft()); + growth_info->OverwriteFullAsDeleted(); + EXPECT_TRUE(growth_info->GetGrowthInfoLowerBound().HasDeletedAndGrowthLeft()); + growth_info->OverwriteEmptyAsFull(); + EXPECT_FALSE( + growth_info->GetGrowthInfoLowerBound().HasDeletedAndGrowthLeft()); +} + +TEST(GrowthInfoViewTest, BigCapacityGrowthOverflow) { + constexpr size_t kCapacity = 256; + for (bool has_deleted : {true, false}) { + SCOPED_TRACE(testing::Message() << "has_deleted: " << has_deleted); + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted( + /*growth_left=*/GrowthInfoLowerBound::kMaxGrowthLeftLowerBound - 1, + kCapacity); + if (has_deleted) { + growth_info->OverwriteFullAsDeleted(); + } + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound - 1); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound - 1); + EXPECT_EQ(growth_info->GetGrowthInfoLowerBound().HasNoDeleted(), + !has_deleted); + growth_info->OverwriteFullAsEmpty(); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + EXPECT_EQ(growth_info->GetGrowthInfoLowerBound().HasNoDeleted(), + !has_deleted); + for (size_t i = 1; i <= 10; ++i) { + growth_info->OverwriteFullAsEmpty(); + // LowerBound stayed the same, but total increased. + ASSERT_EQ(growth_info->GetGrowthLeftLowerBound(), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + ASSERT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound + i); + ASSERT_EQ(growth_info->GetGrowthInfoLowerBound().HasNoDeleted(), + !has_deleted); + } + } +} + +TEST(GrowthInfoViewTest, RebalanceOnInsert) { + constexpr size_t kCapacity = 512; + constexpr size_t kOrigGrowthLeft = 260; + for (bool has_deleted : {false, true}) { + SCOPED_TRACE(testing::Message() << "has_deleted: " << has_deleted); + GrowthInfoAllocator growth_info(kCapacity); + growth_info->InitGrowthLeftNoDeleted(/*growth_left=*/kOrigGrowthLeft, + kCapacity); + if (has_deleted) { + growth_info->OverwriteFullAsDeleted(); + } + + auto has_no_growth = [has_deleted](const GrowthInfoLowerBound& info) { + return has_deleted ? info.HasNoGrowthLeftAndHaveDeleted() + : info.HasNoGrowthLeftAndNoDeleted(); + }; + + auto check_no_rebalance_if_growth_left_with_deleted = + [&](GrowthInfoAllocator& info) { + if (!has_deleted) return; + const size_t growth_left = info->GetGrowthLeftLowerBound(); + if (growth_left > 0) { + auto lower_bound = info->RebalanceGrowthLeftLowerBound(kCapacity); + EXPECT_EQ(lower_bound.GetGrowthLeft(), growth_left); + } + }; + + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), kOrigGrowthLeft); + EXPECT_EQ(growth_info->GetGrowthInfoLowerBound().HasNoDeleted(), + !has_deleted); + for (size_t i = 0; i < GrowthInfoLowerBound::kMaxGrowthLeftLowerBound; + ++i) { + growth_info->OverwriteEmptyAsFull(); + check_no_rebalance_if_growth_left_with_deleted(growth_info); + } + EXPECT_TRUE(has_no_growth(growth_info->GetGrowthInfoLowerBound())); + { + auto lower_bound = growth_info->RebalanceGrowthLeftLowerBound(kCapacity); + EXPECT_EQ(lower_bound.GetGrowthLeft(), 127); + EXPECT_EQ(lower_bound.HasNoDeleted(), !has_deleted); + } + + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 127); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), + kOrigGrowthLeft - 127); + for (size_t i = 0; i < 127; ++i) { + growth_info->OverwriteEmptyAsFull(); + check_no_rebalance_if_growth_left_with_deleted(growth_info); + } + EXPECT_TRUE(has_no_growth(growth_info->GetGrowthInfoLowerBound())); + constexpr size_t kSmallGrowthLeft = kOrigGrowthLeft - 127 * 2; + { + auto lower_bound = growth_info->RebalanceGrowthLeftLowerBound(kCapacity); + EXPECT_EQ(lower_bound.GetGrowthLeft(), kSmallGrowthLeft); + EXPECT_EQ(lower_bound.HasNoDeleted(), !has_deleted); + } + EXPECT_FALSE(has_no_growth(growth_info->GetGrowthInfoLowerBound())); + + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), kSmallGrowthLeft); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), kSmallGrowthLeft); + for (size_t i = 0; i < kSmallGrowthLeft; ++i) { + growth_info->OverwriteEmptyAsFull(); + check_no_rebalance_if_growth_left_with_deleted(growth_info); + } + EXPECT_TRUE(has_no_growth(growth_info->GetGrowthInfoLowerBound())); + { + auto lower_bound = growth_info->RebalanceGrowthLeftLowerBound(kCapacity); + EXPECT_EQ(lower_bound.GetGrowthLeft(), 0); + EXPECT_EQ(lower_bound.HasNoDeleted(), !has_deleted); + } + EXPECT_TRUE(has_no_growth(growth_info->GetGrowthInfoLowerBound())); + EXPECT_EQ(growth_info->GetGrowthLeftLowerBound(), 0); + EXPECT_EQ(growth_info->GetGrowthLeftTotalSlow(kCapacity), 0); + } } TEST(Util, OptimalMemcpySizeForSooSlotTransfer) { @@ -1378,6 +1669,8 @@ template <class TableType> class SmallTableResizeTest : public testing::Test {}; +// TODO: b/517078510 - Speed up compilation by reducing the number of +// types. using SmallTableTypes = ::testing::Types< IntTable, TransferableIntTable, SooIntTable, // int8 @@ -1452,6 +1745,23 @@ } } +// Enables sampling with 1 percent sampling rate and +// resets the rate counter for the current thread. +void SetSamplingRateTo1Percent() { + SetHashtablezEnabled(true); + SetHashtablezSampleParameter(100); // Sample ~1% of tables. + // Reset rate counter for the current thread. + TestOnlyRefreshSamplingStateForCurrentThread(); +} + +// Disables sampling and resets the rate counter for the current thread. +void DisableSampling() { + SetHashtablezEnabled(false); + SetHashtablezSampleParameter(1 << 16); + // Reset rate counter for the current thread. + TestOnlyRefreshSamplingStateForCurrentThread(); +} + TYPED_TEST(SmallTableResizeTest, ResizeReduceSmallTables) { DisableSampling(); for (size_t source_size = 0; source_size < 32; ++source_size) { @@ -2332,16 +2642,22 @@ for (int64_t i = 0; i < init_count; ++i) { t.insert(i); } - EXPECT_TRUE( - RawHashSetTestOnlyAccess::GetCommon(t).growth_info().HasNoDeleted()); + EXPECT_TRUE(RawHashSetTestOnlyAccess::GetCommon(t) + .growth_info() + .GetGrowthInfoLowerBound() + .HasNoDeleted()); t.erase(0); EXPECT_EQ(RawHashSetTestOnlyAccess::CountTombstones(t), 1); - EXPECT_FALSE( - RawHashSetTestOnlyAccess::GetCommon(t).growth_info().HasNoDeleted()); + EXPECT_FALSE(RawHashSetTestOnlyAccess::GetCommon(t) + .growth_info() + .GetGrowthInfoLowerBound() + .HasNoDeleted()); t.rehash(0); EXPECT_EQ(RawHashSetTestOnlyAccess::CountTombstones(t), 0); - EXPECT_TRUE( - RawHashSetTestOnlyAccess::GetCommon(t).growth_info().HasNoDeleted()); + EXPECT_TRUE(RawHashSetTestOnlyAccess::GetCommon(t) + .growth_info() + .GetGrowthInfoLowerBound() + .HasNoDeleted()); } TYPED_TEST(SooTest, Clear) { @@ -2497,6 +2813,25 @@ } } +TYPED_TEST(SooTest, CopyDifferentSizesWithReserve) { + for (size_t size = 0; size < 153; ++size) { + SCOPED_TRACE(absl::StrCat("size: ", size)); + TypeParam t; + t.reserve(size); + for (size_t i = 0; i < size; ++i) { + ASSERT_TRUE(t.insert(static_cast<int>(i)).second) << i; + } + auto t2 = t; + ASSERT_EQ(t2.size(), size); + for (size_t i = 0; i < size; ++i) { + ASSERT_TRUE(t2.contains(static_cast<int>(i))) << i; + } + ASSERT_TRUE(t2.insert(static_cast<int>(size)).second); + ASSERT_EQ(t2.size(), size + 1); + ASSERT_TRUE(t2.contains(static_cast<int>(size))); + } +} + TYPED_TEST(SooTest, CopyDifferentCapacities) { for (int cap = 1; cap < 100; cap = cap * 2 + 1) { TypeParam t; @@ -4698,8 +5033,7 @@ ASSERT_EQ(t.capacity(), cap); // Update growth info to force resize on the next insert. This way we avoid // having to insert many elements. - common.growth_info().OverwriteManyEmptyAsFull(CapacityToGrowth(cap) - - t.size()); + common.growth_info().InitGrowthLeftNoDeleted(/*growth_left=*/0, cap); t.insert(inserted_till++); ASSERT_EQ(t.capacity(), NextCapacity(cap)); for (uint8_t i = 0; i < inserted_till; ++i) {