Rb_tree constructor optimization

François Dumont frs.dumont@gmail.com
Thu May 3 20:11:00 GMT 2018 

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

More information about the Libstdc++ mailing list