Pass small trivial keys by value in SwissTable lookup and hash/eq helpers. Move `ShouldPreferPassByValue` (and its helpers) to `type_traits_internal` in `meta/type_traits.h`, require `std::is_trivially_copy_constructible_v<T>` in `ShouldSemanticallyPreferPassByValue`, and introduce `ConstParamT<T>` which passes types satisfying `ShouldPreferPassByValue<T>` by value (`const T`) rather than by reference (`const T&`). Use `ConstParamT<K>` in `FindLargeKey<K>`, `HashKey`, and `EqualElement` (and `ShouldPreferPassByValue<T>` in `HashSelect::HashValueProbe::Invoke`) so small trivial keys stay in registers across `find_large`, `find_or_prepare_insert_large`, `PolicyTraits::apply`, and `AbslHashValue` calls instead of spilling to the stack and reloading through a reference. PiperOrigin-RevId: 991223700
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h index c438068..9e5762f 100644 --- a/absl/container/internal/common.h +++ b/absl/container/internal/common.h
@@ -89,6 +89,9 @@ template <> struct KeyArg<false> { // Not transparent. Always use `key_type`. + // TODO(ezb): use ConstParamT for non-transparent key arguments. Also + // experiment with using it more widely within non-user-facing functions in + // raw_hash_set. template <typename K, typename key_type> using type = key_type; };
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index c408131..c417752 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -554,11 +554,14 @@ size_t seed; }; +// Pass small trivial keys by value so they are passed in registers rather than +// by reference. +template <class K> +using KeyParamT = type_traits_internal::ConstParamT<K>; + // No arguments function hash function for a specific key. template <class Hash, class Key, bool kIsAbsl, size_t kSeedShift> struct HashKey { - HashKey(const Hash& h, const Key& k) : hash(h), key(k) {} - size_t operator()(size_t seed) const { return HashElement<Hash, kIsAbsl, kSeedShift>{hash, seed}(key); } @@ -568,7 +571,7 @@ return (*static_cast<const HashKey*>(data))(seed); } const Hash& hash; - const Key& key; + KeyParamT<Key> key; }; // Variadic arguments equality function that ignore the rest of the arguments. @@ -579,7 +582,7 @@ bool operator()(const K2& lhs, Args&&...) const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(eq(lhs, rhs)); } - const K1& rhs; + KeyParamT<K1> rhs; const KeyEqual& eq; };
diff --git a/absl/container/internal/raw_hash_map.h b/absl/container/internal/raw_hash_map.h index 8984dfa..d4a7564 100644 --- a/absl/container/internal/raw_hash_map.h +++ b/absl/container/internal/raw_hash_map.h
@@ -382,15 +382,17 @@ // Try to avoid using std::tuple since that slows compilation. // (example: https://godbolt.org/z/nefW93T6K) - if constexpr (ShouldPreferPassByValue<std::conditional_t< - sizeof...(Args) == 0 && - std::is_same_v< - typename std::allocator_traits< - Alloc>::template rebind_alloc<char>, - std::allocator<char>>, - mapped_type, - // Trick to avoid unnecessary template instantiations. - void>>::value) { + if constexpr (type_traits_internal::ShouldPreferPassByValue< + std::conditional_t< + sizeof...(Args) == 0 && + std::is_same_v< + typename std::allocator_traits< + Alloc>::template rebind_alloc<char>, + std::allocator<char>>, + mapped_type, + // Trick to avoid unnecessary template + // instantiations. + void>>::value) { // Common case: operator[] // Note: This has a different run-time performance characteristic than // the other branches, due to the usage of a temporary object. In the
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 9781b5c..4b00848 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2416,36 +2416,12 @@ Alloc>::template rebind_alloc<T>>, T, void>>>; -template <class T> -using ShouldStructurallyPreferPassByValue = std::bool_constant< - // Check if size is a power of 2, to ensure cheap calls. - absl::has_single_bit(sizeof(T)) && - // Check if copying 1-2 registers is enough. We don't want (for example) 32 - // one-byte values to move around, since that sometimes results in poor - // codegen. - alignof(T) * 2 >= sizeof(T) && - sizeof(T) <= sizeof(std::pair<void*, size_t>)>; - -template <class T> -using ShouldSemanticallyPreferPassByValue = - std::bool_constant<std::is_trivially_move_constructible_v<T> && - std::is_trivially_destructible_v<T>>; - -// Checks the given type to see if it is a good candidate for accepting by value -// instead of by rvalue-reference. This includes both a semantic constraint -// (to ensure correctness), as well as a structural constraint (to ensure -// performance). -template <class T> -using ShouldPreferPassByValue = - std::bool_constant<ShouldSemanticallyPreferPassByValue<T>::value && - ShouldStructurallyPreferPassByValue<std::conditional_t< - std::is_void_v<T>, char, T>>::value>; - // This is a 'struct' instead of 'using' in order to avoid eager evaluation for // callers that may be passing incomplete types. template <class T> struct AddConstRefIfExpensive - : std::conditional<ShouldPreferPassByValue<T>::value, T, const T&> { + : std::conditional<type_traits_internal::ShouldPreferPassByValue<T>::value, + T, const T&> { static_assert(std::is_same_v<remove_cvref_t<T>, T>, "passed types must be unqualified"); }; @@ -4093,19 +4069,20 @@ // For string-like keys, we convert to string_view when calling find*_large() // operations to (a) avoid repeatedly (i) branching on SSO or (ii) calling // strlen(), (b) share code between the string-like types, (c) avoid - // materializing string_view on the stack just to pass a reference to it. Note - // that we don't pass FindLargeKey to find*_small() to avoid unnecessarily - // constructing string_view for small empty tables. Note: we use - // type_identity_t and static_asserts to ensure that the key type in - // find*_large is FindLargeKey. (type_identity_t ensures that the template - // argument is not deduced and must be specified explicitly.) - // TODO(ezb): extend this to other types (e.g. small trivial types). + // materializing string_view on the stack just to pass a reference to it. + // For other small trivial keys (see KeyParamT), we pass by value in + // registers rather than by reference. Note that we don't pass FindLargeKey + // to find*_small() to avoid unnecessarily constructing string_view for small + // empty tables. Note: we use type_identity_t and static_asserts to ensure + // that the key type in find*_large is FindLargeKey. (type_identity_t ensures + // that the template argument is not deduced and must be specified + // explicitly.) template <class K> using FindLargeKey = std::conditional_t< std::is_same_v<hasher, absl::container_internal::StringHash> && std::is_same_v<key_equal, absl::container_internal::StringEq> && std::is_convertible_v<const K&, absl::string_view>, - const absl::string_view, const K&>; + const absl::string_view, KeyParamT<K>>; // Prefetch the heap-allocated memory region to resolve potential TLB and // cache misses. This is intended to overlap with execution of calculating the
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index 28cb108..e42e1a0 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -1502,4 +1502,22 @@ #endif } +struct RecursiveHashableType { + template <typename H> + friend H AbslHashValue(H h, const RecursiveHashableType& v) { + return H::combine(std::move(h), v.children); + } + friend bool operator==(const RecursiveHashableType& a, + const RecursiveHashableType& b) { + return a.children == b.children; + } + absl::flat_hash_set<RecursiveHashableType> children; +}; + +TEST(HashTest, IncompleteRecursiveTypeInFlatHashSet) { + RecursiveHashableType root; + root.children.emplace(); + EXPECT_EQ(absl::HashOf(root), absl::HashOf(root)); +} + } // namespace
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 025e57c..68ae414 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -1376,9 +1376,16 @@ } }; + template <typename T> struct HashValueProbe { - template <typename H, typename T> - static H Invoke(H state, const T& value) { + // Use a defaulted template parameter `U = T` to make `ConstParamT<U>` + // dependent on `Invoke`, deferring evaluation of `sizeof` and triviality + // traits until `Invoke` is called. Otherwise, evaluating `is_hashable<T>` + // (which instantiates `HashValueProbe<T>` via `HashSelect::Apply<T>()`) + // while `T` is an incomplete type with a declared `AbslHashValue` overload + // would eagerly instantiate `ConstParamT<T>` and fail to compile. + template <typename H, typename U = T> + static H Invoke(H state, type_traits_internal::ConstParamT<U> value) { return AbslHashValue(std::move(state), value); } }; @@ -1411,7 +1418,7 @@ } else if constexpr (std::is_same_v<State, typename AbslHashValueResultOrVoid< State, const T&>::type>) { - return HashValueProbe(); + return HashValueProbe<T>(); #if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ } else if constexpr (std::is_convertible_v< InvokeResultOrVoid<
diff --git a/absl/meta/type_traits.h b/absl/meta/type_traits.h index b60579c..6f7cc0a 100644 --- a/absl/meta/type_traits.h +++ b/absl/meta/type_traits.h
@@ -635,6 +635,36 @@ IsOwner<absl::remove_cvref_t<U>>, IsView<absl::remove_cvref_t<T>>>; +template <class T> +using ShouldStructurallyPreferPassByValue = std::bool_constant< + // Check if size is a power of 2, to ensure cheap calls. + (sizeof(T) & (sizeof(T) - 1)) == 0 && + // Check if copying 1-2 registers is enough. We don't want (for example) 32 + // one-byte values to move around, since that sometimes results in poor + // codegen. + alignof(T) * 2 >= sizeof(T) && + sizeof(T) <= sizeof(std::pair<void*, size_t>)>; + +template <class T> +using ShouldSemanticallyPreferPassByValue = std::bool_constant< + !std::is_reference_v<T> && + std::is_trivially_move_constructible_v<std::remove_const_t<T>> && + std::is_trivially_copy_constructible_v<T> && + std::is_trivially_destructible_v<T>>; + +// Checks the given type to see if it is a good candidate for accepting by value +// instead of by reference. This includes both a semantic constraint (to ensure +// correctness), as well as a structural constraint (to ensure performance). +template <class T> +using ShouldPreferPassByValue = std::bool_constant< + ShouldSemanticallyPreferPassByValue<T>::value && + ShouldStructurallyPreferPassByValue<std::conditional_t< + ShouldSemanticallyPreferPassByValue<T>::value, T, char>>::value>; + +template <class T> +using ConstParamT = + std::conditional_t<ShouldPreferPassByValue<T>::value, const T, const T&>; + } // namespace type_traits_internal ABSL_NAMESPACE_END
diff --git a/absl/meta/type_traits_test.cc b/absl/meta/type_traits_test.cc index a11049c..8fe3dc6 100644 --- a/absl/meta/type_traits_test.cc +++ b/absl/meta/type_traits_test.cc
@@ -473,4 +473,43 @@ #endif // ABSL_HAVE_CONSTANT_EVALUATED } +TEST(ShouldPreferPassByValue, Basic) { + using absl::type_traits_internal::ShouldPreferPassByValue; + static_assert(ShouldPreferPassByValue<int>::value); + static_assert(ShouldPreferPassByValue<void*>::value); + static_assert(ShouldPreferPassByValue<std::string_view>::value); + static_assert(ShouldPreferPassByValue<std::tuple<int, int>>::value); + static_assert(ShouldPreferPassByValue<const std::tuple<int, int>>::value); + static_assert(!ShouldPreferPassByValue<void>::value); + static_assert(!ShouldPreferPassByValue<char[]>::value); + static_assert(!ShouldPreferPassByValue<const char[]>::value); + static_assert(!ShouldPreferPassByValue<const char (&)[]>::value); + static_assert(!ShouldPreferPassByValue<char[4]>::value); + static_assert(!ShouldPreferPassByValue<int&>::value); + static_assert(!ShouldPreferPassByValue<const int&>::value); + static_assert(!ShouldPreferPassByValue<void()>::value); + static_assert(!ShouldPreferPassByValue<std::string>::value); +} + +TEST(ConstParamT, Basic) { + using absl::type_traits_internal::ConstParamT; + static_assert(std::is_same_v<ConstParamT<int>, const int>); + static_assert(std::is_same_v<ConstParamT<void*>, void* const>); + static_assert( + std::is_same_v<ConstParamT<std::string_view>, const std::string_view>); + static_assert(std::is_same_v<ConstParamT<std::tuple<int, int>>, + const std::tuple<int, int>>); + static_assert(std::is_same_v<ConstParamT<const std::tuple<int, int>>, + const std::tuple<int, int>>); + static_assert(std::is_same_v<ConstParamT<char[]>, const char (&)[]>); + static_assert(std::is_same_v<ConstParamT<const char[]>, const char (&)[]>); + static_assert( + std::is_same_v<ConstParamT<const char (&)[]>, const char (&)[]>); + static_assert(std::is_same_v<ConstParamT<char[4]>, const char (&)[4]>); + static_assert(std::is_same_v<ConstParamT<int&>, int&>); + static_assert(std::is_same_v<ConstParamT<const int&>, const int&>); + static_assert(std::is_same_v<ConstParamT<void()>, void (&)()>); + static_assert(std::is_same_v<ConstParamT<std::string>, const std::string&>); +} + } // namespace