Re: Rb_tree constructor optimization

[François Dumont <frs dot dumont at gmail dot com>]

On 02/05/2018 13:49, Jonathan Wakely wrote:
> On 01/05/18 21:56 +0200, François Dumont wrote:
> > Hi
> >
> > If not told otherwise I'll commit attached patch tomorrow.
>
> Please do not commit it, see below.
>
> > Already discussed here:
> >
> > https://gcc.gnu.org/ml/libstdc++/2017-10/msg00053.html
>
> There's no changelog entry with the patch, so to recap, the changes
> are:
>
> - noexcept specifications are automatically deduced instead of being
>  stated explicitly.
Yes, it helps to make sure rb tree code is correct and it avoids usage 
of non-standard _S_always_equal. We could even use std::allocator_traits 
in C++11.
> - The allocator-extended move constructors get correct exception
>  specifications in Debug Mode (consistent with normal mode). This
>  should be done anyway, independent of any other changes.
Yes, I realized it after I wrote the tests to validate the noexcept 
qualification.
> - We avoid a `if (__x._M_root() != nullptr)` branch in the case where
>  the allocator-extended move constructor is used with an always-equal
>  allocator, right?
Yes, this is consistent with most of the other containers doing the same.
> Deducing the noexcept specifications probably has a (small?) impact on
> compilation speed, as currently the allocator-extended move
> constructors have:
>
> - noexcept(is_nothrow_copy_constructible<_Compare>::value
> -           && _Alloc_traits::_S_always_equal())
>
> After the patch they have to determine the noexcept-ness of the
> _Rep_type constructor taking allocator_type, which has to determine
> the noexcept-ness of the _Rep_type constructor taking a
> _Node_allocator, which has to determine the noexcept-ness of the
> constructor it dispatches to depending on _S_always_equal(), which is
> simply:
>
> + noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>
> So instead of just using that value in the first place we have to
> perform three rounds of overload resolution to find the right
> constructor and then check its exception specification. And then we
> get the wrong answer (see below).
>
> Compilation time for containers is already **much** slower since the
> allocator-extended constructors were added for GCC 5.x, despite very
> few people ever using those constructors. This patch seems to require
> even more work from the compiler to parse constructors nobody uses.

I must confess that I didn't consider this aspect of the patch. I just 
wanted the code to be more logical. I even wonder why it wasn't done 
this way, now I know. Could this compilation cost be testable ? Isn't 
the compiler doing this work only if the constructor is being used ? Or 
even just only if it needs to know about the noexcept qualification ?

> > François
>
> > diff --git a/libstdc++-v3/include/bits/stl_map.h 
> > b/libstdc++-v3/include/bits/stl_map.h
> > index a4a026e..2b8fd27 100644
> > --- a/libstdc++-v3/include/bits/stl_map.h
> > +++ b/libstdc++-v3/include/bits/stl_map.h
> > @@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> >
> >       /// Allocator-extended move constructor.
> >       map(map&& __m, const allocator_type& __a)
> > - noexcept(is_nothrow_copy_constructible<_Compare>::value
> > -           && _Alloc_traits::_S_always_equal())
> > +      noexcept( noexcept(
> > +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>
> All these calls to declval need to be qualified to avoid ADL.
>
> It seems strange to have a mix of real values and declval expressions,
> rather than:
>
>     _Rep_type(std::declval<_Rep_type>(), 
> std::declval<_Pair_alloc_type>())) )
    Has std::declval<>() been modified recently ? I think I tried that 
