Re: Rb_tree constructor optimization

[Jonathan Wakely <jwakely@redhat.com>]

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.
 
- 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.

- 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?


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.


>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>())) )



>       : _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
}


The changes to deduce the exception-specifications seem to make the
code more fragile -- do we really want to make those changes?


>+      : _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.