[PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h>

[PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h>

[Jonathan Wakely]

This refactoring to use RAII doesn't seem to make any difference in
benchmarks, although the generated code for some std::vector operations
seems to be slightly larger. Maybe it will be faster (or slower) in some
cases I didn't test?

I think I like the change anyway - any other opinions on whether it's an
improvement?

Tested x86_64-linux.

-- >8 --

This adds an _UninitDestroyGuard class template, similar to
ranges::_DestroyGuard used in <bits/ranges_uninitialized.h>. This allows
us to remove all the try-catch blocks and rethrows, because any required
cleanup gets done in the guard destructor.

libstdc++-v3/ChangeLog:

	* include/bits/stl_uninitialized.h (_UninitDestroyGuard): New
	class template and partial specialization.
	(__do_uninit_copy, __do_uninit_fill, __do_uninit_fill_n)
	(__uninitialized_copy_a, __uninitialized_fill_a)
	(__uninitialized_fill_n_a, __uninitialized_copy_move)
	(__uninitialized_move_copy, __uninitialized_fill_move)
	(__uninitialized_move_fill, __uninitialized_default_1)
	(__uninitialized_default_n_a, __uninitialized_default_novalue_1)
	(__uninitialized_default_novalue_n_1, __uninitialized_copy_n)
	(__uninitialized_copy_n_pair): Use it.
---
 libstdc++-v3/include/bits/stl_uninitialized.h | 365 ++++++++----------
 1 file changed, 156 insertions(+), 209 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
index 3c405d8fbe8..a9965f26269 100644
--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -107,24 +107,70 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __is_trivial(T) && __is_assignable(T&, U)
 #endif
 
+  template<typename _ForwardIterator, typename _Alloc = void>
+    struct _UninitDestroyGuard
+    {
+      _GLIBCXX20_CONSTEXPR
+      explicit
+      _UninitDestroyGuard(_ForwardIterator& __first, _Alloc& __a)
+      : _M_first(__first), _M_cur(__builtin_addressof(__first)), _M_alloc(__a)
+      { }
+
+      _GLIBCXX20_CONSTEXPR
+      ~_UninitDestroyGuard()
+      {
+	if (__builtin_expect(_M_cur != 0, 0))
+	  std::_Destroy(_M_first, *_M_cur, _M_alloc);
+      }
+
+      _GLIBCXX20_CONSTEXPR
+      void release() { _M_cur = 0; }
+
+    private:
+      _ForwardIterator const _M_first;
+      _ForwardIterator* _M_cur;
+      _Alloc& _M_alloc;
+
+      _UninitDestroyGuard(const _UninitDestroyGuard&);
+    };
+
+  template<typename _ForwardIterator>
+    struct _UninitDestroyGuard<_ForwardIterator, void>
+    {
+      _GLIBCXX20_CONSTEXPR
+      explicit
+      _UninitDestroyGuard(_ForwardIterator& __first)
+      : _M_first(__first), _M_cur(__builtin_addressof(__first))
+      { }
+
+      _GLIBCXX20_CONSTEXPR
+      ~_UninitDestroyGuard()
+      {
+	if (__builtin_expect(_M_cur != 0, 0))
+	  std::_Destroy(_M_first, *_M_cur);
+      }
+
+      _GLIBCXX20_CONSTEXPR
+      void release() { _M_cur = 0; }
+
+      _ForwardIterator const _M_first;
+      _ForwardIterator* _M_cur;
+
+    private:
+      _UninitDestroyGuard(const _UninitDestroyGuard&);
+    };
+
   template<typename _InputIterator, typename _ForwardIterator>
     _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __do_uninit_copy(_InputIterator __first, _InputIterator __last,
 		     _ForwardIterator __result)
     {
-      _ForwardIterator __cur = __result;
-      __try
-	{
-	  for (; __first != __last; ++__first, (void)++__cur)
-	    std::_Construct(std::__addressof(*__cur), *__first);
-	  return __cur;
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __cur);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator> __guard(__result);
+      for (; __first != __last; ++__first, (void)++__result)
+	std::_Construct(std::__addressof(*__result), *__first);
+      __guard.release();
+      return __result;
     }
 
   template<bool _TrivialValueTypes>
@@ -192,17 +238,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __do_uninit_fill(_ForwardIterator __first, _ForwardIterator __last,
 		     const _Tp& __x)
     {
-      _ForwardIterator __cur = __first;
-      __try
-	{
-	  for (; __cur != __last; ++__cur)
-	    std::_Construct(std::__addressof(*__cur), __x);
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first, __cur);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+      for (; __first != __last; ++__first)
+	std::_Construct(std::__addressof(*__first), __x);
+      __guard.release();
     }
 
   template<bool _TrivialValueType>
@@ -260,18 +299,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _ForwardIterator
     __do_uninit_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
     {
-      _ForwardIterator __cur = __first;
-      __try
-	{
-	  for (; __n > 0; --__n, (void) ++__cur)
-	    std::_Construct(std::__addressof(*__cur), __x);
-	  return __cur;
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first, __cur);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+      for (; __n > 0; --__n, (void) ++__first)
+	std::_Construct(std::__addressof(*__first), __x);
+      __guard.release();
+      return __first;
     }
 
   template<bool _TrivialValueType>
@@ -344,19 +376,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
 			   _ForwardIterator __result, _Allocator& __alloc)
     {
-      _ForwardIterator __cur = __result;
-      __try
-	{
-	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
-	  for (; __first != __last; ++__first, (void)++__cur)
-	    __traits::construct(__alloc, std::__addressof(*__cur), *__first);
-	  return __cur;
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __cur, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator>
+	__guard(__result, __alloc);
+
+      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
+      for (; __first != __last; ++__first, (void)++__result)
+	__traits::construct(__alloc, std::__addressof(*__result), *__first);
+      __guard.release();
+      return __result;
     }
 
 #if _GLIBCXX_HOSTED
@@ -406,18 +433,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
 			   const _Tp& __x, _Allocator& __alloc)
     {
-      _ForwardIterator __cur = __first;
-      __try
-	{
-	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
-	  for (; __cur != __last; ++__cur)
-	    __traits::construct(__alloc, std::__addressof(*__cur), __x);
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first, __cur, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator>
+	__guard(__first, __alloc);
+
+      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
+      for (; __first != __last; ++__first)
+	__traits::construct(__alloc, std::__addressof(*__first), __x);
+
+      __guard.release();
     }
 
 #if _GLIBCXX_HOSTED
@@ -442,19 +465,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n,
 			     const _Tp& __x, _Allocator& __alloc)
     {
-      _ForwardIterator __cur = __first;
-      __try
-	{
-	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
-	  for (; __n > 0; --__n, (void) ++__cur)
-	    __traits::construct(__alloc, std::__addressof(*__cur), __x);
-	  return __cur;
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first, __cur, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator>
+	__guard(__first, __alloc);
+      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
+      for (; __n > 0; --__n, (void) ++__first)
+	__traits::construct(__alloc, std::__addressof(*__first), __x);
+      __guard.release();
+      return __first;
     }
 
 #if _GLIBCXX_HOSTED
@@ -493,17 +510,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			      _Allocator& __alloc)
     {
       _ForwardIterator __mid = std::__uninitialized_copy_a(__first1, __last1,
-							   __result,
-							   __alloc);
-      __try
-	{
-	  return std::__uninitialized_move_a(__first2, __last2, __mid, __alloc);
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __mid, __alloc);
-	  __throw_exception_again;
-	}
+							   __result, __alloc);
+      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__result,
+								__alloc);
+      __result = __mid; // Everything up to __mid is now guarded.
+      __result = std::__uninitialized_move_a(__first2, __last2, __mid, __alloc);
+      __guard.release();
+      return __result;
     }
 
   // __uninitialized_move_copy
@@ -521,17 +534,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			      _Allocator& __alloc)
     {
       _ForwardIterator __mid = std::__uninitialized_move_a(__first1, __last1,
-							   __result,
-							   __alloc);
-      __try
-	{
-	  return std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc);
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __mid, __alloc);
-	  __throw_exception_again;
-	}
+							   __result, __alloc);
+      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__result,
+								__alloc);
+      __result = __mid; // Everything up to __mid is now guarded.
+      __result = std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc);
+      __guard.release();
     }
 
   // __uninitialized_fill_move
@@ -545,15 +553,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			      _InputIterator __last, _Allocator& __alloc)
     {
       std::__uninitialized_fill_a(__result, __mid, __x, __alloc);
-      __try
-	{
-	  return std::__uninitialized_move_a(__first, __last, __mid, __alloc);
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __mid, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__result,
+								__alloc);
+      __result = __mid; // Everything up to __mid is now guarded.
+      __result = std::__uninitialized_move_a(__first, __last, __mid, __alloc);
+      __guard.release();
+      return __result;
     }
 
   // __uninitialized_move_fill
