Re: 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).