This is the mail archive of the mailing list for the GCC 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: [patch] libstdc++/29988 Rb_Tree reuse allocated nodes

Index: include/bits/stl_tree.h
--- include/bits/stl_tree.h	(revision 211388)
+++ include/bits/stl_tree.h	(working copy)
@@ -330,6 +330,111 @@
               const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
    { return __x._M_node != __y._M_node; }

+  // Functor recycling a pool of nodes and using allocation once the pool is
+  // empty.
+  template<typename _RbTree>
+    struct _Rb_tree_reuse_or_alloc_node
+    {

Is there a reason to define this and _Rb_tree_alloc_node as
namespace-scope class templates, rather than non-template members of

They wouldn't need to be friends if they were members, and you
wouldn't need a typedef for _Rb_tree_alloc_node<_Rb_tree> because it
would just be called _Rb_tree_alloc_node.

+    private:
+      typedef _RbTree __rb_tree;

This typedef doesn't seem useful, it's only used once and is more
characters than "_RbTree". If the class was a member of _Rb_tree it
could just use that name.

+      typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;

If it was a member the value_type name would be in scope.

+    public:
+      _Rb_tree_reuse_or_alloc_node(const _Rb_tree_node_base& __header,
+				   __rb_tree& __t)
+	: _M_root(__header._M_parent), _M_nodes(__header._M_right), _M_t(__t)
+      {
+	if (_M_root)
+	  _M_root->_M_parent = 0;
+	else
+	  _M_nodes = 0;
+      }
+      ~_Rb_tree_reuse_or_alloc_node()
+      { _M_t._M_erase(static_cast<__node_type*>(_M_root)); }

This type needs to be non-copyable, or unintentional copies would
erase all the nodes and leave nothing to be reused (which might be
difficult to detect as it would only affect performance, not

+      template<typename _Arg>
+	__node_type*
+#if __cplusplus < 201103L
+	operator()(const _Arg& __arg) const
+	operator()(_Arg&& __arg) const

Does this need to be const?

I don't think it does (if you change the function templates taking a
const _NodeGen& to take _NodeGen& instead).

That means the members of this type don't need to be 'mutable'.

+      typedef _Rb_tree_node_base __node_base;

I'm not sure this typedef is useful either, it just means an extra
name to remember when reading the code, when _Rb_tree_node_base is
already in scope and probably understood by readers of the code.

+      mutable __node_base* _M_root;
+      mutable __node_base* _M_nodes;

These members should be of type _Rb_tree::_Base_ptr, not __node_base*,
because that's the type _Rb_tree::_M_right is declared as.

I have a work-in-progress patch to make _Rb_tree use
allocator_traits<_Node_allocator>::pointer for _Link_type, which
might not be the same type as _Rb_tree_node<Val>*, so it is important
to consistently use the _Base_ptr and _Link_type typedefs not the
underlying types they refer to (because those underlying types are
going to change soon).

+      _RbTree& _M_t;
+    };
+  // Functor similar to the previous one but without any pool of node to recycle.
+  template<typename _RbTree>
+    struct _Rb_tree_alloc_node

Again, I think this should be a member of _Rb_tree.

+    {
+    private:
+      typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;

This typedef should be removed.

+    public:
+      _Rb_tree_alloc_node(_RbTree& __t)
+	: _M_t(__t) { }
+      template<typename _Arg>
+	__node_type*

This function should return _Rb_tree::_Link_type because that's what
_M_create_node returns.

+#if __cplusplus < 201103L
+	operator()(const _Arg& __arg) const
+	operator()(_Arg&& __arg) const
+	{ return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
@@ -349,6 +454,12 @@
        rebind<_Rb_tree_node<_Val> >::other _Node_allocator;

      typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
+      template<typename _RT>
+	friend struct _Rb_tree_alloc_node;
+      typedef _Rb_tree_alloc_node<_Rb_tree> __alloc_node_t;
+      template<typename _RT>
+	friend struct _Rb_tree_reuse_or_alloc_node;
+      typedef _Rb_tree_reuse_or_alloc_node<_Rb_tree> __reuse_or_alloc_node_t;

These friend declarations and typedefs become unnecessary.

@@ -389,44 +500,55 @@
      { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }

#if __cplusplus < 201103L
-      _Link_type
-      _M_create_node(const value_type& __x)
+      void
+      _M_construct_node(_Link_type __node, const value_type& __x)
-	_Link_type __tmp = _M_get_node();
-	  { get_allocator().construct(__tmp->_M_valptr(), __x); }
+	  { get_allocator().construct(__node->_M_valptr(), __x); }
-	    _M_put_node(__tmp);
+	    _M_put_node(__node);
+      }
+      _Link_type
+      _M_create_node(const value_type& __x)
+      {
+	_Link_type __tmp = _M_get_node();
+	_M_construct_node(__tmp, __x);
	return __tmp;

      _M_destroy_node(_Link_type __p)
-      {
-	get_allocator().destroy(__p->_M_valptr());
-	_M_put_node(__p);
-      }
+      { get_allocator().destroy(__p->_M_valptr()); }
      template<typename... _Args>
-        _Link_type
-        _M_create_node(_Args&&... __args)
+	void
+	_M_construct_node(_Link_type __node, _Args&&... __args)
-	  _Link_type __tmp = _M_get_node();
-	      ::new(__tmp) _Rb_tree_node<_Val>;
+	      ::new(__node) _Rb_tree_node<_Val>();

This should not be value-initialized.

In C++11 all that does is zero out the __aligned_buffer's
uninitialized storage, which is a waste of time as we're about to
overwrite it anyway in the construct().  If you have a large
value_type (e.g. std::map<int, std::array<double,1000>>) the redundant
initialization has a measurable cost and we've had bug reports for
similar code.

@@ -514,11 +651,11 @@
      { return this->_M_impl._M_header._M_right; }

-      _M_begin() _GLIBCXX_NOEXCEPT
+      _M_begin() const _GLIBCXX_NOEXCEPT
      { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }

What's the purpose of this change?
Although it can be 'const' it is consistent with the usual
begin()/end() functions that the functions returning a mutable iterator
are non-const and the functions returning a constant iterator are const.

-      _M_begin() const _GLIBCXX_NOEXCEPT
+      _M_cbegin() const _GLIBCXX_NOEXCEPT
	return static_cast<_Const_Link_type>
@@ -529,7 +666,7 @@
      { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }

-      _M_end() const _GLIBCXX_NOEXCEPT
+      _M_cend() const _GLIBCXX_NOEXCEPT
      { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }

      static const_reference

I'm not very comfortable with this renaming.

Having consistent _M_begin() functions allows using them in template
code that doesn't care if it's using the const or non-const version.

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