Store only `control` in SwissTable header. This has following effects: 1. sizeof() reduced 24->16 bytes. 2. maximum Soo size reduced 16->8 bytes. 3. load of slot_array is removed. 4. slot_array is computed as `control + capacity + Group::kWidth`. 5. In log-capacity mode (default), we explicitly compute capacity and use and/andn instead of bzhi. Since we need capacity to compute slot_array, using regular bit operations is preferable. 6. For small table (1 element) slot_array == control. Generation is now stored before control to simplify computations for small table case. `find_large` is not accepting hash anymore with a following motivation: 1. if compiler doesn't inline find_large: (a) more code is out of the line (b) hash computation instructions can be computed in parallel with slot_array pointer computation 2. find_large becoming slightly larger, so this change is relevant to the main change. PiperOrigin-RevId: 944289094 Change-Id: Id16e0ba7c4e67252c26c238c30d9225ad59b61dc
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 6c94b53..3fda249 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -97,7 +97,7 @@ // `min(1, RehashProbabilityConstant() / capacity())`. In order to do this, // we probe based on a random hash and see if the offset is less than // RehashProbabilityConstant(). - return probe(HashtableCapacity(capacity), absl::HashOf(RandomSeed())) + return probe(ProbeCapacity{capacity}, absl::HashOf(RandomSeed())) .offset() < RehashProbabilityConstant(); } @@ -189,11 +189,12 @@ FindInfo find_first_non_full_from_h1(const ctrl_t* ctrl, size_t h1, HashtableCapacity capacity) { - auto seq = probe_h1(capacity, h1); + const size_t cap = capacity.capacity(); + auto seq = probe_h1(ProbeCapacity{cap}, h1); if (IsEmptyOrDeleted(ctrl[seq.offset()])) { return {seq.offset(), /*probe_length=*/0}; } - auto mask = probe_till_first_non_full_group(ctrl, seq, capacity.capacity()); + auto mask = probe_till_first_non_full_group(ctrl, seq, cap); return {seq.offset(mask.LowestBitSet()), seq.index()}; } @@ -1123,7 +1124,6 @@ const auto [new_ctrl, new_slots] = AllocBackingArray( common, policy, new_capacity, has_infoz, alloc, blocked_element_count); common.set_control(new_ctrl); - common.set_slots(new_slots); common.generate_new_seed(has_infoz); ResetCtrl(common, slot_size, blocked_element_count); @@ -1146,20 +1146,19 @@ void* new_slots, bool has_infoz) { ABSL_SWISSTABLE_ASSERT(c.size() == policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(policy.soo_enabled); - size_t new_capacity = c.capacity(); + 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(c.capacity_impl(), soo_slot_hash).offset(); + 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); - c.set_slots(new_slots); ResetCtrl(c, policy.slot_size, /*blocked_element_count=*/0); SetCtrl(c, offset, H2(soo_slot_hash), policy.slot_size); } @@ -1718,8 +1717,7 @@ ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); constexpr size_t kOldCapacity = 1; constexpr size_t kNewCapacity = NextCapacity(kOldCapacity); - ctrl_t* old_ctrl = common.control(); - void* old_slots = common.slot_array(); + void* old_slots = common.slot_array(kOldCapacity); const size_t slot_size = policy.slot_size; const size_t slot_align = policy.slot_align; @@ -1732,7 +1730,6 @@ AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc, /*blocked_element_count=*/0); common.set_control(new_ctrl); - common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, kNewCapacity * slot_size); if (ABSL_PREDICT_TRUE(!has_infoz)) { @@ -1753,8 +1750,10 @@ void* new_element_target_slot = SlotAddress(new_slots, offset, slot_size); SanitizerUnpoisonMemoryRegion(new_element_target_slot, slot_size); - policy.dealloc(alloc, kOldCapacity, old_ctrl, slot_size, slot_align, - has_infoz, + policy.dealloc(alloc, kOldCapacity, + // old_slots == old_ctrl in case of capacity == 1. + static_cast<ctrl_t*>(old_slots), + slot_size, slot_align, has_infoz, /*blocked_element_count=*/0); PrepareInsertCommon(common); ABSL_SWISSTABLE_ASSERT(common.size() == 2); @@ -1783,19 +1782,18 @@ void* old_slots = common.slot_array(); size_t old_blocked_element_count = common.blocked_element_count(); + HashtablezInfoHandle infoz = common.infoz(); + const bool has_infoz = infoz.IsSampled(); 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); - HashtablezInfoHandle infoz = common.infoz(); - const bool has_infoz = infoz.IsSampled(); const auto [new_ctrl, new_slots] = AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, /*blocked_element_count=*/0); common.set_control(new_ctrl); - common.set_slots(new_slots); SanitizerPoisonMemoryRegion(new_slots, new_capacity * slot_size); h2_t new_h2 = H2(new_hash); @@ -1881,7 +1879,6 @@ AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc, /*blocked_element_count=*/0); common.set_control(new_ctrl); - common.set_slots(new_slots); static_assert(NextCapacity(0) == 1); PrepareInsertCommon(common); @@ -2116,7 +2113,6 @@ AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, /*blocked_element_count=*/0); common.set_control(new_ctrl); - common.set_slots(new_slots); common.generate_new_seed(has_infoz); size_t total_probe_length = 0; @@ -2196,7 +2192,6 @@ policy.transfer_n(&common, target_slot, common.soo_data(), 1); } common.set_control(new_ctrl); - common.set_slots(new_slots); // Full SOO table couldn't be sampled. If SOO table is sampled, it would // have been resized to the next capacity. @@ -2455,21 +2450,16 @@ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, bool); +#if UINTPTR_MAX == UINT32_MAX +static_assert(MaxSooSlotSize() == 4); +static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(2, 4)); +#else static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(4, 8)); template void* GrowSooTableToNextCapacityAndPrepareInsert< OptimalMemcpySizeForSooSlotTransfer(8), true>( CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, bool); - -#if UINTPTR_MAX == UINT32_MAX static_assert(MaxSooSlotSize() == 8); -#else -static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(9, 16)); -template void* GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(16), true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, - bool); -static_assert(MaxSooSlotSize() == 16); #endif template void* AllocateBackingArray<BackingArrayAlignment(alignof(size_t)),
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 6d0e4ef..dbed05f 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -230,10 +230,6 @@ #include <ranges> // NOLINT(build/c++20) #endif -#if defined(__i386__) || defined(__x86_64__) -#include <immintrin.h> -#endif - namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { @@ -563,19 +559,6 @@ return capacity_data_ <= 1; } - constexpr size_t mask(size_t value) const { -#ifdef __BMI2__ - if constexpr (StorageMode == kCapacityByLog) { - if constexpr (sizeof(size_t) == 8) { - return _bzhi_u64(value, capacity_data_); - } else { - return _bzhi_u32(value, capacity_data_); - } - } -#endif // __BMI2__ - return value & capacity(); - } - private: // We use these sentinel capacity values in debug mode to indicate different // classes of bugs. @@ -1043,7 +1026,8 @@ static constexpr uint64_t kLowerBoundShift = 64 - 8; explicit GrowthInfoAccessor(void* control) - : growth_info_lower_bound_(reinterpret_cast<uint8_t*>(control) - 1) {} + : growth_info_lower_bound_(reinterpret_cast<uint8_t*>(control) - 1 - + NumGenerationBytes()) {} // Initializes the GrowthInfo assuming we can grow `growth_left` elements // and there are no kDeleted slots in the table. @@ -1131,15 +1115,16 @@ : sizeof(uint64_t); } -// Computes the size of the metadata before the control bytes. -// infoz and growth_info are stored at the beginning of the backing array. +// Computes the size of the metadata before the control bytes. infoz, +// growth_info and generation are stored at the beginning of the backing array. constexpr size_t MetadataBeforeControlSize(bool has_infoz, size_t capacity) { if (ABSL_PREDICT_FALSE(has_infoz)) { // We always allocate 8 bytes of growth info for sampled tables to allow // branchless access to infoz pointer. - return sizeof(HashtablezInfoHandle) + sizeof(uint64_t); + return sizeof(HashtablezInfoHandle) + sizeof(uint64_t) + + NumGenerationBytes(); } - return GrowthInfoSizeForCapacity(capacity); + return GrowthInfoSizeForCapacity(capacity) + NumGenerationBytes(); } // Returns the offset of the next item after `offset` that is aligned to `align` @@ -1155,19 +1140,20 @@ size_t slot_align, bool has_infoz, size_t blocked_element_count) : control_offset_(MetadataBeforeControlSize(has_infoz, capacity)), - generation_offset_(control_offset_ + NumControlBytes(capacity)), - slot_offset_( - AlignUpTo(generation_offset_ + NumGenerationBytes(), slot_align)), - alloc_size_(slot_offset_ + - (capacity - blocked_element_count) * slot_size) { + 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 slot_array_padding = aligned_slot_offset - slot_offset_; + slot_offset_ = aligned_slot_offset; ABSL_SWISSTABLE_ASSERT( slot_size <= ((std::numeric_limits<size_t>::max)() - slot_offset_) / capacity); - slot_array_padding_ = - slot_offset_ - generation_offset_ - NumGenerationBytes(); - control_offset_ += slot_array_padding_; - generation_offset_ += slot_array_padding_; + control_offset_ += slot_array_padding; + generation_offset_ += slot_array_padding; + ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(capacity) || + control_offset_ == slot_offset_); + alloc_size_ = slot_offset_ + (capacity - blocked_element_count) * slot_size; } // Returns precomputed offset from the start of the backing allocation of @@ -1191,7 +1177,6 @@ size_t generation_offset_; size_t slot_offset_; size_t alloc_size_; - size_t slot_array_padding_; }; struct HashtableFreeFunctionsAccess; @@ -1215,11 +1200,6 @@ // Note that growth_info is stored immediately before this pointer. // May be uninitialized for small tables. MaybeInitializedPtr<ctrl_t> control; - - // The beginning of the slots, located at `SlotOffset()` bytes after - // `control`. May be uninitialized for empty tables. - // Note: we can't use `slots` because Qt defines "slots" as a macro. - MaybeInitializedPtr<void> slot_array; }; // Returns the maximum size of the SOO slot. @@ -1234,12 +1214,6 @@ MaybeInitializedPtr<ctrl_t> control() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control); } - MaybeInitializedPtr<void>& slot_array() { - ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.slot_array); - } - MaybeInitializedPtr<void> slot_array() const { - ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.slot_array); - } void* get_soo_data() { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(soo_data); } @@ -1310,8 +1284,16 @@ void set_control(ctrl_t* c) { heap_or_soo_.control().set(c); } // Note: we can't use slots() because Qt defines "slots" as a macro. - void* slot_array() const { return heap_or_soo_.slot_array().get(); } - void set_slots(void* s) { heap_or_soo_.slot_array().set(s); } + void* slot_array() const { return slot_array(capacity()); } + // Returns pointer to the slots of a table with explicit capacity that must be + // equal to the actual capacity of the table. + // Useful for capacity known at compile time and capacity in register with + // ABSL_ASSUME conditions. + void* slot_array(size_t capacity) const { + ABSL_SWISSTABLE_ASSERT(capacity == this->capacity()); + ctrl_t* ctrl = control(); + return ctrl + NumControlBytes(capacity); + } // The number of filled slots. size_t size() const { return inline_data_.size(); } @@ -1487,12 +1469,9 @@ void AssertNotDebugCapacityImpl() const; - // TODO(b/289225379): we could put size_ into HeapOrSoo and make capacity_ - // encode the size in SOO case. We would be making size()/capacity() more - // expensive in order to have more SOO space. HashtableInlineData inline_data_; - // Either the control/slots pointers or the SOO slot. + // Either the heap pointer or the SOO slot. HeapOrSoo heap_or_soo_; }; @@ -1716,6 +1695,10 @@ size_t probe_length; }; +struct ProbeCapacity { + size_t capacity; +}; + // The state for a probe sequence. // // Currently, the sequence is a triangular progression of the form @@ -1743,37 +1726,36 @@ // Creates a new probe sequence using `hash` as the initial value of the // sequence and `capacity` as the mask to apply to each value in the // progression. - probe_seq(HashtableCapacity capacity, size_t hash) - : capacity_(capacity), offset_(capacity.mask(hash)) {} + probe_seq(ProbeCapacity capacity, size_t hash) + : capacity_(capacity.capacity), offset_(hash & capacity_) {} // The offset within the table, i.e., the value `p(i)` above. size_t offset() const { return offset_; } - size_t offset(size_t i) const { return capacity_.mask(offset_ + i); } + size_t offset(size_t i) const { return (offset_ + i) & capacity_; } void next() { index_ += Width; offset_ += index_; - offset_ = capacity_.mask(offset_); + offset_ &= capacity_; } // 0-based probe index, a multiple of `Width`. size_t index() const { return index_; } private: - HashtableCapacity capacity_; + size_t capacity_; size_t offset_; size_t index_ = 0; }; // Begins a probing operation on `common.control`, using `hash`. -inline probe_seq<Group::kWidth> probe_h1(HashtableCapacity capacity, - size_t h1) { +inline probe_seq<Group::kWidth> probe_h1(ProbeCapacity capacity, size_t h1) { return probe_seq<Group::kWidth>(capacity, h1); } -inline probe_seq<Group::kWidth> probe(HashtableCapacity capacity, size_t hash) { +inline probe_seq<Group::kWidth> probe(ProbeCapacity capacity, size_t hash) { return probe_h1(capacity, H1(hash)); } inline probe_seq<Group::kWidth> probe(const CommonFields& common, size_t hash) { - return probe(common.capacity_impl(), hash); + return probe(ProbeCapacity{common.capacity()}, hash); } constexpr size_t kProbedElementIndexSentinel = ~size_t{}; @@ -2025,29 +2007,20 @@ // instantiations. constexpr size_t OptimalMemcpySizeForSooSlotTransfer( size_t slot_size, size_t max_soo_slot_size = MaxSooSlotSize()) { - static_assert(MaxSooSlotSize() >= 8, "unexpectedly small SOO slot size"); + static_assert(MaxSooSlotSize() >= 4, "unexpectedly small SOO slot size"); + static_assert(MaxSooSlotSize() <= 8, "unexpectedly large SOO slot size"); if (slot_size == 1) { return 1; } if (slot_size <= 3) { return 4; } + if (slot_size == max_soo_slot_size) { + return max_soo_slot_size; + } // We are merging 4 and 8 into one case because we expect them to be the // hottest cases. Copying 8 bytes is as fast on common architectures. - if (slot_size <= 8) { - return 8; - } - if (max_soo_slot_size <= 16) { - return max_soo_slot_size; - } - if (slot_size <= 16) { - return 16; - } - if (max_soo_slot_size <= 24) { - return max_soo_slot_size; - } - static_assert(MaxSooSlotSize() <= 24, "unexpectedly large SOO slot size"); - return 24; + return 8; } // Resizes SOO table to the NextCapacity(SooCapacity()) and prepares insert for @@ -2414,7 +2387,7 @@ slot_(slot) { // This assumption helps the compiler know that any non-end iterator is // not equal to any end iterator. - ABSL_ASSUME(slot != nullptr); // NOLINT + ABSL_ASSUME(slot != nullptr); } // For end() iterators. explicit iterator(const GenerationType* generation_ptr) @@ -3203,7 +3176,7 @@ AssertOnFind(key); if (is_small()) return find_small(key); prefetch_heap_block(); - return find_large(key, hash_of(key)); + return find_large(key); } template <class K = key_type> @@ -3361,29 +3334,34 @@ // TODO(b/289225379): consider having a helper class that has the impls for // SOO functionality. template <class K = key_type> - iterator find_small(const key_arg<K>& key) { + ABSL_ATTRIBUTE_ALWAYS_INLINE iterator find_small(const key_arg<K>& key) { ABSL_SWISSTABLE_ASSERT(is_small()); return empty() || !equal_to(key, single_slot()) ? end() : single_iterator(); } template <class K = key_type> - iterator find_large(const key_arg<K>& key, size_t hash) { + iterator find_large(const key_arg<K>& key) { ABSL_SWISSTABLE_ASSERT(!is_small()); - auto seq = probe(common(), hash); + const size_t cap = common().capacity(); + ABSL_ASSUME(cap > 1); + const size_t hash = hash_of(key); + auto seq = probe(ProbeCapacity{cap}, hash); const h2_t h2 = H2(hash); - const ctrl_t* ctrl = control(); + ctrl_t* ctrl = control(); + slot_type* slot_array = to_slot(common().slot_array(cap)); while (true) { #ifndef ABSL_HAVE_MEMORY_SANITIZER - absl::PrefetchToLocalCache(slot_array() + seq.offset()); + absl::PrefetchToLocalCache(slot_array + seq.offset()); #endif Group g{ctrl + seq.offset()}; for (uint32_t i : g.Match(h2)) { - if (ABSL_PREDICT_TRUE(equal_to(key, slot_array() + seq.offset(i)))) - return iterator_at(seq.offset(i)); + const size_t offset = seq.offset(i); + if (ABSL_PREDICT_TRUE(equal_to(key, slot_array + offset))) + return iterator_at_ptr(ctrl + offset, slot_array + offset); } if (ABSL_PREDICT_TRUE(g.MaskEmpty())) return end(); seq.next(); - ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity() && "full table!"); + ABSL_SWISSTABLE_ASSERT(seq.index() <= cap && "full table!"); } } @@ -3649,17 +3627,20 @@ std::pair<slot_type*, bool> find_or_prepare_insert_large(const K& key) { ABSL_SWISSTABLE_ASSERT(!is_soo()); prefetch_heap_block(); + const size_t cap = capacity(); + ABSL_ASSUME(cap > 1); const size_t hash = hash_of(key); - auto seq = probe(common(), hash); + auto seq = probe(ProbeCapacity{cap}, hash); const h2_t h2 = H2(hash); const ctrl_t* ctrl = control(); + slot_type* slot_array = to_slot(common().slot_array(cap)); while (true) { #ifndef ABSL_HAVE_MEMORY_SANITIZER - absl::PrefetchToLocalCache(slot_array() + seq.offset()); + absl::PrefetchToLocalCache(slot_array + seq.offset()); #endif Group g{ctrl + seq.offset()}; for (uint32_t i : g.Match(h2)) { - slot_type* slot = slot_array() + seq.offset(i); + slot_type* slot = slot_array + seq.offset(i); if (ABSL_PREDICT_TRUE(equal_to(key, slot))) { return {slot, false}; } @@ -3781,9 +3762,9 @@ const_iterator iterator_at(size_t i) const ABSL_ATTRIBUTE_LIFETIME_BOUND { return const_cast<raw_hash_set*>(this)->iterator_at(i); } - iterator iterator_at_ptr(std::pair<ctrl_t*, void*> ptrs) + iterator iterator_at_ptr(ctrl_t* ctrl, void* slot) ABSL_ATTRIBUTE_LIFETIME_BOUND { - return {ptrs.first, to_slot(ptrs.second), common().generation_ptr()}; + return {ctrl, to_slot(slot), common().generation_ptr()}; } reference unchecked_deref(iterator it) { return it.unchecked_deref(); } @@ -3830,7 +3811,9 @@ } slot_type* single_slot() { ABSL_SWISSTABLE_ASSERT(is_small()); - return SooEnabled() ? soo_slot() : slot_array(); + return SooEnabled() + ? soo_slot() + : to_slot(common().slot_array(/*capacity=*/1)); } const slot_type* single_slot() const { return const_cast<raw_hash_set*>(this)->single_slot(); @@ -4132,11 +4115,8 @@ extern template void* GrowSooTableToNextCapacityAndPrepareInsert<4, true>( CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, bool); -extern template void* GrowSooTableToNextCapacityAndPrepareInsert<8, true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, - bool); #if UINTPTR_MAX == UINT64_MAX -extern template void* GrowSooTableToNextCapacityAndPrepareInsert<16, true>( +extern template void* GrowSooTableToNextCapacityAndPrepareInsert<8, true>( CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, bool); #endif
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index d4160ce..fe987cd 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -128,7 +128,7 @@ constexpr size_t kSlotSize = 1; RawHashSetLayout layout(1, kSlotSize, /*slot_align=*/1, /*has_infoz=*/false, /*blocked_element_count=*/0); - EXPECT_EQ(layout.control_offset(), 0); + EXPECT_EQ(layout.control_offset(), NumGenerationBytes()); EXPECT_EQ(layout.slot_offset(), NumGenerationBytes()); EXPECT_EQ(layout.alloc_size(), NumGenerationBytes() + kSlotSize); } @@ -138,9 +138,8 @@ constexpr size_t kAlignment = 4; RawHashSetLayout layout(1, kSlotSize, kAlignment, /*has_infoz=*/false, /*blocked_element_count=*/0); - EXPECT_EQ(layout.control_offset(), NumGenerationBytes() == 0 - ? 0 - : kAlignment - NumGenerationBytes()); + EXPECT_EQ(layout.control_offset(), + NumGenerationBytes() == 0 ? 0 : kAlignment); EXPECT_EQ(layout.slot_offset(), NumGenerationBytes() == 0 ? 0 : kAlignment); EXPECT_EQ(layout.alloc_size(), layout.slot_offset() + kSlotSize); } @@ -159,12 +158,12 @@ ASSERT_LE(capacity, GrowthInfoLowerBound::kMaxGrowthLeftLowerBound); RawHashSetLayout layout(capacity, slot_size, slot_align, has_infoz, blocked_element_count); - EXPECT_EQ(layout.control_offset(), 1 + padding); // 1 byte for growth_info + EXPECT_EQ(layout.control_offset(), + /*growth*/ 1 + padding + NumGenerationBytes()); size_t expected_slot_offset = - capacity + NumClonedBytes() + 1 + /*growth*/ 1 + NumGenerationBytes(); + layout.control_offset() + NumControlBytes(capacity); EXPECT_LT(padding, slot_align); - EXPECT_EQ((expected_slot_offset + padding) % slot_align, 0); - expected_slot_offset += padding; + EXPECT_EQ(expected_slot_offset % slot_align, 0); EXPECT_EQ(layout.slot_offset(), expected_slot_offset); size_t allocated_values = capacity - blocked_element_count; EXPECT_EQ(layout.alloc_size(), @@ -194,9 +193,8 @@ /*has_infoz=*/true, /*blocked_element_count=*/0); EXPECT_EQ(layout.control_offset(), // growth_info is always 8 bytes for sampled tables. - 8 + sizeof(HashtablezInfoHandle)); - EXPECT_EQ(layout.slot_offset(), - layout.control_offset() + NumGenerationBytes()); + 8 + sizeof(HashtablezInfoHandle) + NumGenerationBytes()); + EXPECT_EQ(layout.slot_offset(), layout.control_offset()); EXPECT_EQ(layout.alloc_size(), layout.slot_offset() + 1); } { @@ -210,10 +208,10 @@ padding += sizeof(HashtablezInfoHandle) == 4 ? 0 : 4; EXPECT_EQ(layout.control_offset(), // growth_info is always 8 bytes for sampled tables. - 8 + sizeof(HashtablezInfoHandle) + padding); + /*growth*/ 8 + sizeof(HashtablezInfoHandle) + padding + + NumGenerationBytes()); size_t expected_slot_offset = - layout.control_offset() + kCapacity + NumClonedBytes() + 1 + - NumGenerationBytes(); + layout.control_offset() + NumControlBytes(kCapacity); EXPECT_EQ(expected_slot_offset % kAlignment, 0); EXPECT_EQ(layout.slot_offset(), expected_slot_offset); EXPECT_EQ(layout.alloc_size(), @@ -234,9 +232,10 @@ blocked_element_count); size_t padding = NumGenerationBytes() == 0 ? 1 : 0; EXPECT_EQ(layout.control_offset(), - padding + (has_infoz ? 8 + sizeof(HashtablezInfoHandle) : 8)); - size_t expected_slot_offset = layout.control_offset() + capacity + - NumClonedBytes() + 1 + NumGenerationBytes(); + padding + (has_infoz ? 8 + sizeof(HashtablezInfoHandle) : 8) + + NumGenerationBytes()); + size_t expected_slot_offset = + layout.control_offset() + NumControlBytes(capacity); EXPECT_EQ(expected_slot_offset % slot_align, 0); EXPECT_EQ(layout.slot_offset(), expected_slot_offset); EXPECT_EQ( @@ -259,17 +258,24 @@ if (capacity <= GrowthInfoLowerBound::kMaxGrowthLeftLowerBound) { SanitizerPoisonMemoryRegion(control_.data(), 7); } - SanitizerPoisonMemoryRegion(control_.data() + 8, 1); + SanitizerPoisonMemoryRegion(control_.data() + kControlStart, 1); + if constexpr (NumGenerationBytes() > 0) { + SanitizerPoisonMemoryRegion( + control_.data() + kControlStart + NumGenerationBytes(), + NumGenerationBytes()); + } } GrowthInfoAccessor* operator->() { return &growth_info_; } private: + static constexpr size_t kControlStart = 8 + NumGenerationBytes(); // We allocate on heap since ASAN fails to detect access to poisoned memory // on stack. - std::vector<ctrl_t> control_ = - std::vector<ctrl_t>(9, /*garbage*/ ctrl_t::kSentinel); - GrowthInfoAccessor growth_info_ = GrowthInfoAccessor(control_.data() + 8); + std::vector<ctrl_t> control_ = std::vector<ctrl_t>( + 9 + NumGenerationBytes(), /*garbage*/ ctrl_t::kSentinel); + GrowthInfoAccessor growth_info_ = + GrowthInfoAccessor(control_.data() + kControlStart); }; TEST(GrowthInfoViewTest, GetGrowthLeft) { @@ -547,33 +553,11 @@ EXPECT_EQ(1, OptimalMemcpySizeForSooSlotTransfer(1)); ASSERT_EQ(4, OptimalMemcpySizeForSooSlotTransfer(2)); ASSERT_EQ(4, OptimalMemcpySizeForSooSlotTransfer(3)); - for (size_t slot_size = 4; slot_size <= 8; ++slot_size) { - ASSERT_EQ(8, OptimalMemcpySizeForSooSlotTransfer(slot_size)); - } - // If maximum amount of memory is 16, then we can copy up to 16 bytes. - for (size_t slot_size = 9; slot_size <= 16; ++slot_size) { - ASSERT_EQ(16, - OptimalMemcpySizeForSooSlotTransfer(slot_size, - /*max_soo_slot_size=*/16)); - ASSERT_EQ(16, - OptimalMemcpySizeForSooSlotTransfer(slot_size, - /*max_soo_slot_size=*/24)); - } - // But we shouldn't try to copy more than maximum amount of memory. - for (size_t slot_size = 9; slot_size <= 12; ++slot_size) { - ASSERT_EQ(12, OptimalMemcpySizeForSooSlotTransfer( - slot_size, /*max_soo_slot_size=*/12)); - } - for (size_t slot_size = 17; slot_size <= 24; ++slot_size) { - ASSERT_EQ(24, - OptimalMemcpySizeForSooSlotTransfer(slot_size, - /*max_soo_slot_size=*/24)); - } - // We shouldn't copy more than maximum. - for (size_t slot_size = 17; slot_size <= 20; ++slot_size) { - ASSERT_EQ(20, - OptimalMemcpySizeForSooSlotTransfer(slot_size, - /*max_soo_slot_size=*/20)); + ASSERT_EQ(4, OptimalMemcpySizeForSooSlotTransfer(4, /*max_soo_slot_size=*/4)); + if constexpr (MaxSooSlotSize() > 4) { + for (size_t slot_size = 4; slot_size <= 8; ++slot_size) { + ASSERT_EQ(8, OptimalMemcpySizeForSooSlotTransfer(slot_size)); + } } } @@ -651,8 +635,8 @@ } TEST(Util, probe_seq) { - HashtableCapacity capacity(127); - probe_seq<16> seq(capacity, /*hash=*/0); + size_t capacity = 127; + probe_seq<16> seq(ProbeCapacity{capacity}, /*hash=*/0); auto gen = [&]() { size_t res = seq.offset(); seq.next(); @@ -661,7 +645,7 @@ std::vector<size_t> offsets(8); std::generate_n(offsets.begin(), 8, gen); EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64)); - seq = probe_seq<16>(capacity, /*hash=*/128); + seq = probe_seq<16>(ProbeCapacity{capacity}, /*hash=*/128); std::generate_n(offsets.begin(), 8, gen); EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64)); } @@ -995,6 +979,8 @@ bool operator==(const SizedValue& rhs) const { return **this == *rhs; } private: + static_assert(N % sizeof(int64_t) == 0); + static_assert(N >= sizeof(int64_t)); int64_t vals_[N / sizeof(int64_t)]; }; template <int N, bool kSoo> @@ -1262,7 +1248,7 @@ using Base::Base; }; -constexpr size_t kNonSooSize = sizeof(HeapOrSoo) + 8; +constexpr size_t kNonSooSize = 2 * sizeof(HeapOrSoo); using NonSooIntTableSlotType = SizedValue<kNonSooSize>; static_assert(sizeof(NonSooIntTableSlotType) > MaxSooSlotSize(), "too small"); using NonSooIntTable = ValueTable<NonSooIntTableSlotType>; @@ -1294,12 +1280,10 @@ size_t capacity; uint64_t size; void* ctrl; - void* slots; }; struct MockTableByLog { uint64_t size; void* ctrl; - void* slots; }; using MockTable = std::conditional_t<HashtableInlineData::kStorageMode == kCapacityByValue, @@ -4745,16 +4729,10 @@ "hash table was modified unexpectedly"); } -template <typename T> -class SooTable : public testing::Test {}; -using FreezableSooTableTypes = - ::testing::Types<FreezableSizedValueSooTable<8>, - FreezableSizedValueSooTable<16>>; -TYPED_TEST_SUITE(SooTable, FreezableSooTableTypes); - -TYPED_TEST(SooTable, Basic) { +TEST(SooTable, Basic) { bool frozen = true; - TypeParam t{FreezableAlloc<typename TypeParam::value_type>(&frozen)}; + FreezableSizedValueSooTable<8> t{ + FreezableAlloc<FreezableSizedValueSooTable<8>::value_type>(&frozen)}; if (t.capacity() != SooCapacity()) { CHECK_LT(sizeof(void*), 8) << "missing SOO coverage"; GTEST_SKIP() << "not SOO on this platform";