* [PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h>
@ 2024-06-27 10:39 Jonathan Wakely
2024-06-27 10:39 ` [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset Jonathan Wakely
2024-06-27 10:39 ` [PATCH 3/3] libstdc++: Use std::__uninitialized_default for ranges::uninitialized_value_construct Jonathan Wakely
0 siblings, 2 replies; 4+ messages in thread
From: Jonathan Wakely @ 2024-06-27 10:39 UTC (permalink / raw)
To: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset
2024-06-27 10:39 [PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h> Jonathan Wakely
@ 2024-06-27 10:39 ` Jonathan Wakely
2024-06-27 11:46 ` Jonathan Wakely
2024-06-27 10:39 ` [PATCH 3/3] libstdc++: Use std::__uninitialized_default for ranges::uninitialized_value_construct Jonathan Wakely
1 sibling, 1 reply; 4+ messages in thread
From: Jonathan Wakely @ 2024-06-27 10:39 UTC (permalink / raw)
To: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH 3/3] libstdc++: Use std::__uninitialized_default for ranges::uninitialized_value_construct
2024-06-27 10:39 [PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h> Jonathan Wakely
2024-06-27 10:39 ` [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset Jonathan Wakely
@ 2024-06-27 10:39 ` Jonathan Wakely
1 sibling, 0 replies; 4+ messages in thread
From: Jonathan Wakely @ 2024-06-27 10:39 UTC (permalink / raw)
To: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset
2024-06-27 10:39 ` [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset Jonathan Wakely
@ 2024-06-27 11:46 ` Jonathan Wakely
0 siblings, 0 replies; 4+ messages in thread
From: Jonathan Wakely @ 2024-06-27 11:46 UTC (permalink / raw)
To: libstdc++, gcc-patches
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
>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2024-06-27 11:46 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-06-27 10:39 [PATCH 1/3] libstdc++: Use RAII in <bits/stl_uninitialized.h> Jonathan Wakely
2024-06-27 10:39 ` [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset Jonathan Wakely
2024-06-27 11:46 ` Jonathan Wakely
2024-06-27 10:39 ` [PATCH 3/3] libstdc++: Use std::__uninitialized_default for ranges::uninitialized_value_construct Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).