@@ -570,15 +575,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _ForwardIterator __mid2 = std::__uninitialized_move_a(__first1, __last1,
 							    __first2,
 							    __alloc);
-      __try
-	{
-	  std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc);
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first2, __mid2, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__first2,
+								__alloc);
+      __first2 = __mid2; // Everything up to __mid2 is now guarded.
+      std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc);
+      __guard.release();
     }
 
   /// @endcond
@@ -596,17 +597,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
         static void
         __uninit_default(_ForwardIterator __first, _ForwardIterator __last)
         {
-	  _ForwardIterator __cur = __first;
-	  __try
-	    {
-	      for (; __cur != __last; ++__cur)
-		std::_Construct(std::__addressof(*__cur));
-	    }
-	  __catch(...)
-	    {
-	      std::_Destroy(__first, __cur);
-	      __throw_exception_again;
-	    }
+	  _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+	  for (; __first != __last; ++__first)
+	    std::_Construct(std::__addressof(*__first));
+	  __guard.release();
 	}
     };
 
@@ -636,18 +630,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
         static _ForwardIterator
         __uninit_default_n(_ForwardIterator __first, _Size __n)
         {
-	  _ForwardIterator __cur = __first;
-	  __try
-	    {
-	      for (; __n > 0; --__n, (void) ++__cur)
-		std::_Construct(std::__addressof(*__cur));
-	      return __cur;
-	    }
-	  __catch(...)
-	    {
-	      std::_Destroy(__first, __cur);
-	      __throw_exception_again;
-	    }
+	  _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+	  for (; __n > 0; --__n, (void) ++__first)
+	    std::_Construct(std::__addressof(*__first));
+	  __guard.release();
+	  return __first;
 	}
     };
 
@@ -722,18 +709,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			      _ForwardIterator __last,
 			      _Allocator& __alloc)
     {
-      _ForwardIterator __cur = __first;
-      __try
-	{
-	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
-	  for (; __cur != __last; ++__cur)
-	    __traits::construct(__alloc, std::__addressof(*__cur));
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first, __cur, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__first,
+								__alloc);
+      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
+      for (; __first != __last; ++__first)
+	__traits::construct(__alloc, std::__addressof(*__first));
+      __guard.release();
     }
 
 #if _GLIBCXX_HOSTED
@@ -753,19 +734,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __uninitialized_default_n_a(_ForwardIterator __first, _Size __n,
 				_Allocator& __alloc)
     {
-      _ForwardIterator __cur = __first;
-      __try
-	{
-	  typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
-	  for (; __n > 0; --__n, (void) ++__cur)
-	    __traits::construct(__alloc, std::__addressof(*__cur));
-	  return __cur;
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__first, __cur, __alloc);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__first,
+								__alloc);
+      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
+      for (; __n > 0; --__n, (void) ++__first)
+	__traits::construct(__alloc, std::__addressof(*__first));
+      __guard.release();
+      return __first;
     }
 
 #if _GLIBCXX_HOSTED
@@ -787,17 +762,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__uninit_default_novalue(_ForwardIterator __first,
 				 _ForwardIterator __last)
 	{
-	  _ForwardIterator __cur = __first;
-	  __try
-	    {
-	      for (; __cur != __last; ++__cur)
-		std::_Construct_novalue(std::__addressof(*__cur));
-	    }
-	  __catch(...)
-	    {
-	      std::_Destroy(__first, __cur);
-	      __throw_exception_again;
-	    }
+	  _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+	  for (; __first != __last; ++__first)
+	    std::_Construct_novalue(std::__addressof(*__first));
+	  __guard.release();
 	}
     };
 
@@ -818,18 +786,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	static _ForwardIterator
 	__uninit_default_novalue_n(_ForwardIterator __first, _Size __n)
 	{
-	  _ForwardIterator __cur = __first;
-	  __try
-	    {
-	      for (; __n > 0; --__n, (void) ++__cur)
-		std::_Construct_novalue(std::__addressof(*__cur));
-	      return __cur;
-	    }
-	  __catch(...)
-	    {
-	      std::_Destroy(__first, __cur);
-	      __throw_exception_again;
-	    }
+	  _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+	  for (; __n > 0; --__n, (void) ++__first)
+	    std::_Construct_novalue(std::__addressof(*__first));
+	  __guard.release();
+	  return __first;
 	}
     };
 
@@ -877,18 +838,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __uninitialized_copy_n(_InputIterator __first, _Size __n,
 			   _ForwardIterator __result, input_iterator_tag)
     {
-      _ForwardIterator __cur = __result;
-      __try
-	{
-	  for (; __n > 0; --__n, (void) ++__first, ++__cur)
-	    std::_Construct(std::__addressof(*__cur), *__first);
-	  return __cur;
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __cur);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator> __guard(__result);
+      for (; __n > 0; --__n, (void) ++__first, ++__result)
+	std::_Construct(std::__addressof(*__result), *__first);
+      __guard.release();
+      return __result;
     }
 
   template<typename _RandomAccessIterator, typename _Size,
@@ -903,20 +857,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _ForwardIterator>
     pair<_InputIterator, _ForwardIterator>
     __uninitialized_copy_n_pair(_InputIterator __first, _Size __n,
-			   _ForwardIterator __result, input_iterator_tag)
+				_ForwardIterator __result, input_iterator_tag)
     {
-      _ForwardIterator __cur = __result;
-      __try
-	{
-	  for (; __n > 0; --__n, (void) ++__first, ++__cur)
-	    std::_Construct(std::__addressof(*__cur), *__first);
-	  return {__first, __cur};
-	}
-      __catch(...)
-	{
-	  std::_Destroy(__result, __cur);
-	  __throw_exception_again;
-	}
+      _UninitDestroyGuard<_ForwardIterator> __guard(__result);
+      for (; __n > 0; --__n, (void) ++__first, ++__result)
+	std::_Construct(std::__addressof(*__result), *__first);
+      __guard.release();
+      return {__first, __result};
     }
 
   template<typename _RandomAccessIterator, typename _Size,
-- 
2.45.2

[PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Jonathan Wakely]

For trivial types std::__uninitialized_default (which is used by
std::uninitialized_value_construct) value-initializes the first element
then copies that to the rest of the range using std::fill.

Tamar is working on improved vectorization for std::fill, but for this
value-initialized case where we just want to fill with zeros it seems
sensible to just ... fill with zeros. We can use memset to do that.

Tested x86_64-linux.

-- >8 --

The current optimized path for __uninitialized_default and
__uninitialized_default_n will use std::fill for trivial types, but we
can just use memset to fill them with zeros instead.

Because these functions are not defined for C++98 at all, we can use
if-constexpr to simplify them and remove the dispatching to members of
class template specializations.

libstdc++-v3/ChangeLog:

	* include/bits/stl_uninitialized.h (__uninitialized_default_1)
	(__uninitialized_default_n_1): Remove.
	(__uninitialized_default, __uninitialized_default_n): Use memset
	for contiguous ranges of trivial types.
	* testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc:
	Check negative size.
---
 libstdc++-v3/include/bits/stl_uninitialized.h | 159 ++++++++----------
 .../uninitialized_value_construct_n/sizes.cc  |  13 ++
 2 files changed, 87 insertions(+), 85 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
index a9965f26269..1216b319f66 100644
--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -61,6 +61,7 @@
 #endif
 
 #include <bits/stl_algobase.h>    // copy
+#include <bits/ptr_traits.h>      // __to_address
 #include <ext/alloc_traits.h>     // __alloc_traits
 
 #if __cplusplus >= 201703L
@@ -590,89 +591,72 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // Extensions: __uninitialized_default, __uninitialized_default_n,
   // __uninitialized_default_a, __uninitialized_default_n_a.
 
-  template<bool _TrivialValueType>
-    struct __uninitialized_default_1
-    {
-      template<typename _ForwardIterator>
-        static void
-        __uninit_default(_ForwardIterator __first, _ForwardIterator __last)
-        {
-	  _UninitDestroyGuard<_ForwardIterator> __guard(__first);
-	  for (; __first != __last; ++__first)
-	    std::_Construct(std::__addressof(*__first));
-	  __guard.release();
-	}
-    };
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions"
 
