Split AllocPolicy out of PolicyFunctions in raw_hash_set. Move layout and allocation information that is not needed by hot insert paths from `PolicyFunctions` into a separate `AllocPolicy`, referenced from `PolicyFunctions::alloc_policy`. Tables with the same slot/key/value sizes and a standard allocator share a single `AllocPolicy` instance. - New `HashtableTypeInfo` in `container_memory.h` holds the numeric fields (`slot_size`, `slot_align_mask`, `soo_enabled`, `is_hashtablez_enabled`, `alloc_offset`, `key_size`, `value_size`); `AllocPolicy` inherits it and adds `alloc` and `dealloc` (40 bytes). - `PolicyFunctions` shrinks from 64 to 40 bytes. `slot_size` is duplicated at offset 0 so hot paths (`PrepareInsertLarge*`, `GrowToNextCapacity*`, `RehashOrGrowToNextCapacityAndPrepareInsert`) never dereference `alloc_policy`. - `ForcedTrySample` takes `const HashtableTypeInfo&` instead of four size arguments and returns an unsampled handle when `is_hashtablez_enabled` is false. - `HashtableSooCapacity()` is added to `container_memory.h`; `SooCapacity()` forwards to it. - `Clear`, `ClearBackingArray*`, `AllocBackingArray`, `DeallocBackingArrayImpl` and `ResizeEmptyNonAllocatedTableImpl` take `const AllocPolicy&` directly. PiperOrigin-RevId: 1004649807
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index fea8605..345371a 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -654,6 +654,7 @@ "//absl:__subpackages__", ], deps = [ + ":container_memory", "//absl/base", "//absl/base:config", "//absl/base:core_headers",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 6432a69..5b33ebf 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -667,6 +667,7 @@ DEPS absl::base absl::config + absl::container_memory absl::exponential_biased absl::no_destructor absl::raw_logging_internal
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 175012f..065d97a 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -43,6 +43,38 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { +// We only allow a maximum of 1 SOO element, which makes the implementation +// much simpler. Complications with multiple SOO elements include: +// - Satisfying the guarantee that erasing one element doesn't invalidate +// iterators to other elements means we would probably need actual SOO +// control bytes. +// - In order to prevent user code from depending on iteration order for small +// tables, we would need to randomize the iteration order somehow. +constexpr size_t HashtableSooCapacity() { return 1; } + +// HashtableTypeInfo bundles the numeric properties of a raw_hash_set<T, ...> +// instantiation. It is defined here (rather than in raw_hash_set.h) so that +// hashtablez sampling can receive a pointer to it instead of several separate +// size arguments. +struct HashtableTypeInfo { + // 8 bytes + uint32_t slot_size; + // `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 + uint32_t alloc_offset; + uint32_t key_size; + // 4 bytes + uint32_t value_size; + + constexpr uint8_t soo_capacity() const { + return static_cast<uint8_t>(soo_enabled ? HashtableSooCapacity() : 0); + } +}; + template <size_t Alignment> struct alignas(Alignment) AlignedType { // When alignment is sufficient for the allocated memory to store pointers,
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 8942cc3..82929bb 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc
@@ -31,6 +31,7 @@ #include "absl/base/macros.h" #include "absl/base/no_destructor.h" #include "absl/base/optimization.h" +#include "absl/container/internal/container_memory.h" #include "absl/debugging/stacktrace.h" #include "absl/memory/memory.h" #include "absl/profiling/internal/exponential_biased.h" @@ -124,12 +125,11 @@ } #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -HashtablezInfoHandle ForcedTrySample(size_t inline_element_size, - size_t key_size, size_t value_size, - uint16_t soo_capacity) { - return HashtablezInfoHandle(SampleSlow(global_next_sample, - inline_element_size, key_size, - value_size, soo_capacity)); +HashtablezInfoHandle ForcedTrySample(const HashtableTypeInfo& info) { + if (!info.is_hashtablez_enabled) return HashtablezInfoHandle(nullptr); + return HashtablezInfoHandle( + SampleSlow(global_next_sample, info.slot_size, info.key_size, + info.value_size, info.soo_capacity())); } void TestOnlyRefreshSamplingStateForCurrentThread() { global_next_sample.next_sample = @@ -137,7 +137,7 @@ global_next_sample.sample_stride = global_next_sample.next_sample; } #else -HashtablezInfoHandle ForcedTrySample(size_t, size_t, size_t, uint16_t) { +HashtablezInfoHandle ForcedTrySample(const HashtableTypeInfo&) { return HashtablezInfoHandle{nullptr}; } void TestOnlyRefreshSamplingStateForCurrentThread() {}
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h index 628acf6..0c7d63a 100644 --- a/absl/container/internal/hashtablez_sampler.h +++ b/absl/container/internal/hashtablez_sampler.h
@@ -52,6 +52,7 @@ #include "absl/base/internal/per_thread_tls.h" #include "absl/base/optimization.h" #include "absl/base/thread_annotations.h" +#include "absl/container/internal/container_memory.h" #include "absl/profiling/internal/sample_recorder.h" #include "absl/synchronization/mutex.h" #include "absl/time/time.h" @@ -237,10 +238,9 @@ // Returns a sampling handle. // Must be called only if HashSetShouldBeSampled() returned true. -// Returned handle still can be unsampled if sampling is not possible. -HashtablezInfoHandle ForcedTrySample(size_t inline_element_size, - size_t key_size, size_t value_size, - uint16_t soo_capacity); +// Returned handle still can be unsampled if sampling is not possible or if +// `info.is_hashtablez_enabled` is false. +HashtablezInfoHandle ForcedTrySample(const HashtableTypeInfo& info); // In case sampling needs to be disabled and re-enabled in tests, this function // can be used to reset the sampling state for the current thread. @@ -255,8 +255,16 @@ if (ABSL_PREDICT_TRUE(!ShouldSampleNextTable())) { return HashtablezInfoHandle(nullptr); } - return ForcedTrySample(inline_element_size, key_size, value_size, - soo_capacity); + const HashtableTypeInfo info = { + static_cast<uint32_t>(inline_element_size), + /*slot_align_mask=*/0, // Unused by sampling. + /*soo_enabled=*/soo_capacity != 0, + /*is_hashtablez_enabled=*/true, + /*alloc_offset=*/0, // Unused by sampling. + static_cast<uint32_t>(key_size), + static_cast<uint32_t>(value_size), + }; + return ForcedTrySample(info); } using HashtablezSampler =
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 2608357..d7e1059 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -314,7 +314,7 @@ that.set_capacity(this == &that ? HashtableCapacity::CreateSelfMovedFrom() : HashtableCapacity::CreateMovedFrom()); if (!maybe_invalid_capacity().IsValid() || - capacity() == policy.soo_capacity()) { + capacity() == policy.alloc_policy->soo_capacity()) { return; } increment_generation(); @@ -439,7 +439,7 @@ } void DeallocBackingArrayImpl(CommonFields& c, - const PolicyFunctions& __restrict policy, + const AllocPolicy& __restrict policy, void* alloc) { DeallocBackingArrayImpl(alloc, c.capacity(), c.control(), policy.slot_size, policy.slot_align_mask, c.has_infoz(), @@ -806,7 +806,7 @@ // Clears the backing array and sets the common fields to the default values for // empty non-allocated tables. REQUIRES: c.capacity > policy.soo_capacity. void ClearBackingArrayNoReuse(CommonFields& c, - const PolicyFunctions& __restrict policy, + const AllocPolicy& __restrict policy, void* alloc) { ABSL_SWISSTABLE_ASSERT(c.capacity() > policy.soo_capacity()); // We need to record infoz before calling dealloc, which will unregister @@ -897,8 +897,8 @@ } void ClearBackingArray(CommonFields& c, - const PolicyFunctions& __restrict policy, void* alloc, - bool reuse) { + const AllocPolicy& __restrict policy, + void* alloc, bool reuse) { ABSL_SWISSTABLE_ASSERT(c.capacity() > kMaxSmallCapacity); if (reuse) { const size_t blocked_element_count = c.blocked_element_count(); @@ -934,7 +934,7 @@ } template <bool kSooEnabled> -void Clear(CommonFields& c, const PolicyFunctions& __restrict policy, +void Clear(CommonFields& c, const AllocPolicy& __restrict policy, DestroySlotFn destroy_slot, void* alloc) { if (SwisstableGenerationsEnabled() && c.maybe_invalid_capacity().IsMovedFrom()) { @@ -1106,11 +1106,9 @@ // Specialization that computes hash and generates new seed. ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportSingleElementTableGrowthToInfozAndForceSample( - CommonFields& common, const PolicyFunctions& __restrict policy, + CommonFields& common, const AllocPolicy& __restrict policy, void* hasher, HashForKeyFn get_hash) { - HashtablezInfoHandle infoz = - ForcedTrySample(policy.slot_size, policy.key_size, policy.value_size, - policy.soo_capacity()); + HashtablezInfoHandle infoz = ForcedTrySample(policy); common.generate_new_seed(/*has_infoz=*/true); ReportGrowthToInfozImpl(common, infoz, get_hash(hasher, common.seed().seed()), /*total_probe_length=*/0, @@ -1142,8 +1140,7 @@ // (Returning a value passed in by the caller doesn't work: the compiler infers // that and keeps the caller's copy alive across the call instead.) ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void* -ReportInsertMissToInfozAndGetSlot(CommonFields& common, - const PolicyFunctions& __restrict policy, +ReportInsertMissToInfozAndGetSlot(CommonFields& common, size_t slot_size, size_t hash, size_t target) { const size_t cap = common.capacity(); auto seq = probe(ProbeCapacity{cap}, hash); @@ -1151,7 +1148,7 @@ seq.next(); } common.infoz().RecordInsertMiss(hash, seq.index()); - return SlotAddress(common.slot_array(cap), target, policy.slot_size); + return SlotAddress(common.slot_array(cap), target, slot_size); } ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportGrowthToInfoz( @@ -1177,12 +1174,10 @@ } ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void -ReportResizeToInfozAndForceSample(CommonFields& common, - const PolicyFunctions& __restrict policy, - size_t total_probe_length) { - HashtablezInfoHandle infoz = - ForcedTrySample(policy.slot_size, policy.key_size, policy.value_size, - policy.soo_capacity()); +ReportResizeToInfozAndForceSample( + CommonFields& common, const AllocPolicy& __restrict policy, + size_t total_probe_length) { + HashtablezInfoHandle infoz = ForcedTrySample(policy); infoz.RecordStorageChanged(common.size(), common.capacity()); infoz.RecordRehash(total_probe_length); common.set_has_infoz(); @@ -1194,10 +1189,9 @@ void* slots; }; -BackingArrayPtrs AllocBackingArray(CommonFields& common, - const PolicyFunctions& __restrict policy, - const RawHashSetLayout& layout, - void* alloc) { +BackingArrayPtrs AllocBackingArray( + CommonFields& common, const AllocPolicy& __restrict policy, + 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)); @@ -1217,35 +1211,33 @@ 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) { +BackingArrayPtrs AllocBackingArray( + CommonFields& common, const AllocPolicy& __restrict policy, + size_t new_capacity, size_t slot_size, bool has_infoz, void* alloc, + size_t blocked_element_count) { return AllocBackingArray( common, policy, - RawHashSetLayout(new_capacity, policy.slot_size, policy.slot_align_mask, + RawHashSetLayout(new_capacity, slot_size, policy.slot_align_mask, has_infoz, blocked_element_count), alloc); } -void ResizeEmptyNonAllocatedTableImpl(CommonFields& common, - const PolicyFunctions& __restrict policy, - size_t new_capacity, - size_t blocked_element_count, - bool force_infoz) { +void ResizeEmptyNonAllocatedTableImpl( + CommonFields& common, const AllocPolicy& __restrict policy, + size_t new_capacity, size_t blocked_element_count, bool force_infoz) { ABSL_SWISSTABLE_ASSERT(IsValidCapacity(new_capacity)); ABSL_SWISSTABLE_ASSERT(new_capacity > policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(!force_infoz || policy.soo_enabled); ABSL_SWISSTABLE_ASSERT(common.capacity() == policy.soo_capacity()); ABSL_SWISSTABLE_ASSERT(common.empty()); const size_t slot_size = policy.slot_size; - const bool has_infoz = - policy.is_hashtablez_enabled && (force_infoz || ShouldSampleNextTable()); + const bool has_infoz = policy.is_hashtablez_enabled && + (force_infoz || ShouldSampleNextTable()); 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, + AllocBackingArray(common, policy, new_capacity, slot_size, has_infoz, policy.get_char_alloc(common), blocked_element_count); common.set_control(new_ctrl); common.generate_new_seed(has_infoz); @@ -1260,12 +1252,14 @@ } void AssertSoo([[maybe_unused]] CommonFields& common, - [[maybe_unused]] const PolicyFunctions& __restrict policy) { + [[maybe_unused]] const AllocPolicy& __restrict + policy) { ABSL_SWISSTABLE_ASSERT(policy.soo_enabled); ABSL_SWISSTABLE_ASSERT(common.capacity() == policy.soo_capacity()); } void AssertFullSoo([[maybe_unused]] CommonFields& common, - [[maybe_unused]] const PolicyFunctions& __restrict policy) { + [[maybe_unused]] const AllocPolicy& __restrict + policy) { AssertSoo(common, policy); ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); } @@ -1285,20 +1279,22 @@ 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()); + ABSL_SWISSTABLE_ASSERT(new_capacity > policy.alloc_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()); + const AllocPolicy& alloc_policy = *policy.alloc_policy; + const bool was_soo = old_capacity == alloc_policy.soo_capacity(); + ABSL_SWISSTABLE_ASSERT(!was_soo || common.size() == + policy.alloc_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`). + // 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; 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. + infoz = ForcedTrySample(alloc_policy); + // If the table was not sampled (including when hashtablez is disabled for + // this table), do not resize. if (!infoz.IsSampled()) return; has_infoz = true; } else { @@ -1316,22 +1312,23 @@ 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, policy.get_char_alloc(common), - /*blocked_element_count=*/0); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, alloc_policy, new_capacity, slot_size, + has_infoz, alloc_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. + // Control is set in `common` only after the transfer to avoid overriding + // the SOO data. common.set_control(new_ctrl); if (!was_soo) { - DeallocBackingArrayImpl(policy.get_char_alloc(common), old_capacity, - old_ctrl, slot_size, policy.slot_align_mask, - has_infoz, old_blocked_element_count, - policy.dealloc); + DeallocBackingArrayImpl( + alloc_policy.get_char_alloc(common), old_capacity, old_ctrl, + slot_size, alloc_policy.slot_align_mask, has_infoz, + old_blocked_element_count, alloc_policy.dealloc); } ResetGrowthLeft(new_capacity, common.size(), common); if (ABSL_PREDICT_FALSE(has_infoz)) { @@ -1840,32 +1837,25 @@ } void IncrementSmallSizeNonSoo(CommonFields& common, - const PolicyFunctions& __restrict policy) { + const AllocPolicy& __restrict policy) { ABSL_SWISSTABLE_ASSERT(common.is_small()); common.increment_size(); SanitizerUnpoisonMemoryRegion( SingleSlotAddress</*kSooEnabled=*/false>(common), policy.slot_size); } -void IncrementSmallSize(CommonFields& common, - const PolicyFunctions& __restrict policy) { - ABSL_SWISSTABLE_ASSERT(common.is_small()); - if (policy.soo_enabled) { - common.set_full_soo(); - } else { - IncrementSmallSizeNonSoo(common, policy); - } -} - +// `slot_align_mask` is passed by value (rather than reading it from +// `AllocPolicy`) so that the caller loads it only once. `dealloc` is +// read through `policy` at the end to avoid keeping it live across calls. void* Grow1To3AndPrepareInsert(CommonFields& common, const PolicyFunctions& __restrict policy, - void* hasher, HashForKeyFn get_hash, void* alloc, + size_t slot_align_mask, 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); ABSL_SWISSTABLE_ASSERT(!common.empty()); - ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); // 1-element tables can't have any blocked elements. ABSL_SWISSTABLE_ASSERT(common.blocked_element_count() == 0); constexpr size_t kOldCapacity = 1; @@ -1879,9 +1869,9 @@ } 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), common.single_non_soo_slot(), - common.seed().seed()); + size_t orig_hash = 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); @@ -1915,8 +1905,9 @@ // Deallocate after `ReportSingleGroupTableGrowthToInfoz`, because it reads // infoz from old_ctrl. DeallocBackingArrayImpl(alloc, kOldCapacity, old_ctrl, slot_size, - policy.slot_align_mask, has_infoz, - /*blocked_element_count=*/0, policy.dealloc); + slot_align_mask, has_infoz, + /*blocked_element_count=*/0, + policy.alloc_policy->dealloc); return new_element_target_slot; } @@ -1927,17 +1918,19 @@ 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(old_capacity > policy.alloc_policy->soo_capacity()); ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(old_capacity)); ABSL_ASSUME(old_capacity > kMaxSmallCapacity); 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); + const size_t slot_size = policy.slot_size; + const AllocPolicy& alloc_policy = *policy.alloc_policy; + void* alloc = alloc_policy.get_char_alloc(common); + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, alloc_policy, new_capacity, slot_size, 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(); @@ -1952,7 +1945,6 @@ 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); @@ -1985,7 +1977,7 @@ SetCtrl(common, new_capacity, new_ctrl, find_info.offset, new_h2, slot_size); } - ABSL_SWISSTABLE_ASSERT(old_capacity > policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(old_capacity > policy.alloc_policy->soo_capacity()); // Reload `has_infoz` to avoid spilling across the indirect call. const bool has_infoz = common.has_infoz(); @@ -1996,8 +1988,8 @@ // Deallocate after `ReportGrowthToInfoz`, because it reads infoz from // old_ctrl. DeallocBackingArrayImpl(alloc, old_capacity, old_ctrl, slot_size, - policy.slot_align_mask, has_infoz, - old_blocked_element_count, policy.dealloc); + alloc_policy.slot_align_mask, has_infoz, + old_blocked_element_count, alloc_policy.dealloc); return SlotAddress(new_slots, find_info.offset, slot_size); } @@ -2037,10 +2029,10 @@ const PolicyFunctions& __restrict policy, void* hasher, HashForKeyFn get_hash) { ABSL_SWISSTABLE_ASSERT(common.is_small()); - ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); + ABSL_SWISSTABLE_ASSERT(!policy.alloc_policy->soo_enabled); const bool is_empty = common.empty_when_small(); if (common.capacity() == 1 && is_empty) { - IncrementSmallSizeNonSoo(common, policy); + IncrementSmallSizeNonSoo(common, *policy.alloc_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. @@ -2052,16 +2044,20 @@ } const size_t size = is_empty ? 0 : 1; + const AllocPolicy& alloc_policy = *policy.alloc_policy; const bool has_infoz = - is_empty ? (policy.is_hashtablez_enabled && ShouldSampleNextTable()) - : common.has_infoz(); - void* alloc = policy.get_char_alloc(common); + is_empty + ? (alloc_policy.is_hashtablez_enabled && ShouldSampleNextTable()) + : common.has_infoz(); + void* alloc = alloc_policy.get_char_alloc(common); + // Load `slot_align_mask` once: it is used for both allocation and + // deallocation. + const size_t slot_align_mask = alloc_policy.slot_align_mask; void* new_slots = - AllocBackingArray( - common, policy, - RawHashSetLayout::CreateForSmallNonSooGrowth( - size, policy.slot_size, policy.slot_align_mask, has_infoz), - alloc) + AllocBackingArray(common, alloc_policy, + RawHashSetLayout::CreateForSmallNonSooGrowth( + size, policy.slot_size, slot_align_mask, has_infoz), + alloc) .slots; if (is_empty) { // Growing from 0 to 1 capacity. @@ -2075,12 +2071,12 @@ if (ABSL_PREDICT_FALSE(has_infoz)) { ReportSingleElementTableGrowthToInfozAndForceSample( - common, policy, hasher, get_hash); + common, alloc_policy, hasher, get_hash); } return new_slots; } - return Grow1To3AndPrepareInsert(common, policy, hasher, get_hash, alloc, - has_infoz, new_slots); + return Grow1To3AndPrepareInsert(common, policy, slot_align_mask, hasher, + get_hash, alloc, has_infoz, new_slots); } namespace { @@ -2194,7 +2190,7 @@ // 2. `c.empty()`. ABSL_ATTRIBUTE_NOINLINE void* GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( - CommonFields& common, const PolicyFunctions& __restrict policy, + CommonFields& common, const AllocPolicy& __restrict policy, void* hasher, HashForKeyFn get_hash) { const size_t kNewCapacity = NextCapacity(SooCapacity()); ResizeEmptyNonAllocatedTableImpl(common, policy, kNewCapacity, @@ -2203,11 +2199,12 @@ PrepareInsertCommon(common); common.OverwriteEmptyAsFull(); const size_t new_hash = get_hash(hasher, common.seed().seed()); + const size_t slot_size = policy.slot_size; // Compute before `SetCtrl*` to avoid reloading `control_`. - void* res = SlotAddress(common.slot_array(kNewCapacity), SooSlotIndex(), - policy.slot_size); + void* res = + SlotAddress(common.slot_array(kNewCapacity), SooSlotIndex(), slot_size); SetCtrlInSingleGroupTable(common, kNewCapacity, common.control(), - SooSlotIndex(), H2(new_hash), policy.slot_size); + SooSlotIndex(), H2(new_hash), slot_size); if (common.has_infoz()) { ReportInsertMissToInfoz(common, /*probe_length=*/0, new_hash); } @@ -2238,11 +2235,11 @@ void ReserveEmptyNonAllocatedTableToFitNewSize( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_size) { - ValidateMaxSize(new_size, policy.key_size, policy.slot_size); + ValidateMaxSize(new_size, policy.alloc_policy->key_size, policy.slot_size); ABSL_ASSUME(new_size > 0); const size_t new_capacity = SizeToCapacity(new_size); ResizeEmptyNonAllocatedTableImpl( - common, policy, new_capacity, + common, *policy.alloc_policy, new_capacity, BlockedElementCountForReservedTable(new_capacity, new_size), /*force_infoz=*/false); // This is after resize, to ensure that we have completed the allocation @@ -2259,9 +2256,10 @@ ABSL_ATTRIBUTE_NOINLINE void ReserveAllocatedTable( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_size) { - ABSL_SWISSTABLE_ASSERT(common.capacity() > policy.soo_capacity() || - !common.empty()); - ValidateMaxSize(new_size, policy.key_size, policy.slot_size); + ABSL_SWISSTABLE_ASSERT( + common.capacity() > policy.alloc_policy->soo_capacity() || + !common.empty()); + ValidateMaxSize(new_size, policy.alloc_policy->key_size, policy.slot_size); ABSL_ASSUME(new_size > 0); const size_t new_capacity = SizeToCapacity(new_size); // TODO(b/382423690): consider using GrowToNextCapacity, when applicable. @@ -2275,7 +2273,7 @@ // sampling is disabled or not possible. void GrowFullSooTableToNextCapacityForceSampling( CommonFields& common, const PolicyFunctions& __restrict policy) { - AssertFullSoo(common, policy); + AssertFullSoo(common, *policy.alloc_policy); ResizeTableWithSeedChangeImpl(common, policy, NextCapacity(SooCapacity()), /*force_sample_soo=*/true); } @@ -2285,7 +2283,8 @@ void ResizeAllocatedTableWithSeedChange( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_capacity) { - ABSL_SWISSTABLE_ASSERT(common.capacity() > policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(common.capacity() > + policy.alloc_policy->soo_capacity()); ResizeTableWithSeedChangeImpl(common, policy, new_capacity, /*force_sample_soo=*/false); } @@ -2295,13 +2294,14 @@ void* GrowSooTableToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, void* hasher, HashForKeyFn get_hash, bool force_sampling) { - AssertSoo(common, policy); + AssertSoo(common, *policy.alloc_policy); if (ABSL_PREDICT_FALSE(force_sampling)) { // The table is empty, it is only used for forced sampling of SOO tables. return GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( - common, policy, hasher, get_hash); + common, *policy.alloc_policy, hasher, get_hash); } - ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(common.size() == + policy.alloc_policy->soo_capacity()); static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); // Generate the seed and compute hashes before `AllocBackingArray` so // `hasher`, `get_hash`, and `new_ctrl`/`new_slots` do not need to be spilled @@ -2316,10 +2316,11 @@ // // 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, - policy.get_char_alloc(common), - /*blocked_element_count=*/0); + const AllocPolicy& alloc_policy = *policy.alloc_policy; + const size_t slot_size = policy.slot_size; + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, alloc_policy, kNewCapacity, slot_size, /*has_infoz=*/false, + alloc_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); @@ -2331,7 +2332,6 @@ 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); @@ -2366,19 +2366,24 @@ size_t n) { const size_t cap = common.capacity(); + // `alloc_policy` is read at each use (rather than once at the top) so that + // `policy` stays in its argument register for the calls that need it. auto clear_backing_array = [&]() { - ClearBackingArrayNoReuse(common, policy, policy.get_char_alloc(common)); + const AllocPolicy& alloc_policy = *policy.alloc_policy; + ClearBackingArrayNoReuse(common, alloc_policy, + alloc_policy.get_char_alloc(common)); }; const size_t slot_size = policy.slot_size; + const size_t soo_capacity = policy.alloc_policy->soo_capacity(); if (n == 0) { - if (cap <= policy.soo_capacity()) return; + if (cap <= soo_capacity) return; if (common.empty()) { clear_backing_array(); return; } - if (common.size() <= policy.soo_capacity()) { + if (common.size() <= soo_capacity) { // When the table is already sampled, we keep it sampled. if (common.has_infoz()) { static constexpr size_t kInitialSampledCapacity = @@ -2393,7 +2398,8 @@ } // Reducing from large capacity to SOO. ABSL_SWISSTABLE_ASSERT(slot_size <= sizeof(HeapOrSoo)); - ABSL_SWISSTABLE_ASSERT(policy.slot_align_mask < alignof(HeapOrSoo)); + ABSL_SWISSTABLE_ASSERT(policy.alloc_policy->slot_align_mask < + alignof(HeapOrSoo)); ABSL_SWISSTABLE_ASSERT(!IsSmallCapacity(cap)); HeapOrSoo tmp_slot; size_t begin_offset = FindFirstFullSlot(0, cap, common.control()); @@ -2411,11 +2417,13 @@ // power-of-2-minus-1, so bitor is good enough. const size_t new_capacity = NormalizeCapacity(n | SizeToCapacity(common.size())); - ValidateMaxCapacity(new_capacity, policy.key_size, policy.slot_size); + ValidateMaxCapacity(new_capacity, policy.alloc_policy->key_size, + slot_size); // n == 0 unconditionally rehashes as per the standard. if (n == 0 || new_capacity > cap) { - if (cap == policy.soo_capacity() && common.empty()) { - ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + if (cap == soo_capacity && common.empty()) { + ResizeEmptyNonAllocatedTableImpl(common, *policy.alloc_policy, + new_capacity, /*blocked_element_count=*/0, /*force_infoz=*/false); } else { @@ -2434,15 +2442,17 @@ other.AssertNotDebugCapacity(); const size_t size = other.size(); if (size == 0) return; - const size_t soo_capacity = policy.soo_capacity(); + const AllocPolicy& alloc_policy = *policy.alloc_policy; + const size_t soo_capacity = alloc_policy.soo_capacity(); const size_t slot_size = policy.slot_size; - const bool soo_enabled = policy.soo_enabled; + const bool soo_enabled = alloc_policy.soo_enabled; if (size == 1) { - if (!soo_enabled) { + if (soo_enabled) { + common.set_full_soo(); + } else { ReserveEmptyNonAllocatedTableToFitNewSize(common, policy, 1); - common.infoz().RecordStorageChanged(1, 1); + IncrementSmallSizeNonSoo(common, alloc_policy); } - IncrementSmallSize(common, policy); const size_t other_capacity = other.capacity(); const void* other_slot = other_capacity <= soo_capacity ? other.soo_data() @@ -2456,9 +2466,12 @@ : SingleSlotAddress</*kSooEnabled=*/false>(common), other_slot); - if (soo_enabled && policy.is_hashtablez_enabled && - ShouldSampleNextTable()) { - GrowFullSooTableToNextCapacityForceSampling(common, policy); + if (soo_enabled) { + if (alloc_policy.is_hashtablez_enabled && ShouldSampleNextTable()) { + GrowFullSooTableToNextCapacityForceSampling(common, policy); + } + } else { + common.infoz().RecordStorageChanged(1, 1); } return; } @@ -2496,21 +2509,25 @@ void ReserveTableToFitNewSize(CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_size) { - new_size = - std::min(new_size, MaxValidSize(policy.key_size, policy.slot_size)); + const AllocPolicy& alloc_policy = *policy.alloc_policy; + new_size = std::min(new_size, + MaxValidSize(alloc_policy.key_size, policy.slot_size)); common.reset_reserved_growth(new_size); common.set_reservation_size(new_size); - ABSL_SWISSTABLE_ASSERT(new_size > policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(new_size > policy.alloc_policy->soo_capacity()); const size_t cap = common.capacity(); - if (ABSL_PREDICT_TRUE(common.empty() && cap <= policy.soo_capacity())) { + if (ABSL_PREDICT_TRUE(common.empty() && + cap <= alloc_policy.soo_capacity())) { return ReserveEmptyNonAllocatedTableToFitNewSize(common, policy, new_size); } - ABSL_SWISSTABLE_ASSERT(!common.empty() || cap > policy.soo_capacity()); + ABSL_SWISSTABLE_ASSERT(!common.empty() || + cap > policy.alloc_policy->soo_capacity()); ABSL_SWISSTABLE_ASSERT(cap > 0); const size_t max_size_before_growth = - IsSmallCapacity(cap) ? cap - : common.size() + common.GetGrowthLeftTotalSlow(cap); + IsSmallCapacity(cap) + ? cap + : common.size() + common.GetGrowthLeftTotalSlow(cap); if (new_size <= max_size_before_growth) { return; } @@ -2537,14 +2554,15 @@ ABSL_ASSUME(cap > kMaxSmallCapacity); target_group_offset += mask_empty.LowestBitSet(); target_group_offset &= cap; + const size_t slot_size = policy.slot_size; // Compute before `SetCtrl` to avoid reloading `control_`. - void* res = SlotAddress(common.slot_array(cap), target_group_offset, - policy.slot_size); + void* res = + SlotAddress(common.slot_array(cap), target_group_offset, slot_size); SetCtrl(common, cap, common.control(), target_group_offset, H2(hash), - policy.slot_size); + slot_size); // Call NOINLINE function to move infoz instructions out of line. if (common.has_infoz()) { - return ReportInsertMissToInfozAndGetSlot(common, policy, hash, + return ReportInsertMissToInfozAndGetSlot(common, slot_size, hash, target_group_offset); } return res; @@ -2644,14 +2662,12 @@ void* backing_array, size_t n); -template void Clear</*kSooEnabled=*/true>(CommonFields& c, - const PolicyFunctions& policy, - DestroySlotFn destroy_slot, - void* alloc); -template void Clear</*kSooEnabled=*/false>(CommonFields& c, - const PolicyFunctions& policy, - DestroySlotFn destroy_slot, - void* alloc); +template void Clear</*kSooEnabled=*/true>( + CommonFields& c, const AllocPolicy& policy, + DestroySlotFn destroy_slot, void* alloc); +template void Clear</*kSooEnabled=*/false>( + CommonFields& c, const AllocPolicy& policy, + DestroySlotFn destroy_slot, void* alloc); template void Destruct</*kSooEnabled=*/true>(CommonFields& c, const DtorPolicy& policy,
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index dac9c39..8ca006f 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -447,14 +447,7 @@ return *generation == SentinelEmptyGeneration(); } -// We only allow a maximum of 1 SOO element, which makes the implementation -// much simpler. Complications with multiple SOO elements include: -// - Satisfying the guarantee that erasing one element doesn't invalidate -// iterators to other elements means we would probably need actual SOO -// control bytes. -// - In order to prevent user code from depending on iteration order for small -// tables, we would need to randomize the iteration order somehow. -constexpr size_t SooCapacity() { return 1; } +constexpr size_t SooCapacity() { return HashtableSooCapacity(); } // Maximum capacity of a table where we don't need to hash any keys. inline constexpr size_t kMaxSmallCapacity = 1; // Sentinel type to indicate SOO CommonFields construction. @@ -1329,6 +1322,12 @@ unsigned char soo_data[MaxSooSlotSize()]; }; +// Returns true if a slot with the given size and alignment can be stored inline +// in `HeapOrSoo`, i.e. small object optimization (SOO) is used for it. +constexpr bool FitsInSooSlot(size_t slot_size, size_t slot_align) { + return slot_size <= sizeof(HeapOrSoo) && slot_align <= alignof(HeapOrSoo); +} + class CommonFields; struct PolicyFunctions; @@ -2014,25 +2013,102 @@ &DeallocateBackingArray<kStandardBackingArrayAlignment, std::allocator<char>>; +// AllocPolicy bundles layout and allocation information for a +// raw_hash_set<T, ...> instantiation. Numeric properties are inherited from +// `HashtableTypeInfo` (defined in container_memory.h). In the common case +// (standard allocator and standard backing array alignment), instances are +// shared across all tables with the same +// (slot_size, slot_align, key_size, value_size). +struct AllocPolicy : HashtableTypeInfo { + // Allocates n bytes for the backing store for common. + void* (*alloc)(void* alloc, size_t n); + + // Deallocates the backing store from common. + DeallocBackingArrayFn dealloc; + + // Returns the pointer to the CharAlloc stored in the set. + void* get_char_alloc(CommonFields& common) const { + return reinterpret_cast<char*>(&common) + alloc_offset; + } + + // TODO(b/382423690): Consider removing `value_size` from hashtablez + // sampling. It would shrink this struct by 8 bytes and reduce the number of + // shared instances (`kValueSize` would no longer be a template parameter). + template <uint32_t kSlotSize, uint16_t kSlotAlign, uint32_t kKeySize, + uint32_t kValueSize> + static constexpr const AllocPolicy& GetNormalRef() { + static_assert(BackingArrayAlignment(kSlotAlign) == + kStandardBackingArrayAlignment); + return P<kSlotSize, kSlotAlign, kKeySize, kValueSize>::kP; + } + + template <typename SetType> + static constexpr const AllocPolicy& GetRef() { + return S<SetType>::kP; + } + + private: + // Short names are used below to minimize the mangled name length of static + // variables and reduce linker input size. + template <uint32_t kSlotSize, uint16_t kSlotAlign, uint32_t kKeySize, + uint32_t kValueSize> + struct P; + template <typename SetType> + struct S; +}; + +template <uint32_t kSlotSize, uint16_t kSlotAlign, uint32_t kKeySize, + uint32_t kValueSize> +struct AllocPolicy::P { + static constexpr AllocPolicy kP = { + { + kSlotSize, + /*slot_align_mask=*/static_cast<uint16_t>(kSlotAlign - 1), + FitsInSooSlot(kSlotSize, kSlotAlign), +#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) + /*is_hashtablez_enabled=*/true, +#else + /*is_hashtablez_enabled=*/false, +#endif + /*alloc_offset=*/0, + kKeySize, + kValueSize, + }, + &AllocateBackingArray<kStandardBackingArrayAlignment, + std::allocator<char>>, + kStandardDeallocBackingArrayFn, + }; +}; + +template <typename SetType> +struct AllocPolicy::S { + static constexpr AllocPolicy kP = { + { + static_cast<uint32_t>(sizeof(typename SetType::slot_type)), + /*slot_align_mask=*/static_cast<uint16_t>( + alignof(typename SetType::slot_type) - 1), + SetType::SooEnabled(), + SetType::HashtablezForTableEnabled(), + static_cast<uint32_t>(SetType::AllocOffset()), + static_cast<uint32_t>(sizeof(typename SetType::key_type)), + static_cast<uint32_t>(sizeof(typename SetType::value_type)), + }, + &AllocateBackingArray< + BackingArrayAlignment(alignof(typename SetType::slot_type)), + typename SetType::CharAlloc>, + SetType::get_dealloc_backing_array_fn(), + }; +}; + // PolicyFunctions bundles together some information for a particular // raw_hash_set<T, ...> instantiation. This information is passed to // 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 + // Duplicated from `AllocPolicy` to avoid an extra pointer + // indirection in hot functions (such as `PrepareInsertLarge`). uint32_t slot_size; - // `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 uint32_t hasher_offset; - uint32_t alloc_offset; // Returns the hash of the pointed-to slot. HashSlotFn hash_slot; @@ -2041,11 +2117,7 @@ // 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); - // Allocates n bytes for the backing store for common. - void* (*alloc)(void* alloc, size_t n); - - // Deallocates the backing store from common. - DeallocBackingArrayFn dealloc; + const AllocPolicy* alloc_policy; // Implementation detail of GrowToNextCapacity. // Iterates over all full slots and transfers unprobed elements. @@ -2063,19 +2135,10 @@ 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); @@ -2087,7 +2150,7 @@ // functions, so we do not want to include non-destructor related fields. struct DtorPolicy { uint32_t slot_size; - // `alignof(slot_type) - 1`. See `PolicyFunctions::slot_align_mask`. + // `alignof(slot_type) - 1`. See `HashtableTypeInfo::slot_align_mask`. uint16_t slot_align_mask; DestroySlotFn destroy_slot; @@ -2255,7 +2318,7 @@ // Clears the backing array, either modifying it in place, or creating a new one // based on the value of "reuse". REQUIRES: c.capacity > MaxSmallCapacity(). -void ClearBackingArray(CommonFields& c, const PolicyFunctions& policy, +void ClearBackingArray(CommonFields& c, const AllocPolicy& policy, void* alloc, bool reuse); // Destroys all full slots in the backing array. @@ -2272,7 +2335,7 @@ // Type erased version of raw_hash_set::clear. template <bool kSooEnabled> -void Clear(CommonFields& c, const PolicyFunctions& policy, +void Clear(CommonFields& c, const AllocPolicy& policy, DestroySlotFn destroy_slot, void* alloc); // Destructs all elements and deallocates the backing array tables. @@ -2466,8 +2529,7 @@ kIsAbslHash ? 0 : HashtableInlineData::kSeedShift; constexpr static bool SooEnabled() { - return sizeof(slot_type) <= sizeof(HeapOrSoo) && - alignof(slot_type) <= alignof(HeapOrSoo); + return FitsInSooSlot(sizeof(slot_type), alignof(slot_type)); } constexpr static bool HashtablezForTableEnabled() { @@ -2997,8 +3059,8 @@ size_t max_size() const { return MaxValidSize(); } ABSL_ATTRIBUTE_REINITIALIZES void clear() { - Clear<SooEnabled()>(common(), GetPolicyFunctions(), get_destroy_slot_fn(), - &char_alloc_ref()); + Clear<SooEnabled()>(common(), GetAllocPolicy(), + get_destroy_slot_fn(), &char_alloc_ref()); } // This overload kicks in when the argument is an rvalue of insertable and @@ -3526,6 +3588,7 @@ friend struct absl::container_internal::HashtableFreeFunctionsAccess; friend DtorPolicy; + friend AllocPolicy; struct FindElement { template <class K, class... Args> @@ -3644,7 +3707,8 @@ void clear_backing_array(bool reuse) { ABSL_SWISSTABLE_ASSERT(capacity() > kMaxSmallCapacity); - ClearBackingArray(common(), GetPolicyFunctions(), &char_alloc_ref(), reuse); + ClearBackingArray(common(), GetAllocPolicy(), &char_alloc_ref(), + reuse); } void destroy_slots() { @@ -4269,37 +4333,45 @@ } } - static const PolicyFunctions& GetPolicyFunctions() { + static constexpr const AllocPolicy& GetAllocPolicy() { static_assert(sizeof(slot_type) <= (std::numeric_limits<uint32_t>::max)(), "Slot size is too large. Use std::unique_ptr for value type " "or use absl::node_hash_{map,set}."); + static_assert(sizeof(key_type) <= (std::numeric_limits<uint32_t>::max)(), + "Key size is too large."); + static_assert(sizeof(value_type) <= (std::numeric_limits<uint32_t>::max)(), + "Value size is too large. Use std::unique_ptr for value type " + "or use absl::node_hash_map."); static_assert(alignof(slot_type) <= size_t{(std::numeric_limits<uint16_t>::max)()}); - static_assert(sizeof(key_type) <= - 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)); + // `alloc_offset` is irrelevant for `kIsDefaultAlloc` because + // `std::allocator` is stateless, so the shared policy uses 0. + if constexpr (BackingArrayAlignment(alignof(slot_type)) == + kStandardBackingArrayAlignment && + kIsDefaultAlloc) { + return AllocPolicy::GetNormalRef< + static_cast<uint32_t>(sizeof(slot_type)), + static_cast<uint16_t>(alignof(slot_type)), + static_cast<uint32_t>(sizeof(key_type)), + static_cast<uint32_t>(sizeof(value_type))>(); + } else { + return AllocPolicy::GetRef<raw_hash_set>(); + } + } + + static const PolicyFunctions& GetPolicyFunctions() { + static_assert(HasherOffset() <= + size_t{(std::numeric_limits<uint32_t>::max)()}); 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)), - /*slot_align_mask=*/static_cast<uint16_t>(alignof(slot_type) - 1), - SooEnabled(), - HashtablezForTableEnabled(), 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, - &AllocateBackingArray<kBackingArrayAlignment, CharAlloc>, - get_dealloc_backing_array_fn(), + &GetAllocPolicy(), &raw_hash_set::transfer_unprobed_elements_to_next_capacity_fn}; return value; } @@ -4471,14 +4543,12 @@ DeallocateBackingArray<kStandardBackingArrayAlignment, std::allocator<char>>( void* alloc, void* backing_array, size_t n); -extern template void Clear</*kSooEnabled=*/true>(CommonFields& c, - const PolicyFunctions& policy, - DestroySlotFn destroy_slot, - void* alloc); -extern template void Clear</*kSooEnabled=*/false>(CommonFields& c, - const PolicyFunctions& policy, - DestroySlotFn destroy_slot, - void* alloc); +extern template void Clear</*kSooEnabled=*/true>( + CommonFields& c, const AllocPolicy& policy, + DestroySlotFn destroy_slot, void* alloc); +extern template void Clear</*kSooEnabled=*/false>( + CommonFields& c, const AllocPolicy& policy, + DestroySlotFn destroy_slot, void* alloc); extern template void Destruct</*kSooEnabled=*/true>( CommonFields& c, const DtorPolicy& policy, DeallocBackingArrayFn dealloc,