Store GrowthInfoLowerBound in HashtableInlineData instead of before control bytes. This change moves the 8-bit GrowthInfoLowerBound from the control bytes allocation (where it was stored immediately before the control bytes) into the inline metadata (HashtableInlineData). Storing this information inline simplifies access and avoids pointer arithmetic. This is preparation for experiments with removal of cloned control bytes. Without cloned bytes we will not have one byte padding between control blocks and values. This reduces the size bitfield in HashtableInlineData by 8 bits to 41 (on 64 bit systems). PiperOrigin-RevId: 972096687 Change-Id: I461e39f4717b91cd3628752c4dfaa76d3a9579f9
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 3f9263c..38ee57b 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -282,58 +282,6 @@ "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 CommonFields::AssertNotDebugCapacityImpl() const { @@ -357,80 +305,6 @@ } } -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 static_cast<size_t>( - 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)); @@ -447,6 +321,71 @@ IterateOverFullSlotsImpl(c, slot_size, cb); } +void CommonFields::InitGrowthLeftNoDeleted(size_t growth_left, + size_t capacity) { + if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + inline_data_.set_growth_info_lower_bound( + GrowthInfoLowerBound(static_cast<uint8_t>(growth_left))); + } else { + uint64_t lower_bound = + (std::min)(uint64_t{growth_left}, + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + inline_data_.set_growth_info_lower_bound( + GrowthInfoLowerBound(static_cast<uint8_t>(lower_bound))); + SetGrowthInfoOverflow(growth_left - lower_bound); + } +} + +size_t CommonFields::GetGrowthLeftTotalSlow(size_t capacity) const { + size_t result = inline_data_.growth_info_lower_bound().GetGrowthLeft(); + if (capacity > GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + result += GetOverflowGrowthLeft(); + } + return result; +} + +void CommonFields::OverwriteFullAsEmpty() { + if (inline_data_.growth_info_lower_bound().GetGrowthLeft() < + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { + inline_data_.overwrite_full_as_empty_in_lower_bound(); + } else { + SetGrowthInfoOverflow(GetOverflowGrowthLeft() + 1); + } +} + +GrowthInfoLowerBound CommonFields::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(); + } +} + +ABSL_ATTRIBUTE_NOINLINE GrowthInfoLowerBound +CommonFields::RebalanceGrowthLeftLowerBoundLargeCapacity() { + uint64_t overflow_growth_left = GetOverflowGrowthLeft(); + uint64_t lower_bound_growth_left = GetGrowthLeftLowerBound(); + uint64_t overflow_to_lower_bound_size = + (std::min)(overflow_growth_left, + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound - + lower_bound_growth_left); + SetGrowthInfoOverflow(overflow_growth_left - overflow_to_lower_bound_size); + inline_data_.increment_growth_info_lower_bound(overflow_to_lower_bound_size); + auto result = GetGrowthInfoLowerBound(); + ABSL_SWISSTABLE_ASSERT(result.HasNoDeleted() == + GetGrowthInfoLowerBound().HasNoDeleted()); + ABSL_SWISSTABLE_ASSERT( + (result.GetGrowthLeft() > 0 || + (GetGrowthLeftLowerBound() + GetOverflowGrowthLeft() == 0)) && + "rebalance may return 0 only if we have absolutely no growth left"); + return result; +} + HashtablezInfoHandle CommonFields::infoz_ptr() const { // growth_info is stored before control bytes. ABSL_SWISSTABLE_ASSERT(has_infoz()); @@ -466,10 +405,10 @@ namespace { -void ResetGrowthLeft(GrowthInfoAccessor growth_info, size_t capacity, - size_t occupied_elements) { - growth_info.InitGrowthLeftNoDeleted( - CapacityToGrowth(capacity) - occupied_elements, capacity); +void ResetGrowthLeft(size_t capacity, size_t occupied_elements, + CommonFields& common) { + common.InitGrowthLeftNoDeleted(CapacityToGrowth(capacity) - occupied_elements, + capacity); } // Finds guaranteed to exists empty slot from the given position. @@ -696,8 +635,7 @@ } // Prepare insert for the new element. PrepareInsertCommon(common); - ResetGrowthLeft(common.growth_info(), capacity, - common.size() + blocked_element_count); + ResetGrowthLeft(capacity, common.size() + blocked_element_count, common); 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); @@ -874,11 +812,11 @@ if (WasNeverFull(c, index)) { SetCtrl(c, index, ctrl_t::kEmpty, slot_size); - c.growth_info().OverwriteFullAsEmpty(); + c.OverwriteFullAsEmpty(); return; } - c.growth_info().OverwriteFullAsDeleted(); + c.OverwriteFullAsDeleted(); SetCtrlInLargeTable(c, index, ctrl_t::kDeleted, slot_size); } @@ -891,7 +829,7 @@ c.set_size_to_zero(); ABSL_SWISSTABLE_ASSERT(c.capacity() > policy.soo_capacity()); ResetCtrl(c, policy.slot_size, blocked_element_count); - ResetGrowthLeft(c.growth_info(), c.capacity(), blocked_element_count); + ResetGrowthLeft(c.capacity(), blocked_element_count, c); ABSL_SWISSTABLE_ASSERT(c.blocked_element_count() == blocked_element_count); c.infoz().RecordStorageChanged(0, c.capacity()); } else { @@ -1043,8 +981,6 @@ infoz.RecordRehash(total_probe_length); infoz.RecordInsertMiss(hash, distance_from_desired); common.set_has_infoz(); - // TODO(b/413062340): we could potentially store infoz in place of the - // control pointer for the capacity 1 case. common.set_infoz(infoz); } @@ -1133,10 +1069,7 @@ common.generate_new_seed(has_infoz); ResetCtrl(common, slot_size, blocked_element_count); - if (GrowthInfoSizeForCapacity(new_capacity) > 0) { - ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, - blocked_element_count); - } + ResetGrowthLeft(new_capacity, blocked_element_count, common); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportResizeToInfoz(common, infoz, 0); @@ -1218,7 +1151,7 @@ InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots, has_infoz); - ResetGrowthLeft(common.growth_info(), new_capacity, kTableSize); + ResetGrowthLeft(new_capacity, kTableSize, common); if (has_infoz) { common.set_has_infoz(); common.set_infoz(infoz); @@ -1459,10 +1392,7 @@ // Initializes mirrored control bytes after // transfer_unprobed_elements_to_next_capacity. void InitializeMirroredControlBytes(ctrl_t* new_ctrl, size_t new_capacity) { - std::memcpy(new_ctrl + new_capacity, - // We own GrowthInfo just before control bytes. So it is ok - // to read one byte from it. - new_ctrl - 1, Group::kWidth); + std::memcpy(new_ctrl + new_capacity + 1, new_ctrl, Group::kWidth - 1); new_ctrl[new_capacity] = ctrl_t::kSentinel; } @@ -1764,8 +1694,7 @@ /*blocked_element_count=*/0); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); - GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2, - kNewCapacity); + common.InitGrowthLeftNoDeleted(kNewCapacity - 2, kNewCapacity); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportSingleGroupTableGrowthToInfoz(common, infoz, new_hash); @@ -1779,8 +1708,7 @@ CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_hash) { const size_t old_capacity = common.capacity(); - ABSL_SWISSTABLE_ASSERT( - common.growth_info().GetGrowthLeftTotalSlow(old_capacity) == 0); + ABSL_SWISSTABLE_ASSERT(common.GetGrowthLeftTotalSlow(old_capacity) == 0); ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(old_capacity)); ABSL_ASSUME(old_capacity > kMaxSmallCapacity); @@ -1838,8 +1766,7 @@ (*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align, has_infoz, old_blocked_element_count); PrepareInsertCommon(common); - ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, - common.size()); + ResetGrowthLeft(new_capacity, common.size(), common); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportGrowthToInfoz(common, infoz, new_hash, total_probe_length, @@ -1907,8 +1834,7 @@ void* RehashOrGrowToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_hash) { - ABSL_SWISSTABLE_ASSERT( - !common.growth_info().GetGrowthInfoLowerBound().HasNoDeleted()); + ABSL_SWISSTABLE_ASSERT(!common.GetGrowthInfoLowerBound().HasNoDeleted()); const size_t cap = common.capacity(); ABSL_ASSUME(cap > 0); // Do these calculations in 64-bit to avoid overflow. @@ -1968,11 +1894,10 @@ void* PrepareInsertLargeSlow(CommonFields& common, const PolicyFunctions& __restrict policy, size_t hash) { - GrowthInfoAccessor growth_info = common.growth_info(); const size_t cap = common.capacity(); ABSL_ASSUME(cap > kMaxSmallCapacity); GrowthInfoLowerBound growth_info_lower_bound = - growth_info.RebalanceGrowthLeftLowerBound(cap); + common.RebalanceGrowthLeftLowerBound(cap); if (ABSL_PREDICT_TRUE( growth_info_lower_bound.HasNoGrowthLeftAndNoDeleted())) { // Table without deleted slots (>95% cases) that needs to be resized. @@ -1989,7 +1914,7 @@ // rebalanced. FindInfo target = find_first_non_full(common, hash); PrepareInsertCommon(common); - growth_info.OverwriteControlAsFull(common.control()[target.offset]); + common.OverwriteControlAsFull(common.control()[target.offset]); SetCtrlInLargeTable(common, target.offset, H2(hash), policy.slot_size); common.infoz().RecordInsertMiss(hash, target.probe_length); return SlotAddress(common.slot_array(cap), target.offset, policy.slot_size); @@ -2010,7 +1935,7 @@ /*blocked_element_count=*/0, /*force_infoz=*/true); PrepareInsertCommon(common); - common.growth_info().OverwriteEmptyAsFull(); + common.OverwriteEmptyAsFull(); const size_t new_hash = get_hash(common.seed().seed()); SetCtrlInSingleGroupTable(common, SooSlotIndex(), H2(new_hash), policy.slot_size); @@ -2133,10 +2058,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 (GrowthInfoSizeForCapacity(new_capacity) > 0) { - ResetGrowthLeft(GetGrowthInfoFromControl(new_ctrl), new_capacity, - common.size()); - } + ResetGrowthLeft(new_capacity, common.size(), common); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportResizeToInfoz(common, infoz, total_probe_length); @@ -2171,8 +2093,7 @@ PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); - GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2, - kNewCapacity); + common.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())); @@ -2338,7 +2259,7 @@ common.maybe_increment_generation_on_insert(); }); common.increment_size(size); - ResetGrowthLeft(common.growth_info(), cap, size + blocked_element_count); + ResetGrowthLeft(cap, size + blocked_element_count, common); } void ReserveTableToFitNewSize(CommonFields& common, @@ -2357,9 +2278,8 @@ 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_info().GetGrowthLeftTotalSlow(cap); + IsSmallCapacity(cap) ? cap + : common.size() + common.GetGrowthLeftTotalSlow(cap); if (new_size <= max_size_before_growth) { return; } @@ -2373,16 +2293,15 @@ Group::NonIterableBitMaskType mask_empty, FindInfo target_group) { ABSL_SWISSTABLE_ASSERT(!common.is_small()); - 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.GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft())) { + !common.GetGrowthInfoLowerBound().HasNoDeletedAndGrowthLeft())) { return PrepareInsertLargeSlow(common, policy, hash); } PrepareInsertCommon(common); - growth_info.OverwriteEmptyAsFull(); + common.OverwriteEmptyAsFull(); const size_t cap = common.capacity(); ABSL_ASSUME(cap > kMaxSmallCapacity); target_group.offset += mask_empty.LowestBitSet(); @@ -2410,7 +2329,7 @@ // NOLINTNEXTLINE(misc-static-assert) ABSL_SWISSTABLE_ASSERT(SwisstableGenerationsEnabled()); const size_t cap = common.capacity(); - const size_t growth_left = common.growth_info().GetGrowthLeftTotalSlow(cap); + const size_t growth_left = common.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()) {
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index ad416cd..d02af7e 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -62,10 +62,7 @@ // 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; +// uint64_t growth_left_overflow; // optional // // Control bytes for the "real" slots. // ctrl_t ctrl[capacity]; // // Always `ctrl_t::kSentinel`. This is used by iterators to find when to @@ -204,6 +201,7 @@ #include "absl/base/internal/endian.h" #include "absl/base/internal/iterator_traits.h" #include "absl/base/internal/raw_logging.h" +#include "absl/base/internal/unaligned_access.h" #include "absl/base/macros.h" #include "absl/base/optimization.h" #include "absl/base/options.h" @@ -651,6 +649,96 @@ uint8_t tail_blocked_; }; +// Stored the information regarding number of slots we can still fill +// without needing to rehash. +// +// We want to ensure sufficient number of empty slots in the table in order +// to keep probe sequences relatively short. Empty slot in the probe group +// is required to stop probing. +// +// Tombstones (kDeleted slots) are not included in the growth capacity, +// because we'd like to rehash when the table is filled with tombstones and/or +// full slots. +// +// GrowthInfo also stores a bit that encodes whether table may have any +// deleted slots. +// Most of the tables (>95%) have no deleted slots, so some functions can +// be more efficient with this information. +// +// Callers can also force a rehash via the standard `rehash(0)`, +// which will recompute this value as a side-effect. +// +// See also `CapacityToGrowth()`. +// +// GrowthInfoLowerBound is stored as 8 bits in HashtableInlineData. +// For capacity > kMaxGrowthLeftLowerBound we additionally store 8 bytes +// at the beginning of the backing array. Storing GrowthInfoLowerBound in +// HashtableInlineData 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. GrowthInfo +// overflow for capacity > kMaxGrowthLeftLowerBound is stored as unaligned +// uint64_t. + +// 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: + static constexpr uint8_t kGrowthLeftMask = 0x7Fu; + static constexpr uint8_t kDeletedBit = 0x80u; + static constexpr uint64_t kMaxGrowthLeftLowerBound = 127; + static_assert(kMaxGrowthLeftLowerBound == kGrowthLeftMask); + + explicit constexpr GrowthInfoLowerBound(uint8_t growth_left) + : growth_left_(growth_left) {} + + // Returns the raw one byte encoded value of the GrowthInfoLowerBound. + uint8_t ToRawData() const { return 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. + 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. + constexpr bool HasNoGrowthLeftAndNoDeleted() const { + return growth_left_ == 0; + } + + // 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. + constexpr bool HasNoDeleted() const { + return (growth_left_ & kDeletedBit) == 0; + } + + // 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: + uint8_t growth_left_; +}; + // Capacity, size and also has additionally // 1) one bit that stores whether we have infoz. // 2) kBlockedElementsBitCount bits that stores number of blocked elements in @@ -668,6 +756,7 @@ public: static constexpr HashtableCapacityStorageMode kStorageMode = StorageMode; using HashtableCapacity = HashtableCapacityImpl<StorageMode>; + static constexpr size_t kGrowthInfoLowerBoundBitCount = 8; static constexpr size_t kBlockedElementBitCount = 3; static constexpr size_t kMaxBlockedElementCount = (uint64_t{1} << kBlockedElementBitCount) - 1; @@ -676,8 +765,9 @@ static constexpr size_t kCapacityBitStoredInDataCount = StorageMode == kCapacityByValue ? 0 : kCapacityBitCount; static constexpr size_t kSizeBitCount = - 64 - (kBlockedElementBitCount + kSeedBitCount + - /*has_infoz*/ 1 + kCapacityBitStoredInDataCount); + 64 - + (kBlockedElementBitCount + kSeedBitCount + kGrowthInfoLowerBoundBitCount + + /*has_infoz*/ 1 + kCapacityBitStoredInDataCount); explicit HashtableInlineDataImpl(uninitialized_tag_t) {} explicit HashtableInlineDataImpl(HashtableCapacity capacity, @@ -758,11 +848,63 @@ } void set_blocked_element_count_to_zero() { data_ &= ~kBlockedElementMask; } + GrowthInfoLowerBound growth_info_lower_bound() const { + ABSL_SWISSTABLE_ASSERT(!is_small() && + "we do not track growth for small tables"); + return GrowthInfoLowerBound(static_cast<uint8_t>( + (data_ & kGrowthInfoLowerBoundMask) >> kGrowthInfoLowerBoundShift)); + } + + void set_growth_info_lower_bound( + GrowthInfoLowerBound growth_info_lower_bound) { + data_ = (data_ & ~kGrowthInfoLowerBoundMask) | + (uint64_t{growth_info_lower_bound.ToRawData()} + << kGrowthInfoLowerBoundShift); + } + + // Overwrites single empty slot with a full slot. + // Must be called when growth left lower bound is positive. + void overwrite_empty_as_full() { + ABSL_SWISSTABLE_ASSERT(growth_info_lower_bound().GetGrowthLeft() > 0); + data_ -= kGrowthInfoLowerBoundOne; + } + + // Overwrites single full slot with an empty slot. + // Must be called when growth left lower bound is less than + // kMaxGrowthLeftLowerBound. + void overwrite_full_as_empty_in_lower_bound() { + increment_growth_info_lower_bound(1); + } + + // Increments the growth left lower bound by the given increment. + // Must be called when the growth left lower bound + increment does not exceed + // kMaxGrowthLeftLowerBound. + void increment_growth_info_lower_bound(size_t increment) { + ABSL_SWISSTABLE_ASSERT(growth_info_lower_bound().GetGrowthLeft() + + increment <= + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + data_ += increment << kGrowthInfoLowerBoundShift; + } + + // Overwrites specified control element with full slot. + // Must be called when growth left lower bound is >= IsEmpty(ctrl). + void overwrite_control_as_full(ctrl_t ctrl) { + ABSL_SWISSTABLE_ASSERT(growth_info_lower_bound().GetGrowthLeft() >= + static_cast<size_t>(IsEmpty(ctrl))); + data_ -= static_cast<size_t>(IsEmpty(ctrl)) << kGrowthInfoLowerBoundShift; + } + + // Overwrites single full slot with a deleted slot. + void overwrite_full_as_deleted() { + data_ |= (GrowthInfoLowerBound::kDeletedBit << kGrowthInfoLowerBoundShift); + } + void set_no_seed_for_testing() { data_ &= ~kSeedMask; } private: // Bit layout of `data_` and `capacity_internal_` from MSB to LSB: - // (55/49 bits) : size + // (47/41 bits) : size + // (8 bits) : growth_info_lower_bound // (3 bits) : blocked_element_count // (1 bit) : has_infoz // (5 bits) : seed @@ -770,8 +912,7 @@ // We don't split these components of `data_` into separate bit field elements // because we get worse generated code that way. - static constexpr size_t kDataBitCount = - kSeedBitCount + 1 + kSizeBitCount + kBlockedElementBitCount; + static constexpr size_t kDataBitCount = 64 - kCapacityBitStoredInDataCount; static constexpr size_t kSizeShift = kDataBitCount - kSizeBitCount; static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift; static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1; @@ -781,6 +922,12 @@ static constexpr uint64_t kBlockedElementsShift = kSeedBitCount + 1; static constexpr uint64_t kBlockedElementMask = kMaxBlockedElementCount << kBlockedElementsShift; + static constexpr uint64_t kGrowthInfoLowerBoundShift = + kBlockedElementsShift + kBlockedElementBitCount; + static constexpr uint64_t kGrowthInfoLowerBoundOne = + uint64_t{1} << kGrowthInfoLowerBoundShift; + static constexpr uint64_t kGrowthInfoLowerBoundMask = + uint64_t{0xff} << kGrowthInfoLowerBoundShift; // For SOO tables, the seed is unused, and bit 0 is repurposed to track // whether the table has already queried should_sample_soo(). static constexpr uint64_t kSooHasTriedSamplingMask = 1; @@ -976,171 +1123,6 @@ using HashSetIteratorGenerationInfo = HashSetIteratorGenerationInfoDisabled; #endif -// Stored the information regarding number of slots we can still fill -// without needing to rehash. -// -// We want to ensure sufficient number of empty slots in the table in order -// to keep probe sequences relatively short. Empty slot in the probe group -// is required to stop probing. -// -// Tombstones (kDeleted slots) are not included in the growth capacity, -// because we'd like to rehash when the table is filled with tombstones and/or -// full slots. -// -// GrowthInfo also stores a bit that encodes whether table may have any -// deleted slots. -// Most of the tables (>95%) have no deleted slots, so some functions can -// be more efficient with this information. -// -// Callers can also force a rehash via the standard `rehash(0)`, -// which will recompute this value as a side-effect. -// -// See also `CapacityToGrowth()`. -// -// 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: - static constexpr uint8_t kGrowthLeftMask = 0x7Fu; - static constexpr uint8_t kDeletedBit = 0x80u; - static constexpr uint64_t kMaxGrowthLeftLowerBound = 127; - static_assert(kMaxGrowthLeftLowerBound == kGrowthLeftMask); - - 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. - 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. - constexpr bool HasNoGrowthLeftAndNoDeleted() const { - return growth_left_ == 0; - } - - // 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. - constexpr bool HasNoDeleted() const { - return (growth_left_ & kDeletedBit) == 0; - } - - // 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: - uint8_t growth_left_; -}; - -// 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 - - NumGenerationBytes()) {} - - // 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". // // This is the number of control bytes that are present both at the beginning @@ -1154,13 +1136,10 @@ } // Returns the size in bytes table with given capacity use to store GrowthInfo. -// Returns 0 for small tables that doesn't store GrowthInfo. +// Returns 0 for small tables that store GrowthInfo in the inline data. constexpr size_t GrowthInfoSizeForCapacity(size_t capacity) { - if (IsSmallCapacity(capacity)) { - return 0; - } return capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound - ? sizeof(uint8_t) + ? 0 : sizeof(uint64_t); } @@ -1274,12 +1253,6 @@ unsigned char soo_data[MaxSooSlotSize()]; }; -// Returns a reference to the GrowthInfo object stored immediately before -// `control`. -inline GrowthInfoAccessor GetGrowthInfoFromControl(ctrl_t* control) { - return GrowthInfoAccessor(control); -} - // CommonFields hold the fields in raw_hash_set that do not depend // on template parameters. This allows us to conveniently pass all // of this state to helper functions as a single argument. @@ -1409,11 +1382,48 @@ } bool is_small() const { return inline_data_.is_small(); } - GrowthInfoAccessor growth_info() const { - ABSL_SWISSTABLE_ASSERT(GrowthInfoSizeForCapacity(capacity()) > 0); - return GetGrowthInfoFromControl(control()); + // Returns the GrowthInfoLowerBound of the table. + // This value is used to determine the minimum number of elements that can be + // inserted into the table before a rehash is required. + GrowthInfoLowerBound GetGrowthInfoLowerBound() const { + return inline_data_.growth_info_lower_bound(); } + // Returns the number of growth left in the lower bound of the table. + size_t GetGrowthLeftLowerBound() const { + return inline_data_.growth_info_lower_bound().GetGrowthLeft(); + } + + // The number of slots we can still fill without needing to rehash. + // Hot code paths should try to work with GetGrowthLeftLowerBound() instead. + size_t GetGrowthLeftTotalSlow(size_t capacity) const; + + // 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); + + // Modifies the GrowthInfo to mark full element as deleted. + void OverwriteFullAsDeleted() { inline_data_.overwrite_full_as_deleted(); } + + // Modifies the GrowthInfo to mark empty element as full. + // Requires: GetGrowthLeftLowerBound() > 0. + void OverwriteEmptyAsFull() { inline_data_.overwrite_empty_as_full(); } + + // Modifies the control byte to mark the element as full. + // Requires: GetGrowthLeftLowerBound() > IsEmpty(ctrl). + void OverwriteControlAsFull(ctrl_t ctrl) { + inline_data_.overwrite_control_as_full(ctrl); + } + + // Modifies the GrowthInfo to mark full element as empty. + void OverwriteFullAsEmpty(); + + // 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); + bool has_infoz() const { return inline_data_.has_infoz(); } void set_has_infoz() { ABSL_SWISSTABLE_ASSERT(inline_data_.is_sampled_seed()); @@ -1509,6 +1519,26 @@ return (size_t{1} << HasInfozShift()) - 1; } + void* GrowthInfoOverflowAddress() const { + return reinterpret_cast<void*>( + reinterpret_cast<uintptr_t>(control()) - + /*growth_info_overflow_size=*/sizeof(uint64_t) - NumGenerationBytes()); + } + + size_t GetOverflowGrowthLeft() const { + ABSL_SWISSTABLE_ASSERT(capacity() > + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + return base_internal::UnalignedLoad64(GrowthInfoOverflowAddress()); + } + + void SetGrowthInfoOverflow(size_t overflow) { + ABSL_SWISSTABLE_ASSERT(capacity() > + GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); + base_internal::UnalignedStore64(GrowthInfoOverflowAddress(), overflow); + } + + GrowthInfoLowerBound RebalanceGrowthLeftLowerBoundLargeCapacity(); + // We can't assert that SOO is enabled because we don't have SooEnabled(), but // we assert what we can. void AssertInSooMode() const { @@ -2284,12 +2314,6 @@ constexpr static size_t kSeedShift = kIsDefaultHash ? 0 : HashtableInlineData::kCapacityBitStoredInDataCount; - // TODO(b/289225379): we could add extra SOO space inside raw_hash_set - // after CommonFields to allow inlining larger slot_types (e.g. std::string), - // but it's a bit complicated if we want to support incomplete mapped_type in - // flat_hash_map. We could potentially do this for flat_hash_set and for an - // allowlist of `mapped_type`s of flat_hash_map that includes e.g. arithmetic - // types, strings, cords, and pairs/tuples of allowlisted types. constexpr static bool SooEnabled() { return PolicyTraits::soo_enabled() && sizeof(slot_type) <= sizeof(HeapOrSoo) && @@ -3834,8 +3858,6 @@ private: friend struct RawHashSetTestOnlyAccess; - 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 // hash for a key.
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index ec5ec30..a37cf5b 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -158,8 +158,7 @@ ASSERT_LE(capacity, GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, blocked_element_count); - EXPECT_EQ(layout.control_offset(), - /*growth*/ 1 + padding + NumGenerationBytes()); + EXPECT_EQ(layout.control_offset(), padding + NumGenerationBytes()); size_t expected_slot_offset = layout.control_offset() + NumControlBytes(capacity); EXPECT_LT(padding, slot_align); @@ -172,17 +171,21 @@ TEST(RawHashSetLayout, MiddleSize) { VerifyMiddleSizeTableLayout(/*capacity=*/3, /*slot_size=*/4, + /*slot_align=*/1, /*has_infoz=*/false, + /*blocked_element_count=*/1, + /*padding=*/0); + VerifyMiddleSizeTableLayout(/*capacity=*/3, /*slot_size=*/4, /*slot_align=*/4, /*has_infoz=*/false, /*blocked_element_count=*/1, - /*padding=*/NumGenerationBytes() == 0 ? 0 : 3); + /*padding=*/NumGenerationBytes() == 0 ? 1 : 0); VerifyMiddleSizeTableLayout(/*capacity=*/7, /*slot_size=*/4, /*slot_align=*/4, /*has_infoz=*/false, /*blocked_element_count=*/1, - /*padding=*/NumGenerationBytes() == 0 ? 0 : 3); + /*padding=*/NumGenerationBytes() == 0 ? 1 : 0); VerifyMiddleSizeTableLayout(/*capacity=*/127, /*slot_size=*/8, /*slot_align=*/8, /*has_infoz=*/false, /*blocked_element_count=*/3, - /*padding=*/NumGenerationBytes() == 0 ? 0 : 7); + /*padding=*/NumGenerationBytes() == 0 ? 1 : 0); } #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) @@ -310,17 +313,22 @@ public: explicit GrowthInfoAllocator(size_t capacity) { if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { - SanitizerPoisonMemoryRegion(control_.data(), 7); + SanitizerPoisonMemoryRegion(control_.data(), 8); } SanitizerPoisonMemoryRegion(control_.data() + kControlStart, 1); if constexpr (NumGenerationBytes() > 0) { - SanitizerPoisonMemoryRegion( - control_.data() + kControlStart + NumGenerationBytes(), - NumGenerationBytes()); + SanitizerPoisonMemoryRegion(control_.data() + 8, NumGenerationBytes()); } + common_fields_.set_capacity(capacity); + common_fields_.set_control(control_.data() + kControlStart); } - GrowthInfoAccessor* operator->() { return &growth_info_; } + ~GrowthInfoAllocator() { + SanitizerUnpoisonMemoryRegion(control_.data(), control_.size()); + } + + CommonFields* operator->() { return &common_fields_; } + const CommonFields* operator->() const { return &common_fields_; } private: static constexpr size_t kControlStart = 8 + NumGenerationBytes(); @@ -328,8 +336,7 @@ // on stack. std::vector<ctrl_t> control_ = std::vector<ctrl_t>( 9 + NumGenerationBytes(), /*garbage*/ ctrl_t::kSentinel); - GrowthInfoAccessor growth_info_ = - GrowthInfoAccessor(control_.data() + kControlStart); + CommonFields common_fields_ = CommonFields(non_soo_tag_t{}); }; TEST(GrowthInfoViewTest, GetGrowthLeft) { @@ -489,7 +496,7 @@ } TEST(GrowthInfoViewTest, BigCapacityGrowthOverflow) { - constexpr size_t kCapacity = 256; + constexpr size_t kCapacity = 255; for (bool has_deleted : {true, false}) { SCOPED_TRACE(testing::Message() << "has_deleted: " << has_deleted); GrowthInfoAllocator growth_info(kCapacity); @@ -526,7 +533,7 @@ } TEST(GrowthInfoViewTest, RebalanceOnInsert) { - constexpr size_t kCapacity = 512; + constexpr size_t kCapacity = 511; constexpr size_t kOrigGrowthLeft = 260; for (bool has_deleted : {false, true}) { SCOPED_TRACE(testing::Message() << "has_deleted: " << has_deleted); @@ -835,7 +842,7 @@ EXPECT_EQ(data.size(), 5); constexpr size_t kHugeIncrement = - (size_t(1) << (sizeof(size_t) == 4 ? 31 : 42)); + (size_t(1) << (sizeof(size_t) == 4 ? 31 : 39)); data.increment_size(kHugeIncrement); EXPECT_EQ(data.size(), kHugeIncrement + 5); @@ -1643,7 +1650,6 @@ // We want to test codepath deciding whether to rehash in place or not. // For this we need to potentially have tombstone. EXPECT_FALSE(RawHashSetTestOnlyAccess::GetCommon(t) - .growth_info() .GetGrowthInfoLowerBound() .HasNoDeleted()); for (int64_t i = static_cast<int64_t>(Group::kWidth); @@ -3452,19 +3458,16 @@ t.insert(i); } 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() .GetGrowthInfoLowerBound() .HasNoDeleted()); t.rehash(0); EXPECT_EQ(RawHashSetTestOnlyAccess::CountTombstones(t), 0); EXPECT_TRUE(RawHashSetTestOnlyAccess::GetCommon(t) - .growth_info() .GetGrowthInfoLowerBound() .HasNoDeleted()); } @@ -5202,6 +5205,34 @@ } }; +// We use unaligned value to verify that no padding is accidentally used during +// growth. +class UnalignedInt32 { + public: + UnalignedInt32() = default; + UnalignedInt32(uint32_t x) { // NOLINT: implicit conversion + std::memcpy(x_, &x, sizeof(uint32_t)); + } + + bool operator==(UnalignedInt32 other) const { + return static_cast<uint32_t>(*this) == static_cast<uint32_t>(other); + } + bool operator==(uint32_t other) const { + return static_cast<uint32_t>(*this) == other; + } + operator uint32_t() const { // NOLINT: implicit conversion + uint32_t result; + std::memcpy(&result, x_, 4); + return result; + } + + private: + uint8_t x_[4]; +}; + +static_assert(sizeof(UnalignedInt32) == 4); +static_assert(alignof(UnalignedInt32) == 1); + // This test is imitating growth of a very big table and triggers all buffer // overflows. // We try to insert all elements into the first probe group. @@ -5226,7 +5257,7 @@ NextCapacity(ProbedItem8Bytes::kMaxNewCapacity); #endif - absl::flat_hash_set<uint32_t, ZeroHash> t(63); + absl::flat_hash_set<UnalignedInt32, ZeroHash> t(21); CommonFields& common = RawHashSetTestOnlyAccess::GetCommon(t); // Set 0 seed so that H1 is always 0. common.set_no_seed_for_testing(); @@ -5244,8 +5275,7 @@ ASSERT_EQ(t.capacity(), cap); // Block upto 100 elements to test that kMarkedForSlowTransfer elements do // not conflict with blocked elements. - for (size_t i = cap - 1, - growth_left = common.growth_info().GetGrowthLeftTotalSlow(cap), + for (size_t i = cap - 1, growth_left = common.GetGrowthLeftTotalSlow(cap), blocked = 0; i > cap / 2; --i) { if (common.control()[i] == ctrl_t::kEmpty && growth_left > 1) { @@ -5257,7 +5287,7 @@ } // Update growth info to force resize on the next insert. This way we avoid // having to insert many elements. - common.growth_info().InitGrowthLeftNoDeleted(/*growth_left=*/0, cap); + common.InitGrowthLeftNoDeleted(/*growth_left=*/0, cap); t.insert(inserted_till++); ASSERT_EQ(t.capacity(), NextCapacity(cap)); for (uint8_t i = 0; i < inserted_till; ++i) {