-  template<>
-    struct __uninitialized_default_1<true>
+  // If we can value-initialize *__first using memset then return
+  // std::to_address(__first), otherwise return nullptr.
+  template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
+    inline void*
+    __ptr_for_trivial_zero_init(_ForwardIterator __first)
     {
-      template<typename _ForwardIterator>
-        static void
-        __uninit_default(_ForwardIterator __first, _ForwardIterator __last)
-        {
-	  if (__first == __last)
-	    return;
+#ifdef __cpp_lib_is_constant_evaluated
+      if (std::is_constant_evaluated())
+	return nullptr; // Cannot memset during constant evaluation.
+#endif
 
-	  typename iterator_traits<_ForwardIterator>::value_type* __val
-	    = std::__addressof(*__first);
-	  std::_Construct(__val);
-	  if (++__first != __last)
-	    std::fill(__first, __last, *__val);
-	}
-    };
-
-  template<bool _TrivialValueType>
-    struct __uninitialized_default_n_1
-    {
-      template<typename _ForwardIterator, typename _Size>
-	_GLIBCXX20_CONSTEXPR
-        static _ForwardIterator
-        __uninit_default_n(_ForwardIterator __first, _Size __n)
-        {
-	  _UninitDestroyGuard<_ForwardIterator> __guard(__first);
-	  for (; __n > 0; --__n, (void) ++__first)
-	    std::_Construct(std::__addressof(*__first));
-	  __guard.release();
-	  return __first;
-	}
-    };
-
-  template<>
-    struct __uninitialized_default_n_1<true>
-    {
-      template<typename _ForwardIterator, typename _Size>
-	_GLIBCXX20_CONSTEXPR
-        static _ForwardIterator
-        __uninit_default_n(_ForwardIterator __first, _Size __n)
-        {
-	  if (__n > 0)
+#if __cpp_lib_concepts
+      if constexpr (!contiguous_iterator<_ForwardIterator>)
+	return nullptr; // Need a raw pointer for memset.
+#else
+      if constexpr (!is_pointer<_ForwardIterator>::value)
+	return nullptr;
+#endif
+      else
+	{
+	  using _ValueType
+	    = typename iterator_traits<_ForwardIterator>::value_type;
+	  // Need value-init to be equivalent to zero-init.
+	  using __value_init_is_zero_init
+	    = __and_<is_trivial<_ValueType>,
+		     is_trivially_constructible<_ValueType>>;
+	  if constexpr (__value_init_is_zero_init::value)
 	    {
-	      typename iterator_traits<_ForwardIterator>::value_type* __val
-		= std::__addressof(*__first);
-	      std::_Construct(__val);
-	      ++__first;
-	      __first = std::fill_n(__first, __n - 1, *__val);
+	      using _Ptr = decltype(std::__to_address(__first));
+	      // Cannot use memset if _Ptr is cv-qualified.
+	      if constexpr (is_convertible<_Ptr, void*>::value)
+		return std::__to_address(__first);
 	    }
-	  return __first;
 	}
-    };
+      return nullptr;
+    }
 
   // __uninitialized_default
   // Fills [first, last) with value-initialized value_types.
   template<typename _ForwardIterator>
     inline void
-    __uninitialized_default(_ForwardIterator __first,
-			    _ForwardIterator __last)
+    __uninitialized_default(_ForwardIterator __first, _ForwardIterator __last)
     {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-      // trivial types can have deleted assignment
-      const bool __assignable = is_copy_assignable<_ValueType>::value;
+      if constexpr (__is_random_access_iter<_ForwardIterator>::__value)
+	if (void* __ptr = std::__ptr_for_trivial_zero_init(__first))
+	  {
+	    using _ValueType
+	      = typename iterator_traits<_ForwardIterator>::value_type;
+	    if (auto __dist = __last - __first)
+	      {
+		__glibcxx_assert(__dist > 0);
+		const size_t __n = __dist;
+		__glibcxx_assert(__n < __SIZE_MAX__ / sizeof(_ValueType));
+		__builtin_memset(__ptr, 0, __n * sizeof(_ValueType));
+	      }
+	    return;
+	  }
 
-      std::__uninitialized_default_1<__is_trivial(_ValueType)
-				     && __assignable>::
-	__uninit_default(__first, __last);
+      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+      for (; __first != __last; ++__first)
+	std::_Construct(std::__addressof(*__first));
+      __guard.release();
     }
 
   // __uninitialized_default_n
@@ -682,23 +666,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline _ForwardIterator
     __uninitialized_default_n(_ForwardIterator __first, _Size __n)
     {
-#ifdef __cpp_lib_is_constant_evaluated
-      if (std::is_constant_evaluated())
-	return __uninitialized_default_n_1<false>::
-		 __uninit_default_n(__first, __n);
-#endif
+      if constexpr (is_integral<_Size>::value)
+	if constexpr (__is_random_access_iter<_ForwardIterator>::__value)
+	  if (void* __ptr = std::__ptr_for_trivial_zero_init(__first))
+	    {
+	      using _ValueType
+		= typename iterator_traits<_ForwardIterator>::value_type;
+	      if (__n <= 0)
+		return __first;
+	      else if (size_t(__n) < __SIZE_MAX__ / sizeof(_ValueType))
+		{
+		  __builtin_memset(__ptr, 0, __n * sizeof(_ValueType));
+		  return __first + __n;
+		}
+	    }
 
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-      // See uninitialized_fill_n for the conditions for using std::fill_n.
-      constexpr bool __can_fill
-	= __and_<is_integral<_Size>, is_copy_assignable<_ValueType>>::value;
-
-      return __uninitialized_default_n_1<__is_trivial(_ValueType)
-					 && __can_fill>::
-	__uninit_default_n(__first, __n);
+      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
+      for (; __n > 0; --__n, (void) ++__first)
+	std::_Construct(std::__addressof(*__first));
+      __guard.release();
+      return __first;
     }
-
+#pragma GCC diagnostic pop
 
   // __uninitialized_default_a
   // Fills [first, last) with value_types constructed by the allocator
diff --git a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc
index 7705c6813e3..9c4198c1a98 100644
--- a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc
+++ b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc
@@ -52,9 +52,22 @@ test02()
   VERIFY( i[4] == 5 );
 }
 
+void
+test03()
+{
+  int i[3] = { 1, 2, 3 };
+  // The standard defines it in terms of a loop which only runs for positive n.
+  auto j = std::uninitialized_value_construct_n(i+1, -5);
+  VERIFY( j == i+1 );
+  VERIFY( i[0] == 1 );
+  VERIFY( i[1] == 2 );
+  VERIFY( i[2] == 3 );
+}
+
 int
 main()
 {
   test01();
   test02();
+  test03();
 }
-- 
2.45.2

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Jonathan Wakely]

On Thu, 27 Jun 2024 at 11:53, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> For trivial types std::__uninitialized_default (which is used by
> std::uninitialized_value_construct) value-initializes the first element
> then copies that to the rest of the range using std::fill.
>
> Tamar is working on improved vectorization for std::fill, but for this
> value-initialized case where we just want to fill with zeros it seems
> sensible to just ... fill with zeros. We can use memset to do that.

Oops, I misremembered. Tamar is working on std::find not std::fill, so
that isn't relevant to this change to use memset for all trivial
types.

The current optimization to use std::fill in
std::uninitialized_value_construct only helps for trivial types of
size 1, because otherwise std::fill isn't optimized to memset. So an
alternative solution for std::uninitialized_value_construct of trivial
types would be to convert the contiguous iterators to char* (via
reinterpret_cast) and then use std::fill(f, l, '\0') which would then
use memset. Rather than relying on that detail of std::fill, I think
it makes sense just to do the memset directly where we know it's valid
for trivial types of any size. And that can be generalized for
non-common ranges, so can be used for
ranges::uninitialized_value_construct, which isn't the case if we
defer to std::fill.



