[patch] libstdc++/29988 Rb_Tree reuse allocated nodes

[Jonathan Wakely]

>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
_Rb_tree?

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


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

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
>+#else
>+	operator()(_Arg&& __arg) const
>+#endif
>+	{ 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();
> 	__try
>-	  { get_allocator().construct(__tmp->_M_valptr(), __x); }
>+	  { get_allocator().construct(__node->_M_valptr(), __x); }
> 	__catch(...)
> 	  {
>-	    _M_put_node(__tmp);
>+	    _M_put_node(__node);
> 	    __throw_exception_again;
> 	  }
>+      }
>+
>+      _Link_type
>+      _M_create_node(const value_type& __x)
>+      {
>+	_Link_type __tmp = _M_get_node();
>+	_M_construct_node(__tmp, __x);
> 	return __tmp;
>       }
> 
>       void
>       _M_destroy_node(_Link_type __p)
>-      {
>-	get_allocator().destroy(__p->_M_valptr());
>-	_M_put_node(__p);
>-      }
>+      { get_allocator().destroy(__p->_M_valptr()); }
> #else
>       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();
> 	  __try
> 	    {
>-	      ::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; }
> 
>       _Link_type
>-      _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.

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