Re: Rb_tree constructor optimization

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1492 bytes --]

Hi

     Any feedback regarding this patch ?

Thanks,
François

On 14/09/2017 22:04, François Dumont wrote:
> I realized there was no test on the noexcept qualification of the move 
> constructor with allocator.
>
> I added some and found out that patch was missing a noexcept 
> qualification at _Rb_tree level.
>
> Here is the updated patch fully tested, ok to commit ?
>
> François
>
>
> On 13/09/2017 21:57, François Dumont wrote:
>> On 08/09/2017 17:50, Jonathan Wakely wrote:
>>>
>>> Since we know __a == __x.get_allocator() we could just do:
>>>
>>>      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
>>> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>>>      : _M_impl(std::move(__x._M_impl))
>>>      { }
>>>
>>> This means we don't need the new constructor.
>>
>>     You want to consider that a always equal allocator is stateless 
>> and so that the provided allocator rvalue reference do not need to be 
>> moved. IMHO you can have allocator with state that do not participate 
>> in comparison like some monitoring info.
>>
>>     I'm not confortable with that and prefer to keep current behavior 
>> so I propose this new patch considering all your other remarks.
>>
>>     I change noexcept qualification on [multi]map/set constructors to 
>> just rely on _Rep_type constructor noexcept qualification to not 
>> duplicate it.
>>
>> François
>>
>>
>
>
>


[-- Attachment #2: rb_tree.patch --]
[-- Type: text/x-patch, Size: 11520 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index bad6020..e343f04 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -235,8 +235,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(declval<_Rep_type>(), 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 6f5cb7a..8c7ae2c 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -232,8 +232,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(declval<_Rep_type>(), 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 517e77e..9ab4ab7 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -244,8 +244,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(declval<_Rep_type>(), 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 e804a7c..6b64bcd 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -248,8 +248,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(declval<_Rep_type>(), 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 c2417f1..ebfc3f9 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -704,6 +704,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)
 	  { }
@@ -944,10 +950,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Rb_tree(_Rb_tree&&) = default;
 
       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
+      noexcept( noexcept(
+	_Rb_tree(declval<_Rb_tree>(), 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)
+      : _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(declval<_Rb_tree>(), declval<_Node_allocator>(),
+		 declval<typename _Alloc_traits::is_always_equal>()) ) )
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1347,22 +1375,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, true_type)
       { _M_impl._M_move_data(__x._M_impl); }
 
       // Move elements from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1590,23 +1618,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-	   typename _Compare, typename _Alloc>
     void
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_move_data(_Rb_tree& __x, std::false_type)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1628,7 +1645,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }
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 b172df7..97c1a47 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&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  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&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
index 03ef459..9acfbb5 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multimap<int, int> mmtype;
 
-static_assert(std::is_nothrow_move_constructible<mmtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mmtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mmtype(std::declval<mmtype>(),
+		std::declval<const typename mmtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multimap<int, int, ExceptLess> emmtype;
+
+static_assert( !noexcept( emmtype(std::declval<emmtype>(),
+		std::declval<const typename emmtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
index 49878e0..adc7a72 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multiset<int> mstype;
 
-static_assert(std::is_nothrow_move_constructible<mstype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mstype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mstype(std::declval<mstype>(),
+		std::declval<const typename mstype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multiset<int, ExceptLess> emstype;
+
+static_assert( !noexcept( emstype(std::declval<emstype>(),
+		std::declval<const typename emstype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
index 95b5100..0e1f2fa 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::set<int> stype;
 
-static_assert(std::is_nothrow_move_constructible<stype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<stype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( stype(std::declval<stype>(),
+		std::declval<const typename stype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::set<int, ExceptLess> estype;
+
+static_assert( !noexcept( estype(std::declval<estype>(),
+		std::declval<const typename estype::allocator_type&>()) ),
+	       "except move constructor with allocator" );