>
> Tested x86_64-linux.
>
> -- >8 --
>
> The current optimized path for __uninitialized_default and
> __uninitialized_default_n will use std::fill for trivial types, but we
> can just use memset to fill them with zeros instead.
>
> Because these functions are not defined for C++98 at all, we can use
> if-constexpr to simplify them and remove the dispatching to members of
> class template specializations.
>
> libstdc++-v3/ChangeLog:
>
>         * include/bits/stl_uninitialized.h (__uninitialized_default_1)
>         (__uninitialized_default_n_1): Remove.
>         (__uninitialized_default, __uninitialized_default_n): Use memset
>         for contiguous ranges of trivial types.
>         * testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc:
>         Check negative size.
> ---
>  libstdc++-v3/include/bits/stl_uninitialized.h | 159 ++++++++----------
>  .../uninitialized_value_construct_n/sizes.cc  |  13 ++
>  2 files changed, 87 insertions(+), 85 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
> index a9965f26269..1216b319f66 100644
> --- a/libstdc++-v3/include/bits/stl_uninitialized.h
> +++ b/libstdc++-v3/include/bits/stl_uninitialized.h
> @@ -61,6 +61,7 @@
>  #endif
>
>  #include <bits/stl_algobase.h>    // copy
> +#include <bits/ptr_traits.h>      // __to_address
>  #include <ext/alloc_traits.h>     // __alloc_traits
>
>  #if __cplusplus >= 201703L
> @@ -590,89 +591,72 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>    // Extensions: __uninitialized_default, __uninitialized_default_n,
>    // __uninitialized_default_a, __uninitialized_default_n_a.
>
> -  template<bool _TrivialValueType>
> -    struct __uninitialized_default_1
> -    {
> -      template<typename _ForwardIterator>
> -        static void
> -        __uninit_default(_ForwardIterator __first, _ForwardIterator __last)
> -        {
> -         _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> -         for (; __first != __last; ++__first)
> -           std::_Construct(std::__addressof(*__first));
> -         __guard.release();
> -       }
> -    };
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wc++17-extensions"
>
> -  template<>
> -    struct __uninitialized_default_1<true>
> +  // If we can value-initialize *__first using memset then return
> +  // std::to_address(__first), otherwise return nullptr.
> +  template<typename _ForwardIterator>
> +    _GLIBCXX20_CONSTEXPR
> +    inline void*
> +    __ptr_for_trivial_zero_init(_ForwardIterator __first)
>      {
> -      template<typename _ForwardIterator>
> -        static void
> -        __uninit_default(_ForwardIterator __first, _ForwardIterator __last)
> -        {
> -         if (__first == __last)
> -           return;
> +#ifdef __cpp_lib_is_constant_evaluated
> +      if (std::is_constant_evaluated())
> +       return nullptr; // Cannot memset during constant evaluation.
> +#endif
>
> -         typename iterator_traits<_ForwardIterator>::value_type* __val
> -           = std::__addressof(*__first);
> -         std::_Construct(__val);
> -         if (++__first != __last)
> -           std::fill(__first, __last, *__val);
> -       }
> -    };
> -
> -  template<bool _TrivialValueType>
> -    struct __uninitialized_default_n_1
> -    {
> -      template<typename _ForwardIterator, typename _Size>
> -       _GLIBCXX20_CONSTEXPR
> -        static _ForwardIterator
> -        __uninit_default_n(_ForwardIterator __first, _Size __n)
> -        {
> -         _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> -         for (; __n > 0; --__n, (void) ++__first)
> -           std::_Construct(std::__addressof(*__first));
> -         __guard.release();
> -         return __first;
> -       }
> -    };
> -
> -  template<>
> -    struct __uninitialized_default_n_1<true>
> -    {
> -      template<typename _ForwardIterator, typename _Size>
> -       _GLIBCXX20_CONSTEXPR
> -        static _ForwardIterator
> -        __uninit_default_n(_ForwardIterator __first, _Size __n)
> -        {
> -         if (__n > 0)
> +#if __cpp_lib_concepts
> +      if constexpr (!contiguous_iterator<_ForwardIterator>)
> +       return nullptr; // Need a raw pointer for memset.
> +#else
> +      if constexpr (!is_pointer<_ForwardIterator>::value)
> +       return nullptr;
> +#endif
> +      else
> +       {
> +         using _ValueType
> +           = typename iterator_traits<_ForwardIterator>::value_type;
> +         // Need value-init to be equivalent to zero-init.
> +         using __value_init_is_zero_init
> +           = __and_<is_trivial<_ValueType>,
> +                    is_trivially_constructible<_ValueType>>;
> +         if constexpr (__value_init_is_zero_init::value)
>             {
> -             typename iterator_traits<_ForwardIterator>::value_type* __val
> -               = std::__addressof(*__first);
> -             std::_Construct(__val);
> -             ++__first;
> -             __first = std::fill_n(__first, __n - 1, *__val);
> +             using _Ptr = decltype(std::__to_address(__first));
> +             // Cannot use memset if _Ptr is cv-qualified.
> +             if constexpr (is_convertible<_Ptr, void*>::value)
> +               return std::__to_address(__first);
>             }
> -         return __first;
>         }
> -    };
> +      return nullptr;
> +    }
>
>    // __uninitialized_default
>    // Fills [first, last) with value-initialized value_types.
>    template<typename _ForwardIterator>
>      inline void
> -    __uninitialized_default(_ForwardIterator __first,
> -                           _ForwardIterator __last)
> +    __uninitialized_default(_ForwardIterator __first, _ForwardIterator __last)
>      {
> -      typedef typename iterator_traits<_ForwardIterator>::value_type
> -       _ValueType;
> -      // trivial types can have deleted assignment
> -      const bool __assignable = is_copy_assignable<_ValueType>::value;
> +      if constexpr (__is_random_access_iter<_ForwardIterator>::__value)
> +       if (void* __ptr = std::__ptr_for_trivial_zero_init(__first))
> +         {
> +           using _ValueType
> +             = typename iterator_traits<_ForwardIterator>::value_type;
> +           if (auto __dist = __last - __first)
> +             {
> +               __glibcxx_assert(__dist > 0);
> +               const size_t __n = __dist;
> +               __glibcxx_assert(__n < __SIZE_MAX__ / sizeof(_ValueType));
> +               __builtin_memset(__ptr, 0, __n * sizeof(_ValueType));
> +             }
> +           return;
> +         }
>
> -      std::__uninitialized_default_1<__is_trivial(_ValueType)
> -                                    && __assignable>::
> -       __uninit_default(__first, __last);
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +      for (; __first != __last; ++__first)
> +       std::_Construct(std::__addressof(*__first));
> +      __guard.release();
>      }
>
>    // __uninitialized_default_n
> @@ -682,23 +666,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      inline _ForwardIterator
>      __uninitialized_default_n(_ForwardIterator __first, _Size __n)
>      {
> -#ifdef __cpp_lib_is_constant_evaluated
> -      if (std::is_constant_evaluated())
> -       return __uninitialized_default_n_1<false>::
> -                __uninit_default_n(__first, __n);
> -#endif
> +      if constexpr (is_integral<_Size>::value)
> +       if constexpr (__is_random_access_iter<_ForwardIterator>::__value)
> +         if (void* __ptr = std::__ptr_for_trivial_zero_init(__first))
> +           {
> +             using _ValueType
> +               = typename iterator_traits<_ForwardIterator>::value_type;
> +             if (__n <= 0)
> +               return __first;
> +             else if (size_t(__n) < __SIZE_MAX__ / sizeof(_ValueType))
> +               {
> +                 __builtin_memset(__ptr, 0, __n * sizeof(_ValueType));
> +                 return __first + __n;
> +               }
> +           }
>
> -      typedef typename iterator_traits<_ForwardIterator>::value_type
> -       _ValueType;
> -      // See uninitialized_fill_n for the conditions for using std::fill_n.
> -      constexpr bool __can_fill
> -       = __and_<is_integral<_Size>, is_copy_assignable<_ValueType>>::value;
> -
> -      return __uninitialized_default_n_1<__is_trivial(_ValueType)
> -                                        && __can_fill>::
> -       __uninit_default_n(__first, __n);
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +      for (; __n > 0; --__n, (void) ++__first)
> +       std::_Construct(std::__addressof(*__first));
> +      __guard.release();
> +      return __first;
>      }
> -
> +#pragma GCC diagnostic pop
>
>    // __uninitialized_default_a
>    // Fills [first, last) with value_types constructed by the allocator
> diff --git a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc
> index 7705c6813e3..9c4198c1a98 100644
> --- a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc
> +++ b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc
> @@ -52,9 +52,22 @@ test02()
>    VERIFY( i[4] == 5 );
>  }
>
> +void
> +test03()
> +{
> +  int i[3] = { 1, 2, 3 };
> +  // The standard defines it in terms of a loop which only runs for positive n.
> +  auto j = std::uninitialized_value_construct_n(i+1, -5);
> +  VERIFY( j == i+1 );
> +  VERIFY( i[0] == 1 );
> +  VERIFY( i[1] == 2 );
> +  VERIFY( i[2] == 3 );
> +}
> +
>  int
>  main()
>  {
>    test01();
>    test02();
> +  test03();
>  }
> --
> 2.45.2
>

[PATCH 3/3] libstdc++: Use std::__uninitialized_default for ranges::uninitialized_value_construct

[Jonathan Wakely]

By generalizing std::__uninitialized_default to work with non-common
ranges (i.e. iterator/sentinel pair) we can reuse it for the
ranges::uninitialized_value_construct function. Doing that ensures that
whatever optimizations we have for std::uninitialized_value_construct
are automatically used for the ranges version too.

Tested x86_64-linux.

-- >8 --

