Share the slot transfer code between the cold paths that move elements to new positions in raw_hash_set.cc to reduce binary size. `DecodeAndInsertImpl` (three instantiations, one per probed item encoding), `ProcessProbedMarkedElements`, and `FindNewPositionsAndTransferSlots` all did the same thing for each element: find the first non-full slot in the probe sequence, set its control byte, unpoison it, and transfer the slot into it. Only the way the hash is obtained differed (decoded from the probed item vs. recomputed from the slot). Extract this into a single out-of-line `TransferSlotToNewPosition` that takes `h1` and `h2` and call it from all three loops. The control bytes are passed explicitly so that the function can also be used while `CommonFields` still stores the SOO data in place of the control pointer. All callers are cold (growth of the probed elements that did not fit into a group, rehash, and reserve). The type-erased code in `raw_hash_set.cc` shrinks by 762 bytes (-3.8%) in optimized builds. PiperOrigin-RevId: 1002630645
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 7792be0..fea8605 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -813,7 +813,6 @@ deps = [ ":common", ":common_policy_traits", - ":compressed_tuple", ":container_memory", ":hash_function_defaults", ":hash_policy_traits",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 0c07fed..4326b8c 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -815,7 +815,6 @@ absl::base absl::bits absl::common_policy_traits - absl::compressed_tuple absl::config absl::container_common absl::container_memory
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 70d00cf..05de26a 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -178,9 +178,8 @@ } } -FindInfo find_first_non_full_from_h1(const ctrl_t* ctrl, size_t h1, - HashtableCapacity capacity) { - const size_t cap = capacity.capacity(); +FindInfo find_first_non_full_from_h1(size_t cap, const ctrl_t* ctrl, + size_t h1) { auto seq = probe_h1(ProbeCapacity{cap}, h1); if (IsEmptyOrDeleted(ctrl[seq.offset()])) { return {seq.offset(), /*probe_length=*/0}; @@ -196,9 +195,8 @@ // // NOTE: this function must work with tables having both empty and deleted // slots in the same group. Such tables appear during `erase()`. -FindInfo find_first_non_full(const CommonFields& common, size_t hash) { - return find_first_non_full_from_h1(common.control(), H1(hash), - common.capacity_impl()); +FindInfo find_first_non_full(size_t cap, const ctrl_t* ctrl, size_t hash) { + return find_first_non_full_from_h1(cap, ctrl, H1(hash)); } // Same as `find_first_non_full`, but returns the mask corresponding to the @@ -518,65 +516,73 @@ // // Unlike setting it directly, this function will perform bounds checks and // mirror the value to the cloned tail if necessary. -inline void SetCtrlNoSanitizeImpl(const CommonFields& c, size_t i, ctrl_t h) { - ABSL_SWISSTABLE_ASSERT(i < c.capacity()); - ctrl_t* ctrl = c.control(); - const size_t cap = c.capacity(); +inline void SetCtrlNoSanitizeImpl(size_t cap, ctrl_t* ctrl, size_t i, + ctrl_t h) { + ABSL_SWISSTABLE_ASSERT(i < cap); + // Select the base pointer rather than the index so `ctrl + cap + 1` does not + // depend on `i`. When inlined, it can reuse `ctrl + cap` from `slot_array` + // and be hoisted out of loops. + ctrl_t* cloned_ctrl_base = i < NumClonedBytes() ? ctrl + cap + 1 : ctrl; ctrl[i] = h; - ctrl[i < NumClonedBytes() ? i + cap + 1 : i] = h; + cloned_ctrl_base[i] = h; } -inline void SetCtrl(const CommonFields& c, size_t i, ctrl_t h, - size_t slot_size) { +inline void SetCtrl(const CommonFields& c, size_t cap, ctrl_t* ctrl, size_t i, + ctrl_t h, size_t slot_size) { ABSL_SWISSTABLE_ASSERT(!c.is_small()); DoSanitizeOnSetCtrl(c, i, h, slot_size); - SetCtrlNoSanitizeImpl(c, i, h); + SetCtrlNoSanitizeImpl(cap, ctrl, i, h); } -// Overload for setting to an occupied `h2_t` rather than a special `ctrl_t`. -inline void SetCtrl(const CommonFields& c, size_t i, h2_t h, size_t slot_size) { - SetCtrl(c, i, static_cast<ctrl_t>(h), slot_size); + +inline void SetCtrl(const CommonFields& c, size_t cap, ctrl_t* ctrl, size_t i, + h2_t h, size_t slot_size) { + SetCtrl(c, cap, ctrl, i, static_cast<ctrl_t>(h), slot_size); } // Sets `ctrl[i]` to `ctrl_t::kSentinel`. // // Unlike setting it directly, this function will perform bounds checks and // mirror the value to the cloned tail if necessary. -inline void BlockCtrl(const CommonFields& c, size_t i) { - ABSL_SWISSTABLE_ASSERT(!c.is_small()); - SetCtrlNoSanitizeImpl(c, i, ctrl_t::kSentinel); +inline void BlockCtrl(size_t cap, ctrl_t* ctrl, size_t i) { + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(cap)); + SetCtrlNoSanitizeImpl(cap, ctrl, i, ctrl_t::kSentinel); } // Like SetCtrl, but in a single group table, we can save some operations when // setting the cloned control byte. -inline void SetCtrlInSingleGroupTable(const CommonFields& c, size_t i, ctrl_t h, +inline void SetCtrlInSingleGroupTable(const CommonFields& c, size_t cap, + ctrl_t* ctrl, size_t i, ctrl_t h, size_t slot_size) { - const size_t cap = c.capacity(); ABSL_SWISSTABLE_ASSERT(!c.is_small()); + ABSL_SWISSTABLE_ASSERT(cap == c.capacity()); + ABSL_SWISSTABLE_ASSERT(ctrl == c.control()); ABSL_SWISSTABLE_ASSERT(is_single_group(cap)); DoSanitizeOnSetCtrl(c, i, h, slot_size); - ctrl_t* ctrl = c.control(); ctrl[i] = h; ctrl[i + cap + 1] = h; } // Overload for setting to an occupied `h2_t` rather than a special `ctrl_t`. -inline void SetCtrlInSingleGroupTable(const CommonFields& c, size_t i, h2_t h, +inline void SetCtrlInSingleGroupTable(const CommonFields& c, size_t cap, + ctrl_t* ctrl, size_t i, h2_t h, size_t slot_size) { - SetCtrlInSingleGroupTable(c, i, static_cast<ctrl_t>(h), slot_size); + SetCtrlInSingleGroupTable(c, cap, ctrl, i, static_cast<ctrl_t>(h), slot_size); } -void BlockControlBytes(CommonFields& common, size_t blocked_element_count) { - const size_t capacity = common.capacity(); +void BlockControlBytes(size_t capacity, ctrl_t* ctrl, + size_t blocked_element_count) { + ABSL_ASSUME(blocked_element_count <= + HashtableInlineData::kMaxBlockedElementCount); while (blocked_element_count > 0) { - BlockCtrl(common, capacity - blocked_element_count); + BlockCtrl(capacity, ctrl, capacity - blocked_element_count); --blocked_element_count; } } void* DropDeletesWithoutResizeAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_hash) { + size_t new_hash, size_t capacity) { void* set = &common; - const size_t capacity = common.capacity(); + ABSL_SWISSTABLE_ASSERT(common.capacity() == capacity); ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity)); ABSL_SWISSTABLE_ASSERT(!is_single_group(capacity)); ABSL_ASSUME(capacity > kMaxSmallCapacity); @@ -601,7 +607,7 @@ // repeat procedure for current slot with moved from element (target) const size_t blocked_element_count = common.blocked_element_count(); ConvertDeletedToEmptyAndFullToDeleted(ctrl, capacity); - BlockControlBytes(common, blocked_element_count); + BlockControlBytes(capacity, ctrl, blocked_element_count); const void* hash_fn = policy.hash_fn(common); auto hasher = policy.hash_slot; auto transfer_n = policy.transfer_n; @@ -624,14 +630,14 @@ } if (!IsDeleted(ctrl[i])) continue; const size_t hash = (*hasher)(hash_fn, slot_ptr, common.seed().seed()); - const FindInfo target = find_first_non_full(common, hash); + const FindInfo target = find_first_non_full(capacity, ctrl, hash); const size_t new_i = target.offset; total_probe_length += target.probe_length; // Verify if the old and new i fall within the same group wrt the hash. // If they do, we don't need to move the object as it falls already in the // best probe we can. - const size_t probe_offset = probe(common, hash).offset(); + const size_t probe_offset = probe(ProbeCapacity{capacity}, hash).offset(); const h2_t h2 = H2(hash); const auto probe_index = [probe_offset, capacity](size_t pos) { return ((pos - probe_offset) & capacity) / Group::kWidth; @@ -639,7 +645,7 @@ // Element doesn't move. if (ABSL_PREDICT_TRUE(probe_index(new_i) == probe_index(i))) { - SetCtrl(common, i, h2, slot_size); + SetCtrl(common, capacity, ctrl, i, h2, slot_size); continue; } @@ -648,14 +654,14 @@ // Transfer element to the empty spot. // SetCtrl poisons/unpoisons the slots so we have to call it at the // right time. - SetCtrl(common, new_i, h2, slot_size); + SetCtrl(common, capacity, ctrl, new_i, h2, slot_size); (*transfer_n)(set, new_slot_ptr, slot_ptr, 1); - SetCtrl(common, i, ctrl_t::kEmpty, slot_size); + SetCtrl(common, capacity, ctrl, i, ctrl_t::kEmpty, slot_size); // Initialize or change empty space id. tmp_space_id = i; } else { ABSL_SWISSTABLE_ASSERT(IsDeleted(ctrl[new_i])); - SetCtrl(common, new_i, h2, slot_size); + SetCtrl(common, capacity, ctrl, new_i, h2, slot_size); // Until we are done rehashing, DELETED marks previously FULL slots. if (tmp_space_id == kUnknownId) { @@ -679,20 +685,20 @@ // Prepare insert for the new element. PrepareInsertCommon(common); ResetGrowthLeft(capacity, common.size() + blocked_element_count, common); - FindInfo find_info = find_first_non_full(common, new_hash); - SetCtrl(common, find_info.offset, H2(new_hash), slot_size); + FindInfo find_info = find_first_non_full(capacity, ctrl, new_hash); + SetCtrl(common, capacity, ctrl, find_info.offset, H2(new_hash), slot_size); common.infoz().RecordInsertMiss(new_hash, find_info.probe_length); common.infoz().RecordRehash(total_probe_length); return SlotAddress(slot_array, find_info.offset, slot_size); } -bool WasNeverFull(CommonFields& c, size_t index) { - if (is_single_group(c.capacity())) { +bool WasNeverFull(size_t capacity, ctrl_t* ctrl, size_t index) { + if (is_single_group(capacity)) { return true; } - const size_t index_before = (index - Group::kWidth) & c.capacity(); - const auto empty_after = Group(c.control() + index).MaskEmpty(); - const auto empty_before = Group(c.control() + index_before).MaskEmpty(); + const size_t index_before = (index - Group::kWidth) & capacity; + const auto empty_after = Group(ctrl + index).MaskEmpty(); + const auto empty_before = Group(ctrl + index_before).MaskEmpty(); // We count how many consecutive non empties we have to the right and to the // left of `it`. If the sum is >= kWidth then there is at least one probe @@ -707,12 +713,10 @@ // control bytes are kEmpty except for the kSentinel bytes. // If the table has blocked elements, last `blocked_element_count` are set to // kSentinel. -void ResetCtrl(CommonFields& common, size_t slot_size, - size_t blocked_element_count) { - ABSL_SWISSTABLE_ASSERT(IsCapacityValidForBlockedElements(common.capacity()) || +void ResetCtrl(size_t capacity, ctrl_t* ctrl, void* slot_array, + size_t slot_size, size_t blocked_element_count) { + ABSL_SWISSTABLE_ASSERT(IsCapacityValidForBlockedElements(capacity) || blocked_element_count == 0); - const size_t capacity = common.capacity(); - ctrl_t* ctrl = common.control(); static constexpr size_t kTwoGroupCapacity = 2 * Group::kWidth - 1; if (ABSL_PREDICT_TRUE(capacity <= kTwoGroupCapacity)) { if (IsSmallCapacity(capacity)) return; @@ -728,9 +732,9 @@ capacity + 1 + NumClonedBytes()); } ctrl[capacity] = ctrl_t::kSentinel; - SanitizerPoisonMemoryRegion(common.slot_array(capacity), + SanitizerPoisonMemoryRegion(slot_array, slot_size * (capacity - blocked_element_count)); - BlockControlBytes(common, blocked_element_count); + BlockControlBytes(capacity, ctrl, blocked_element_count); } // Initializes control bytes for growing from capacity 1 to 3. @@ -881,14 +885,16 @@ c.decrement_size(); c.infoz().RecordErase(); - if (WasNeverFull(c, index)) { - SetCtrl(c, index, ctrl_t::kEmpty, slot_size); + const size_t cap = c.capacity(); + ctrl_t* ctrl = c.control(); + if (WasNeverFull(cap, ctrl, index)) { + SetCtrl(c, cap, ctrl, index, ctrl_t::kEmpty, slot_size); c.OverwriteFullAsEmpty(); return; } c.OverwriteFullAsDeleted(); - SetCtrl(c, index, ctrl_t::kDeleted, slot_size); + SetCtrl(c, cap, ctrl, index, ctrl_t::kDeleted, slot_size); } void ClearBackingArray(CommonFields& c, @@ -898,9 +904,12 @@ if (reuse) { const size_t blocked_element_count = c.blocked_element_count(); c.set_size_to_zero(); - ABSL_SWISSTABLE_ASSERT(c.capacity() > policy.soo_capacity()); - ResetCtrl(c, policy.slot_size, blocked_element_count); - ResetGrowthLeft(c.capacity(), blocked_element_count, c); + size_t cap = c.capacity(); + ctrl_t* ctrl = c.control(); + void* slot_array = c.slot_array(cap); + ABSL_SWISSTABLE_ASSERT(cap > policy.soo_capacity()); + ResetCtrl(cap, ctrl, slot_array, policy.slot_size, blocked_element_count); + ResetGrowthLeft(cap, blocked_element_count, c); ABSL_SWISSTABLE_ASSERT(c.blocked_element_count() == blocked_element_count); c.infoz().RecordStorageChanged(0, c.capacity()); } else { @@ -1012,32 +1021,58 @@ namespace { -// Iterates over full slots in old table, finds new positions for them and -// transfers the slots. +// Finds the first non-full slot in the probe sequence of `h1` in the large +// table with control bytes `new_ctrl`, marks it as full with `h2` and transfers +// `src_slot` into it. `new_ctrl` is passed explicitly rather than read from `c` +// so that the function can be used while `c` still stores SOO data in place of +// the control pointer. +// This function is shared by the cold paths that move elements to new +// positions (growth of probed elements, rehash and reserve). +// Returns the probe length. +ABSL_ATTRIBUTE_NOINLINE size_t TransferSlotToNewPosition( + CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* new_ctrl, + void* src_slot, size_t h1, h2_t h2) { + const size_t new_capacity = c.capacity(); + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(new_capacity)); + const FindInfo target = + find_first_non_full_from_h1(new_capacity, new_ctrl, h1); + ABSL_SWISSTABLE_ASSERT(IsEmptyOrDeleted(new_ctrl[target.offset])); + SetCtrlNoSanitizeImpl(new_capacity, new_ctrl, target.offset, + static_cast<ctrl_t>(h2)); + const size_t slot_size = policy.slot_size; + void* dst_slot = + SlotAddress(new_ctrl + NumControlBytesForLargeTable(new_capacity), + target.offset, slot_size); + SanitizerUnpoisonMemoryRegion(dst_slot, slot_size); + policy.transfer_n(&c, dst_slot, src_slot, 1); + return target.probe_length; +} + +// Iterates over full slots in the old table, finds new positions for them and +// transfers the slots to the new backing array (`new_ctrl`, `new_slots`). +// `common` must already have the new capacity and the new seed. `new_ctrl` and +// `new_slots` are passed explicitly rather than read from `common` so that the +// old slot may still be stored inline in `common` (full SOO table). // This function is used for reserving or rehashing non-empty tables. // This use case is rare so the function is type erased. // Returns the total probe length. size_t FindNewPositionsAndTransferSlots( CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots, size_t old_capacity) { - void* new_slots = common.is_small() ? common.single_non_soo_slot() - : common.slot_array(common.capacity()); + const ctrl_t* old_ctrl, void* old_slots, size_t old_capacity, + ctrl_t* new_ctrl, void* new_slots) { const void* hash_fn = policy.hash_fn(common); const size_t slot_size = policy.slot_size; const size_t seed = common.seed().seed(); + const size_t new_capacity = common.capacity(); - const auto insert_slot = [&](void* slot) { - size_t hash = policy.hash_slot(hash_fn, slot, seed); - FindInfo target; - if (common.is_small()) { - target = FindInfo{0, 0}; - } else { - target = find_first_non_full(common, hash); - SetCtrl(common, target.offset, H2(hash), slot_size); + const auto insert_slot = [&](void* slot) -> size_t { + if (IsSmallCapacity(new_capacity)) { + policy.transfer_n(&common, new_slots, slot, 1); + return 0; } - policy.transfer_n(&common, SlotAddress(new_slots, target.offset, slot_size), - slot, 1); - return target.probe_length; + const size_t hash = policy.hash_slot(hash_fn, slot, seed); + return TransferSlotToNewPosition(common, policy, new_ctrl, slot, H1(hash), + H2(hash)); }; if (IsSmallCapacity(old_capacity)) { if (common.size() == 1) insert_slot(old_slots); @@ -1130,11 +1165,17 @@ total_probe_length, distance_from_desired); } +// Passed as `total_probe_length` to `ReportResizeToInfoz` when the resize must +// not be reported as a rehash. +constexpr size_t kNoRehash = ~size_t{}; + ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportResizeToInfoz( CommonFields& common, HashtablezInfoHandle infoz, size_t total_probe_length) { infoz.RecordStorageChanged(common.size(), common.capacity()); - infoz.RecordRehash(total_probe_length); + if (total_probe_length != kNoRehash) { + infoz.RecordRehash(total_probe_length); + } common.set_has_infoz(); common.set_infoz(infoz); } @@ -1159,10 +1200,8 @@ BackingArrayPtrs AllocBackingArray(CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_capacity, bool has_infoz, - void* alloc, size_t blocked_element_count) { - RawHashSetLayout layout(new_capacity, policy.slot_size, policy.slot_align, - has_infoz, blocked_element_count); + const RawHashSetLayout& layout, + void* alloc) { // Perform a direct call in the common case to allow for profile-guided // heap optimization (PGHO) to understand which allocation function is used. constexpr size_t kDefaultAlignment = BackingArrayAlignment(alignof(size_t)); @@ -1182,6 +1221,17 @@ mem + layout.slot_offset()}; } +BackingArrayPtrs AllocBackingArray(CommonFields& common, + const PolicyFunctions& __restrict policy, + size_t new_capacity, bool has_infoz, + void* alloc, size_t blocked_element_count) { + return AllocBackingArray( + common, policy, + RawHashSetLayout(new_capacity, policy.slot_size, policy.slot_align, + has_infoz, blocked_element_count), + alloc); +} + void ResizeEmptyNonAllocatedTableImpl(CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_capacity, @@ -1195,16 +1245,17 @@ const size_t slot_size = policy.slot_size; const bool has_infoz = policy.is_hashtablez_enabled && (force_infoz || ShouldSampleNextTable()); - void* alloc = policy.get_char_alloc(common); common.set_capacity(new_capacity); common.init_blocked_element_count(blocked_element_count); - const auto [new_ctrl, new_slots] = AllocBackingArray( - common, policy, new_capacity, has_infoz, alloc, blocked_element_count); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, has_infoz, + policy.get_char_alloc(common), blocked_element_count); common.set_control(new_ctrl); common.generate_new_seed(has_infoz); - ResetCtrl(common, slot_size, blocked_element_count); + ResetCtrl(new_capacity, new_ctrl, new_slots, slot_size, + blocked_element_count); ResetGrowthLeft(new_capacity, blocked_element_count, common); if (ABSL_PREDICT_FALSE(has_infoz)) { @@ -1212,38 +1263,6 @@ } } -// If the table was SOO, initializes new control bytes and transfers slot. -// After transferring the slot, sets control and slots in CommonFields. -// It is rare to resize an SOO table with one element to a large size. -// Requires: `c` contains SOO data. -void InsertOldSooSlotAndInitializeControlBytes( - CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* new_ctrl, - void* new_slots, bool has_infoz) { - ABSL_SWISSTABLE_ASSERT(c.size() == policy.soo_capacity()); - ABSL_SWISSTABLE_ASSERT(policy.soo_enabled); - const size_t new_capacity = c.capacity(); - - c.generate_new_seed(has_infoz); - - const size_t soo_slot_hash = - policy.hash_slot(policy.hash_fn(c), c.soo_data(), c.seed().seed()); - size_t offset = probe(ProbeCapacity{new_capacity}, soo_slot_hash).offset(); - offset = offset == new_capacity ? 0 : offset; - SanitizerPoisonMemoryRegion(new_slots, policy.slot_size * new_capacity); - void* target_slot = SlotAddress(new_slots, offset, policy.slot_size); - SanitizerUnpoisonMemoryRegion(target_slot, policy.slot_size); - policy.transfer_n(&c, target_slot, c.soo_data(), 1); - c.set_control(new_ctrl); - ResetCtrl(c, policy.slot_size, /*blocked_element_count=*/0); - SetCtrl(c, offset, H2(soo_slot_hash), policy.slot_size); -} - -enum class ResizeFullSooTableSamplingMode { - kNoSampling, - // Force sampling. If the table was still not sampled, do not resize. - kForceSampleNoResizeIfUnsampled, -}; - void AssertSoo([[maybe_unused]] CommonFields& common, [[maybe_unused]] const PolicyFunctions& __restrict policy) { ABSL_SWISSTABLE_ASSERT(policy.soo_enabled); @@ -1255,44 +1274,73 @@ ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); } -void ResizeFullSooTable(CommonFields& common, - const PolicyFunctions& __restrict policy, - size_t new_capacity, - ResizeFullSooTableSamplingMode sampling_mode) { - AssertFullSoo(common, policy); - const size_t slot_size = policy.slot_size; - void* alloc = policy.get_char_alloc(common); - constexpr size_t kTableSize = 1; - +// Resizes an allocated table or a full SOO table to `new_capacity`, changes the +// table seed and transfers all elements to the new backing array. +// Allocated tables keep their infoz. If `force_sample_soo`, the table must be a +// full SOO table and it is forced to be sampled. If the table was still not +// sampled, it is not resized. +// It is rare to resize a table that is not empty or to resize an SOO table to +// a large size, so this function is shared by all such cases and is kept out of +// line. +// Requires: +// 1. `new_capacity > policy.soo_capacity()`. +// 2. `common.capacity() > policy.soo_capacity()` OR `!common.empty()`. +ABSL_ATTRIBUTE_NOINLINE void ResizeTableWithSeedChangeImpl( + CommonFields& common, const PolicyFunctions& __restrict policy, + size_t new_capacity, bool force_sample_soo) { + ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); + ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); + const size_t old_capacity = common.capacity(); + const bool was_soo = old_capacity == policy.soo_capacity(); + ABSL_SWISSTABLE_ASSERT(!was_soo || common.size() == policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(!force_sample_soo || was_soo); + // Note: `has_infoz` determines the layout of the backing array and may be set + // even if `infoz` is not sampled (see `ReportResizeToInfozAndForceSample`). HashtablezInfoHandle infoz; - bool has_infoz = false; - if (sampling_mode == - ResizeFullSooTableSamplingMode::kForceSampleNoResizeIfUnsampled) { - if (policy.is_hashtablez_enabled) { - infoz = ForcedTrySample(slot_size, policy.key_size, policy.value_size, - policy.soo_capacity()); - } - + bool has_infoz; + if (force_sample_soo) { + if (!policy.is_hashtablez_enabled) return; + infoz = ForcedTrySample(policy.slot_size, policy.key_size, + policy.value_size, policy.soo_capacity()); // If the table was not sampled, do not resize. if (!infoz.IsSampled()) return; has_infoz = true; + } else { + has_infoz = common.has_infoz(); + infoz = common.infoz(); } + // `old_ctrl` is not used for SOO tables. + ctrl_t* const old_ctrl = was_soo ? nullptr : common.control(); + void* const old_slots = was_soo ? common.soo_data() + : (IsSmallCapacity(old_capacity) + ? common.single_non_soo_slot() + : common.slot_array(old_capacity)); + const size_t old_blocked_element_count = common.blocked_element_count(); + const size_t slot_size = policy.slot_size; common.set_capacity(new_capacity); - - // We do not set control and slots in CommonFields yet to avoid overriding + common.set_blocked_element_count_to_zero(); + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, policy, new_capacity, has_infoz, policy.get_char_alloc(common), + /*blocked_element_count=*/0); + common.generate_new_seed(has_infoz); + ResetCtrl(new_capacity, new_ctrl, new_slots, slot_size, + /*blocked_element_count=*/0); + const size_t total_probe_length = FindNewPositionsAndTransferSlots( + common, policy, old_ctrl, old_slots, old_capacity, new_ctrl, new_slots); + // Control is set in `common` only after the transfer to avoid overriding the // SOO data. - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, - /*blocked_element_count=*/0); - - InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots, - has_infoz); - ResetGrowthLeft(new_capacity, kTableSize, common); - if (has_infoz) { - common.set_has_infoz(); - common.set_infoz(infoz); - infoz.RecordStorageChanged(kTableSize, new_capacity); + common.set_control(new_ctrl); + if (!was_soo) { + DeallocBackingArrayImpl(policy.get_char_alloc(common), old_capacity, + old_ctrl, slot_size, policy.slot_align, has_infoz, + old_blocked_element_count, policy.dealloc); + } + ResetGrowthLeft(new_capacity, common.size(), common); + if (ABSL_PREDICT_FALSE(has_infoz)) { + // Forced sampling of a full SOO table is not reported as a rehash. + ReportResizeToInfoz(common, infoz, + force_sample_soo ? kNoRehash : total_probe_length); } } @@ -1453,29 +1501,15 @@ CommonFields& c, const PolicyFunctions& __restrict policy, const ProbedItem* start, const ProbedItem* end, void* old_slots) { ABSL_SWISSTABLE_ASSERT(!c.is_small()); - const HashtableCapacity new_capacity = c.capacity_impl(); - - void* new_slots = c.slot_array(new_capacity.capacity()); ctrl_t* new_ctrl = c.control(); - size_t total_probe_length = 0; - const size_t slot_size = policy.slot_size; - auto transfer_n = policy.transfer_n; - + size_t total_probe_length = 0; for (; start < end; ++start) { - const FindInfo target = find_first_non_full_from_h1( - new_ctrl, static_cast<size_t>(start->h1), new_capacity); - total_probe_length += target.probe_length; const size_t old_index = static_cast<size_t>(start->source_offset); - const size_t new_i = target.offset; - ABSL_SWISSTABLE_ASSERT(old_index < new_capacity.capacity() / 2); - ABSL_SWISSTABLE_ASSERT(new_i < new_capacity.capacity()); - ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[new_i])); - void* src_slot = SlotAddress(old_slots, old_index, slot_size); - void* dst_slot = SlotAddress(new_slots, new_i, slot_size); - SanitizerUnpoisonMemoryRegion(dst_slot, slot_size); - transfer_n(&c, dst_slot, src_slot, 1); - SetCtrl(c, new_i, static_cast<h2_t>(start->h2), slot_size); + ABSL_SWISSTABLE_ASSERT(old_index < c.capacity() / 2); + total_probe_length += TransferSlotToNewPosition( + c, policy, new_ctrl, SlotAddress(old_slots, old_index, slot_size), + static_cast<size_t>(start->h1), static_cast<h2_t>(start->h2)); } return total_probe_length; } @@ -1491,14 +1525,11 @@ ABSL_ATTRIBUTE_NOINLINE size_t ProcessProbedMarkedElements( CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* old_ctrl, void* old_slots, size_t start) { - const size_t new_capacity = c.capacity(); - const size_t old_capacity = PreviousCapacity(new_capacity); + const size_t old_capacity = PreviousCapacity(c.capacity()); const size_t slot_size = policy.slot_size; - void* new_slots = c.slot_array(new_capacity); size_t total_probe_length = 0; const void* hash_fn = policy.hash_fn(c); auto hash_slot = policy.hash_slot; - auto transfer_n = policy.transfer_n; const size_t seed = c.seed().seed(); for (size_t old_index = start; old_index < old_capacity; ++old_index) { if (old_ctrl[old_index] != ctrl_t::kMarkedForSlowTransfer) { @@ -1506,12 +1537,8 @@ } void* src_slot = SlotAddress(old_slots, old_index, slot_size); const size_t hash = hash_slot(hash_fn, src_slot, seed); - const FindInfo target = find_first_non_full(c, hash); - total_probe_length += target.probe_length; - const size_t new_i = target.offset; - void* dst_slot = SlotAddress(new_slots, new_i, slot_size); - SetCtrl(c, new_i, H2(hash), slot_size); - transfer_n(&c, dst_slot, src_slot, 1); + total_probe_length += TransferSlotToNewPosition( + c, policy, c.control(), src_slot, H1(hash), H2(hash)); } return total_probe_length; } @@ -1551,8 +1578,73 @@ class ProbedItemEncoder { public: using ProbedItem = ProbedItemType; - explicit ProbedItemEncoder(ctrl_t* control) : control_(control) {} + ProbedItemEncoder(CommonFields& common, + const PolicyFunctions& __restrict policy, ctrl_t* control, + void* old_slots, size_t new_capacity) + : common_(common), + policy_(policy), + control_(control), + old_slots_(old_slots), + new_capacity_(new_capacity), + new_ctrl_(common.control()), + new_slots_(common.slot_array(new_capacity)) {} + // Transfers item to the first probe group if possible, otherwise encodes it + // into the best available location. + void EncodeProbedElement(size_t hash, size_t source_offset) { + size_t h1 = H1(hash); + const size_t new_capacity = new_capacity_; + const size_t old_capacity = PreviousCapacity(new_capacity); + ABSL_SWISSTABLE_ASSERT(((source_offset - h1) & old_capacity) >= + Group::kWidth); + // Try to insert element into the first probe group. + // new_ctrl is not yet fully initialized so we can't use regular search via + // find_first_non_full. + // + // We can search in the first probe group only if it is located in already + // initialized part of the table. + if (ABSL_PREDICT_TRUE((h1 & old_capacity) < source_offset)) { + ctrl_t* new_ctrl = new_ctrl_; + size_t offset = h1 & new_capacity; + Group new_g(new_ctrl + offset); + if (auto mask = new_g.MaskNonFull(); ABSL_PREDICT_TRUE(mask)) { + size_t new_index = offset + mask.LowestBitSet(); + ABSL_SWISSTABLE_ASSERT((new_index & old_capacity) <= source_offset); + ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[new_index])); + new_ctrl[new_index] = static_cast<ctrl_t>(H2(hash)); + const size_t slot_size = policy_.slot_size; + void* new_slot = SlotAddress(new_slots_, new_index, slot_size); + void* old_slot = SlotAddress(old_slots_, source_offset, slot_size); + SanitizerUnpoisonMemoryRegion(new_slot, slot_size); + policy_.transfer_n(&common_, new_slot, old_slot, 1); + SanitizerPoisonMemoryRegion(old_slot, slot_size); + return; + } + } + EncodeItem(ProbedItem(H2(hash), source_offset, h1)); + } + + // Decodes information about probed elements from all available sources. + // Finds new position for each element and transfers it to the new slots. + // Returns the total probe length. + size_t DecodeAndInsertToTable() const { + if (pos_ == buffer_) { + return 0; + } + if constexpr (kGuaranteedFitToBuffer) { + return DecodeAndInsertImpl(common_, policy_, buffer_, pos_, old_slots_); + } + size_t total_probe_length = DecodeAndInsertImpl( + common_, policy_, buffer_, + local_buffer_full_ ? buffer_ + kBufferSize : pos_, old_slots_); + if (!local_buffer_full_) { + return total_probe_length; + } + total_probe_length += DecodeAndInsertToTableOverflow(); + return total_probe_length; + } + + private: // Encode item into the best available location. void EncodeItem(ProbedItem item) { if (ABSL_PREDICT_FALSE(!kGuaranteedFitToBuffer && pos_ >= end_)) { @@ -1563,30 +1655,6 @@ ++pos_; } - // Decodes information about probed elements from all available sources. - // Finds new position for each element and transfers it to the new slots. - // Returns the total probe length. - size_t DecodeAndInsertToTable(CommonFields& common, - const PolicyFunctions& __restrict policy, - void* old_slots) const { - if (pos_ == buffer_) { - return 0; - } - if constexpr (kGuaranteedFitToBuffer) { - return DecodeAndInsertImpl(common, policy, buffer_, pos_, old_slots); - } - size_t total_probe_length = DecodeAndInsertImpl( - common, policy, buffer_, - local_buffer_full_ ? buffer_ + kBufferSize : pos_, old_slots); - if (!local_buffer_full_) { - return total_probe_length; - } - total_probe_length += - DecodeAndInsertToTableOverflow(common, policy, old_slots); - return total_probe_length; - } - - private: static ProbedItem* AlignToNextItem(void* ptr) { return reinterpret_cast<ProbedItem*>(AlignUpTo( reinterpret_cast<uintptr_t>(ptr), alignof(ProbedItem))); @@ -1647,33 +1715,37 @@ // marked elements. // Finds new position for each element and transfers it to the new slots. // Returns the total probe length. - ABSL_ATTRIBUTE_NOINLINE size_t DecodeAndInsertToTableOverflow( - CommonFields& common, const PolicyFunctions& __restrict policy, - void* old_slots) const { + ABSL_ATTRIBUTE_NOINLINE size_t DecodeAndInsertToTableOverflow() const { ABSL_SWISSTABLE_ASSERT(local_buffer_full_ && "must not be called when local buffer is not full"); size_t total_probe_length = DecodeAndInsertImpl( - common, policy, OverflowBufferStart(), pos_, old_slots); + common_, policy_, OverflowBufferStart(), pos_, old_slots_); if (ABSL_PREDICT_TRUE(marked_elements_starting_position_ == kNoMarkedElementsSentinel)) { return total_probe_length; } total_probe_length += - ProcessProbedMarkedElements(common, policy, control_, old_slots, + ProcessProbedMarkedElements(common_, policy_, control_, old_slots_, marked_elements_starting_position_); return total_probe_length; } static constexpr size_t kBufferSize = kProbedElementsBufferSize / sizeof(ProbedItem); - ProbedItem buffer_[kBufferSize]; + CommonFields& common_; + const PolicyFunctions& policy_; + ctrl_t* const control_; + void* const old_slots_; + const size_t new_capacity_; + ctrl_t* const new_ctrl_; + void* const new_slots_; // If local_buffer_full_ is false, then pos_/end_ are in the local buffer, // otherwise, they're in the overflow buffer. ProbedItem* pos_ = buffer_; const void* end_ = buffer_ + kBufferSize; - ctrl_t* const control_; size_t marked_elements_starting_position_ = kNoMarkedElementsSentinel; bool local_buffer_full_ = false; + ProbedItem buffer_[kBufferSize]; }; // Grows to next capacity with specified encoder type. @@ -1683,18 +1755,19 @@ template <typename Encoder> size_t GrowToNextCapacity(CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { - using ProbedItem = typename Encoder::ProbedItem; - ABSL_SWISSTABLE_ASSERT(common.capacity() <= ProbedItem::kMaxNewCapacity); - Encoder encoder(old_ctrl); + ctrl_t* old_ctrl, void* old_slots, + size_t new_capacity) { + ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity); + ABSL_SWISSTABLE_ASSERT(new_capacity <= Encoder::ProbedItem::kMaxNewCapacity); + Encoder encoder(common, policy, old_ctrl, old_slots, new_capacity); policy.transfer_unprobed_elements_to_next_capacity( - common, old_ctrl, old_slots, &encoder, - [](void* probed_storage, h2_t h2, size_t source_offset, size_t h1) { + common, old_ctrl, &encoder, old_slots, PreviousCapacity(new_capacity), + [](void* probed_storage, size_t hash, size_t source_offset) { auto encoder_ptr = static_cast<Encoder*>(probed_storage); - encoder_ptr->EncodeItem(ProbedItem(h2, source_offset, h1)); + encoder_ptr->EncodeProbedElement(hash, source_offset); }); - InitializeMirroredControlBytes(common.control(), common.capacity()); - return encoder.DecodeAndInsertToTable(common, policy, old_slots); + InitializeMirroredControlBytes(common.control(), new_capacity); + return encoder.DecodeAndInsertToTable(); } // Grows to next capacity for relatively small tables so that even if all @@ -1702,32 +1775,34 @@ // Returns total probe length. size_t GrowToNextCapacityThatFitsInLocalBuffer( CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { - ABSL_SWISSTABLE_ASSERT(common.capacity() <= kMaxLocalBufferNewCapacity); + ctrl_t* old_ctrl, void* old_slots, size_t new_capacity) { + ABSL_SWISSTABLE_ASSERT(new_capacity <= kMaxLocalBufferNewCapacity); return GrowToNextCapacity< ProbedItemEncoder<ProbedItem4Bytes, /*kGuaranteedFitToBuffer=*/true>>( - common, policy, old_ctrl, old_slots); + common, policy, old_ctrl, old_slots, new_capacity); } // Grows to next capacity with different encodings. Returns total probe length. // These functions are useful to simplify profile analysis. size_t GrowToNextCapacity4BytesEncoder(CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { + ctrl_t* old_ctrl, void* old_slots, + size_t new_capacity) { return GrowToNextCapacity<ProbedItemEncoder<ProbedItem4Bytes>>( - common, policy, old_ctrl, old_slots); + common, policy, old_ctrl, old_slots, new_capacity); } size_t GrowToNextCapacity8BytesEncoder(CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { + ctrl_t* old_ctrl, void* old_slots, + size_t new_capacity) { return GrowToNextCapacity<ProbedItemEncoder<ProbedItem8Bytes>>( - common, policy, old_ctrl, old_slots); + common, policy, old_ctrl, old_slots, new_capacity); } size_t GrowToNextCapacity16BytesEncoder( CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { + ctrl_t* old_ctrl, void* old_slots, size_t new_capacity) { return GrowToNextCapacity<ProbedItemEncoder<ProbedItem16Bytes>>( - common, policy, old_ctrl, old_slots); + common, policy, old_ctrl, old_slots, new_capacity); } // Grows to next capacity for tables with relatively large capacity so that we @@ -1735,16 +1810,19 @@ // total probe length. size_t GrowToNextCapacityOverflowLocalBuffer( CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { - const size_t new_capacity = common.capacity(); + ctrl_t* old_ctrl, void* old_slots, size_t new_capacity) { + ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity); if (ABSL_PREDICT_TRUE(new_capacity <= ProbedItem4Bytes::kMaxNewCapacity)) { - return GrowToNextCapacity4BytesEncoder(common, policy, old_ctrl, old_slots); + return GrowToNextCapacity4BytesEncoder(common, policy, old_ctrl, old_slots, + new_capacity); } if (ABSL_PREDICT_TRUE(new_capacity <= ProbedItem8Bytes::kMaxNewCapacity)) { - return GrowToNextCapacity8BytesEncoder(common, policy, old_ctrl, old_slots); + return GrowToNextCapacity8BytesEncoder(common, policy, old_ctrl, old_slots, + new_capacity); } // 16 bytes encoding supports the maximum swisstable capacity. - return GrowToNextCapacity16BytesEncoder(common, policy, old_ctrl, old_slots); + return GrowToNextCapacity16BytesEncoder(common, policy, old_ctrl, old_slots, + new_capacity); } // Dispatches to the appropriate `GrowToNextCapacity*` function based on the @@ -1752,14 +1830,15 @@ ABSL_ATTRIBUTE_NOINLINE size_t GrowToNextCapacityDispatch(CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { - const size_t new_capacity = common.capacity(); + ctrl_t* old_ctrl, void* old_slots, + size_t new_capacity) { + ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity); if (ABSL_PREDICT_TRUE(new_capacity <= kMaxLocalBufferNewCapacity)) { return GrowToNextCapacityThatFitsInLocalBuffer(common, policy, old_ctrl, - old_slots); + old_slots, new_capacity); } else { return GrowToNextCapacityOverflowLocalBuffer(common, policy, old_ctrl, - old_slots); + old_slots, new_capacity); } } @@ -1783,7 +1862,8 @@ void* Grow1To3AndPrepareInsert(CommonFields& common, const PolicyFunctions& __restrict policy, - void* hasher, HashForKeyFn get_hash) { + void* hasher, HashForKeyFn get_hash, void* alloc, + bool has_infoz, void* new_slots) { // TODO(b/413062340): Refactor to reuse more code with // GrowSooTableToNextCapacityAndPrepareInsert. ABSL_SWISSTABLE_ASSERT(common.capacity() == 1); @@ -1793,21 +1873,8 @@ ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); constexpr size_t kOldCapacity = 1; constexpr size_t kNewCapacity = NextCapacity(kOldCapacity); - void* old_slots = common.single_non_soo_slot(); - // old_slots == old_ctrl in case of capacity == 1. - ctrl_t* old_ctrl = static_cast<ctrl_t*>(old_slots); - - const size_t slot_size = policy.slot_size; - const size_t slot_align = policy.slot_align; - void* alloc = policy.get_char_alloc(common); - const bool has_infoz = common.has_infoz(); - common.set_capacity(kNewCapacity); - - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc, - /*blocked_element_count=*/0); - common.set_control(new_ctrl); - SanitizerPoisonMemoryRegion(new_slots, kNewCapacity * slot_size); + ctrl_t* new_ctrl = + static_cast<ctrl_t*>(new_slots) - NumControlBytes(kNewCapacity); if (ABSL_PREDICT_TRUE(!has_infoz)) { // When we're sampled, we already have a seed. @@ -1816,28 +1883,40 @@ const size_t new_hash = get_hash(hasher, common.seed().seed()); h2_t new_h2 = H2(new_hash); size_t orig_hash = - policy.hash_slot(policy.hash_fn(common), old_slots, common.seed().seed()); + policy.hash_slot(policy.hash_fn(common), common.single_non_soo_slot(), + common.seed().seed()); size_t offset = Resize1To3NewOffset(new_hash); InitializeThreeElementsControlBytes(H2(orig_hash), new_h2, offset, new_ctrl); + // Read `old_slots` and `slot_size` after the hash calls to avoid keeping + // them live across indirect calls. + void* old_slots = common.single_non_soo_slot(); + // old_slots == old_ctrl in case of capacity == 1. + ctrl_t* old_ctrl = static_cast<ctrl_t*>(old_slots); + common.set_control(new_ctrl); + const size_t slot_size = policy.slot_size; + SanitizerPoisonMemoryRegion(new_slots, kNewCapacity * slot_size); + void* old_element_target = NextSlot(new_slots, slot_size); + void* new_element_target_slot = SlotAddress(new_slots, offset, slot_size); SanitizerUnpoisonMemoryRegion(old_element_target, slot_size); policy.transfer_n(&common, old_element_target, old_slots, 1); - - void* new_element_target_slot = SlotAddress(new_slots, offset, slot_size); SanitizerUnpoisonMemoryRegion(new_element_target_slot, slot_size); + // Group `common` updates together so `inline_data_` is modified in a single + // load-store sequence. + common.set_capacity(kNewCapacity); + common.InitGrowthLeftNoDeleted(kNewCapacity - 2, kNewCapacity); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); - common.InitGrowthLeftNoDeleted(kNewCapacity - 2, kNewCapacity); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportSingleGroupTableGrowthToInfoz(common, old_ctrl, new_hash); } // Deallocate after `ReportSingleGroupTableGrowthToInfoz`, because it reads // infoz from old_ctrl. - DeallocBackingArrayImpl(alloc, kOldCapacity, old_ctrl, slot_size, slot_align, - has_infoz, + DeallocBackingArrayImpl(alloc, kOldCapacity, old_ctrl, slot_size, + policy.slot_align, has_infoz, /*blocked_element_count=*/0, policy.dealloc); return new_element_target_slot; } @@ -1846,8 +1925,8 @@ // Returns the offset of the new element. void* GrowToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_hash) { - const size_t old_capacity = common.capacity(); + size_t new_hash, size_t old_capacity) { + ABSL_SWISSTABLE_ASSERT(common.capacity() == old_capacity); ABSL_SWISSTABLE_ASSERT(common.GetGrowthLeftTotalSlow(old_capacity) == 0); ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(old_capacity)); @@ -1855,21 +1934,26 @@ const size_t new_capacity = NextCapacity(old_capacity); ABSL_ASSUME(new_capacity > kMaxSmallCapacity); + + void* alloc = policy.get_char_alloc(common); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, common.has_infoz(), alloc, + /*blocked_element_count=*/0); + // Read old `common` fields after `AllocBackingArray` to avoid spilling them + // across the call. ctrl_t* old_ctrl = common.control(); void* old_slots = common.slot_array(old_capacity); size_t old_blocked_element_count = common.blocked_element_count(); + const size_t old_size = common.size(); - const bool has_infoz = common.has_infoz(); + // Group all `common` updates together so `inline_data_` is modified in a + // single load-store sequence. common.set_capacity(new_capacity); common.set_blocked_element_count_to_zero(); - const size_t slot_size = policy.slot_size; - const size_t slot_align = policy.slot_align; - void* alloc = policy.get_char_alloc(common); - - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, - /*blocked_element_count=*/0); common.set_control(new_ctrl); + PrepareInsertCommon(common); + ResetGrowthLeft(new_capacity, old_size + 1, common); + const size_t slot_size = policy.slot_size; SanitizerPoisonMemoryRegion(new_slots, new_capacity * slot_size); h2_t new_h2 = H2(new_hash); @@ -1877,7 +1961,6 @@ FindInfo find_info; if (ABSL_PREDICT_TRUE(is_single_group(new_capacity))) { size_t offset; - const size_t old_size = common.size(); GrowIntoSingleGroupShuffleControlBytes(old_ctrl, old_capacity, old_blocked_element_count, new_ctrl, new_capacity); @@ -1886,82 +1969,120 @@ offset = new_hash & 1 ? 0 : new_capacity - 1; ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[offset])); - SetCtrlInSingleGroupTable(common, offset, new_h2, policy.slot_size); + SetCtrlInSingleGroupTable(common, new_capacity, new_ctrl, offset, new_h2, + slot_size); find_info = FindInfo{offset, 0}; // Single group tables have all slots full on resize. So we can transfer // all slots without checking the control bytes. - ABSL_SWISSTABLE_ASSERT(common.size() + old_blocked_element_count == + ABSL_SWISSTABLE_ASSERT(old_size + old_blocked_element_count == old_capacity); void* target = NextSlot(new_slots, slot_size); SanitizerUnpoisonMemoryRegion(target, old_size * slot_size); policy.transfer_n(&common, target, old_slots, old_size); } else { - total_probe_length = - GrowToNextCapacityDispatch(common, policy, old_ctrl, old_slots); - find_info = find_first_non_full(common, new_hash); - SetCtrl(common, find_info.offset, new_h2, policy.slot_size); + total_probe_length = GrowToNextCapacityDispatch(common, policy, old_ctrl, + old_slots, new_capacity); + find_info = find_first_non_full(new_capacity, new_ctrl, new_hash); + SetCtrl(common, new_capacity, new_ctrl, find_info.offset, new_h2, + slot_size); } ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); - PrepareInsertCommon(common); - ResetGrowthLeft(new_capacity, common.size(), common); - + const bool has_infoz = common.has_infoz(); if (ABSL_PREDICT_FALSE(has_infoz)) { ReportGrowthToInfoz(common, old_ctrl, new_hash, total_probe_length, find_info.probe_length); } // Deallocate after `ReportGrowthToInfoz`, because it reads infoz from // old_ctrl. - DeallocBackingArrayImpl(alloc, old_capacity, old_ctrl, slot_size, slot_align, - has_infoz, old_blocked_element_count, policy.dealloc); - return SlotAddress(new_slots, find_info.offset, policy.slot_size); + DeallocBackingArrayImpl(alloc, old_capacity, old_ctrl, slot_size, + policy.slot_align, has_infoz, + old_blocked_element_count, policy.dealloc); + return SlotAddress(new_slots, find_info.offset, slot_size); } } // namespace +RawHashSetLayout RawHashSetLayout::CreateForSmallNonSooGrowth(size_t size, + size_t slot_size, + size_t slot_align, + bool has_infoz) { + ABSL_SWISSTABLE_ASSERT(size <= 1); + static_assert(NumControlBytes(1) == 0); + const size_t num_control_bytes = size * NumControlBytes(3); + static_assert(NextCapacity(0) == 1); + static_assert(NextCapacity(1) == 3); + const size_t new_capacity = NextCapacity(size); + const size_t slots_size = new_capacity * slot_size; + + // Since `GrowthInfoSizeForCapacity` is 0 for capacities 1 and 3, compute + // `metadata_size` directly without `MetadataBeforeControlSize` to avoid its + // `ABSL_PREDICT_FALSE(has_infoz)` branch and allow a branchless shift. + static_assert(GrowthInfoSizeForCapacity(1) == 0); + static_assert(GrowthInfoSizeForCapacity(3) == 0); + const size_t metadata_size = + (has_infoz ? sizeof(HashtablezInfoHandle) + sizeof(uint64_t) : 0) + + NumGenerationBytes(); + ABSL_SWISSTABLE_ASSERT(metadata_size == + MetadataBeforeControlSize(has_infoz, new_capacity)); + + RawHashSetLayout layout(uninitialized_tag_t{}); + layout.slot_offset_ = + AlignUpTo(metadata_size + num_control_bytes, slot_align); + layout.control_offset_ = layout.slot_offset_ - num_control_bytes; + layout.generation_offset_ = layout.control_offset_ - NumGenerationBytes(); + layout.alloc_size_ = layout.slot_offset_ + slots_size; + return layout; +} + void* PrepareInsertSmallNonSoo(CommonFields& common, const PolicyFunctions& __restrict policy, void* hasher, HashForKeyFn get_hash) { ABSL_SWISSTABLE_ASSERT(common.is_small()); ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); - if (common.capacity() == 1) { - if (common.empty()) { - IncrementSmallSizeNonSoo(common, policy); - // Compute before `RecordInsertMissCold` to avoid reloading `control_`. - void* res = common.single_non_soo_slot(); - // Call NOINLINE function to move infoz instructions out of line. - if (common.has_infoz()) { - ReportInsertMissToInfozAndComputeHash(common, /*probe_length=*/0, - hasher, get_hash); - } - return res; - } else { - return Grow1To3AndPrepareInsert(common, policy, hasher, get_hash); + const bool is_empty = common.empty(); + if (common.capacity() == 1 && is_empty) { + IncrementSmallSizeNonSoo(common, policy); + // Compute before `RecordInsertMissCold` to avoid reloading `control_`. + void* res = common.single_non_soo_slot(); + // Call NOINLINE function to move infoz instructions out of line. + if (common.has_infoz()) { + ReportInsertMissToInfozAndComputeHash(common, /*probe_length=*/0, hasher, + get_hash); } + return res; } - // Growing from 0 to 1 capacity. - ABSL_SWISSTABLE_ASSERT(common.capacity() == 0); - constexpr size_t kNewCapacity = 1; - - common.set_capacity(kNewCapacity); + const size_t size = common.size(); const bool has_infoz = - policy.is_hashtablez_enabled && ShouldSampleNextTable(); + is_empty ? (policy.is_hashtablez_enabled && ShouldSampleNextTable()) + : common.has_infoz(); void* alloc = policy.get_char_alloc(common); + void* new_slots = + AllocBackingArray( + common, policy, + RawHashSetLayout::CreateForSmallNonSooGrowth( + size, policy.slot_size, policy.slot_align, has_infoz), + alloc) + .slots; + if (is_empty) { + // Growing from 0 to 1 capacity. + ABSL_SWISSTABLE_ASSERT(common.capacity() == 0); + constexpr size_t kNewCapacity = 1; + common.set_capacity(kNewCapacity); + common.set_control(static_cast<ctrl_t*>(new_slots)); - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc, - /*blocked_element_count=*/0); - common.set_control(new_ctrl); + static_assert(NextCapacity(0) == 1); + PrepareInsertCommon(common); - static_assert(NextCapacity(0) == 1); - PrepareInsertCommon(common); - - if (ABSL_PREDICT_FALSE(has_infoz)) { - ReportSingleElementTableGrowthToInfozAndForceSample(common, policy, hasher, - get_hash); + if (ABSL_PREDICT_FALSE(has_infoz)) { + ReportSingleElementTableGrowthToInfozAndForceSample( + common, policy, hasher, get_hash); + } + return new_slots; } - return new_slots; + return Grow1To3AndPrepareInsert(common, policy, hasher, get_hash, alloc, + has_infoz, new_slots); } namespace { @@ -1971,9 +2092,9 @@ ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void* RehashOrGrowToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - size_t new_hash) { + size_t new_hash, size_t cap) { ABSL_SWISSTABLE_ASSERT(!common.GetGrowthInfoLowerBound().HasNoDeleted()); - const size_t cap = common.capacity(); + ABSL_SWISSTABLE_ASSERT(common.capacity() == cap); ABSL_ASSUME(cap > 0); // Do these calculations in 64-bit to avoid overflow. if (common.size() * uint64_t{32} <= @@ -2019,10 +2140,11 @@ // 762 | 149836 0.37 13 | 148559 0.74 190 // 807 | 149736 0.39 14 | 151107 0.39 14 // 852 | 150204 0.42 15 | 151019 0.42 15 - return DropDeletesWithoutResizeAndPrepareInsert(common, policy, new_hash); + return DropDeletesWithoutResizeAndPrepareInsert(common, policy, new_hash, + cap); } else { // Otherwise grow the container. - return GrowToNextCapacityAndPrepareInsert(common, policy, new_hash); + return GrowToNextCapacityAndPrepareInsert(common, policy, new_hash, cap); } } @@ -2039,24 +2161,27 @@ if (ABSL_PREDICT_TRUE( growth_info_lower_bound.HasNoGrowthLeftAndNoDeleted())) { // Table without deleted slots (>95% cases) that needs to be resized. - return GrowToNextCapacityAndPrepareInsert(common, policy, hash); + return GrowToNextCapacityAndPrepareInsert(common, policy, hash, cap); } 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); + return RehashOrGrowToNextCapacityAndPrepareInsert(common, policy, hash, + cap); } // 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); + const size_t slot_size = policy.slot_size; + ctrl_t* ctrl = common.control(); + FindInfo target = find_first_non_full(cap, ctrl, hash); + // Read `ctrl` before `PrepareInsertCommon` so `common` updates coalesce. + common.OverwriteControlAsFull(ctrl[target.offset]); PrepareInsertCommon(common); - common.OverwriteControlAsFull(common.control()[target.offset]); // Compute before `SetCtrl*` to avoid reloading `control_`. - void* res = - SlotAddress(common.slot_array(cap), target.offset, policy.slot_size); - SetCtrl(common, target.offset, H2(hash), policy.slot_size); + void* res = SlotAddress(common.slot_array(cap), target.offset, slot_size); + SetCtrl(common, cap, ctrl, target.offset, H2(hash), slot_size); if (common.has_infoz()) { ReportInsertMissToInfoz(common, target.probe_length, hash); } @@ -2083,8 +2208,8 @@ // Compute before `SetCtrl*` to avoid reloading `control_`. void* res = SlotAddress(common.slot_array(kNewCapacity), SooSlotIndex(), policy.slot_size); - SetCtrlInSingleGroupTable(common, SooSlotIndex(), H2(new_hash), - policy.slot_size); + SetCtrlInSingleGroupTable(common, kNewCapacity, common.control(), + SooSlotIndex(), H2(new_hash), policy.slot_size); if (common.has_infoz()) { ReportInsertMissToInfoz(common, /*probe_length=*/0, new_hash); } @@ -2136,82 +2261,35 @@ ABSL_ATTRIBUTE_NOINLINE void ReserveAllocatedTable( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_size) { - const size_t cap = common.capacity(); + ABSL_SWISSTABLE_ASSERT(common.capacity() > policy.soo_capacity() || + !common.empty()); ValidateMaxSize(new_size, policy.key_size, policy.slot_size); ABSL_ASSUME(new_size > 0); const size_t new_capacity = SizeToCapacity(new_size); - if (cap == policy.soo_capacity()) { - ABSL_SWISSTABLE_ASSERT(!common.empty()); - ResizeFullSooTable(common, policy, new_capacity, - ResizeFullSooTableSamplingMode::kNoSampling); - } else { - ABSL_SWISSTABLE_ASSERT(cap > policy.soo_capacity()); - // TODO(b/382423690): consider using GrowToNextCapacity, when applicable. - ResizeAllocatedTableWithSeedChange(common, policy, new_capacity); - } + // TODO(b/382423690): consider using GrowToNextCapacity, when applicable. + ResizeTableWithSeedChangeImpl(common, policy, new_capacity, + /*force_sample_soo=*/false); common.infoz().RecordReservation(new_size); } -// As `ResizeFullSooTableToNextCapacity`, except that we also force the SOO -// table to be sampled. SOO tables need to switch from SOO to heap in order to -// store the infoz. No-op if sampling is disabled or not possible. +// Grows a full SOO table to the next capacity and forces it to be sampled. SOO +// tables need to switch from SOO to heap in order to store the infoz. No-op if +// sampling is disabled or not possible. void GrowFullSooTableToNextCapacityForceSampling( CommonFields& common, const PolicyFunctions& __restrict policy) { AssertFullSoo(common, policy); - ResizeFullSooTable( - common, policy, NextCapacity(SooCapacity()), - ResizeFullSooTableSamplingMode::kForceSampleNoResizeIfUnsampled); + ResizeTableWithSeedChangeImpl(common, policy, NextCapacity(SooCapacity()), + /*force_sample_soo=*/true); } } // namespace -void* GetRefForEmptyClass(CommonFields& common) { - // Empty base optimization typically make the empty base class address to be - // the same as the first address of the derived class object. - // But we generally assume that for empty classes we can return any valid - // pointer. - return &common; -} - void ResizeAllocatedTableWithSeedChange( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_capacity) { - ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); - ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); - - const size_t old_capacity = common.capacity(); - ctrl_t* const old_ctrl = common.control(); - void* const old_slots = IsSmallCapacity(old_capacity) - ? common.single_non_soo_slot() - : common.slot_array(old_capacity); - const size_t old_blocked_element_count = common.blocked_element_count(); - - const size_t slot_size = policy.slot_size; - const size_t slot_align = policy.slot_align; - HashtablezInfoHandle infoz = common.infoz(); - const bool has_infoz = common.has_infoz(); - void* alloc = policy.get_char_alloc(common); - - common.set_capacity(new_capacity); - common.set_blocked_element_count_to_zero(); - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, - /*blocked_element_count=*/0); - common.set_control(new_ctrl); - common.generate_new_seed(has_infoz); - - size_t total_probe_length = 0; - ResetCtrl(common, slot_size, /*blocked_element_count=*/0); - ABSL_SWISSTABLE_ASSERT(old_capacity > 0); - total_probe_length = FindNewPositionsAndTransferSlots( - common, policy, old_ctrl, old_slots, old_capacity); - DeallocBackingArrayImpl(alloc, old_capacity, old_ctrl, slot_size, slot_align, - has_infoz, old_blocked_element_count, policy.dealloc); - ResetGrowthLeft(new_capacity, common.size(), common); - - if (ABSL_PREDICT_FALSE(has_infoz)) { - ReportResizeToInfoz(common, infoz, total_probe_length); - } + ABSL_SWISSTABLE_ASSERT(common.capacity() > policy.soo_capacity()); + ResizeTableWithSeedChangeImpl(common, policy, new_capacity, + /*force_sample_soo=*/false); } // Resizes a full SOO table to the NextCapacity(SooCapacity()). @@ -2227,33 +2305,38 @@ } ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); - const size_t slot_size = policy.slot_size; - void* alloc = policy.get_char_alloc(common); - common.set_capacity(kNewCapacity); + // Generate the seed and compute hashes before `AllocBackingArray` so + // `hasher`, `get_hash`, and `new_ctrl`/`new_slots` do not need to be spilled + // across calls. + common.generate_new_seed(/*has_infoz=*/false); + const size_t new_hash = get_hash(hasher, common.seed().seed()); + const h2_t soo_slot_h2 = H2(policy.hash_slot( + policy.hash_fn(common), common.soo_data(), common.seed().seed())); // Since the table is not empty, it will not be sampled. // The decision to sample was already made during the first insertion. // // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. - const auto [new_ctrl, new_slots] = AllocBackingArray( - common, policy, kNewCapacity, /*has_infoz=*/false, alloc, - /*blocked_element_count=*/0); - + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, kNewCapacity, /*has_infoz=*/false, + policy.get_char_alloc(common), + /*blocked_element_count=*/0); + // Group `common` updates together after `AllocBackingArray` so `inline_data_` + // is modified in a single load-store sequence. + common.set_capacity(kNewCapacity); + common.InitGrowthLeftNoDeleted(kNewCapacity - 2, kNewCapacity); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); - 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())); - const size_t new_hash = get_hash(hasher, common.seed().seed()); const size_t offset = Resize1To3NewOffset(new_hash); InitializeThreeElementsControlBytes(soo_slot_h2, H2(new_hash), offset, new_ctrl); + const size_t slot_size = policy.slot_size; SanitizerPoisonMemoryRegion(new_slots, slot_size * kNewCapacity); void* target_slot = SlotAddress(new_slots, SooSlotIndex(), slot_size); + void* new_slot = SlotAddress(new_slots, offset, slot_size); SanitizerUnpoisonMemoryRegion(target_slot, slot_size); if constexpr (TransferUsesMemcpy) { // Target slot is placed at index 1, but capacity is at @@ -2277,7 +2360,6 @@ // Full SOO table couldn't be sampled. If SOO table is sampled, it would // have been resized to the next capacity. ABSL_SWISSTABLE_ASSERT(!common.infoz().IsSampled()); - void* new_slot = SlotAddress(new_slots, offset, slot_size); SanitizerUnpoisonMemoryRegion(new_slot, slot_size); return new_slot; } @@ -2334,17 +2416,13 @@ ValidateMaxCapacity(new_capacity, policy.key_size, policy.slot_size); // n == 0 unconditionally rehashes as per the standard. if (n == 0 || new_capacity > cap) { - if (cap == policy.soo_capacity()) { - if (common.empty()) { - ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, - /*blocked_element_count=*/0, - /*force_infoz=*/false); - } else { - ResizeFullSooTable(common, policy, new_capacity, - ResizeFullSooTableSamplingMode::kNoSampling); - } + if (cap == policy.soo_capacity() && common.empty()) { + ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + /*blocked_element_count=*/0, + /*force_infoz=*/false); } else { - ResizeAllocatedTableWithSeedChange(common, policy, new_capacity); + ResizeTableWithSeedChangeImpl(common, policy, new_capacity, + /*force_sample_soo=*/false); } // This is after resize, to ensure that we have completed the allocation // and have potentially sampled the hashtable. @@ -2404,10 +2482,11 @@ // The table is guaranteed to be empty, so we can do faster than // a full `insert`. const size_t hash = (*hasher)(hash_fn, that_slot, seed); - FindInfo target = find_first_non_full(common, hash); - infoz.RecordInsertMiss(hash, target.probe_length); + ctrl_t* ctrl = common.control(); + FindInfo target = find_first_non_full(cap, ctrl, hash); offset = target.offset; - SetCtrl(common, offset, H2(hash), slot_size); + SetCtrl(common, cap, ctrl, offset, H2(hash), slot_size); + infoz.RecordInsertMiss(hash, target.probe_length); copy_fn(&common, SlotAddress(target_slot_array, offset, slot_size), that_slot); common.maybe_increment_generation_on_insert(); @@ -2463,7 +2542,8 @@ // Compute before `SetCtrl` to avoid reloading `control_`. void* res = SlotAddress(common.slot_array(cap), target_group_offset, policy.slot_size); - SetCtrl(common, target_group_offset, H2(hash), policy.slot_size); + SetCtrl(common, cap, common.control(), target_group_offset, H2(hash), + policy.slot_size); // Call NOINLINE function to move infoz instructions out of line. if (common.has_infoz()) { return ReportInsertMissToInfozAndGetSlot(common, policy, hash, @@ -2595,9 +2675,8 @@ const DtorPolicy& policy); // Extern template instantiation for inline functions. -template size_t TryFindNewIndexWithoutProbing(size_t h1, size_t old_index, +template size_t TryFindNewIndexWithoutProbing(size_t hash, size_t old_index, size_t old_capacity, - ctrl_t* new_ctrl, size_t new_capacity); template void AssertIsFull(const ctrl_t* const& ctrl, const void* slot, GenerationType generation,
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 83b547e..591de39 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -213,7 +213,6 @@ #include "absl/base/prefetch.h" #include "absl/container/internal/common.h" // IWYU pragma: export // for node_handle #include "absl/container/internal/common_policy_traits.h" -#include "absl/container/internal/compressed_tuple.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" #include "absl/container/internal/hash_policy_traits.h" @@ -1207,6 +1206,13 @@ alloc_size_ = slot_offset_ + (capacity - blocked_element_count) * slot_size; } + // Creates a layout for a small non-SOO table growing from capacity + // 0 -> 1 (`size == 0`) or 1 -> 3 (`size == 1`). + static RawHashSetLayout CreateForSmallNonSooGrowth(size_t size, + size_t slot_size, + size_t slot_align, + bool has_infoz); + // Returns precomputed offset from the start of the backing allocation of // control. size_t control_offset() const { return control_offset_; } @@ -1224,6 +1230,8 @@ size_t alloc_size() const { return alloc_size_; } private: + explicit RawHashSetLayout(uninitialized_tag_t) {} + size_t control_offset_; size_t generation_offset_; size_t slot_offset_; @@ -1893,54 +1901,28 @@ constexpr size_t kProbedElementIndexSentinel = ~size_t{}; // Implementation detail of transfer_unprobed_elements_to_next_capacity_fn. -// Tries to find the new index for an element whose hash corresponds to -// `h1` for growth to the next capacity. -// Returns kProbedElementIndexSentinel if full probing is required. +// Tries to find the new index for an element with `hash` for growth to the next +// capacity. +// Returns kProbedElementIndexSentinel if element was probed in the table before +// growth. // // If element is located in the first probing group in the table before growth, // returns one of two positions: `old_index` or `old_index + old_capacity + 1`. -// -// Otherwise, we will try to insert it into the first probe group of the new -// table. We only attempt to do so if the first probe group is already -// initialized. template <typename = void> -inline size_t TryFindNewIndexWithoutProbing(size_t h1, size_t old_index, +inline size_t TryFindNewIndexWithoutProbing(size_t hash, size_t old_index, size_t old_capacity, - ctrl_t* new_ctrl, size_t new_capacity) { - size_t index_diff = old_index - h1; + size_t h1 = H1(hash); // The first probe group starts with h1 & capacity. // All following groups start at (h1 + Group::kWidth * K) & capacity. - // We can find an index within the floating group as index_diff modulo - // Group::kWidth. - // Both old and new capacity are larger than Group::kWidth so we can avoid - // computing `& capacity`. - size_t in_floating_group_index = index_diff & (Group::kWidth - 1); - // By subtracting we will get the difference between the first probe group - // and the probe group corresponding to old_index. - index_diff -= in_floating_group_index; - if (ABSL_PREDICT_TRUE((index_diff & old_capacity) == 0)) { - size_t new_index = (h1 + in_floating_group_index) & new_capacity; + // If old_index is in the first probe group, (old_index - h1) & old_capacity + // is the index within the floating group (< Group::kWidth). + size_t index_diff = (old_index - h1) & old_capacity; + if (ABSL_PREDICT_TRUE(index_diff < Group::kWidth)) { + size_t new_index = (h1 + index_diff) & new_capacity; ABSL_ASSUME(new_index != kProbedElementIndexSentinel); return new_index; } - ABSL_SWISSTABLE_ASSERT(((old_index - h1) & old_capacity) >= Group::kWidth); - // Try to insert element into the first probe group. - // new_ctrl is not yet fully initialized so we can't use regular search via - // find_first_non_full. - - // We can search in the first probe group only if it is located in already - // initialized part of the table. - if (ABSL_PREDICT_FALSE((h1 & old_capacity) >= old_index)) { - return kProbedElementIndexSentinel; - } - size_t offset = h1 & new_capacity; - Group new_g(new_ctrl + offset); - if (auto mask = new_g.MaskNonFull(); ABSL_PREDICT_TRUE(mask)) { - size_t result = offset + mask.LowestBitSet(); - ABSL_ASSUME(result != kProbedElementIndexSentinel); - return result; - } return kProbedElementIndexSentinel; } @@ -1995,15 +1977,18 @@ // type-erased functions that want to do small amounts of type-specific // work. struct PolicyFunctions { + // 8 bytes uint32_t key_size; uint32_t value_size; + + // 8 bytes uint32_t slot_size; uint16_t slot_align; bool soo_enabled; bool is_hashtablez_enabled; - - // Returns the pointer to the hash function stored in the set. - void* (*hash_fn)(CommonFields& common); + // 8 bytes + uint32_t hasher_offset; + uint32_t alloc_offset; // Returns the hash of the pointed-to slot. HashSlotFn hash_slot; @@ -2012,9 +1997,6 @@ // We use ability to transfer several slots in single group table growth. void (*transfer_n)(void* set, void* dst_slot, void* src_slot, size_t count); - // Returns the pointer to the CharAlloc stored in the set. - void* (*get_char_alloc)(CommonFields& common); - // Allocates n bytes for the backing store for common. void* (*alloc)(void* alloc, size_t n); @@ -2031,15 +2013,25 @@ // Different encoding is used depending on the capacity of the table. // See ProbedItem*Bytes classes for details. void (*transfer_unprobed_elements_to_next_capacity)( - CommonFields& common, const ctrl_t* old_ctrl, void* old_slots, + CommonFields& common, const ctrl_t* old_ctrl, // TODO(b/382423690): Try to use absl::FunctionRef here. - void* probed_storage, - void (*encode_probed_element)(void* probed_storage, h2_t h2, - size_t source_offset, size_t h1)); + void* probed_storage, void* old_slots, size_t old_capacity, + void (*encode_probed_element)(void* probed_storage, size_t hash, + size_t source_offset)); uint8_t soo_capacity() const { return static_cast<uint8_t>(soo_enabled ? SooCapacity() : 0); } + + // Returns the pointer to the hash function stored in the set. + const void* hash_fn(const CommonFields& common) const { + return reinterpret_cast<const char*>(&common) + hasher_offset; + } + + // Returns the pointer to the CharAlloc stored in the set. + void* get_char_alloc(CommonFields& common) const { + return reinterpret_cast<char*>(&common) + alloc_offset; + } }; using DestroySlotFn = void (*)(void* set, void* slot); @@ -2279,11 +2271,6 @@ memcpy(dst, src, SizeOfSlot * count); } -// Returns a pointer to `common`. This is used to implement type erased -// raw_hash_set::get_hash_ref_fn and raw_hash_set::get_alloc_ref_fn for the -// empty class cases. -void* GetRefForEmptyClass(CommonFields& common); - // Given the hash of a value not currently in the table and the first group with // an empty slot in the probe sequence, finds a viable slot to insert it at. // @@ -2770,13 +2757,16 @@ raw_hash_set() noexcept( std::is_nothrow_default_constructible_v<hasher> && std::is_nothrow_default_constructible_v<key_equal> && - std::is_nothrow_default_constructible_v<allocator_type>) {} + std::is_nothrow_default_constructible_v<allocator_type>) + : hash_(), eq_(), alloc_() {} explicit raw_hash_set(size_t reservation_size, const hasher& hash = hasher(), const key_equal& eq = key_equal(), const allocator_type& alloc = allocator_type()) - : settings_(CommonFields::CreateDefault<SooEnabled()>(), hash, eq, - alloc) { + : common_(CommonFields::CreateDefault<SooEnabled()>()), + hash_(hash), + eq_(eq), + alloc_(alloc) { if (reservation_size > DefaultCapacity()) { ReserveTableToFitNewSize(common(), GetPolicyFunctions(), reservation_size); @@ -2922,11 +2912,13 @@ // `that` must be left valid. If Hash is std::function<Key>, moving it // would create a nullptr functor that cannot be called. // Note: we avoid using exchange for better generated code. - settings_(PolicyTraits::transfer_uses_memcpy() || !that.is_full_soo() - ? std::move(that.common()) - : CommonFields{full_soo_tag_t{}, - that.common().soo_has_tried_sampling()}, - that.hash_ref(), that.eq_ref(), that.char_alloc_ref()) { + common_(PolicyTraits::transfer_uses_memcpy() || !that.is_full_soo() + ? std::move(that.common()) + : CommonFields{full_soo_tag_t{}, + that.common().soo_has_tried_sampling()}), + hash_(that.hash_ref()), + eq_(that.eq_ref()), + alloc_(that.char_alloc_ref()) { if constexpr (SooEnabled() && !PolicyTraits::transfer_uses_memcpy()) { if (that.is_full_soo()) { transfer(soo_slot(), that.soo_slot()); @@ -2938,8 +2930,10 @@ } raw_hash_set(raw_hash_set&& that, const allocator_type& a) - : settings_(CommonFields::CreateDefault<SooEnabled()>(), that.hash_ref(), - that.eq_ref(), a) { + : common_(CommonFields::CreateDefault<SooEnabled()>()), + hash_(that.hash_ref()), + eq_(that.eq_ref()), + alloc_(a) { if (CharAlloc(a) == that.char_alloc_ref()) { swap_common(that); common().annotate_for_bug_detection_on_move(that.common(), @@ -3978,10 +3972,9 @@ std::is_same_v<key_equal, std::equal_to<key_type>>; if constexpr (kIsDebug && !kIsStringAbslHashEq && !kIsScalarAbslHashEq) { if (empty()) return; - AssertHashEqConsistentImpl( - common(), get_hash_ref_fn(common()), get_hash_slot_fn(), - sizeof(slot_type), SooEnabled(), hash_of(key), &key, - &equal_to_key_fn<K>); + AssertHashEqConsistentImpl(common(), &hash_ref(), get_hash_slot_fn(), + sizeof(slot_type), SooEnabled(), hash_of(key), + &key, &equal_to_key_fn<K>); } } @@ -4064,8 +4057,8 @@ #endif } - CommonFields& common() { return settings_.template get<0>(); } - const CommonFields& common() const { return settings_.template get<0>(); } + CommonFields& common() { return common_; } + const CommonFields& common() const { return common_; } // For use when the capacity is potentially invalid we return // HashtableCapacity directly. @@ -4113,24 +4106,33 @@ return common().infoz(); } - hasher& hash_ref() { return settings_.template get<1>(); } - const hasher& hash_ref() const { return settings_.template get<1>(); } - key_equal& eq_ref() { return settings_.template get<2>(); } - const key_equal& eq_ref() const { return settings_.template get<2>(); } - CharAlloc& char_alloc_ref() { return settings_.template get<3>(); } - const CharAlloc& char_alloc_ref() const { - return settings_.template get<3>(); - } + hasher& hash_ref() { return hash_; } + const hasher& hash_ref() const { return hash_; } + key_equal& eq_ref() { return eq_; } + const key_equal& eq_ref() const { return eq_; } + CharAlloc& char_alloc_ref() { return alloc_; } + const CharAlloc& char_alloc_ref() const { return alloc_; } - static void* get_char_alloc_ref_fn(CommonFields& common) { - auto* h = reinterpret_cast<raw_hash_set*>(&common); - return &h->char_alloc_ref(); + // Offsets of `hash_` and `alloc_` relative to `common_`. They are stored in + // `PolicyFunctions` so that type erased functions can access the hasher and + // the allocator given only a `CommonFields&`. + // `offsetof` on a non-standard-layout type (e.g. when `hasher` is + // not standard-layout) is conditionally-supported, but all the compilers we + // care about support it for direct non-static data members. Hence, we + // suppress the corresponding warning. +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Winvalid-offsetof" +#endif + static constexpr size_t HasherOffset() { + return offsetof(raw_hash_set, hash_) - offsetof(raw_hash_set, common_); } - static void* get_hash_ref_fn(CommonFields& common) { - auto* h = reinterpret_cast<raw_hash_set*>(&common); - // TODO(b/397453582): Remove support for const hasher. - return const_cast<std::remove_const_t<hasher>*>(&h->hash_ref()); + static constexpr size_t AllocOffset() { + return offsetof(raw_hash_set, alloc_) - offsetof(raw_hash_set, common_); } +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic pop +#endif static constexpr HashSlotFn get_hash_slot_fn() { return PolicyTraits::template get_hash_slot_fn<hasher, kIsAbslHash, kSeedShift>(); @@ -4169,15 +4171,15 @@ // by GetKey + Hash for memcpyable types. // TODO(b/382423690): Try to type erase for big slots: sizeof(slot_type) > 16. static void transfer_unprobed_elements_to_next_capacity_fn( - CommonFields& common, const ctrl_t* old_ctrl, void* old_slots, - void* probed_storage, - void (*encode_probed_element)(void* probed_storage, h2_t h2, - size_t source_offset, size_t h1)) { - const size_t new_capacity = common.capacity(); - ABSL_ASSUME(new_capacity > kMaxSmallCapacity); - const size_t old_capacity = PreviousCapacity(new_capacity); + CommonFields& common, const ctrl_t* old_ctrl, void* probed_storage, + void* old_slots, size_t old_capacity, + void (*encode_probed_element)(void* probed_storage, size_t hash, + size_t source_offset)) { ABSL_ASSUME(old_capacity + 1 >= Group::kWidth); ABSL_ASSUME((old_capacity + 1) % Group::kWidth == 0); + const size_t new_capacity = NextCapacity(old_capacity); + ABSL_ASSUME(new_capacity > kMaxSmallCapacity); + ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity); auto* set = reinterpret_cast<raw_hash_set*>(&common); slot_type* old_slots_ptr = to_slot(old_slots); @@ -4199,19 +4201,17 @@ // TODO(b/382423690): try to avoid entire hash calculation since we need // only one new bit of h1. size_t hash = set->hash_of(old_slot); - size_t h1 = H1(hash); - h2_t h2 = H2(hash); size_t new_index = TryFindNewIndexWithoutProbing( - h1, old_index, old_capacity, new_ctrl, new_capacity); + hash, old_index, old_capacity, new_capacity); // Note that encode_probed_element is allowed to use old_ctrl buffer // till and included the old_index. if (ABSL_PREDICT_FALSE(new_index == kProbedElementIndexSentinel)) { - encode_probed_element(probed_storage, h2, old_index, h1); + encode_probed_element(probed_storage, hash, old_index); continue; } ABSL_SWISSTABLE_ASSERT((new_index & old_capacity) <= old_index); ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[new_index])); - new_ctrl[new_index] = static_cast<ctrl_t>(h2); + new_ctrl[new_index] = static_cast<ctrl_t>(H2(hash)); auto* new_slot = new_slots + new_index; SanitizerUnpoisonMemoryRegion(new_slot, sizeof(slot_type)); set->transfer(new_slot, old_slot); @@ -4250,37 +4250,45 @@ size_t{(std::numeric_limits<uint32_t>::max)()}); static_assert(sizeof(value_type) <= size_t{(std::numeric_limits<uint32_t>::max)()}); + static_assert(HasherOffset() <= + size_t{(std::numeric_limits<uint32_t>::max)()}); + static_assert(AllocOffset() <= + size_t{(std::numeric_limits<uint32_t>::max)()}); static constexpr size_t kBackingArrayAlignment = BackingArrayAlignment(alignof(slot_type)); static constexpr PolicyFunctions value = { static_cast<uint32_t>(sizeof(key_type)), static_cast<uint32_t>(sizeof(value_type)), static_cast<uint32_t>(sizeof(slot_type)), - static_cast<uint16_t>(alignof(slot_type)), SooEnabled(), + static_cast<uint16_t>(alignof(slot_type)), + SooEnabled(), HashtablezForTableEnabled(), - // TODO(b/328722020): try to type erase - // for standard layout and alignof(Hash) <= alignof(CommonFields). - std::is_empty_v<hasher> ? &GetRefForEmptyClass - : &raw_hash_set::get_hash_ref_fn, + static_cast<uint32_t>(HasherOffset()), + static_cast<uint32_t>(AllocOffset()), get_hash_slot_fn(), PolicyTraits::transfer_uses_memcpy() ? TransferNRelocatable<sizeof(slot_type)> : &raw_hash_set::transfer_n_slots_fn, - std::is_empty_v<Alloc> ? &GetRefForEmptyClass - : &raw_hash_set::get_char_alloc_ref_fn, &AllocateBackingArray<kBackingArrayAlignment, CharAlloc>, get_dealloc_backing_array_fn(), &raw_hash_set::transfer_unprobed_elements_to_next_capacity_fn}; return value; } - // Bundle together CommonFields plus other objects which might be empty. - // CompressedTuple will ensure that sizeof is not affected by any of the - // empty fields that occur after CommonFields. - absl::container_internal::CompressedTuple<CommonFields, hasher, key_equal, - CharAlloc> - settings_{CommonFields::CreateDefault<SooEnabled()>(), hasher{}, - key_equal{}, CharAlloc{}}; + // `common_` must be the first member: type erased functions cast + // `CommonFields*` to `raw_hash_set*`. + CommonFields common_ = CommonFields::CreateDefault<SooEnabled()>(); + // ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS ensures that sizeof is not affected by any + // of the fields below if they are empty. + // + // Note: these members must not have default member initializers and must be + // initialized in the constructor mem-initializer lists instead. MSVC + // miscompiles `[[msvc::no_unique_address]]` members with default member + // initializers and overwrites bytes of the overlapping `common_`: + // https://developercommunity.visualstudio.com/t/miscompilation-with-msvcno-unique-address-and-defa/1699750 + ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS hasher hash_; + ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS key_equal eq_; + ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS CharAlloc alloc_; }; // Friend access for free functions in raw_hash_set.h. @@ -4461,10 +4469,9 @@ // Extern template for inline function keeps possibility of inlining. // When compiler decided to not inline, no symbols will be added to the // corresponding translation unit. -extern template size_t TryFindNewIndexWithoutProbing(size_t h1, +extern template size_t TryFindNewIndexWithoutProbing(size_t hash, size_t old_index, size_t old_capacity, - ctrl_t* new_ctrl, size_t new_capacity); extern template void AssertIsFull(const ctrl_t* const& ctrl, const void* slot, GenerationType generation,
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 429d7cf..1268851 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -147,6 +147,26 @@ } } +TEST(RawHashSetLayout, CreateForSmallNonSooGrowth) { + for (size_t size : {0u, 1u}) { + for (size_t slot_align : {1u, 2u, 4u, 8u, 16u}) { + for (size_t slot_size : {slot_align, slot_align * 2, slot_align * 3}) { + for (bool has_infoz : {false, true}) { + RawHashSetLayout expected(NextCapacity(size), slot_size, slot_align, + has_infoz, /*blocked_element_count=*/0); + RawHashSetLayout actual = + RawHashSetLayout::CreateForSmallNonSooGrowth( + size, slot_size, slot_align, has_infoz); + EXPECT_EQ(actual.control_offset(), expected.control_offset()); + EXPECT_EQ(actual.generation_offset(), expected.generation_offset()); + EXPECT_EQ(actual.slot_offset(), expected.slot_offset()); + EXPECT_EQ(actual.alloc_size(), expected.alloc_size()); + } + } + } + } +} + void VerifyMiddleSizeTableLayout(size_t capacity, size_t slot_size, size_t slot_align, bool has_infoz, size_t blocked_element_count, @@ -1326,6 +1346,12 @@ TEST(Table, EmptyFunctorOptimization) { static_assert(std::is_empty_v<std::equal_to<absl::string_view>>); static_assert(std::is_empty_v<std::allocator<int>>); +#if defined(_MSC_VER) && _MSC_VER < 1929 + // ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS expands to nothing for MSVC compatibility + // versions below 19.29 (e.g. clang with `-fms-compatibility-version=19.25`), + // so empty functors still take space. + GTEST_SKIP() << "ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS is a no-op."; +#endif struct MockTable { uint64_t size;