Rb_tree constructor optimization

[Jonathan Wakely]

On 28/08/17 21:12 +0200, François Dumont wrote:
>Hi
>
>    Here is the always equal allocator optimization for associative 
>containers.
>
>    Tested under Linux x86_64.
>
>    * include/bits/stl_tree.h
>    (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): Likewise.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>
>    Ok to apply ?
>
>François
>
>

>diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
>index c2417f1..f7d34e3 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) noexcept

This is an unconditional noexcept, but ...

>+	    : _Node_allocator(std::move(__a)),
>+	      _Base_key_compare(std::move(__x)),

This constructor has a conditional noexcept. That's a bug.

>+	      _Rb_tree_header(std::move(__x))
>+	  { }

However, I don't think we need this new constructor anyway, see below.

> 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
> 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
> 	  { }
>@@ -947,7 +953,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>       : _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, std::true_type) noexcept

This noexcept should be conditional.

>+      : _M_impl(std::move(__x._M_impl), std::move(__a))
>+      { }

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.

Or equivalently, just delegate to the move constructor:

      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
      noexcept(is_nothrow_move_constructible<_Rb_tree>::value)
      : _Rb_tree(std::move(__x))
      { }

>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type);
>+
>+    public:
>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
>+      : _Rb_tree(std::move(__x), std::move(__a),
>+		 typename _Alloc_traits::is_always_equal{})
>+      { }
> #endif
> 
>       ~_Rb_tree() _GLIBCXX_NOEXCEPT
>@@ -1591,12 +1608,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>   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)
>+    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type __eq)
>     : _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());
>+	_M_move_data(__x, __eq);
>     }

I think this constructor is simple enough that it should be defined
in-class, so it's inline.

There's no need to qualify true_type and false_type with the std
namespace (I don't know why some of the existing code does that).