This reuses the memset optimization in __uninitialized_default for the
ranges equivalent, and similarly for uninitialized_value_construct_n.

libstdc++-v3/ChangeLog:

	* include/bits/ranges_uninitialized.h (uninitialized_value_construct):
	Use __uninitialized_default.
	(uninitialized_value_construct_n): Use __uninitialized_default_n.
	* include/bits/stl_uninitialized.h (__uninitialized_default):
	Allow first and last to be different types, to support arbitrary
	sentinels. Return the end of the initialized range.
	(uninitialized_value_construct): Discard return value from
	__uninitialized_default.
---
 .../include/bits/ranges_uninitialized.h       | 27 +++----------------
 libstdc++-v3/include/bits/stl_uninitialized.h | 13 +++++----
 2 files changed, 11 insertions(+), 29 deletions(-)

diff --git a/libstdc++-v3/include/bits/ranges_uninitialized.h b/libstdc++-v3/include/bits/ranges_uninitialized.h
index f16f2ef39f5..d84c8502eb9 100644
--- a/libstdc++-v3/include/bits/ranges_uninitialized.h
+++ b/libstdc++-v3/include/bits/ranges_uninitialized.h
@@ -201,18 +201,8 @@ namespace ranges
       _Iter
       operator()(_Iter __first, _Sent __last) const
       {
-	using _ValueType = remove_reference_t<iter_reference_t<_Iter>>;
-	if constexpr (is_trivial_v<_ValueType>
-		      && is_copy_assignable_v<_ValueType>)
-	  return ranges::fill(__first, __last, _ValueType());
-	else
-	  {
-	    auto __guard = __detail::_DestroyGuard(__first);
-	    for (; __first != __last; ++__first)
-	      ::new (__detail::__voidify(*__first)) _ValueType();
-	    __guard.release();
-	    return __first;
-	  }
+	return std::__uninitialized_default(std::move(__first),
+					    std::move(__last));
       }
 
     template<__detail::__nothrow_forward_range _Range>
@@ -234,18 +224,7 @@ namespace ranges
       _Iter
       operator()(_Iter __first, iter_difference_t<_Iter> __n) const
       {
-	using _ValueType = remove_reference_t<iter_reference_t<_Iter>>;
-	if constexpr (is_trivial_v<_ValueType>
-		      && is_copy_assignable_v<_ValueType>)
-	  return ranges::fill_n(__first, __n, _ValueType());
-	else
-	  {
-	    auto __guard = __detail::_DestroyGuard(__first);
-	    for (; __n > 0; ++__first, (void) --__n)
-	      ::new (__detail::__voidify(*__first)) _ValueType();
-	    __guard.release();
-	    return __first;
-	  }
+	return std::__uninitialized_default_n(std::move(__first), __n);
       }
   };
 
diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
index 1216b319f66..b13562992de 100644
--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -634,9 +634,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   // __uninitialized_default
   // Fills [first, last) with value-initialized value_types.
-  template<typename _ForwardIterator>
-    inline void
-    __uninitialized_default(_ForwardIterator __first, _ForwardIterator __last)
+  template<typename _ForwardIterator, typename _Sentinel>
+    _GLIBCXX20_CONSTEXPR
+    inline _ForwardIterator
+    __uninitialized_default(_ForwardIterator __first, _Sentinel __last)
     {
       if constexpr (__is_random_access_iter<_ForwardIterator>::__value)
 	if (void* __ptr = std::__ptr_for_trivial_zero_init(__first))
@@ -649,14 +650,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		const size_t __n = __dist;
 		__glibcxx_assert(__n < __SIZE_MAX__ / sizeof(_ValueType));
 		__builtin_memset(__ptr, 0, __n * sizeof(_ValueType));
+		return __first + __dist;
 	      }
-	    return;
+	    return __first;
 	  }
 
       _UninitDestroyGuard<_ForwardIterator> __guard(__first);
       for (; __first != __last; ++__first)
 	std::_Construct(std::__addressof(*__first));
       __guard.release();
+      return __first;
     }
 
   // __uninitialized_default_n
