Pass capacity as a parameter to growth and rehash functions to reduce binary size. 1. **Pass `cap` from `PrepareInsertLargeSlow` to growth and rehash functions**: Pass `cap` (already computed in `PrepareInsertLargeSlow`) as the 4th parameter to `GrowToNextCapacityAndPrepareInsert`, `RehashOrGrowToNextCapacityAndPrepareInsert`, and `DropDeletesWithoutResizeAndPrepareInsert`. This eliminates redundant `common.capacity()` (`(1ULL << shift) - 1`) bit-shift/mask decoding in each callee and simplifies `old_capacity` / `new_capacity` arithmetic (`leaq (%rbx,%rbx), %r14` and `leaq 1(,%rbx,2), %rsi`) at the entry of `GrowToNextCapacityAndPrepareInsert`. 2. **Call `AllocBackingArray` right after `get_char_alloc` without spilling `has_infoz`**: Pass `common.has_infoz()` inline to `AllocBackingArray` at the beginning of `GrowToNextCapacityAndPrepareInsert` and reload `common.has_infoz()` right before `if (ABSL_PREDICT_FALSE(has_infoz))` so `has_infoz` does not need to be spilled across `AllocBackingArray` and `GrowToNextCapacityDispatch` (shrinking the stack frame from `0x68` to `0x58` bytes). 3. **Pass `new_capacity` to `GrowToNextCapacityDispatch` and helpers**: Pass `new_capacity` as the 5th parameter through `GrowToNextCapacity*` (`InitializeMirroredControlBytes`), eliminating repeated `common.capacity()` decoding across the dispatch and encoder functions. 4. **Reorder `slot_size` load and `OverwriteControlAsFull` in `PrepareInsertLargeSlow`**: Read `const size_t slot_size = policy.slot_size` before `find_first_non_full` so `policy` (`%rsi`) dies at the `HasNoGrowthLeftAndHaveDeleted()` branch (eliminating the stack spill/reload of `policy`), and call `common.OverwriteControlAsFull(ctrl[target.offset])` before `PrepareInsertCommon(common)` so both `common.inline_data_` updates coalesce into a single load-modify-store sequence without an intervening `ctrl_t` load. PiperOrigin-RevId: 1001434653
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 4847749..374ab9b 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -519,9 +519,12 @@ inline void SetCtrlNoSanitizeImpl(size_t cap, ctrl_t* ctrl, size_t i, ctrl_t h) { ABSL_SWISSTABLE_ASSERT(i < cap); - // Note: writing the cloned byte first results in better generated code. - ctrl[i < NumClonedBytes() ? i + cap + 1 : i] = h; + // 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; + cloned_ctrl_base[i] = h; } inline void SetCtrl(const CommonFields& c, size_t cap, ctrl_t* ctrl, size_t i, @@ -577,9 +580,9 @@ 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); @@ -1696,9 +1699,11 @@ template <typename Encoder> size_t GrowToNextCapacity(CommonFields& common, const PolicyFunctions& __restrict policy, - ctrl_t* old_ctrl, void* old_slots) { + ctrl_t* old_ctrl, void* old_slots, + size_t new_capacity) { using ProbedItem = typename Encoder::ProbedItem; - ABSL_SWISSTABLE_ASSERT(common.capacity() <= ProbedItem::kMaxNewCapacity); + ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity); + ABSL_SWISSTABLE_ASSERT(new_capacity <= ProbedItem::kMaxNewCapacity); Encoder encoder(old_ctrl); policy.transfer_unprobed_elements_to_next_capacity( common, old_ctrl, old_slots, &encoder, @@ -1706,7 +1711,7 @@ auto encoder_ptr = static_cast<Encoder*>(probed_storage); encoder_ptr->EncodeItem(ProbedItem(h2, source_offset, h1)); }); - InitializeMirroredControlBytes(common.control(), common.capacity()); + InitializeMirroredControlBytes(common.control(), new_capacity); return encoder.DecodeAndInsertToTable(common, policy, old_slots); } @@ -1715,32 +1720,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 @@ -1748,16 +1755,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 @@ -1765,14 +1775,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); } } @@ -1859,30 +1870,37 @@ // 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)); ABSL_ASSUME(old_capacity > kMaxSmallCapacity); + // Call `get_char_alloc` first so no local variables need to be spilled + // across the indirect call, which may alias `common`. + void* alloc = policy.get_char_alloc(common); const size_t new_capacity = NextCapacity(old_capacity); ABSL_ASSUME(new_capacity > kMaxSmallCapacity); + + 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); @@ -1890,7 +1908,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); @@ -1900,36 +1917,36 @@ ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[offset])); SetCtrlInSingleGroupTable(common, new_capacity, new_ctrl, offset, new_h2, - policy.slot_size); + 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); + 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, - policy.slot_size); + slot_size); } ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); - PrepareInsertCommon(common); - ResetGrowthLeft(new_capacity, common.size(), common); - + // Reload `has_infoz` to avoid spilling across the indirect call. + 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 @@ -1986,9 +2003,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} <= @@ -2034,10 +2051,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); } } @@ -2054,25 +2072,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. + const size_t slot_size = policy.slot_size; ctrl_t* ctrl = common.control(); FindInfo target = find_first_non_full(cap, ctrl, hash); - PrepareInsertCommon(common); + // Read `ctrl` before `PrepareInsertCommon` so `common` updates coalesce. common.OverwriteControlAsFull(ctrl[target.offset]); + PrepareInsertCommon(common); // Compute before `SetCtrl*` to avoid reloading `control_`. - void* res = - SlotAddress(common.slot_array(cap), target.offset, policy.slot_size); - SetCtrl(common, cap, ctrl, 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); }