On Thu, 17 Oct 2024 at 11:12, Jonathan Wakely <jwak...@redhat.com> wrote:
>
> On Thu, 17 Oct 2024 at 02:39, Patrick Palka <ppa...@redhat.com> wrote:
> >
> > On Tue, 15 Oct 2024, Jonathan Wakely wrote:
> >
> > > This is v2 of
> > > https://gcc.gnu.org/pipermail/gcc-patches/2024-October/665246.html
> > > fixing some thinkos in uninitialized_{fill,fill_n}. We don't need to
> > > worry about overwriting tail-padding in those algos, because we only use
> > > memset for 1-byte integer types. So they have no tail padding that can
> > > be reused anyway! So this changes __n > 1 to __n > 0 in a few places
> > > (which fixes the problem that it was not actually filling anything for
> > > the n==1 cases).
> > >
> > > Also simplify std::__to_address(__result++) to just __result++ because
> > > we already have a pointer, and use std::to_address(result++) for a C++20
> > > std::contiguous_iterator case, instead of addressof(*result++).
> > >
> > > Tested x86_64-linux.
> > >
> > > -- >8 --
> > >
> > > This refactors the std::uninitialized_copy, std::uninitialized_fill and
> > > std::uninitialized_fill_n algorithms to directly perform memcpy/memset
> > > optimizations instead of dispatching to std::copy/std::fill/std::fill_n.
> > >
> > > The reasons for this are:
> > >
> > > - Use 'if constexpr' to simplify and optimize compilation throughput, so
> > > dispatching to specialized class templates is only needed for C++98
> > > mode.
> > > - Relax the conditions for using memcpy/memset, because the C++20 rules
> > > on implicit-lifetime types mean that we can rely on memcpy to begin
> > > lifetimes of trivially copyable types. We don't need to require
> > > trivially default constructible, so don't need to limit the
> > > optimization to trivial types. See PR 68350 for more details.
> > > - The conditions on non-overlapping ranges are stronger for
> > > std::uninitialized_copy than for std::copy so we can use memcpy instead
> > > of memmove, which might be a minor optimization.
> > > - Avoid including <bits/stl_algobase.h> in <bits/stl_uninitialized.h>.
> > > It only needs some iterator utilities from that file now, which belong
> > > in <bits/stl_iterator.h> anyway, so this moves them there.
> > >
> > > Several tests need changes to the diagnostics matched by dg-error
> > > because we no longer use the __constructible() function that had a
> > > static assert in. Now we just get straightforward errors for attempting
> > > to use a deleted constructor.
> > >
> > > Two tests needed more signficant changes to the actual expected results
> > > of executing the tests, because they were checking for old behaviour
> > > which was incorrect according to the standard.
> > > 20_util/specialized_algorithms/uninitialized_copy/64476.cc was expecting
> > > std::copy to be used for a call to std::uninitialized_copy involving two
> > > trivially copyable types. That was incorrect behaviour, because a
> > > non-trivial constructor should have been used, but using std::copy used
> > > trivial default initialization followed by assignment.
> > > 20_util/specialized_algorithms/uninitialized_fill_n/sizes.cc was testing
> > > the behaviour with a non-integral Size passed to uninitialized_fill_n,
> > > but I wrote the test looking at the requirements of uninitialized_copy_n
> > > which are not the same as uninitialized_fill_n. The former uses --n and
> > > tests n > 0, but the latter just tests n-- (which will never be false
> > > for a floating-point value with a fractional part).
> > >
> > > libstdc++-v3/ChangeLog:
> > >
> > > PR libstdc++/68350
> > > PR libstdc++/93059
> > > * include/bits/stl_algobase.h (__niter_base, __niter_wrap): Move
> > > to ...
> > > * include/bits/stl_iterator.h: ... here.
> > > * include/bits/stl_uninitialized.h (__check_constructible)
> > > (_GLIBCXX_USE_ASSIGN_FOR_INIT): Remove.
> > > [C++98] (__unwrappable_niter): New trait.
> > > (__uninitialized_copy<true>): Replace use of std::copy.
> > > (uninitialized_copy): Fix Doxygen comments. Open-code memcpy
> > > optimization for C++11 and later.
> > > (__uninitialized_fill<true>): Replace use of std::fill.
> > > (uninitialized_fill): Fix Doxygen comments. Open-code memset
> > > optimization for C++11 and later.
> > > (__uninitialized_fill_n<true>): Replace use of std::fill_n.
> > > (uninitialized_fill_n): Fix Doxygen comments. Open-code memset
> > > optimization for C++11 and later.
> > > *
> > > testsuite/20_util/specialized_algorithms/uninitialized_copy/64476.cc:
> > > Adjust expected behaviour to match what the standard specifies.
> > > *
> > > testsuite/20_util/specialized_algorithms/uninitialized_fill_n/sizes.cc:
> > > Likewise.
> > > * testsuite/20_util/specialized_algorithms/uninitialized_copy/1.cc:
> > > Adjust dg-error directives.
> > > *
> > > testsuite/20_util/specialized_algorithms/uninitialized_copy/89164.cc:
> > > Likewise.
> > > *
> > > testsuite/20_util/specialized_algorithms/uninitialized_copy_n/89164.cc:
> > > Likewise.
> > > *
> > > testsuite/20_util/specialized_algorithms/uninitialized_fill/89164.cc:
> > > Likewise.
> > > *
> > > testsuite/20_util/specialized_algorithms/uninitialized_fill_n/89164.cc:
> > > Likewise.
> > > * testsuite/23_containers/vector/cons/89164.cc: Likewise.
> > > * testsuite/23_containers/vector/cons/89164_c++17.cc: Likewise.
> > > ---
> > > libstdc++-v3/include/bits/stl_algobase.h | 45 --
> > > libstdc++-v3/include/bits/stl_iterator.h | 54 +++
> > > libstdc++-v3/include/bits/stl_uninitialized.h | 385 +++++++++++++-----
> > > .../uninitialized_copy/1.cc | 3 +-
> > > .../uninitialized_copy/64476.cc | 6 +-
> > > .../uninitialized_copy/89164.cc | 3 +-
> > > .../uninitialized_copy_n/89164.cc | 3 +-
> > > .../uninitialized_fill/89164.cc | 3 +-
> > > .../uninitialized_fill_n/89164.cc | 3 +-
> > > .../uninitialized_fill_n/sizes.cc | 22 +-
> > > .../23_containers/vector/cons/89164.cc | 5 +-
> > > .../23_containers/vector/cons/89164_c++17.cc | 3 +-
> > > 12 files changed, 383 insertions(+), 152 deletions(-)
> > >
> > > diff --git a/libstdc++-v3/include/bits/stl_algobase.h
> > > b/libstdc++-v3/include/bits/stl_algobase.h
> > > index 384e5fdcdc9..751b7ad119b 100644
> > > --- a/libstdc++-v3/include/bits/stl_algobase.h
> > > +++ b/libstdc++-v3/include/bits/stl_algobase.h
> > > @@ -308,51 +308,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > > return __a;
> > > }
> > >
> > > - // Fallback implementation of the function in bits/stl_iterator.h used
> > > to
> > > - // remove the __normal_iterator wrapper. See copy, fill, ...
> > > - template<typename _Iterator>
> > > - _GLIBCXX20_CONSTEXPR
> > > - inline _Iterator
> > > - __niter_base(_Iterator __it)
> > > -
> > > _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
> > > - { return __it; }
> > > -
> > > -#if __cplusplus < 201103L
> > > - template<typename _Ite, typename _Seq>
> > > - _Ite
> > > - __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
> > > - std::random_access_iterator_tag>&);
> > > -
> > > - template<typename _Ite, typename _Cont, typename _Seq>
> > > - _Ite
> > > - __niter_base(const ::__gnu_debug::_Safe_iterator<
> > > - ::__gnu_cxx::__normal_iterator<_Ite, _Cont>, _Seq,
> > > - std::random_access_iterator_tag>&);
> > > -#else
> > > - template<typename _Ite, typename _Seq>
> > > - _GLIBCXX20_CONSTEXPR
> > > - decltype(std::__niter_base(std::declval<_Ite>()))
> > > - __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
> > > - std::random_access_iterator_tag>&)
> > > - noexcept(std::is_nothrow_copy_constructible<_Ite>::value);
> > > -#endif
> > > -
> > > - // Reverse the __niter_base transformation to get a
> > > - // __normal_iterator back again (this assumes that __normal_iterator
> > > - // is only used to wrap random access iterators, like pointers).
> > > - template<typename _From, typename _To>
> > > - _GLIBCXX20_CONSTEXPR
> > > - inline _From
> > > - __niter_wrap(_From __from, _To __res)
> > > - { return __from + (std::__niter_base(__res) -
> > > std::__niter_base(__from)); }
> > > -
> > > - // No need to wrap, iterator already has the right type.
> > > - template<typename _Iterator>
> > > - _GLIBCXX20_CONSTEXPR
> > > - inline _Iterator
> > > - __niter_wrap(const _Iterator&, _Iterator __res)
> > > - { return __res; }
> > > -
> > > // All of these auxiliary structs serve two purposes. (1) Replace
> > > // calls to copy with memmove whenever possible. (Memmove, not memcpy,
> > > // because the input and output ranges are permitted to overlap.)
> > > diff --git a/libstdc++-v3/include/bits/stl_iterator.h
> > > b/libstdc++-v3/include/bits/stl_iterator.h
> > > index 28a600c81cb..85b98ffff61 100644
> > > --- a/libstdc++-v3/include/bits/stl_iterator.h
> > > +++ b/libstdc++-v3/include/bits/stl_iterator.h
> > > @@ -1338,10 +1338,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > > _GLIBCXX_END_NAMESPACE_VERSION
> > > } // namespace
> > >
> > > +namespace __gnu_debug
> > > +{
> > > + template<typename _Iterator, typename _Sequence, typename _Category>
> > > + class _Safe_iterator;
> > > +}
> > > +
> > > namespace std _GLIBCXX_VISIBILITY(default)
> > > {
> > > _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > >
> > > + // Unwrap a __normal_iterator to get the underlying iterator
> > > + // (usually a pointer)
> > > template<typename _Iterator, typename _Container>
> > > _GLIBCXX20_CONSTEXPR
> > > _Iterator
> > > @@ -1349,6 +1357,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > >
> > > _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
> > > { return __it.base(); }
> > >
> > > + // Fallback implementation of the function in bits/stl_iterator.h used
> > > to
> > > + // remove the __normal_iterator wrapper. See std::copy, std::fill, etc.
> > > + template<typename _Iterator>
> > > + _GLIBCXX20_CONSTEXPR
> > > + inline _Iterator
> > > + __niter_base(_Iterator __it)
> > > +
> > > _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
> > > + { return __it; }
> > > +
> > > + // Overload for _Safe_iterator needs to be declared before
> > > __niter_base uses.
> >
> > Do we also need to declare __niter_base(move_iterator) earlier in this
> > file so that name lookup finds it when calling __niter_base ...
> >
> > > +#if __cplusplus < 201103L
> > > + template<typename _Ite, typename _Seq>
> > > + _Ite
> > > + __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
> > > + std::random_access_iterator_tag>&);
> > > +
> > > + template<typename _Ite, typename _Cont, typename _Seq>
> > > + _Ite
> > > + __niter_base(const ::__gnu_debug::_Safe_iterator<
> > > + ::__gnu_cxx::__normal_iterator<_Ite, _Cont>, _Seq,
> > > + std::random_access_iterator_tag>&);
> > > +#else
> > > + template<typename _Ite, typename _Seq>
> > > + _GLIBCXX20_CONSTEXPR
> > > + decltype(std::__niter_base(std::declval<_Ite>()))
> >
> > ... here and ...
>
> I don't think the move_iterator overload is needed here.
>
> We should never have a debug mode _Safe_iterator that wraps a move_iterator.
>
> >
> > > + __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
> > > + std::random_access_iterator_tag>&)
> > > + noexcept(std::is_nothrow_copy_constructible<_Ite>::value);
> > > +#endif
> > > +
> > > + // Reverse the __niter_base transformation to get a
> > > + // __normal_iterator back again (this assumes that __normal_iterator
> > > + // is only used to wrap random access iterators, like pointers).
> > > + template<typename _From, typename _To>
> > > + _GLIBCXX20_CONSTEXPR
> > > + inline _From
> > > + __niter_wrap(_From __from, _To __res)
> > > + { return __from + (std::__niter_base(__res) -
> > > std::__niter_base(__from)); }
> >
> > ... here?
>
> But here, maybe yes.
>
> I'll see if I can come up with a test that fails, to verify that
> moving it helps.
This compiles with current trunk but fails in my tree with this change:
#define _GLIBCXX_DEBUG
#include <iterator>
#include <algorithm>
#include <vector>
struct S { };
int main()
{
std::vector<S> v;
std::vector<S> vout;
std::copy(v.begin(), v.end(), std::make_move_iterator(vout.rbegin()));
}
So I need to fix that. Thanks for spotting it.