@@ -939,7 +942,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     uninitialized_value_construct(_ForwardIterator __first,
 				  _ForwardIterator __last)
     {
-      return std::__uninitialized_default(__first, __last);
+      std::__uninitialized_default(__first, __last);
     }
 
   /**
-- 
2.45.2

Re: [PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h>

[Jonathan Wakely]

On Thu, 27 Jun 2024 at 11:52, Jonathan Wakely wrote:
>
> This refactoring to use RAII doesn't seem to make any difference in
> benchmarks, although the generated code for some std::vector operations
> seems to be slightly larger. Maybe it will be faster (or slower) in some
> cases I didn't test?
>
> I think I like the change anyway - any other opinions on whether it's an
> improvement?

Any thoughts before I push this? Better? Worse? Needs more cowbell?


> Tested x86_64-linux.
>
> -- >8 --
>
> This adds an _UninitDestroyGuard class template, similar to
> ranges::_DestroyGuard used in <bits/ranges_uninitialized.h>. This allows
> us to remove all the try-catch blocks and rethrows, because any required
> cleanup gets done in the guard destructor.
>
> libstdc++-v3/ChangeLog:
>
>         * include/bits/stl_uninitialized.h (_UninitDestroyGuard): New
>         class template and partial specialization.
>         (__do_uninit_copy, __do_uninit_fill, __do_uninit_fill_n)
>         (__uninitialized_copy_a, __uninitialized_fill_a)
>         (__uninitialized_fill_n_a, __uninitialized_copy_move)
>         (__uninitialized_move_copy, __uninitialized_fill_move)
>         (__uninitialized_move_fill, __uninitialized_default_1)
>         (__uninitialized_default_n_a, __uninitialized_default_novalue_1)
>         (__uninitialized_default_novalue_n_1, __uninitialized_copy_n)
>         (__uninitialized_copy_n_pair): Use it.
> ---
>  libstdc++-v3/include/bits/stl_uninitialized.h | 365 ++++++++----------
>  1 file changed, 156 insertions(+), 209 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
> index 3c405d8fbe8..a9965f26269 100644
> --- a/libstdc++-v3/include/bits/stl_uninitialized.h
> +++ b/libstdc++-v3/include/bits/stl_uninitialized.h
> @@ -107,24 +107,70 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __is_trivial(T) && __is_assignable(T&, U)
>  #endif
>
> +  template<typename _ForwardIterator, typename _Alloc = void>
> +    struct _UninitDestroyGuard
> +    {
> +      _GLIBCXX20_CONSTEXPR
> +      explicit
> +      _UninitDestroyGuard(_ForwardIterator& __first, _Alloc& __a)
> +      : _M_first(__first), _M_cur(__builtin_addressof(__first)), _M_alloc(__a)
> +      { }
> +
> +      _GLIBCXX20_CONSTEXPR
> +      ~_UninitDestroyGuard()
> +      {
> +       if (__builtin_expect(_M_cur != 0, 0))
> +         std::_Destroy(_M_first, *_M_cur, _M_alloc);
> +      }
> +
> +      _GLIBCXX20_CONSTEXPR
> +      void release() { _M_cur = 0; }
> +
> +    private:
> +      _ForwardIterator const _M_first;
> +      _ForwardIterator* _M_cur;
> +      _Alloc& _M_alloc;
> +
> +      _UninitDestroyGuard(const _UninitDestroyGuard&);
> +    };
> +
> +  template<typename _ForwardIterator>
> +    struct _UninitDestroyGuard<_ForwardIterator, void>
> +    {
> +      _GLIBCXX20_CONSTEXPR
> +      explicit
> +      _UninitDestroyGuard(_ForwardIterator& __first)
> +      : _M_first(__first), _M_cur(__builtin_addressof(__first))
> +      { }
> +
> +      _GLIBCXX20_CONSTEXPR
> +      ~_UninitDestroyGuard()
> +      {
> +       if (__builtin_expect(_M_cur != 0, 0))
> +         std::_Destroy(_M_first, *_M_cur);
> +      }
> +
> +      _GLIBCXX20_CONSTEXPR
> +      void release() { _M_cur = 0; }
> +
> +      _ForwardIterator const _M_first;
> +      _ForwardIterator* _M_cur;
> +
> +    private:
> +      _UninitDestroyGuard(const _UninitDestroyGuard&);
> +    };
> +
>    template<typename _InputIterator, typename _ForwardIterator>
>      _GLIBCXX20_CONSTEXPR
>      _ForwardIterator
>      __do_uninit_copy(_InputIterator __first, _InputIterator __last,
>                      _ForwardIterator __result)
>      {
> -      _ForwardIterator __cur = __result;
> -      __try
> -       {
> -         for (; __first != __last; ++__first, (void)++__cur)
> -           std::_Construct(std::__addressof(*__cur), *__first);
> -         return __cur;
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __cur);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__result);
> +      for (; __first != __last; ++__first, (void)++__result)
> +       std::_Construct(std::__addressof(*__result), *__first);
> +      __guard.release();
> +      return __result;
>      }
>
>    template<bool _TrivialValueTypes>
> @@ -192,17 +238,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __do_uninit_fill(_ForwardIterator __first, _ForwardIterator __last,
>                      const _Tp& __x)
>      {
> -      _ForwardIterator __cur = __first;
> -      __try
> -       {
> -         for (; __cur != __last; ++__cur)
> -           std::_Construct(std::__addressof(*__cur), __x);
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first, __cur);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +      for (; __first != __last; ++__first)
> +       std::_Construct(std::__addressof(*__first), __x);
> +      __guard.release();
>      }
>
>    template<bool _TrivialValueType>
> @@ -260,18 +299,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      _ForwardIterator
>      __do_uninit_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
>      {
> -      _ForwardIterator __cur = __first;
> -      __try
> -       {
> -         for (; __n > 0; --__n, (void) ++__cur)
> -           std::_Construct(std::__addressof(*__cur), __x);
> -         return __cur;
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first, __cur);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +      for (; __n > 0; --__n, (void) ++__first)
> +       std::_Construct(std::__addressof(*__first), __x);
> +      __guard.release();
> +      return __first;
>      }
>
>    template<bool _TrivialValueType>
> @@ -344,19 +376,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
>                            _ForwardIterator __result, _Allocator& __alloc)
>      {
> -      _ForwardIterator __cur = __result;
> -      __try
> -       {
> -         typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> -         for (; __first != __last; ++__first, (void)++__cur)
> -           __traits::construct(__alloc, std::__addressof(*__cur), *__first);
> -         return __cur;
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __cur, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator>
> +       __guard(__result, __alloc);
> +
> +      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> +      for (; __first != __last; ++__first, (void)++__result)
> +       __traits::construct(__alloc, std::__addressof(*__result), *__first);
> +      __guard.release();
> +      return __result;
>      }
>
>  #if _GLIBCXX_HOSTED
> @@ -406,18 +433,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
>                            const _Tp& __x, _Allocator& __alloc)
>      {
> -      _ForwardIterator __cur = __first;
> -      __try
> -       {
> -         typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> -         for (; __cur != __last; ++__cur)
> -           __traits::construct(__alloc, std::__addressof(*__cur), __x);
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first, __cur, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator>
> +       __guard(__first, __alloc);
> +
> +      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> +      for (; __first != __last; ++__first)
> +       __traits::construct(__alloc, std::__addressof(*__first), __x);
> +
> +      __guard.release();
>      }
>
>  #if _GLIBCXX_HOSTED
> @@ -442,19 +465,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n,
>                              const _Tp& __x, _Allocator& __alloc)
>      {
> -      _ForwardIterator __cur = __first;
> -      __try
> -       {
> -         typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> -         for (; __n > 0; --__n, (void) ++__cur)
> -           __traits::construct(__alloc, std::__addressof(*__cur), __x);
> -         return __cur;
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first, __cur, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator>
> +       __guard(__first, __alloc);
> +      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> +      for (; __n > 0; --__n, (void) ++__first)
> +       __traits::construct(__alloc, std::__addressof(*__first), __x);
> +      __guard.release();
> +      return __first;
>      }
>
>  #if _GLIBCXX_HOSTED
> @@ -493,17 +510,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>                               _Allocator& __alloc)
>      {
>        _ForwardIterator __mid = std::__uninitialized_copy_a(__first1, __last1,
> -                                                          __result,
> -                                                          __alloc);
> -      __try
> -       {
> -         return std::__uninitialized_move_a(__first2, __last2, __mid, __alloc);
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __mid, __alloc);
> -         __throw_exception_again;
> -       }
> +                                                          __result, __alloc);
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__result,
> +                                                               __alloc);
> +      __result = __mid; // Everything up to __mid is now guarded.
> +      __result = std::__uninitialized_move_a(__first2, __last2, __mid, __alloc);
> +      __guard.release();
> +      return __result;
>      }
>
>    // __uninitialized_move_copy
> @@ -521,17 +534,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>                               _Allocator& __alloc)
>      {
>        _ForwardIterator __mid = std::__uninitialized_move_a(__first1, __last1,
> -                                                          __result,
> -                                                          __alloc);
> -      __try
> -       {
> -         return std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc);
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __mid, __alloc);
> -         __throw_exception_again;
> -       }
> +                                                          __result, __alloc);
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__result,
> +                                                               __alloc);
> +      __result = __mid; // Everything up to __mid is now guarded.
> +      __result = std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc);
> +      __guard.release();
>      }
>
>    // __uninitialized_fill_move
> @@ -545,15 +553,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>                               _InputIterator __last, _Allocator& __alloc)
>      {
>        std::__uninitialized_fill_a(__result, __mid, __x, __alloc);
> -      __try
> -       {
> -         return std::__uninitialized_move_a(__first, __last, __mid, __alloc);
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __mid, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__result,
> +                                                               __alloc);
> +      __result = __mid; // Everything up to __mid is now guarded.
> +      __result = std::__uninitialized_move_a(__first, __last, __mid, __alloc);
> +      __guard.release();
> +      return __result;
>      }
>
>    // __uninitialized_move_fill
> @@ -570,15 +575,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        _ForwardIterator __mid2 = std::__uninitialized_move_a(__first1, __last1,
>                                                             __first2,
>                                                             __alloc);
> -      __try
> -       {
> -         std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc);
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first2, __mid2, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__first2,
> +                                                               __alloc);
> +      __first2 = __mid2; // Everything up to __mid2 is now guarded.
> +      std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc);
> +      __guard.release();
>      }
>
>    /// @endcond
> @@ -596,17 +597,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>          static void
>          __uninit_default(_ForwardIterator __first, _ForwardIterator __last)
>          {
> -         _ForwardIterator __cur = __first;
> -         __try
> -           {
> -             for (; __cur != __last; ++__cur)
> -               std::_Construct(std::__addressof(*__cur));
> -           }
> -         __catch(...)
> -           {
> -             std::_Destroy(__first, __cur);
> -             __throw_exception_again;
> -           }
> +         _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +         for (; __first != __last; ++__first)
> +           std::_Construct(std::__addressof(*__first));
> +         __guard.release();
>         }
>      };
>
> @@ -636,18 +630,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>          static _ForwardIterator
>          __uninit_default_n(_ForwardIterator __first, _Size __n)
>          {
> -         _ForwardIterator __cur = __first;
> -         __try
> -           {
> -             for (; __n > 0; --__n, (void) ++__cur)
> -               std::_Construct(std::__addressof(*__cur));
> -             return __cur;
> -           }
> -         __catch(...)
> -           {
> -             std::_Destroy(__first, __cur);
> -             __throw_exception_again;
> -           }
> +         _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +         for (; __n > 0; --__n, (void) ++__first)
> +           std::_Construct(std::__addressof(*__first));
> +         __guard.release();
> +         return __first;
>         }
>      };
>
> @@ -722,18 +709,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>                               _ForwardIterator __last,
>                               _Allocator& __alloc)
>      {
> -      _ForwardIterator __cur = __first;
> -      __try
> -       {
> -         typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> -         for (; __cur != __last; ++__cur)
> -           __traits::construct(__alloc, std::__addressof(*__cur));
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first, __cur, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__first,
> +                                                               __alloc);
> +      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> +      for (; __first != __last; ++__first)
> +       __traits::construct(__alloc, std::__addressof(*__first));
> +      __guard.release();
>      }
>
>  #if _GLIBCXX_HOSTED
> @@ -753,19 +734,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __uninitialized_default_n_a(_ForwardIterator __first, _Size __n,
>                                 _Allocator& __alloc)
>      {
> -      _ForwardIterator __cur = __first;
> -      __try
> -       {
> -         typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> -         for (; __n > 0; --__n, (void) ++__cur)
> -           __traits::construct(__alloc, std::__addressof(*__cur));
> -         return __cur;
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__first, __cur, __alloc);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator, _Allocator> __guard(__first,
> +                                                               __alloc);
> +      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
> +      for (; __n > 0; --__n, (void) ++__first)
> +       __traits::construct(__alloc, std::__addressof(*__first));
> +      __guard.release();
> +      return __first;
>      }
>
>  #if _GLIBCXX_HOSTED
> @@ -787,17 +762,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>         __uninit_default_novalue(_ForwardIterator __first,
>                                  _ForwardIterator __last)
>         {
> -         _ForwardIterator __cur = __first;
> -         __try
> -           {
> -             for (; __cur != __last; ++__cur)
> -               std::_Construct_novalue(std::__addressof(*__cur));
> -           }
> -         __catch(...)
> -           {
> -             std::_Destroy(__first, __cur);
> -             __throw_exception_again;
> -           }
> +         _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +         for (; __first != __last; ++__first)
> +           std::_Construct_novalue(std::__addressof(*__first));
> +         __guard.release();
>         }
>      };
>
> @@ -818,18 +786,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>         static _ForwardIterator
>         __uninit_default_novalue_n(_ForwardIterator __first, _Size __n)
>         {
> -         _ForwardIterator __cur = __first;
> -         __try
> -           {
> -             for (; __n > 0; --__n, (void) ++__cur)
> -               std::_Construct_novalue(std::__addressof(*__cur));
> -             return __cur;
> -           }
> -         __catch(...)
> -           {
> -             std::_Destroy(__first, __cur);
> -             __throw_exception_again;
> -           }
> +         _UninitDestroyGuard<_ForwardIterator> __guard(__first);
> +         for (; __n > 0; --__n, (void) ++__first)
> +           std::_Construct_novalue(std::__addressof(*__first));
> +         __guard.release();
> +         return __first;
>         }
>      };
>
> @@ -877,18 +838,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      __uninitialized_copy_n(_InputIterator __first, _Size __n,
>                            _ForwardIterator __result, input_iterator_tag)
>      {
> -      _ForwardIterator __cur = __result;
> -      __try
> -       {
> -         for (; __n > 0; --__n, (void) ++__first, ++__cur)
> -           std::_Construct(std::__addressof(*__cur), *__first);
> -         return __cur;
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __cur);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__result);
> +      for (; __n > 0; --__n, (void) ++__first, ++__result)
> +       std::_Construct(std::__addressof(*__result), *__first);
> +      __guard.release();
> +      return __result;
>      }
>
>    template<typename _RandomAccessIterator, typename _Size,
> @@ -903,20 +857,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>            typename _ForwardIterator>
>      pair<_InputIterator, _ForwardIterator>
>      __uninitialized_copy_n_pair(_InputIterator __first, _Size __n,
> -                          _ForwardIterator __result, input_iterator_tag)
> +                               _ForwardIterator __result, input_iterator_tag)
>      {
> -      _ForwardIterator __cur = __result;
> -      __try
> -       {
> -         for (; __n > 0; --__n, (void) ++__first, ++__cur)
> -           std::_Construct(std::__addressof(*__cur), *__first);
> -         return {__first, __cur};
> -       }
> -      __catch(...)
> -       {
> -         std::_Destroy(__result, __cur);
> -         __throw_exception_again;
> -       }
> +      _UninitDestroyGuard<_ForwardIterator> __guard(__result);
> +      for (; __n > 0; --__n, (void) ++__first, ++__result)
> +       std::_Construct(std::__addressof(*__result), *__first);
> +      __guard.release();
> +      return {__first, __result};
>      }
>
>    template<typename _RandomAccessIterator, typename _Size,
> --
> 2.45.2
>

Re: [PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h>

[Ville Voutilainen]

On Wed, 3 Jul 2024 at 18:33, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On Thu, 27 Jun 2024 at 11:52, Jonathan Wakely wrote:
> >
> > This refactoring to use RAII doesn't seem to make any difference in
> > benchmarks, although the generated code for some std::vector operations
> > seems to be slightly larger. Maybe it will be faster (or slower) in some
> > cases I didn't test?
> >
> > I think I like the change anyway - any other opinions on whether it's an
> > improvement?
>
> Any thoughts before I push this? Better? Worse? Needs more cowbell?

I think the patch is an improvement. Push it.

[PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Maciej Cencora]

[-- Attachment #1: Type: text/plain, Size: 250 bytes --]

Hi,

not sure whether I've missed some conditional that would exclude this case,
but your change seems to incorrectly handle trivial types that have a
non-zero bit pattern of value-initialized object, e.g. pointer to member.

Regards,
Maciej Cencora

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Jonathan Wakely]

On Thu, 27 Jun 2024 at 13:40, Maciej Cencora wrote:
>
> Hi,
>
> not sure whether I've missed some conditional that would exclude this case, but your change seems to incorrectly handle trivial types that have a non-zero bit pattern of value-initialized object, e.g. pointer to member.

Good point. I started working on this optimization after last week's
https://gcc.gnu.org/r15-1550-g139d65d1f5a60a where is_trivial is
appropriate, because valarray only supports numeric types, not
pointers to members.

But the uninitialized memory algos don't have that restriction, so
need to be more careful.

I think memset is OK for arithmetic types, enums, pointers, nullptr_t,
and trivial classes ... except when those trivial classes contain
pointers to members. Which we can't tell.

So maybe we can only do it for is_trivial && ((is_scalar and not
is_member_pointer) or (is_class and is_empty)).

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Jonathan Wakely]

On Thu, 27 Jun 2024 at 13:49, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On Thu, 27 Jun 2024 at 13:40, Maciej Cencora wrote:
> >
> > Hi,
> >
> > not sure whether I've missed some conditional that would exclude this case, but your change seems to incorrectly handle trivial types that have a non-zero bit pattern of value-initialized object, e.g. pointer to member.
>
> Good point. I started working on this optimization after last week's
> https://gcc.gnu.org/r15-1550-g139d65d1f5a60a where is_trivial is
> appropriate, because valarray only supports numeric types, not
> pointers to members.
>
> But the uninitialized memory algos don't have that restriction, so
> need to be more careful.
>
> I think memset is OK for arithmetic types, enums, pointers, nullptr_t,
> and trivial classes ... except when those trivial classes contain
> pointers to members. Which we can't tell.
>
> So maybe we can only do it for is_trivial && ((is_scalar and not
> is_member_pointer) or (is_class and is_empty)).

I suppose any trivial class type smaller than sizeof(int T::*) would
be OK, because it can't hold a member pointer if it's smaller than
one.

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Maciej Cencora]

[-- Attachment #1: Type: text/plain, Size: 1521 bytes --]

You could include some of the bigger classes by checking whether the class
type is bit_cast-able to std::array of bytes, and that bitcasted output is
equal to value-initialized array.

Regards,
Maciej

czw., 27 cze 2024 o 14:50 Jonathan Wakely <jwakely@redhat.com> napisał(a):

> On Thu, 27 Jun 2024 at 13:49, Jonathan Wakely <jwakely@redhat.com> wrote:
> >
> > On Thu, 27 Jun 2024 at 13:40, Maciej Cencora wrote:
> > >
> > > Hi,
> > >
> > > not sure whether I've missed some conditional that would exclude this
> case, but your change seems to incorrectly handle trivial types that have a
> non-zero bit pattern of value-initialized object, e.g. pointer to member.
> >
> > Good point. I started working on this optimization after last week's
> > https://gcc.gnu.org/r15-1550-g139d65d1f5a60a where is_trivial is
> > appropriate, because valarray only supports numeric types, not
> > pointers to members.
> >
> > But the uninitialized memory algos don't have that restriction, so
> > need to be more careful.
> >
> > I think memset is OK for arithmetic types, enums, pointers, nullptr_t,
> > and trivial classes ... except when those trivial classes contain
> > pointers to members. Which we can't tell.
> >
> > So maybe we can only do it for is_trivial && ((is_scalar and not
> > is_member_pointer) or (is_class and is_empty)).
>
> I suppose any trivial class type smaller than sizeof(int T::*) would
> be OK, because it can't hold a member pointer if it's smaller than
> one.
>
>

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Maciej Cencora]

[-- Attachment #1: Type: text/plain, Size: 1863 bytes --]

I think going the bit_cast way would be the best because it enables the
optimization for many more classes including common wrappers like optional,
variant, pair, tuple and std::array.

Regards,
Maciej Cencora

czw., 27 cze 2024 o 14:57 Maciej Cencora <m.cencora@gmail.com> napisał(a):

> You could include some of the bigger classes by checking whether the class
> type is bit_cast-able to std::array of bytes, and that bitcasted output is
> equal to value-initialized array.
>
> Regards,
> Maciej
>
> czw., 27 cze 2024 o 14:50 Jonathan Wakely <jwakely@redhat.com> napisał(a):
>
>> On Thu, 27 Jun 2024 at 13:49, Jonathan Wakely <jwakely@redhat.com> wrote:
>> >
>> > On Thu, 27 Jun 2024 at 13:40, Maciej Cencora wrote:
>> > >
>> > > Hi,
>> > >
>> > > not sure whether I've missed some conditional that would exclude this
>> case, but your change seems to incorrectly handle trivial types that have a
>> non-zero bit pattern of value-initialized object, e.g. pointer to member.
>> >
>> > Good point. I started working on this optimization after last week's
>> > https://gcc.gnu.org/r15-1550-g139d65d1f5a60a where is_trivial is
>> > appropriate, because valarray only supports numeric types, not
>> > pointers to members.
>> >
>> > But the uninitialized memory algos don't have that restriction, so
>> > need to be more careful.
>> >
>> > I think memset is OK for arithmetic types, enums, pointers, nullptr_t,
>> > and trivial classes ... except when those trivial classes contain
>> > pointers to members. Which we can't tell.
>> >
>> > So maybe we can only do it for is_trivial && ((is_scalar and not
>> > is_member_pointer) or (is_class and is_empty)).
>>
>> I suppose any trivial class type smaller than sizeof(int T::*) would
>> be OK, because it can't hold a member pointer if it's smaller than
>> one.
>>
>>

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Jonathan Wakely]

On Thu, 27 Jun 2024 at 14:27, Maciej Cencora <m.cencora@gmail.com> wrote:
>
> I think going the bit_cast way would be the best because it enables the optimization for many more classes including common wrappers like optional, variant, pair, tuple and std::array.

This isn't tested but seems to work on simple cases. But for large
objects the loop hits the constexpr iteration limit and compilation
fails, so it needs a sizeof(_Tp) < 64 or something.

  using _ValueType
    = typename iterator_traits<_ForwardIterator>::value_type;
  using _Tp = remove_all_extents_t<_ValueType>;
  // Need value-init to be equivalent to zero-init.
  if constexpr (is_member_pointer<_Tp>::value)
    return nullptr;
  else if constexpr (!is_scalar<_Tp>::value)
    {
      using __trivial
        = __and_<is_trivial<_ValueType>,
                 is_trivially_constructible<_ValueType>>;
      if constexpr (__trivial::value)
        {
          struct _Bytes
          {
            unsigned char __b[sizeof(_Tp)];

#if __cpp_constexpr >= 201304
            constexpr bool _M_nonzero() const
            {
              for (auto __c : __b)
                if (__c)
                  return true;
              return false;
            }
#else
            constexpr bool _M_nonzero(size_t __n = 0) const
            {
              return __n < sizeof(_Tp)
                             && (__b[__n] || _M_nonzero(__n + 1));
            }
#endif
          };
          if constexpr (__builtin_bit_cast(_Bytes, _Tp())._M_nonzero())
            return nullptr;
        }
    }
  using _Ptr = decltype(std::__to_address(__first));
  // Cannot use memset if _Ptr is cv-qualified.
  if constexpr (is_convertible<_Ptr, void*>::value)
    return std::__to_address(__first);

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Maciej Cencora]

[-- Attachment #1: Type: text/plain, Size: 2778 bytes --]

But constexpr-ness of bit_cast has additional limitations and e.g.
providing an union as _Tp would be a hard-error. So we have two options:
 - before bitcasting check if type can be bitcast-ed at compile-time,
 - change the 'if constexpr' to regular 'if'.

If we go with the second solution then we will include classes with
pointers, and unions.
Additionally we could also include types with padding by passing
zero-initialized object (like a class-scope static constexpr or global)
into bit_cast... but then such a variable would be ODR-used and most-likely
won't be optimized out.

I guess the best option would be to introduce in C++ language a new
compiler-backed type trait like:
std::zero_initialized_object_has_all_zeros_object_representation<T>.

Regards,
Maciej

pt., 28 cze 2024 o 00:25 Jonathan Wakely <jwakely@redhat.com> napisał(a):

> On Thu, 27 Jun 2024 at 14:27, Maciej Cencora <m.cencora@gmail.com> wrote:
> >
> > I think going the bit_cast way would be the best because it enables the
> optimization for many more classes including common wrappers like optional,
> variant, pair, tuple and std::array.
>
> This isn't tested but seems to work on simple cases. But for large
> objects the loop hits the constexpr iteration limit and compilation
> fails, so it needs a sizeof(_Tp) < 64 or something.
>
>   using _ValueType
>     = typename iterator_traits<_ForwardIterator>::value_type;
>   using _Tp = remove_all_extents_t<_ValueType>;
>   // Need value-init to be equivalent to zero-init.
>   if constexpr (is_member_pointer<_Tp>::value)
>     return nullptr;
>   else if constexpr (!is_scalar<_Tp>::value)
>     {
>       using __trivial
>         = __and_<is_trivial<_ValueType>,
>                  is_trivially_constructible<_ValueType>>;
>       if constexpr (__trivial::value)
>         {
>           struct _Bytes
>           {
>             unsigned char __b[sizeof(_Tp)];
>
> #if __cpp_constexpr >= 201304
>             constexpr bool _M_nonzero() const
>             {
>               for (auto __c : __b)
>                 if (__c)
>                   return true;
>               return false;
>             }
> #else
>             constexpr bool _M_nonzero(size_t __n = 0) const
>             {
>               return __n < sizeof(_Tp)
>                              && (__b[__n] || _M_nonzero(__n + 1));
>             }
> #endif
>           };
>           if constexpr (__builtin_bit_cast(_Bytes, _Tp())._M_nonzero())
>             return nullptr;
>         }
>     }
>   using _Ptr = decltype(std::__to_address(__first));
>   // Cannot use memset if _Ptr is cv-qualified.
>   if constexpr (is_convertible<_Ptr, void*>::value)
>     return std::__to_address(__first);
>
>

Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset

[Jonathan Wakely]

On Fri, 28 Jun 2024 at 07:53, Maciej Cencora <m.cencora@gmail.com> wrote:
>
> But constexpr-ness of bit_cast has additional limitations and e.g. providing an union as _Tp would be a hard-error. So we have two options:
>  - before bitcasting check if type can be bitcast-ed at compile-time,
>  - change the 'if constexpr' to regular 'if'.
>
> If we go with the second solution then we will include classes with pointers, and unions.

I don't think we want to add runtime comparisons, the point is to
optimize the code not do more work :-)

> Additionally we could also include types with padding by passing zero-initialized object (like a class-scope static constexpr or global) into bit_cast... but then such a variable would be ODR-used and most-likely won't be optimized out.
>
> I guess the best option would be to introduce in C++ language a new compiler-backed type trait like: std::zero_initialized_object_has_all_zeros_object_representation<T>.

Yes, I think a new built-in is the only approach that will work for
class types. I'll just limit the optimization to scalars (excluding
member pointers).



>
> Regards,
> Maciej
>
> pt., 28 cze 2024 o 00:25 Jonathan Wakely <jwakely@redhat.com> napisał(a):
>>
>> On Thu, 27 Jun 2024 at 14:27, Maciej Cencora <m.cencora@gmail.com> wrote:
>> >
>> > I think going the bit_cast way would be the best because it enables the optimization for many more classes including common wrappers like optional, variant, pair, tuple and std::array.
>>
>> This isn't tested but seems to work on simple cases. But for large
>> objects the loop hits the constexpr iteration limit and compilation
>> fails, so it needs a sizeof(_Tp) < 64 or something.
>>
>>   using _ValueType
>>     = typename iterator_traits<_ForwardIterator>::value_type;
>>   using _Tp = remove_all_extents_t<_ValueType>;
>>   // Need value-init to be equivalent to zero-init.
>>   if constexpr (is_member_pointer<_Tp>::value)
>>     return nullptr;
>>   else if constexpr (!is_scalar<_Tp>::value)
>>     {
>>       using __trivial
>>         = __and_<is_trivial<_ValueType>,
>>                  is_trivially_constructible<_ValueType>>;
>>       if constexpr (__trivial::value)
>>         {
>>           struct _Bytes
>>           {
>>             unsigned char __b[sizeof(_Tp)];
>>
>> #if __cpp_constexpr >= 201304
>>             constexpr bool _M_nonzero() const
>>             {
>>               for (auto __c : __b)
>>                 if (__c)
>>                   return true;
>>               return false;
>>             }
>> #else
>>             constexpr bool _M_nonzero(size_t __n = 0) const
>>             {
>>               return __n < sizeof(_Tp)
>>                              && (__b[__n] || _M_nonzero(__n + 1));
>>             }
>> #endif
>>           };
>>           if constexpr (__builtin_bit_cast(_Bytes, _Tp())._M_nonzero())
>>             return nullptr;
>>         }
>>     }
>>   using _Ptr = decltype(std::__to_address(__first));
>>   // Cannot use memset if _Ptr is cv-qualified.
>>   if constexpr (is_convertible<_Ptr, void*>::value)
>>     return std::__to_address(__first);
>>