Collapse input key/value types and prefer implicit conversions in some cases for flat_hash_map/flat_hash_set - Collapse `T&&` into `const T&` when we can prove the two are equivalent. - Collapse `const T&` into `T` when it is equivalent and possibly cheaper. This avoids some codegen bloat and hopefully increases compile times as well. PiperOrigin-RevId: 993971185 Change-Id: Ib3cf2df93755551e69643d886664fbf70f689d31
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 8c12057..2c353ac 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -833,6 +833,7 @@ "//absl/memory", "//absl/meta:type_traits", "//absl/numeric:bits", + "//absl/strings:string_view", "//absl/utility", ], )
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index cb0b6de..2bdf685 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -829,6 +829,7 @@ absl::optional absl::prefetch absl::raw_logging_internal + absl::string_view absl::utility absl::weakly_mixed_integer PUBLIC
diff --git a/absl/container/internal/raw_hash_map.h b/absl/container/internal/raw_hash_map.h index 8301b50..7904e7b 100644 --- a/absl/container/internal/raw_hash_map.h +++ b/absl/container/internal/raw_hash_map.h
@@ -76,12 +76,18 @@ // // TODO(b/402804213): Remove these traits and simplify the overloads whenever // we have a better mechanism available to handle lifetime analysis. - template <class K, bool Value, typename = void> - using LifetimeBoundK = HasValue< - Value, std::conditional_t<policy_trait_element_is_owner<Policy>::value, - std::false_type, - type_traits_internal::IsLifetimeBoundAssignment< - typename Policy::key_type, K>>>; + // + // MovableOrVoid is an optional, extra constraint (via SFINAE) to guard + // separate move-only overloads. + template <class K, bool Value, typename MovableOrVoid = void> + using LifetimeBoundK = std::bool_constant< + (std::is_void_v<MovableOrVoid> || + !IsAllocMoveSameAsCopy<absl::remove_cvref_t<K>, Alloc>::value) && + HasValue<Value, std::conditional_t< + policy_trait_element_is_owner<Policy>::value, + std::false_type, + type_traits_internal::IsLifetimeBoundAssignment< + typename Policy::key_type, K>>>::value>; template <class V, bool Value, typename = void> using LifetimeBoundV = HasValue<Value, type_traits_internal::IsLifetimeBoundAssignment<
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 824f0f4..2239854 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -181,6 +181,7 @@ #define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_ #include <algorithm> +#include <array> #include <cassert> #include <cmath> #include <cstddef> @@ -191,9 +192,12 @@ #include <iterator> #include <limits> #include <memory> +#include <optional> #include <tuple> #include <type_traits> +#include <typeindex> #include <utility> +#include <variant> #include "absl/base/attributes.h" #include "absl/base/casts.h" @@ -222,6 +226,7 @@ #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" #include "absl/numeric/bits.h" +#include "absl/strings/string_view.h" #include "absl/utility/utility.h" #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L @@ -2292,6 +2297,63 @@ TypeList<Policy, Hash, Eq, Alloc>>::type; }; +template <class T> +using HasTrivialCopyAndMove = + std::bool_constant<std::is_trivially_copy_constructible_v<T> && + std::is_trivially_move_constructible_v<T>>; + +// In principle, being trivially copy- and move-constructible is sufficient +// (though not necessary) for proving copy and move equivalence. However, we +// can't even test that for all types, because not all types are complete at the +// point of evaluation of this trait. Therefore, we restrict this trait to a +// subset of common types that we know to be complete at the point of evaluation +// of this trait. +template <class T> +inline constexpr bool kIsMoveSameAsCopy = HasTrivialCopyAndMove< + std::conditional_t<(!std::is_class_v<T> && !std::is_union_v<T>) || + std::is_same_v<T, std::type_index> || + std::is_same_v<T, absl::string_view>, + T, void>>::value; + +template <class T, class Traits> +inline constexpr bool kIsMoveSameAsCopy<std::basic_string_view<T, Traits>> = + std::is_trivially_copy_constructible_v<std::basic_string_view<T, Traits>>; + +template <class T, size_t N> +inline constexpr bool kIsMoveSameAsCopy<std::array<T, N>> = + kIsMoveSameAsCopy<T>; + +template <class T> +inline constexpr bool kIsMoveSameAsCopy<std::optional<T>> = + kIsMoveSameAsCopy<T>; + +template <class T1, class T2> +inline constexpr bool kIsMoveSameAsCopy<std::pair<T1, T2>> = + kIsMoveSameAsCopy<T1> && kIsMoveSameAsCopy<T2>; + +template <class... T> +inline constexpr bool kIsMoveSameAsCopy<std::tuple<T...>> = + (true && ... && kIsMoveSameAsCopy<T>); + +template <class... T> +inline constexpr bool kIsMoveSameAsCopy<std::variant<T...>> = + (true && ... && kIsMoveSameAsCopy<T>); + +template <class T, class Alloc = std::allocator<T>> +using IsAllocMoveSameAsCopy = + std::bool_constant<kIsMoveSameAsCopy<std::conditional_t< + std::is_same_v<std::allocator<T>, typename std::allocator_traits< + Alloc>::template rebind_alloc<T>>, + T, void>>>; + +template <class T, class Alloc = std::allocator<T>> +using PreferredParamType = std::conditional_t< + IsAllocMoveSameAsCopy<T, Alloc>::value, + std::conditional_t<std::is_arithmetic_v<T> || std::is_enum_v<T> || + std::is_member_pointer_v<T>, + T, const T&>, + T&&>; + // A SwissTable. // // Policy: a policy defines how to perform different operations on @@ -2366,6 +2428,11 @@ using slot_type = typename PolicyTraits::slot_type; + using IsDefaultPolicy = + std::bool_constant<std::is_same_v<Hash, typename Policy::DefaultHash> && + std::is_same_v<Eq, typename Policy::DefaultEq> && + std::is_same_v<Alloc, typename Policy::DefaultAlloc>>; + constexpr static bool kIsAbslHash = std::is_same_v<hasher, absl::Hash<key_type>> || (!HasAbslContainerHash<key_type>::value && @@ -2455,8 +2522,13 @@ using Insertable = std::disjunction< std::is_same<absl::remove_cvref_t<reference>, absl::remove_cvref_t<T>>, std::is_convertible<T, init_type>>; + + // Bit-fields cannot be moved, and types with trivial copy and move + // constructors should also not be moved. template <class T> - using IsNotBitField = std::is_pointer<T*>; + using EnableElementMoveFrom = + std::bool_constant<std::is_pointer_v<T*> && + !IsAllocMoveSameAsCopy<T, Alloc>::value>; // RequiresNotInit is a workaround for gcc prior to 7.1. // See https://godbolt.org/g/Y4xsUh. @@ -2925,7 +2997,7 @@ // m.insert(std::make_pair("abc", 42)); template <class T, int = std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && !IsLifetimeBoundAssignmentFrom<T>::value, int>()> std::pair<iterator, bool> insert(T&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { @@ -2934,7 +3006,7 @@ template <class T, int&..., std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && IsLifetimeBoundAssignmentFrom<T>::value, int> = 0> std::pair<iterator, bool> insert( @@ -2977,7 +3049,7 @@ // // flat_hash_map<std::string, int> s; // s.insert({"abc", 42}); - std::pair<iterator, bool> insert(init_type&& value) + std::pair<iterator, bool> insert(PreferredParamType<init_type, Alloc> value) ABSL_ATTRIBUTE_LIFETIME_BOUND #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L requires(!IsLifetimeBoundAssignmentFrom<init_type>::value) @@ -2986,8 +3058,8 @@ return emplace(std::move(value)); } #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L - std::pair<iterator, bool> insert( - init_type&& value ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY_THIS) + std::pair<iterator, bool> insert(PreferredParamType<init_type, Alloc> value + ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY_THIS) ABSL_ATTRIBUTE_LIFETIME_BOUND requires(IsLifetimeBoundAssignmentFrom<init_type>::value) { @@ -2997,7 +3069,7 @@ template <class T, int = std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && !IsLifetimeBoundAssignmentFrom<T>::value, int>()> iterator insert(const_iterator, T&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { @@ -3005,7 +3077,7 @@ } template <class T, int&..., std::enable_if_t<IsDecomposableAndInsertable<T>::value && - IsNotBitField<T>::value && + EnableElementMoveFrom<T>::value && IsLifetimeBoundAssignmentFrom<T>::value, int> = 0> iterator insert(const_iterator hint, @@ -3021,8 +3093,8 @@ return insert(value).first; } - iterator insert(const_iterator, - init_type&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { + iterator insert(const_iterator, PreferredParamType<init_type, Alloc> value) + ABSL_ATTRIBUTE_LIFETIME_BOUND { return insert(std::move(value)).first; }
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 3ad18c9..a4254ed 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -36,11 +36,13 @@ #include <random> #include <set> #include <string> +#include <string_view> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> +#include <variant> #include <vector> #include "gmock/gmock.h" @@ -1921,6 +1923,94 @@ Pair("DEF", "!!!"))); } +struct CopyTracker { + static inline int num_copies = 0; + CopyTracker() = default; + CopyTracker(const CopyTracker&) { ++num_copies; } + CopyTracker(CopyTracker&&) = default; + + bool operator==(const CopyTracker&) const { return true; } + + template <typename H> + friend H AbslHashValue(H h, const CopyTracker&) { + return H::combine(std::move(h)); + } +}; + +struct MoveTracker { + static inline int num_destructions = 0; + static inline int num_moves = 0; + ~MoveTracker() { ++num_destructions; } + MoveTracker() = default; + MoveTracker(const MoveTracker&) = default; + MoveTracker(MoveTracker&&) { ++num_moves; } + + bool operator==(const MoveTracker&) const { return true; } + + template <typename H> + friend H AbslHashValue(H h, const MoveTracker&) { + return H::combine(std::move(h)); + } +}; + +TEST(Table, InsertDoesNotAccidentallyCopy) { + CopyTracker::num_copies = 0; + { + ValueTable<CopyTracker> tc; + EXPECT_TRUE(tc.insert(CopyTracker()).second); + tc.insert(tc.end(), CopyTracker()); + } + EXPECT_EQ(CopyTracker::num_copies, 0); + + int num_default_constructs = 0; + MoveTracker::num_moves = 0; + MoveTracker::num_destructions = 0; + { + ValueTable<MoveTracker> tm; + EXPECT_TRUE(tm.insert((++num_default_constructs, MoveTracker())).second); + tm.insert(tm.end(), (++num_default_constructs, MoveTracker())); + } + EXPECT_EQ(MoveTracker::num_destructions - num_default_constructs, + MoveTracker::num_moves); +} + +TEST(Table, InsertWithMovesCollapsedIntoCopy) { + { + ValueTable<std::string_view> t; + EXPECT_TRUE(t.insert(std::string_view("a")).second); + EXPECT_EQ(*t.insert(t.end(), std::string_view("b")), "b"); + } + { + ValueTable<std::array<int, 2>> t; + EXPECT_TRUE(t.insert(std::array<int, 2>{1, 2}).second); + EXPECT_EQ(*t.insert(t.end(), std::array<int, 2>{3, 4}), + (std::array<int, 2>{3, 4})); + } + { + ValueTable<std::optional<int>> t; + EXPECT_TRUE(t.insert(std::optional<int>(1)).second); + EXPECT_EQ(*t.insert(t.end(), std::optional<int>(2)), 2); + } + { + ValueTable<std::pair<int, int>> t; + EXPECT_TRUE(t.insert(std::pair<int, int>{1, 2}).second); + EXPECT_EQ(*t.insert(t.end(), std::pair<int, int>{3, 4}), + (std::pair<int, int>{3, 4})); + } + { + ValueTable<std::tuple<int, int>> t; + EXPECT_TRUE(t.insert(std::tuple<int, int>{1, 2}).second); + EXPECT_EQ(*t.insert(t.end(), std::tuple<int, int>{3, 4}), + (std::tuple<int, int>{3, 4})); + } + { + ValueTable<std::variant<int, double>> t; + EXPECT_TRUE(t.insert(std::variant<int, double>{1}).second); + EXPECT_EQ(*t.insert(t.end(), std::variant<int, double>{2.5}), + (std::variant<int, double>{2.5})); + } +} + TYPED_TEST(SooTest, LargeTable) { TypeParam t; for (int64_t i = 0; i != 10000; ++i) {