Store `alignof(slot_type) - 1` instead of `alignof(slot_type)` in raw_hash_set policies. `PolicyFunctions::slot_align` and `DtorPolicy::slot_align` are replaced with `slot_align_mask` (`alignof(slot_type) - 1`), and `RawHashSetLayout` / `CreateForSmallNonSooGrowth` take the mask. A new `AlignUpToMask(offset, mask)` computes `(offset + mask) & ~mask`, which avoids negating the alignment at runtime: on x86-64 with BMI1 it compiles to `add` + `andn` instead of `lea` + `neg` + `and`, and callers that need the value for both allocation and deallocation only keep one value live instead of `align` and `-align`. PiperOrigin-RevId: 1007521147
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index e60b237..2608357 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -427,10 +427,10 @@ namespace { void DeallocBackingArrayImpl(void* alloc, size_t capacity, ctrl_t* ctrl, - size_t slot_size, size_t slot_align, + size_t slot_size, size_t slot_align_mask, bool has_infoz, size_t blocked_element_count, DeallocBackingArrayFn dealloc) { - RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, + RawHashSetLayout layout(capacity, slot_size, slot_align_mask, has_infoz, blocked_element_count); void* backing_array = ctrl - layout.control_offset(); // Unpoison before returning the memory to the allocator. @@ -442,7 +442,7 @@ const PolicyFunctions& __restrict policy, void* alloc) { DeallocBackingArrayImpl(alloc, c.capacity(), c.control(), policy.slot_size, - policy.slot_align, c.has_infoz(), + policy.slot_align_mask, c.has_infoz(), c.blocked_element_count(), policy.dealloc); } @@ -456,7 +456,7 @@ // in a local variable before Unregister(). c.infoz().Unregister(); DeallocBackingArrayImpl(alloc, cap, c.control(), policy.slot_size, - policy.slot_align, c.has_infoz(), + policy.slot_align_mask, c.has_infoz(), c.blocked_element_count(), dealloc); } @@ -1223,7 +1223,7 @@ void* alloc, size_t blocked_element_count) { return AllocBackingArray( common, policy, - RawHashSetLayout(new_capacity, policy.slot_size, policy.slot_align, + RawHashSetLayout(new_capacity, policy.slot_size, policy.slot_align_mask, has_infoz, blocked_element_count), alloc); } @@ -1329,8 +1329,9 @@ 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); + old_ctrl, slot_size, policy.slot_align_mask, + has_infoz, old_blocked_element_count, + policy.dealloc); } ResetGrowthLeft(new_capacity, common.size(), common); if (ABSL_PREDICT_FALSE(has_infoz)) { @@ -1914,7 +1915,7 @@ // Deallocate after `ReportSingleGroupTableGrowthToInfoz`, because it reads // infoz from old_ctrl. DeallocBackingArrayImpl(alloc, kOldCapacity, old_ctrl, slot_size, - policy.slot_align, has_infoz, + policy.slot_align_mask, has_infoz, /*blocked_element_count=*/0, policy.dealloc); return new_element_target_slot; } @@ -1995,17 +1996,15 @@ // Deallocate after `ReportGrowthToInfoz`, because it reads infoz from // old_ctrl. DeallocBackingArrayImpl(alloc, old_capacity, old_ctrl, slot_size, - policy.slot_align, has_infoz, + policy.slot_align_mask, 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) { +RawHashSetLayout RawHashSetLayout::CreateForSmallNonSooGrowth( + size_t size, size_t slot_size, size_t slot_align_mask, bool has_infoz) { ABSL_SWISSTABLE_ASSERT(size <= 1); static_assert(NumControlBytes(1) == 0); const size_t num_control_bytes = size * NumControlBytes(3); @@ -2027,7 +2026,7 @@ RawHashSetLayout layout(uninitialized_tag_t{}); layout.slot_offset_ = - AlignUpTo(metadata_size + num_control_bytes, slot_align); + AlignUpToMask(metadata_size + num_control_bytes, slot_align_mask); layout.control_offset_ = layout.slot_offset_ - num_control_bytes; layout.generation_offset_ = layout.control_offset_ - NumGenerationBytes(); layout.alloc_size_ = layout.slot_offset_ + slots_size; @@ -2061,7 +2060,7 @@ AllocBackingArray( common, policy, RawHashSetLayout::CreateForSmallNonSooGrowth( - size, policy.slot_size, policy.slot_align, has_infoz), + size, policy.slot_size, policy.slot_align_mask, has_infoz), alloc) .slots; if (is_empty) { @@ -2394,7 +2393,7 @@ } // Reducing from large capacity to SOO. ABSL_SWISSTABLE_ASSERT(slot_size <= sizeof(HeapOrSoo)); - ABSL_SWISSTABLE_ASSERT(policy.slot_align <= alignof(HeapOrSoo)); + ABSL_SWISSTABLE_ASSERT(policy.slot_align_mask < alignof(HeapOrSoo)); ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(cap)); HeapOrSoo tmp_slot; size_t begin_offset = FindFirstFullSlot(0, cap, common.control());
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 08cc0d1..a97bab2 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1219,17 +1219,26 @@ return (offset + align - 1) & (~align + 1); } +// Same as `AlignUpTo(offset, align_mask + 1)`. `align_mask` must be one less +// than a power of two. Taking the mask avoids negating the alignment (and with +// BMI1 the computation is just `add` + `andn`). +constexpr size_t AlignUpToMask(size_t offset, size_t align_mask) { + return (offset + align_mask) & ~align_mask; +} + // Helper class for computing offsets and allocation size of hash set fields. class RawHashSetLayout { public: + // `slot_align_mask` is `alignof(slot_type) - 1`. explicit RawHashSetLayout(size_t capacity, size_t slot_size, - size_t slot_align, bool has_infoz, + size_t slot_align_mask, bool has_infoz, size_t blocked_element_count) : control_offset_(MetadataBeforeControlSize(has_infoz, capacity)), generation_offset_(control_offset_ - NumGenerationBytes()), slot_offset_(control_offset_ + NumControlBytes(capacity)) { ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity)); - size_t aligned_slot_offset = AlignUpTo(slot_offset_, slot_align); + size_t aligned_slot_offset = + AlignUpToMask(slot_offset_, slot_align_mask); size_t slot_array_padding = aligned_slot_offset - slot_offset_; slot_offset_ = aligned_slot_offset; ABSL_SWISSTABLE_ASSERT( @@ -1246,7 +1255,7 @@ // 0 -> 1 (`size == 0`) or 1 -> 3 (`size == 1`). static RawHashSetLayout CreateForSmallNonSooGrowth(size_t size, size_t slot_size, - size_t slot_align, + size_t slot_align_mask, bool has_infoz); // Returns precomputed offset from the start of the backing allocation of @@ -1573,7 +1582,8 @@ // The size of the backing array allocation. size_t alloc_size(size_t slot_size, size_t slot_align) const { - return RawHashSetLayout(capacity(), slot_size, slot_align, has_infoz(), + return RawHashSetLayout(capacity(), slot_size, + /*slot_align_mask=*/slot_align - 1, has_infoz(), blocked_element_count()) .alloc_size(); } @@ -2013,7 +2023,9 @@ // 8 bytes uint32_t slot_size; - uint16_t slot_align; + // `alignof(slot_type) - 1`. Storing the mask instead of the alignment lets + // `AlignUpToMask` compute `(offset + mask) & ~mask` without negation. + uint16_t slot_align_mask; bool soo_enabled; bool is_hashtablez_enabled; // 8 bytes @@ -2073,7 +2085,8 @@ // functions, so we do not want to include non-destructor related fields. struct DtorPolicy { uint32_t slot_size; - uint16_t slot_align; + // `alignof(slot_type) - 1`. See `PolicyFunctions::slot_align_mask`. + uint16_t slot_align_mask; DestroySlotFn destroy_slot; template <uint32_t kSlotSize, uint16_t kSlotAlign> @@ -2092,15 +2105,17 @@ // to minimize the name length of static variables. template <uint32_t kSlotSize, uint16_t kSlotAlign> static const DtorPolicy& R() { - static constexpr DtorPolicy p = {kSlotSize, kSlotAlign, - /*destroy_slot=*/nullptr}; + static constexpr DtorPolicy p = { + kSlotSize, + /*slot_align_mask=*/static_cast<uint16_t>(kSlotAlign - 1), + /*destroy_slot=*/nullptr}; return p; } template <typename SetType> static const DtorPolicy& R() { static constexpr DtorPolicy p = { sizeof(typename SetType::slot_type), - alignof(typename SetType::slot_type), + /*slot_align_mask=*/alignof(typename SetType::slot_type) - 1, SetType::get_destroy_slot_fn(), }; return p; @@ -4298,7 +4313,7 @@ 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)), + /*slot_align_mask=*/static_cast<uint16_t>(alignof(slot_type) - 1), SooEnabled(), HashtablezForTableEnabled(), static_cast<uint32_t>(HasherOffset()),
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 65c8886..60fb142 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -128,7 +128,7 @@ { SCOPED_TRACE("capacity=1 no alignment after generation"); constexpr size_t kSlotSize = 1; - RawHashSetLayout layout(1, kSlotSize, /*slot_align=*/1, + RawHashSetLayout layout(1, kSlotSize, /*slot_align_mask=*/0, /*has_infoz=*/false, /*blocked_element_count=*/0); EXPECT_EQ(layout.control_offset(), NumGenerationBytes()); EXPECT_EQ(layout.slot_offset(), NumGenerationBytes()); @@ -138,7 +138,7 @@ SCOPED_TRACE("capacity=1 with alignment after generation"); constexpr size_t kSlotSize = 8; constexpr size_t kAlignment = 4; - RawHashSetLayout layout(1, kSlotSize, kAlignment, + RawHashSetLayout layout(1, kSlotSize, /*slot_align_mask=*/kAlignment - 1, /*has_infoz=*/false, /*blocked_element_count=*/0); EXPECT_EQ(layout.control_offset(), NumGenerationBytes() == 0 ? 0 : kAlignment); @@ -152,11 +152,13 @@ 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, + RawHashSetLayout expected(NextCapacity(size), slot_size, + /*slot_align_mask=*/slot_align - 1, has_infoz, /*blocked_element_count=*/0); RawHashSetLayout actual = RawHashSetLayout::CreateForSmallNonSooGrowth( - size, slot_size, slot_align, has_infoz); + size, slot_size, /*slot_align_mask=*/slot_align - 1, + 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()); @@ -178,7 +180,8 @@ << " padding: " << padding); ASSERT_GT(capacity, 1); ASSERT_LE(capacity, GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); - RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, + RawHashSetLayout layout(capacity, slot_size, + /*slot_align_mask=*/slot_align - 1, has_infoz, blocked_element_count); EXPECT_EQ(layout.control_offset(), padding + NumGenerationBytes()); size_t expected_slot_offset = @@ -214,7 +217,7 @@ TEST(RawHashSetLayout, SmallWithInfoZ) { { SCOPED_TRACE("capacity=1 no alignment after generation"); - RawHashSetLayout layout(1, /*slot_size=*/1, /*slot_align=*/1, + RawHashSetLayout layout(1, /*slot_size=*/1, /*slot_align_mask=*/0, /*has_infoz=*/true, /*blocked_element_count=*/0); EXPECT_EQ(layout.control_offset(), // growth_info is always 8 bytes for sampled tables. @@ -227,7 +230,7 @@ constexpr size_t kAlignment = 8; constexpr size_t kCapacity = 3; RawHashSetLayout layout(kCapacity, /*slot_size=*/kSlotSize, - /*slot_align=*/kAlignment, + /*slot_align_mask=*/kAlignment - 1, /*has_infoz=*/true, /*blocked_element_count=*/0); size_t padding = NumGenerationBytes() == 0 ? 1 : 0; padding += sizeof(HashtablezInfoHandle) == 4 ? 0 : 4; @@ -253,7 +256,8 @@ << " slot_align: " << slot_align << " has_infoz: " << has_infoz << " blocked_element_count: " << blocked_element_count); ASSERT_GT(capacity, GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); - RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, + RawHashSetLayout layout(capacity, slot_size, + /*slot_align_mask=*/slot_align - 1, has_infoz, blocked_element_count); size_t padding = NumGenerationBytes() == 0 ? 1 : 0; EXPECT_EQ(layout.control_offset(),