From c44dd5acd7848a175d1fb939cdb81a4cf8d4c912 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 30 Jan 2024 12:52:43 -0800 Subject: Early return from destroy_slots for trivially destructible types in flat_hash_{*}. PiperOrigin-RevId: 602813933 Change-Id: I744fe438281755a141b2fd47e54ab9c6c0fad5a3 --- absl/container/BUILD.bazel | 2 + absl/container/CMakeLists.txt | 2 + absl/container/flat_hash_map.h | 5 +- absl/container/flat_hash_map_test.cc | 12 ++++ absl/container/flat_hash_set.h | 5 +- absl/container/flat_hash_set_test.cc | 12 ++++ absl/container/internal/common_policy_traits.h | 12 +++- .../internal/common_policy_traits_test.cc | 65 +++++++++++++++------- absl/container/internal/container_memory.h | 15 ++++- absl/container/internal/container_memory_test.cc | 18 ++++++ absl/container/internal/raw_hash_set.h | 1 + 11 files changed, 122 insertions(+), 27 deletions(-) diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index fda866a5..bc5b2201 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -264,6 +264,7 @@ cc_test( deps = [ ":flat_hash_map", ":hash_generator_testing", + ":test_allocator", ":unordered_map_constructor_test", ":unordered_map_lookup_test", ":unordered_map_members_test", @@ -301,6 +302,7 @@ cc_test( ":container_memory", ":flat_hash_set", ":hash_generator_testing", + ":test_allocator", ":unordered_set_constructor_test", ":unordered_set_lookup_test", ":unordered_set_members_test", diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index ee9ca9c3..3f80d29b 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -307,6 +307,7 @@ absl_cc_test( absl::check absl::flat_hash_map absl::hash_generator_testing + absl::test_allocator absl::type_traits absl::unordered_map_constructor_test absl::unordered_map_lookup_test @@ -348,6 +349,7 @@ absl_cc_test( absl::hash_generator_testing absl::memory absl::strings + absl::test_allocator absl::unordered_set_constructor_test absl::unordered_set_lookup_test absl::unordered_set_members_test diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index acd013b0..808a62ba 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h @@ -573,9 +573,10 @@ struct FlatHashMapPolicy { slot_policy::construct(alloc, slot, std::forward(args)...); } + // Returns std::true_type in case destroy is trivial. template - static void destroy(Allocator* alloc, slot_type* slot) { - slot_policy::destroy(alloc, slot); + static auto destroy(Allocator* alloc, slot_type* slot) { + return slot_policy::destroy(alloc, slot); } template diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc index d90fe9d5..8ef1a62b 100644 --- a/absl/container/flat_hash_map_test.cc +++ b/absl/container/flat_hash_map_test.cc @@ -22,6 +22,7 @@ #include "gtest/gtest.h" #include "absl/container/internal/hash_generator_testing.h" +#include "absl/container/internal/test_allocator.h" #include "absl/container/internal/unordered_map_constructor_test.h" #include "absl/container/internal/unordered_map_lookup_test.h" #include "absl/container/internal/unordered_map_members_test.h" @@ -351,6 +352,17 @@ TEST(FlatHashMap, RecursiveTypeCompiles) { t.m[0] = RecursiveType{}; } +TEST(FlatHashMap, FlatHashMapPolicyDestroyReturnsTrue) { + EXPECT_TRUE( + (decltype(FlatHashMapPolicy::destroy>( + nullptr, nullptr))())); + EXPECT_FALSE( + (decltype(FlatHashMapPolicy::destroy>( + nullptr, nullptr))())); + EXPECT_FALSE((decltype(FlatHashMapPolicy>::destroy< + std::allocator>(nullptr, nullptr))())); +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index a94a82a0..cd74923c 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h @@ -29,6 +29,7 @@ #ifndef ABSL_CONTAINER_FLAT_HASH_SET_H_ #define ABSL_CONTAINER_FLAT_HASH_SET_H_ +#include #include #include @@ -473,9 +474,11 @@ struct FlatHashSetPolicy { std::forward(args)...); } + // Return std::true_type in case destroy is trivial. template - static void destroy(Allocator* alloc, slot_type* slot) { + static auto destroy(Allocator* alloc, slot_type* slot) { absl::allocator_traits::destroy(*alloc, slot); + return IsDestructionTrivial(); } static T& element(slot_type* slot) { return *slot; } diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc index a60b4bf5..9ce9267e 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc @@ -16,6 +16,7 @@ #include #include +#include #include #include @@ -24,6 +25,7 @@ #include "absl/base/config.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_generator_testing.h" +#include "absl/container/internal/test_allocator.h" #include "absl/container/internal/unordered_set_constructor_test.h" #include "absl/container/internal/unordered_set_lookup_test.h" #include "absl/container/internal/unordered_set_members_test.h" @@ -237,6 +239,16 @@ TEST(FlatHashSet, PoisonInline) { } } +TEST(FlatHashSet, FlatHashSetPolicyDestroyReturnsTrue) { + EXPECT_TRUE((decltype(FlatHashSetPolicy::destroy>( + nullptr, nullptr))())); + EXPECT_FALSE( + (decltype(FlatHashSetPolicy::destroy>( + nullptr, nullptr))())); + EXPECT_FALSE((decltype(FlatHashSetPolicy>::destroy< + std::allocator>(nullptr, nullptr))())); +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/common_policy_traits.h b/absl/container/internal/common_policy_traits.h index 57eac678..77df4790 100644 --- a/absl/container/internal/common_policy_traits.h +++ b/absl/container/internal/common_policy_traits.h @@ -45,9 +45,10 @@ struct common_policy_traits { // PRECONDITION: `slot` is INITIALIZED // POSTCONDITION: `slot` is UNINITIALIZED + // Returns std::true_type in case destroy is trivial. template - static void destroy(Alloc* alloc, slot_type* slot) { - Policy::destroy(alloc, slot); + static auto destroy(Alloc* alloc, slot_type* slot) { + return Policy::destroy(alloc, slot); } // Transfers the `old_slot` to `new_slot`. Any memory allocated by the @@ -86,6 +87,13 @@ struct common_policy_traits { std::true_type>::value; } + // Returns true if destroy is trivial and can be omitted. + template + static constexpr bool destroy_is_trivial() { + return std::is_same(nullptr, nullptr)), + std::true_type>::value; + } + private: // To rank the overloads below for overload resolution. Rank0 is preferred. struct Rank2 {}; diff --git a/absl/container/internal/common_policy_traits_test.cc b/absl/container/internal/common_policy_traits_test.cc index faee3e7a..8d8f8baa 100644 --- a/absl/container/internal/common_policy_traits_test.cc +++ b/absl/container/internal/common_policy_traits_test.cc @@ -39,44 +39,59 @@ struct PolicyWithoutOptionalOps { using key_type = Slot; using init_type = Slot; - static std::function construct; - static std::function destroy; + struct PolicyFunctions { + std::function construct; + std::function destroy; + std::function element; + }; + + static PolicyFunctions* functions() { + static PolicyFunctions* functions = new PolicyFunctions(); + return functions; + } - static std::function element; + static void construct(void* a, Slot* b, Slot c) { + functions()->construct(a, b, c); + } + static void destroy(void* a, Slot* b) { functions()->destroy(a, b); } + static Slot& element(Slot* b) { return functions()->element(b); } }; -std::function PolicyWithoutOptionalOps::construct; -std::function PolicyWithoutOptionalOps::destroy; - -std::function PolicyWithoutOptionalOps::element; - struct PolicyWithOptionalOps : PolicyWithoutOptionalOps { - static std::function transfer; + struct TransferFunctions { + std::function transfer; + }; + + static TransferFunctions* transfer_fn() { + static TransferFunctions* transfer_fn = new TransferFunctions(); + return transfer_fn; + } + static void transfer(void* a, Slot* b, Slot* c) { + transfer_fn()->transfer(a, b, c); + } }; -std::function PolicyWithOptionalOps::transfer; -struct PolicyWithMemcpyTransfer : PolicyWithoutOptionalOps { - static std::function transfer; +struct PolicyWithMemcpyTransferAndTrivialDestroy : PolicyWithoutOptionalOps { + static std::true_type transfer(void*, Slot*, Slot*) { return {}; } + static std::true_type destroy(void*, Slot*) { return {}; } }; -std::function - PolicyWithMemcpyTransfer::transfer; struct Test : ::testing::Test { Test() { - PolicyWithoutOptionalOps::construct = [&](void* a1, Slot* a2, Slot a3) { + PolicyWithoutOptionalOps::functions()->construct = [&](void* a1, Slot* a2, + Slot a3) { construct.Call(a1, a2, std::move(a3)); }; - PolicyWithoutOptionalOps::destroy = [&](void* a1, Slot* a2) { + PolicyWithoutOptionalOps::functions()->destroy = [&](void* a1, Slot* a2) { destroy.Call(a1, a2); }; - PolicyWithoutOptionalOps::element = [&](Slot* a1) -> Slot& { + PolicyWithoutOptionalOps::functions()->element = [&](Slot* a1) -> Slot& { return element.Call(a1); }; - PolicyWithOptionalOps::transfer = [&](void* a1, Slot* a2, Slot* a3) { - return transfer.Call(a1, a2, a3); - }; + PolicyWithOptionalOps::transfer_fn()->transfer = + [&](void* a1, Slot* a2, Slot* a3) { return transfer.Call(a1, a2, a3); }; } std::allocator alloc; @@ -125,7 +140,15 @@ TEST(TransferUsesMemcpy, Basic) { EXPECT_FALSE( common_policy_traits::transfer_uses_memcpy()); EXPECT_TRUE( - common_policy_traits::transfer_uses_memcpy()); + common_policy_traits< + PolicyWithMemcpyTransferAndTrivialDestroy>::transfer_uses_memcpy()); +} + +TEST(DestroyIsTrivial, Basic) { + EXPECT_FALSE(common_policy_traits::destroy_is_trivial< + std::allocator>()); + EXPECT_TRUE(common_policy_traits:: + destroy_is_trivial>()); } } // namespace diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 3262d4eb..d86d7b80 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h @@ -68,6 +68,18 @@ void* Allocate(Alloc* alloc, size_t n) { return p; } +// Returns true if the destruction of the value with given Allocator will be +// trivial. +template +constexpr auto IsDestructionTrivial() { + constexpr bool result = + std::is_trivially_destructible::value && + std::is_same::template rebind_alloc, + std::allocator>::value; + return std::integral_constant(); +} + // The pointer must have been previously obtained by calling // Allocate(alloc, n). template @@ -414,12 +426,13 @@ struct map_slot_policy { } template - static void destroy(Allocator* alloc, slot_type* slot) { + static auto destroy(Allocator* alloc, slot_type* slot) { if (kMutableKeys::value) { absl::allocator_traits::destroy(*alloc, &slot->mutable_value); } else { absl::allocator_traits::destroy(*alloc, &slot->value); } + return IsDestructionTrivial(); } template diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index 90d64bf5..c973ac25 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc @@ -280,6 +280,24 @@ TEST(MapSlotPolicy, TransferReturnsTrue) { } } +TEST(MapSlotPolicy, DestroyReturnsTrue) { + { + using slot_policy = map_slot_policy; + EXPECT_TRUE( + (std::is_same>( + nullptr, nullptr)), + std::true_type>::value)); + } + { + EXPECT_FALSE(std::is_trivially_destructible>::value); + using slot_policy = map_slot_policy>; + EXPECT_TRUE( + (std::is_same>( + nullptr, nullptr)), + std::false_type>::value)); + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index ba7df607..9f16a815 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -2881,6 +2881,7 @@ class raw_hash_set { } inline void destroy_slots() { + if (PolicyTraits::template destroy_is_trivial()) return; const size_t cap = capacity(); const ctrl_t* ctrl = control(); slot_type* slot = slot_array(); -- cgit v1.2.3