This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Rb_tree constructor optimization


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



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]