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

For the testsuite allocator I though that for an internal allocator used in our tests it was ok. But alright, I will make it better and compatible with SimpleAllocator.

On 11/06/2014 14:02, Jonathan Wakely wrote:
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
Just to limit amount of code within _Rb_tree. I wanted to do something like in _Hashtable where many code is isolated in different types aggregated to build the final _Hashtable type. But it looks like you prefer it nested so I will do so.

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
Yes, sure, like in the equivalent _Hashtable types. I guess I didn't do so here because we might not be in c++11 so it is not as convenient to forbid its usage.

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

Sometimes I used lambdas, I am not sure but I think it forced me to take functors as const lvalue reference and so the const qualification on the operator.

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.
Sorry, didn't know about this one, I will revert it then.
@@ -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.

I will try to remember why I did those :-)

Thanks for feedback.


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