[gcc r13-8421] libstdc++: Optimize std::to_array for trivial types [PR110167]

[Jonathan Wakely]

https://gcc.gnu.org/g:4c6bb36e88d5c8e510b10d12c01e3461c2aa4259

commit r13-8421-g4c6bb36e88d5c8e510b10d12c01e3461c2aa4259
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jun 8 12:24:43 2023 +0100

    libstdc++: Optimize std::to_array for trivial types [PR110167]
    
    As reported in PR libstdc++/110167, std::to_array compiles extremely
    slowly for very large arrays. It needs to instantiate a very large
    specialization of std::index_sequence<N...> and then create a very large
    aggregate initializer from the pack expansion. For trivial types we can
    simply default-initialize the std::array and then use memcpy to copy the
    values. For non-trivial types we need to use the existing
    implementation, despite the compilation cost.
    
    As also noted in the PR, using a generic lambda instead of the
    __to_array helper compiles faster since gcc-13. It also produces
    slightly smaller code at -O1, due to additional inlining. The code at
    -Os, -O2 and -O3 seems to be the same. This new implementation requires
    __cpp_generic_lambdas >= 201707L (i.e. P0428R2) but that is supported
    since Clang 10 and since Intel icc 2021.5.0 (and since GCC 10.1).
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/110167
            * include/std/array (to_array): Initialize arrays of trivial
            types using memcpy. For non-trivial types, use lambda
            expressions instead of a separate helper function.
            (__to_array): Remove.
            * testsuite/23_containers/array/creation/110167.cc: New test.
    
    (cherry picked from commit 960de5dd886572711ef86fa1e15e30d3810eccb9)

Diff:
---
 libstdc++-v3/include/std/array                     | 53 +++++++++++++++-------
 .../23_containers/array/creation/110167.cc         | 14 ++++++
 2 files changed, 51 insertions(+), 16 deletions(-)

diff --git a/libstdc++-v3/include/std/array b/libstdc++-v3/include/std/array
index 97cca454ef9..edcac892b52 100644
--- a/libstdc++-v3/include/std/array
+++ b/libstdc++-v3/include/std/array
@@ -414,19 +414,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return std::move(std::get<_Int>(__arr));
     }
 
-#if __cplusplus > 201703L
+#if __cplusplus >= 202002L && __cpp_generic_lambdas >= 201707L
 #define __cpp_lib_to_array 201907L
-
-  template<bool _Move = false, typename _Tp, size_t... _Idx>
-    constexpr array<remove_cv_t<_Tp>, sizeof...(_Idx)>
-    __to_array(_Tp (&__a)[sizeof...(_Idx)], index_sequence<_Idx...>)
-    {
-      if constexpr (_Move)
-	return {{std::move(__a[_Idx])...}};
-      else
-	return {{__a[_Idx]...}};
-    }
-
   template<typename _Tp, size_t _Nm>
     [[nodiscard]]
     constexpr array<remove_cv_t<_Tp>, _Nm>
@@ -436,8 +425,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static_assert(!is_array_v<_Tp>);
       static_assert(is_constructible_v<_Tp, _Tp&>);
       if constexpr (is_constructible_v<_Tp, _Tp&>)
-	return std::__to_array(__a, make_index_sequence<_Nm>{});
-      __builtin_unreachable(); // FIXME: see PR c++/91388
+	{
+	  if constexpr (is_trivial_v<_Tp>)
+	    {
+	      array<remove_cv_t<_Tp>, _Nm> __arr;
+	      if (!__is_constant_evaluated() && _Nm != 0)
+		__builtin_memcpy((void*)__arr.data(), (void*)__a, sizeof(__a));
+	      else
+		for (size_t __i = 0; __i < _Nm; ++__i)
+		  __arr._M_elems[__i] = __a[__i];
+	      return __arr;
+	    }
+	  else
+	    return [&__a]<size_t... _Idx>(index_sequence<_Idx...>) {
+	      return array<remove_cv_t<_Tp>, _Nm>{{ __a[_Idx]... }};
+	    }(make_index_sequence<_Nm>{});
+	}
+      else
+	__builtin_unreachable(); // FIXME: see PR c++/91388
     }
 
   template<typename _Tp, size_t _Nm>
@@ -449,8 +454,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static_assert(!is_array_v<_Tp>);
       static_assert(is_move_constructible_v<_Tp>);
       if constexpr (is_move_constructible_v<_Tp>)
-	return std::__to_array<1>(__a, make_index_sequence<_Nm>{});
-      __builtin_unreachable(); // FIXME: see PR c++/91388
+	{
+	  if constexpr (is_trivial_v<_Tp>)
+	    {
+	      array<remove_cv_t<_Tp>, _Nm> __arr;
+	      if (!__is_constant_evaluated() && _Nm != 0)
+		__builtin_memcpy((void*)__arr.data(), (void*)__a, sizeof(__a));
+	      else
+		for (size_t __i = 0; __i < _Nm; ++__i)
+		  __arr._M_elems[__i] = __a[__i];
+	      return __arr;
+	    }
+	  else
+	    return [&__a]<size_t... _Idx>(index_sequence<_Idx...>) {
+	      return array<remove_cv_t<_Tp>, _Nm>{{ std::move(__a[_Idx])... }};
+	    }(make_index_sequence<_Nm>{});
+	}
+      else
+	__builtin_unreachable(); // FIXME: see PR c++/91388
     }
 #endif // C++20
 
diff --git a/libstdc++-v3/testsuite/23_containers/array/creation/110167.cc b/libstdc++-v3/testsuite/23_containers/array/creation/110167.cc
new file mode 100644
index 00000000000..c2aecc911bd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/array/creation/110167.cc
@@ -0,0 +1,14 @@
+// { dg-options "-std=gnu++20" }
+// { dg-do compile { target c++20 } }
+
+// PR libstdc++/110167 - excessive compile time when optimizing std::to_array
+
+#include <array>
+
+constexpr int N = 512 * 512;
+
+std::array<int, N>
+make_std_array(int (&a)[N])
+{
+  return std::to_array(a);
+}