Pass small trivial keys by value in SwissTable lookup and hash/eq helpers. Use `AddConstRefIfExpensiveToCopy<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. We add type traits: `ShouldPreferPassByValueOverConstRef` (based on `ShouldPreferPassByValueOverRRef`) and `AddConstRefIfExpensiveToCopy` (based on `AddConstRefIfExpensive`, which is now renamed to `AddConstRefIfExpensiveToMove`). PiperOrigin-RevId: 991223700
diff --git a/absl/container/internal/common.h b/absl/container/internal/common.h index c438068..344c9fe 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 AddConstRefIfExpensiveToCopy 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..175012f 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -550,6 +550,8 @@ // NOLINTNEXTLINE(clang-diagnostic-sign-conversion) return hash(key) ^ seed; } + // TODO(ezb): try using AddConstRefIfExpensiveToCopy and + // ABSL_ATTRIBUTE_NO_UNIQUE_ADDRESS for `hash`/`eq` functor members. const Hash& hash; size_t seed; }; @@ -557,8 +559,6 @@ // 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 +568,7 @@ return (*static_cast<const HashKey*>(data))(seed); } const Hash& hash; - const Key& key; + type_traits_internal::AddConstRefIfExpensiveToCopy<Key> key; }; // Variadic arguments equality function that ignore the rest of the arguments. @@ -579,7 +579,7 @@ bool operator()(const K2& lhs, Args&&...) const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(eq(lhs, rhs)); } - const K1& rhs; + type_traits_internal::AddConstRefIfExpensiveToCopy<K1> rhs; const KeyEqual& eq; };
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 24fd52c..b7fb4d1 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2358,7 +2358,7 @@ // 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 +struct AddConstRefIfExpensiveToMove : std::conditional_t< type_traits_internal::ShouldPreferPassByValueOverRRef<T>::value, type_identity<T>, std::add_lvalue_reference<std::add_const_t<T>>> { @@ -2369,7 +2369,7 @@ template <class T, class Alloc = std::allocator<T>> using PreferredMoveParamType = typename std::conditional_t< type_traits_internal::IsAllocMoveSameAsCopy<T, Alloc>::value, - AddConstRefIfExpensive<T>, std::add_rvalue_reference<T>>::type; + AddConstRefIfExpensiveToMove<T>, std::add_rvalue_reference<T>>::type; // A SwissTable. // @@ -4020,20 +4020,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). + // strlen(), (b) share code between the string-like types. 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&>; + using FindLargeKey = + type_traits_internal::AddConstRefIfExpensiveToCopy<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 absl::remove_cvref_t<K>&, + absl::string_view>, + absl::string_view, absl::remove_cvref_t<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 c0d3833..5bbb5d1 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -1378,9 +1378,14 @@ } }; + template <typename T> struct HashValueProbe { - template <typename H, typename T> - static H Invoke(H state, const T& value) { + // The std::conditional_t<false, H, T> test is to enable SFINAE by making T + // be a dependent type. + template <typename H> + static H Invoke(H state, type_traits_internal::AddConstRefIfExpensiveToCopy< + std::conditional_t<false, H, T>> + value) { return AbslHashValue(std::move(state), value); } }; @@ -1413,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 3d9657c..6fe09b4 100644 --- a/absl/meta/type_traits.h +++ b/absl/meta/type_traits.h
@@ -720,6 +720,17 @@ std::is_trivially_destructible_v<T>, T, char[SHRT_MAX]>>; +// As above, but for const-lvalue-reference. +template <class T> +using ShouldPreferPassByValueOverConstRef = + std::bool_constant<ShouldPreferPassByValueOverRRef<T>::value && + std::is_trivially_copy_constructible_v<T>>; + +template <class T> +using AddConstRefIfExpensiveToCopy = + std::conditional_t<ShouldPreferPassByValueOverConstRef<T>::value, T, + std::add_lvalue_reference_t<std::add_const_t<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 9543861..bd2f6f6 100644 --- a/absl/meta/type_traits_test.cc +++ b/absl/meta/type_traits_test.cc
@@ -491,6 +491,10 @@ TrivialCopyNonTrivialMove(const TrivialCopyNonTrivialMove&) = default; TrivialCopyNonTrivialMove(TrivialCopyNonTrivialMove&&) {} // NOLINT }; +struct TrivialCopyNoMove { + TrivialCopyNoMove(const TrivialCopyNoMove&) = default; + TrivialCopyNoMove(TrivialCopyNoMove&&) = delete; +}; TEST(ShouldPreferPassByValueOverRRef, Basic) { static_assert(ShouldPreferPassByValueOverRRef<int>::value); @@ -505,6 +509,8 @@ ShouldPreferPassByValueOverRRef<TrivialMoveNonTrivialCopy>::value); static_assert( !ShouldPreferPassByValueOverRRef<TrivialCopyNonTrivialMove>::value); + static_assert( + !ShouldPreferPassByValueOverRRef<TrivialCopyNoMove>::value); static_assert(!ShouldPreferPassByValueOverRRef<void>::value); static_assert(!ShouldPreferPassByValueOverRRef<char[3]>::value); static_assert(!ShouldPreferPassByValueOverRRef<char[4]>::value); @@ -512,6 +518,31 @@ static_assert(!ShouldPreferPassByValueOverRRef<std::shared_ptr<int>>::value); } +TEST(ShouldPreferPassByValueOverConstRef, Basic) { + static_assert(ShouldPreferPassByValueOverConstRef<int>::value); + static_assert(ShouldPreferPassByValueOverConstRef<void*>::value); + static_assert(ShouldPreferPassByValueOverConstRef<UnscopedEnum>::value); + static_assert(ShouldPreferPassByValueOverConstRef<ScopedEnum>::value); + static_assert(ShouldPreferPassByValueOverConstRef<TrivialUnion>::value); + static_assert(ShouldPreferPassByValueOverConstRef<std::string_view>::value); + static_assert( + ShouldPreferPassByValueOverConstRef<std::pair<int, int>>::value); + static_assert( + ShouldPreferPassByValueOverConstRef<std::pair<char, int>>::value); + static_assert( + !ShouldPreferPassByValueOverConstRef<TrivialMoveNonTrivialCopy>::value); + static_assert( + !ShouldPreferPassByValueOverConstRef<TrivialCopyNonTrivialMove>::value); + static_assert( + !ShouldPreferPassByValueOverConstRef<TrivialCopyNoMove>::value); + static_assert(!ShouldPreferPassByValueOverConstRef<void>::value); + static_assert(!ShouldPreferPassByValueOverConstRef<char[3]>::value); + static_assert(!ShouldPreferPassByValueOverConstRef<char[4]>::value); + static_assert(!ShouldPreferPassByValueOverConstRef<std::string>::value); + static_assert( + !ShouldPreferPassByValueOverConstRef<std::shared_ptr<int>>::value); +} + } // namespace } // namespace type_traits_internal ABSL_NAMESPACE_END