Early return from destroy_slots for trivially destructible types in flat_hash_{*}.

PiperOrigin-RevId: 602813933
Change-Id: I744fe438281755a141b2fd47e54ab9c6c0fad5a3

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>(args)...);
   }
 
+  // Returns std::true_type in case destroy is trivial.
   template <class Allocator>
-  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 <class Allocator>
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<int, char>::destroy<std::allocator<char>>(
+          nullptr, nullptr))()));
+  EXPECT_FALSE(
+      (decltype(FlatHashMapPolicy<int, char>::destroy<CountingAllocator<char>>(
+          nullptr, nullptr))()));
+  EXPECT_FALSE((decltype(FlatHashMapPolicy<int, std::unique_ptr<int>>::destroy<
+                         std::allocator<char>>(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 <memory>
 #include <type_traits>
 #include <utility>
 
@@ -473,9 +474,11 @@ struct FlatHashSetPolicy {
                                                  std::forward<Args>(args)...);
   }
 
+  // Return std::true_type in case destroy is trivial.
   template <class Allocator>
-  static void destroy(Allocator* alloc, slot_type* slot) {
+  static auto destroy(Allocator* alloc, slot_type* slot) {
     absl::allocator_traits<Allocator>::destroy(*alloc, slot);
+    return IsDestructionTrivial<Allocator, slot_type>();
   }
 
   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 <cstdint>
 #include <memory>
+#include <type_traits>
 #include <utility>
 #include <vector>
 
@@ -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<int>::destroy<std::allocator<int>>(
+      nullptr, nullptr))()));
+  EXPECT_FALSE(
+      (decltype(FlatHashSetPolicy<int>::destroy<CountingAllocator<int>>(
+          nullptr, nullptr))()));
+  EXPECT_FALSE((decltype(FlatHashSetPolicy<std::unique_ptr<int>>::destroy<
+                         std::allocator<int>>(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 <class Alloc>
-  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 <class Alloc>
+  static constexpr bool destroy_is_trivial() {
+    return std::is_same<decltype(destroy<Alloc>(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<void(void*, Slot*, Slot)> construct;
-  static std::function<void(void*, Slot*)> destroy;
+  struct PolicyFunctions {
+    std::function<void(void*, Slot*, Slot)> construct;
+    std::function<void(void*, Slot*)> destroy;
+    std::function<Slot&(Slot*)> element;
+  };
+
+  static PolicyFunctions* functions() {
+    static PolicyFunctions* functions = new PolicyFunctions();
+    return functions;
+  }
 
-  static std::function<Slot&(Slot*)> 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<void(void*, Slot*, Slot)> PolicyWithoutOptionalOps::construct;
-std::function<void(void*, Slot*)> PolicyWithoutOptionalOps::destroy;
-
-std::function<Slot&(Slot*)> PolicyWithoutOptionalOps::element;
-
 struct PolicyWithOptionalOps : PolicyWithoutOptionalOps {
-  static std::function<void(void*, Slot*, Slot*)> transfer;
+  struct TransferFunctions {
+    std::function<void(void*, Slot*, Slot*)> 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<void(void*, Slot*, Slot*)> PolicyWithOptionalOps::transfer;
 
-struct PolicyWithMemcpyTransfer : PolicyWithoutOptionalOps {
-  static std::function<std::true_type(void*, Slot*, Slot*)> transfer;
+struct PolicyWithMemcpyTransferAndTrivialDestroy : PolicyWithoutOptionalOps {
+  static std::true_type transfer(void*, Slot*, Slot*) { return {}; }
+  static std::true_type destroy(void*, Slot*) { return {}; }
 };
-std::function<std::true_type(void*, Slot*, Slot*)>
-    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<Slot> alloc;
@@ -125,7 +140,15 @@ TEST(TransferUsesMemcpy, Basic) {
   EXPECT_FALSE(
       common_policy_traits<PolicyWithOptionalOps>::transfer_uses_memcpy());
   EXPECT_TRUE(
-      common_policy_traits<PolicyWithMemcpyTransfer>::transfer_uses_memcpy());
+      common_policy_traits<
+          PolicyWithMemcpyTransferAndTrivialDestroy>::transfer_uses_memcpy());
+}
+
+TEST(DestroyIsTrivial, Basic) {
+  EXPECT_FALSE(common_policy_traits<PolicyWithOptionalOps>::destroy_is_trivial<
+               std::allocator<char>>());
+  EXPECT_TRUE(common_policy_traits<PolicyWithMemcpyTransferAndTrivialDestroy>::
+                  destroy_is_trivial<std::allocator<char>>());
 }
 
 }  // 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 <class Allocator, class ValueType>
+constexpr auto IsDestructionTrivial() {
+  constexpr bool result =
+      std::is_trivially_destructible<ValueType>::value &&
+      std::is_same<typename absl::allocator_traits<
+                       Allocator>::template rebind_alloc<char>,
+                   std::allocator<char>>::value;
+  return std::integral_constant<bool, result>();
+}
+
 // The pointer must have been previously obtained by calling
 // Allocate<Alignment>(alloc, n).
 template <size_t Alignment, class Alloc>
@@ -414,12 +426,13 @@ struct map_slot_policy {
   }
 
   template <class Allocator>
-  static void destroy(Allocator* alloc, slot_type* slot) {
+  static auto destroy(Allocator* alloc, slot_type* slot) {
     if (kMutableKeys::value) {
       absl::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
     } else {
       absl::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
     }
+    return IsDestructionTrivial<Allocator, value_type>();
   }
 
   template <class Allocator>
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<int, float>;
+    EXPECT_TRUE(
+        (std::is_same<decltype(slot_policy::destroy<std::allocator<char>>(
+                          nullptr, nullptr)),
+                      std::true_type>::value));
+  }
+  {
+    EXPECT_FALSE(std::is_trivially_destructible<std::unique_ptr<int>>::value);
+    using slot_policy = map_slot_policy<int, std::unique_ptr<int>>;
+    EXPECT_TRUE(
+        (std::is_same<decltype(slot_policy::destroy<std::allocator<char>>(
+                          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<Alloc>()) return;
     const size_t cap = capacity();
     const ctrl_t* ctrl = control();
     slot_type* slot = slot_array();