Store hasher and allocator offsets in PolicyFunctions instead of accessor function pointers. `PolicyFunctions` carried two per-instantiation accessor functions, `hash_fn` and `get_char_alloc`, whose only job was to compute the address of the hasher and of the allocator from a `CommonFields&`. Every type-erased growth, rehash, and copy path paid an indirect call for what is a compile-time constant offset, the calls acted as optimization barriers (values had to be moved into callee-saved registers or spilled around them). Replace the two function pointers with 32 bit offsets computed with `offsetof`. `sizeof(PolicyFunctions)` shrinks from 72 to 64 bytes (one cache line), `GetRefForEmptyClass` and the per-instantiation accessor functions disappear, and the type-erased code in `raw_hash_set.cc` shrinks by 95 bytes (-0.45%) in optimized builds. PiperOrigin-RevId: 1002065508
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 7792be0..fea8605 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -813,7 +813,6 @@ deps = [ ":common", ":common_policy_traits", - ":compressed_tuple", ":container_memory", ":hash_function_defaults", ":hash_policy_traits",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 82548bc..6432a69 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -815,7 +815,6 @@ absl::base absl::bits absl::common_policy_traits - absl::compressed_tuple absl::config absl::container_common absl::container_memory
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 285d269..7892d2d 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -1215,12 +1215,12 @@ const size_t slot_size = policy.slot_size; const bool has_infoz = policy.is_hashtablez_enabled && (force_infoz || ShouldSampleNextTable()); - void* alloc = policy.get_char_alloc(common); common.set_capacity(new_capacity); common.init_blocked_element_count(blocked_element_count); - const auto [new_ctrl, new_slots] = AllocBackingArray( - common, policy, new_capacity, has_infoz, alloc, blocked_element_count); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, new_capacity, has_infoz, + policy.get_char_alloc(common), blocked_element_count); common.set_control(new_ctrl); common.generate_new_seed(has_infoz); @@ -1284,7 +1284,6 @@ ResizeFullSooTableSamplingMode sampling_mode) { AssertFullSoo(common, policy); const size_t slot_size = policy.slot_size; - void* alloc = policy.get_char_alloc(common); constexpr size_t kTableSize = 1; HashtablezInfoHandle infoz; @@ -1305,9 +1304,9 @@ // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, - /*blocked_element_count=*/0); + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, policy, new_capacity, has_infoz, policy.get_char_alloc(common), + /*blocked_element_count=*/0); InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots, has_infoz); @@ -1880,11 +1879,9 @@ } const size_t new_hash = get_hash(hasher, common.seed().seed()); h2_t new_h2 = H2(new_hash); - // `hash_fn` is in separate statement, so the hash_slot function pointer is - // not loaded before the hash_fn call. - const void* hash_fn = policy.hash_fn(common); - size_t orig_hash = policy.hash_slot( - hash_fn, 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); @@ -1934,12 +1931,10 @@ 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); + 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); @@ -2295,14 +2290,6 @@ } // namespace -void* GetRefForEmptyClass(CommonFields& common) { - // Empty base optimization typically make the empty base class address to be - // the same as the first address of the derived class object. - // But we generally assume that for empty classes we can return any valid - // pointer. - return &common; -} - void ResizeAllocatedTableWithSeedChange( CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_capacity) { @@ -2320,13 +2307,12 @@ const size_t slot_align = policy.slot_align; HashtablezInfoHandle infoz = common.infoz(); const bool has_infoz = common.has_infoz(); - void* alloc = policy.get_char_alloc(common); common.set_capacity(new_capacity); common.set_blocked_element_count_to_zero(); - const auto [new_ctrl, new_slots] = - AllocBackingArray(common, policy, new_capacity, has_infoz, alloc, - /*blocked_element_count=*/0); + const auto [new_ctrl, new_slots] = AllocBackingArray( + common, policy, new_capacity, has_infoz, policy.get_char_alloc(common), + /*blocked_element_count=*/0); common.set_control(new_ctrl); common.generate_new_seed(has_infoz); @@ -2336,8 +2322,9 @@ ABSL_SWISSTABLE_ASSERT(old_capacity > 0); total_probe_length = FindNewPositionsAndTransferSlots( common, policy, old_ctrl, old_slots, old_capacity); - DeallocBackingArrayImpl(alloc, old_capacity, old_ctrl, slot_size, slot_align, - has_infoz, old_blocked_element_count, policy.dealloc); + DeallocBackingArrayImpl(policy.get_char_alloc(common), old_capacity, old_ctrl, + slot_size, slot_align, has_infoz, + old_blocked_element_count, policy.dealloc); ResetGrowthLeft(new_capacity, common.size(), common); if (ABSL_PREDICT_FALSE(has_infoz)) { @@ -2363,19 +2350,18 @@ // across calls. common.generate_new_seed(/*has_infoz=*/false); const size_t new_hash = get_hash(hasher, common.seed().seed()); - const void* hash_fn = policy.hash_fn(common); - const h2_t soo_slot_h2 = - H2(policy.hash_slot(hash_fn, common.soo_data(), common.seed().seed())); + const h2_t soo_slot_h2 = H2(policy.hash_slot( + policy.hash_fn(common), common.soo_data(), common.seed().seed())); - void* alloc = policy.get_char_alloc(common); // Since the table is not empty, it will not be sampled. // The decision to sample was already made during the first insertion. // // We do not set control and slots in CommonFields yet to avoid overriding // SOO data. - const auto [new_ctrl, new_slots] = AllocBackingArray( - common, policy, kNewCapacity, /*has_infoz=*/false, alloc, - /*blocked_element_count=*/0); + const auto [new_ctrl, new_slots] = + AllocBackingArray(common, policy, kNewCapacity, /*has_infoz=*/false, + policy.get_char_alloc(common), + /*blocked_element_count=*/0); // Group `common` updates together after `AllocBackingArray` so `inline_data_` // is modified in a single load-store sequence. common.set_capacity(kNewCapacity);
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 2d9e654..49e5b2e 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -213,7 +213,6 @@ #include "absl/base/prefetch.h" #include "absl/container/internal/common.h" // IWYU pragma: export // for node_handle #include "absl/container/internal/common_policy_traits.h" -#include "absl/container/internal/compressed_tuple.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" #include "absl/container/internal/hash_policy_traits.h" @@ -2037,15 +2036,18 @@ // type-erased functions that want to do small amounts of type-specific // work. struct PolicyFunctions { + // 8 bytes uint32_t key_size; uint32_t value_size; + + // 8 bytes uint32_t slot_size; uint16_t slot_align; bool soo_enabled; bool is_hashtablez_enabled; - - // Returns the pointer to the hash function stored in the set. - void* (*hash_fn)(CommonFields& common); + // 8 bytes + uint32_t hasher_offset; + uint32_t alloc_offset; // Returns the hash of the pointed-to slot. HashSlotFn hash_slot; @@ -2054,9 +2056,6 @@ // We use ability to transfer several slots in single group table growth. void (*transfer_n)(void* set, void* dst_slot, void* src_slot, size_t count); - // Returns the pointer to the CharAlloc stored in the set. - void* (*get_char_alloc)(CommonFields& common); - // Allocates n bytes for the backing store for common. void* (*alloc)(void* alloc, size_t n); @@ -2082,6 +2081,16 @@ 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); @@ -2321,11 +2330,6 @@ memcpy(dst, src, SizeOfSlot * count); } -// Returns a pointer to `common`. This is used to implement type erased -// raw_hash_set::get_hash_ref_fn and raw_hash_set::get_alloc_ref_fn for the -// empty class cases. -void* GetRefForEmptyClass(CommonFields& common); - // Given the hash of a value not currently in the table and the first group with // an empty slot in the probe sequence, finds a viable slot to insert it at. // @@ -2812,13 +2816,16 @@ raw_hash_set() noexcept( std::is_nothrow_default_constructible_v<hasher> && std::is_nothrow_default_constructible_v<key_equal> && - std::is_nothrow_default_constructible_v<allocator_type>) {} + std::is_nothrow_default_constructible_v<allocator_type>) + : hash_(), eq_(), alloc_() {} explicit raw_hash_set(size_t reservation_size, const hasher& hash = hasher(), const key_equal& eq = key_equal(), const allocator_type& alloc = allocator_type()) - : settings_(CommonFields::CreateDefault<SooEnabled()>(), hash, eq, - alloc) { + : common_(CommonFields::CreateDefault<SooEnabled()>()), + hash_(hash), + eq_(eq), + alloc_(alloc) { if (reservation_size > DefaultCapacity()) { ReserveTableToFitNewSize(common(), GetPolicyFunctions(), reservation_size); @@ -2964,11 +2971,13 @@ // `that` must be left valid. If Hash is std::function<Key>, moving it // would create a nullptr functor that cannot be called. // Note: we avoid using exchange for better generated code. - settings_(PolicyTraits::transfer_uses_memcpy() || !that.is_full_soo() - ? std::move(that.common()) - : CommonFields{full_soo_tag_t{}, - that.common().soo_has_tried_sampling()}, - that.hash_ref(), that.eq_ref(), that.char_alloc_ref()) { + common_(PolicyTraits::transfer_uses_memcpy() || !that.is_full_soo() + ? std::move(that.common()) + : CommonFields{full_soo_tag_t{}, + that.common().soo_has_tried_sampling()}), + hash_(that.hash_ref()), + eq_(that.eq_ref()), + alloc_(that.char_alloc_ref()) { if constexpr (SooEnabled() && !PolicyTraits::transfer_uses_memcpy()) { if (that.is_full_soo()) { transfer(soo_slot(), that.soo_slot()); @@ -2980,8 +2989,10 @@ } raw_hash_set(raw_hash_set&& that, const allocator_type& a) - : settings_(CommonFields::CreateDefault<SooEnabled()>(), that.hash_ref(), - that.eq_ref(), a) { + : common_(CommonFields::CreateDefault<SooEnabled()>()), + hash_(that.hash_ref()), + eq_(that.eq_ref()), + alloc_(a) { if (CharAlloc(a) == that.char_alloc_ref()) { swap_common(that); common().annotate_for_bug_detection_on_move(that.common(), @@ -4020,10 +4031,9 @@ std::is_same_v<key_equal, std::equal_to<key_type>>; if constexpr (kIsDebug && !kIsStringAbslHashEq && !kIsScalarAbslHashEq) { if (empty()) return; - AssertHashEqConsistentImpl( - common(), get_hash_ref_fn(common()), get_hash_slot_fn(), - sizeof(slot_type), SooEnabled(), hash_of(key), &key, - &equal_to_key_fn<K>); + AssertHashEqConsistentImpl(common(), &hash_ref(), get_hash_slot_fn(), + sizeof(slot_type), SooEnabled(), hash_of(key), + &key, &equal_to_key_fn<K>); } } @@ -4108,8 +4118,8 @@ #endif } - CommonFields& common() { return settings_.template get<0>(); } - const CommonFields& common() const { return settings_.template get<0>(); } + CommonFields& common() { return common_; } + const CommonFields& common() const { return common_; } // For use when the capacity is potentially invalid we return // HashtableCapacity directly. @@ -4176,24 +4186,34 @@ return common().infoz(); } - hasher& hash_ref() { return settings_.template get<1>(); } - const hasher& hash_ref() const { return settings_.template get<1>(); } - key_equal& eq_ref() { return settings_.template get<2>(); } - const key_equal& eq_ref() const { return settings_.template get<2>(); } - CharAlloc& char_alloc_ref() { return settings_.template get<3>(); } - const CharAlloc& char_alloc_ref() const { - return settings_.template get<3>(); - } + hasher& hash_ref() { return hash_; } + const hasher& hash_ref() const { return hash_; } + key_equal& eq_ref() { return eq_; } + const key_equal& eq_ref() const { return eq_; } + CharAlloc& char_alloc_ref() { return alloc_; } + const CharAlloc& char_alloc_ref() const { return alloc_; } - static void* get_char_alloc_ref_fn(CommonFields& common) { - auto* h = reinterpret_cast<raw_hash_set*>(&common); - return &h->char_alloc_ref(); + // Offsets of `hash_` and `alloc_` relative to `common_`. They are stored in + // `PolicyFunctions` so that type erased functions can access the hasher and + // the allocator given only a `CommonFields&`. + // `offsetof` on a non-standard-layout type (e.g. when `hasher` is + // not standard-layout) is conditionally-supported, but all the compilers we + // care about support it for direct non-static data members. Hence, we + // suppress the corresponding warning. +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Winvalid-offsetof" +#endif + static constexpr size_t HasherOffset() { + return offsetof(raw_hash_set, hash_) - offsetof(raw_hash_set, common_); } - static void* get_hash_ref_fn(CommonFields& common) { - auto* h = reinterpret_cast<raw_hash_set*>(&common); - // TODO(b/397453582): Remove support for const hasher. - return const_cast<std::remove_const_t<hasher>*>(&h->hash_ref()); + static constexpr size_t AllocOffset() { + return offsetof(raw_hash_set, alloc_) - offsetof(raw_hash_set, common_); } +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic pop +#endif + static constexpr HashSlotFn get_hash_slot_fn() { return PolicyTraits::template get_hash_slot_fn<hasher, kIsAbslHash, kSeedShift>(); @@ -4311,37 +4331,45 @@ size_t{(std::numeric_limits<uint32_t>::max)()}); static_assert(sizeof(value_type) <= size_t{(std::numeric_limits<uint32_t>::max)()}); + static_assert(HasherOffset() <= + size_t{(std::numeric_limits<uint32_t>::max)()}); + static_assert(AllocOffset() <= + size_t{(std::numeric_limits<uint32_t>::max)()}); static constexpr size_t kBackingArrayAlignment = BackingArrayAlignment(alignof(slot_type)); static constexpr PolicyFunctions value = { static_cast<uint32_t>(sizeof(key_type)), static_cast<uint32_t>(sizeof(value_type)), static_cast<uint32_t>(sizeof(slot_type)), - static_cast<uint16_t>(alignof(slot_type)), SooEnabled(), + static_cast<uint16_t>(alignof(slot_type)), + SooEnabled(), HashtablezForTableEnabled(), - // TODO(b/328722020): try to type erase - // for standard layout and alignof(Hash) <= alignof(CommonFields). - std::is_empty_v<hasher> ? &GetRefForEmptyClass - : &raw_hash_set::get_hash_ref_fn, + static_cast<uint32_t>(HasherOffset()), + static_cast<uint32_t>(AllocOffset()), get_hash_slot_fn(), PolicyTraits::transfer_uses_memcpy() ? TransferNRelocatable<sizeof(slot_type)> : &raw_hash_set::transfer_n_slots_fn, - std::is_empty_v<Alloc> ? &GetRefForEmptyClass - : &raw_hash_set::get_char_alloc_ref_fn, &AllocateBackingArray<kBackingArrayAlignment, CharAlloc>, get_dealloc_backing_array_fn(), &raw_hash_set::transfer_unprobed_elements_to_next_capacity_fn}; return value; } - // Bundle together CommonFields plus other objects which might be empty. - // CompressedTuple will ensure that sizeof is not affected by any of the - // empty fields that occur after CommonFields. - absl::container_internal::CompressedTuple<CommonFields, hasher, key_equal, - CharAlloc> - settings_{CommonFields::CreateDefault<SooEnabled()>(), hasher{}, - key_equal{}, CharAlloc{}}; + // `common_` must be the first member: type erased functions cast + // `CommonFields*` to `raw_hash_set*`. + CommonFields common_ = CommonFields::CreateDefault<SooEnabled()>(); + // ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS ensures that sizeof is not affected by any + // of the fields below if they are empty. + // + // Note: these members must not have default member initializers and must be + // initialized in the constructor mem-initializer lists instead. MSVC + // miscompiles `[[msvc::no_unique_address]]` members with default member + // initializers and overwrites bytes of the overlapping `common_`: + // https://developercommunity.visualstudio.com/t/miscompilation-with-msvcno-unique-address-and-defa/1699750 + ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS hasher hash_; + ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS key_equal eq_; + ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS CharAlloc alloc_; }; // Friend access for free functions in raw_hash_set.h.
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index ed25c05..1268851 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1346,6 +1346,12 @@ TEST(Table, EmptyFunctorOptimization) { static_assert(std::is_empty_v<std::equal_to<absl::string_view>>); static_assert(std::is_empty_v<std::allocator<int>>); +#if defined(_MSC_VER) && _MSC_VER < 1929 + // ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS expands to nothing for MSVC compatibility + // versions below 19.29 (e.g. clang with `-fms-compatibility-version=19.25`), + // so empty functors still take space. + GTEST_SKIP() << "ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS is a no-op."; +#endif struct MockTable { uint64_t size;