and it was working but after a while it started to fail so I had to 
replace with the other expression. I'll try it again if I eventually 
commit this.
> >       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
> >
> >       /// Allocator-extended initialier-list constructor.
> > diff --git a/libstdc++-v3/include/bits/stl_multimap.h 
> > b/libstdc++-v3/include/bits/stl_multimap.h
> > index fc8f454..b9289ab 100644
> > --- a/libstdc++-v3/include/bits/stl_multimap.h
> > +++ b/libstdc++-v3/include/bits/stl_multimap.h
> > @@ -237,8 +237,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> >
> >       /// Allocator-extended move constructor.
> >       multimap(multimap&& __m, const allocator_type& __a)
> > - noexcept(is_nothrow_copy_constructible<_Compare>::value
> > -           && _Alloc_traits::_S_always_equal())
> > +      noexcept( noexcept(
> > +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
> >       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
> >
> >       /// Allocator-extended initialier-list constructor.
> > diff --git a/libstdc++-v3/include/bits/stl_multiset.h 
> > b/libstdc++-v3/include/bits/stl_multiset.h
> > index f41f56c..afaf3b6 100644
> > --- a/libstdc++-v3/include/bits/stl_multiset.h
> > +++ b/libstdc++-v3/include/bits/stl_multiset.h
> > @@ -253,8 +253,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> >
> >       /// Allocator-extended move constructor.
> >       multiset(multiset&& __m, const allocator_type& __a)
> > - noexcept(is_nothrow_copy_constructible<_Compare>::value
> > -           && _Alloc_traits::_S_always_equal())
> > +      noexcept( noexcept(
> > +    _Rep_type(std::move(__m._M_t), declval<_Key_alloc_type>())) )
> >       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
> >
> >       /// Allocator-extended initialier-list constructor.
> > diff --git a/libstdc++-v3/include/bits/stl_set.h 
> > b/libstdc++-v3/include/bits/stl_set.h
> > index 2e332ef..fc6d1f7 100644
> > --- a/libstdc++-v3/include/bits/stl_set.h
> > +++ b/libstdc++-v3/include/bits/stl_set.h
> > @@ -257,8 +257,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> >
> >       /// Allocator-extended move constructor.
> >       set(set&& __x, const allocator_type& __a)
> > - noexcept(is_nothrow_copy_constructible<_Compare>::value
> > -           && _Alloc_traits::_S_always_equal())
> > +      noexcept( noexcept(
> > +    _Rep_type(std::move(__x._M_t), declval<_Key_alloc_type>())) )
> >       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
> >
> >       /// Allocator-extended initialier-list constructor.
> > diff --git a/libstdc++-v3/include/bits/stl_tree.h 
> > b/libstdc++-v3/include/bits/stl_tree.h
> > index d0a8448..732ac55 100644
> > --- a/libstdc++-v3/include/bits/stl_tree.h
> > +++ b/libstdc++-v3/include/bits/stl_tree.h
> > @@ -715,6 +715,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > #else
> >       _Rb_tree_impl(_Rb_tree_impl&&) = default;
> >
> > +      _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
> > +      : _Node_allocator(std::move(__a)),
> > +        _Base_key_compare(std::move(__x)),
> > +        _Rb_tree_header(std::move(__x))
> > +      { }
> > +
> >       _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
> >       : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
> >       { }
> > @@ -955,10 +961,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >       _Rb_tree(_Rb_tree&&) = default;
> >
> >       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
> > +      noexcept( noexcept(
> > +    _Rb_tree(std::move(__x), declval<_Node_allocator>())) )
> >       : _Rb_tree(std::move(__x), _Node_allocator(__a))
> >       { }
> >
> > -      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
> > +    private:
> > +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
> > + noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>
> This is wrong.
>
> The result of is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>
> depends on this constructor:
>
>  _Rb_tree_impl(_Rb_tree_impl&&) = default;
>
> That constructor depends on the allocator type, which might not be
> noexcept, but it's undefined behaviour for it to throw. We don't want
> the exception-specification to depend on the allocator, otherwise we
> fail this test on the line marked XXX:
>
> template<typename T>
> struct Alloc : std::allocator<T>
> {
>  Alloc() { }
>  Alloc(const Alloc&) { }
>  template<typename U> Alloc(const Alloc<U>&) { }
>
>  template<typename U> struct rebind { using other = Alloc<U>; };
> };
>
> template<typename A>
> using Set = std::set<int, std::less<int>, A>;
>
> template<typename A>
>  using Test = std::is_nothrow_constructible<Set<A>, Set<A>, A>;
>
> int main()
> {
>  static_assert(Test<std::allocator<int>>::value, "");
>  static_assert(Test<Alloc<int>>::value, "");  // XXX
> }
In my copy of the Standard I see no noexcept qualifications on 
associative container constructors, is it too old ?

> The changes to deduce the exception-specifications seem to make the
> code more fragile -- do we really want to make those changes?
Considering all your feedbacks I would say no. I'll rework it then.
> > +      : _M_impl(std::move(__x._M_impl), std::move(__a))
> > +      { }
> > +
> > +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
> > +      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
> > +      {
> > +    if (__x._M_root() != nullptr)
> > +      _M_move_data(__x, false_type{});
> > +      }
> > +
> > +    public:
> > +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
> > +      noexcept( noexcept(
> > +    _Rb_tree(std::move(__x), std::move(__a),
> > +         declval<typename _Alloc_traits::is_always_equal>()) ) )
> > +      : _Rb_tree(std::move(__x), std::move(__a),
> > +         typename _Alloc_traits::is_always_equal{})
> > +      { }
> > #endif
>
>
> > diff --git a/libstdc++-v3/include/debug/map.h 
> > b/libstdc++-v3/include/debug/map.h
> > index 414b4dc..9edb7dc 100644
> > --- a/libstdc++-v3/include/debug/map.h
> > +++ b/libstdc++-v3/include/debug/map.h
> > @@ -105,8 +105,10 @@ namespace __debug
> >       : _Base(__m, __a) { }
> >
> >       map(map&& __m, const allocator_type& __a)
> > +      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
> >       : _Safe(std::move(__m._M_safe()), __a),
> > -    _Base(std::move(__m._M_base()), __a) { }
> > +    _Base(std::move(__m._M_base()), __a)
> > +      { }
>
> This part of the patch is actually a bug fix, making the debug mode
> consistent with normal mode.
>
> > diff --git 
> > a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc 
> > b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc 
> >
> > index 0041408..8791eb8 100644
> > --- 
> > a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
> > +++ 
> > b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
> > @@ -23,4 +23,25 @@
> >
> > typedef std::map<int, int> mtype;
> >
> > -static_assert(std::is_nothrow_move_constructible<mtype>::value, 
> > "Error");
> > +static_assert( std::is_nothrow_move_constructible<mtype>::value,
> > +           "noexcept move constructor" );
> > +static_assert( noexcept( mtype(std::declval<mtype>(),
> > +        std::declval<const typename mtype::allocator_type&>()) ),
>
> This can use std::is_nothrow_constructible
>
> > +           "noexcept move constructor with allocator" );
> > +
> > +struct ExceptLess
>
> Please name this "ThrowingLess" instead of "ExceptLess", I think
> that's more descriptive.
>
> > +{
> > +  ExceptLess() = default;
> > +  ExceptLess(const ExceptLess&) /* noexcept */
> > +  { }
> > +
> > +  bool
> > +  operator()(int l, int r) const
> > +  { return l < r; }
> > +};
> > +
> > +typedef std::map<int, int, ExceptLess> emtype;
> > +
> > +static_assert( !noexcept( emtype(std::declval<emtype>(),
> > +        std::declval<const typename emtype::allocator_type&>()) ),
>
> This can use std::is_nothrow_constructible too.
>
> Same comments for the other tests

Ok