public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
* Rb_tree constructor optimization
@ 2017-08-28 19:13 François Dumont
  2017-09-08 15:50 ` Jonathan Wakely
  0 siblings, 1 reply; 19+ messages in thread
From: François Dumont @ 2017-08-28 19:13 UTC (permalink / raw)
  To: libstdc++, gcc-patches

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

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



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

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
+	    : _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)
 	  { }
@@ -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
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _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);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,


^ permalink raw reply	[flat|nested] 19+ messages in thread
* Rb_tree constructor optimization
@ 2018-05-01 19:56 François Dumont
  2018-05-01 21:23 ` Ville Voutilainen
  2018-05-02 11:49 ` Jonathan Wakely
  0 siblings, 2 replies; 19+ messages in thread
From: François Dumont @ 2018-05-01 19:56 UTC (permalink / raw)
  To: libstdc++, gcc-patches

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

Hi

If not told otherwise I'll commit attached patch tomorrow.

Already discussed here:

https://gcc.gnu.org/ml/libstdc++/2017-10/msg00053.html

François


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

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>())) )
       : _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)
+      : _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
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1358,22 +1386,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
@@ -1601,23 +1629,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);
@@ -1639,7 +1656,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/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)
+      { }
 
       map(initializer_list<value_type> __l, const allocator_type& __a)
       : _Base(__l, __a) { }
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index 8d6358b..9ee3809 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -105,6 +105,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multimap(multimap&& __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) { }
 
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 4e1406e..0be14d7 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multiset(multiset&& __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) { }
 
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index a886860..7f24a83 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__x, __a) { }
 
       set(set&& __x, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
       : _Safe(std::move(__x._M_safe()), __a),
 	_Base(std::move(__x._M_base()), __a) { }
 
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&>()) ),
+	       "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 0319a61..9b81666 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 b1c6dd5..f6dd42c 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 a7de0ef..0a6f2da 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" );

^ permalink raw reply	[flat|nested] 19+ messages in thread
end of thread, other threads:[~2018-05-21 19:59 UTC | newest]

Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-08-28 19:13 Rb_tree constructor optimization François Dumont
2017-09-08 15:50 ` Jonathan Wakely
2017-09-13 19:57   ` François Dumont
2017-09-14 20:04     ` François Dumont
2017-10-19  5:39       ` François Dumont
2018-05-01 19:56 François Dumont
2018-05-01 21:23 ` Ville Voutilainen
2018-05-01 21:28   ` Jakub Jelinek
2018-05-01 21:47     ` Ville Voutilainen
2018-05-01 22:42       ` Jonathan Wakely
2018-05-02 11:49 ` Jonathan Wakely
2018-05-03 20:11   ` François Dumont
2018-05-06 14:06   ` François Dumont
2018-05-11 12:16     ` Jonathan Wakely
2018-05-15  5:31       ` François Dumont
2018-05-17 15:10         ` Jonathan Wakely
2018-05-19  1:45           ` Jonathan Wakely
2018-05-19 23:16             ` H.J. Lu
2018-05-21 19:59               ` François Dumont

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).