Rb tree node recycling patch

François Dumont frs.dumont@gmail.com
Fri Jan 3 18:41:00 GMT 2014

Thanks for your feedback.

     I considered my patch enough tested because it impacts basic 
operations on the Rb tree containers. There are also a number of tests 
that are normally dedicated to exception safety but that has the 
advantage of challenging numerous containers operations in a generic way 
and with some randomness. I have already enhance those tests adding 
checks on memory leaks. It is the biggest issue that could occur with 
this patch. I will add some tests to this framework to cover the newly 
introduced C++11 allocator aware methods.

     To really know how bad or good is the testsuite we should also work 
on test coverage computation but that's a big subject, perhaps for a GSOC...


On 01/03/2014 12:57 PM, Christopher Jefferson wrote:
> Personally, I consider the testing insufficent, although the testing
> was already insufficient! Note that this is my opinion, don't assume I
> talk for all of libstdc++!
> After I broke std::nth_element in 4.8.2 (woops), I am of the view that
> the libstdc++ testsuite is defficient -- many code paths are never
> tested. The nth_element breakage should really have been picked up,
> about 1/3 of all random invocations of nth_element failed!
> You could be "inspired" by the code I wrote for algorithms, it is in
> testsuite/util/testsuite_containergen.h. The basic idea is I make sure
> to generate special cases (size 0 containers, containers containing
> only a single value repeated), and then a range of containers of
> various different sizes.
> I realise suggesting this is probably as much work as your patch, and
> you shouldn't assume this is required, but I think it would improve
> the testsuite. If you do go down this route, then be sure to reduce
> your test's size for simulators. You can look at for example at my new
> tests which feature:
> // { dg-options "-std=gnu++11" }
> // { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } }
> Which enables the macro SIMULATOR_TEST on simulators, where I do much
> less testing (else the tester takes too long.
> On 27 December 2013 18:30, François Dumont <frs.dumont@gmail.com> wrote:
>> Hi
>>      Here is a patch to add recycling of Rb tree nodes when possible.
>>      I replaced the _Rb_tree::_M_move_assign with a move assignment operator
>> to benefit from:
>> - move of elements when the whole data structure cannot be moved
>> - faster data structure cloning rather than full regeneration of the tree
>> when _M_move_assign was failing
>>      Note that this patch contains also a cleanup of a useless template
>> parameter _Is_pod_comparator on _Rb_tree_impl. If you want to apply it
>> quickly for 4.9 do not hesitate.
>>      I haven't done any specific test for this feature, existing ones looks
>> good enough to me. If you want me to add some I will when back from
>> vacation. I am mostly submitting this patch to show you that I worked on it
>> and you do not need to do it yourself.
>> 2013-12-27  François Dumont <fdumont@gcc.gnu.org>
>>      * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New.
>>      (_Rb_tree_alloc_node<>): Likewise.
>>      (_Rb_tree<>::_M_clone_node): Made template to take a node
>>      generator.
>>      (_Rb_tree_impl<>): Remove unused _Is_pod_comparator template
>>      value.
>>      (_Rb_tree<>::_M_move_assign): Replace by...
>>      (_Rb_tree<>::operator(_Rb_tree&&)): ...this.
>>      (_Rb_tree_impl<>::_M_reset): New.
>>      (_Rb_tree<>::_M_insert_): Add node generator parameter.
>>      (_Rb_tree<>::_M_copy): Add overload taking a node generator.
>>      (_Rb_tree<>::_M_insert_unique_): Add node generator parameter.
>>      (_Rb_tree<>::_M_insert_equal_): Add node generator parameter.
>>      (_Rb_tree<>::_M_assign_unique): New.
>>      (_Rb_tree<>::_M_assign_equal): New.
>>      (_Rb_tree<>): Adapt to use _Rb_tree_impl<>::_M_reset and reuse
>>      nodes as much as possible.
>>      * include/bits/stl_set.h (set<>::operator=(set<>&&): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (set<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_unique.
>>      * include/bits/stl_multiset.h
>>      (multiset<>::operator=(multiset<>&&)): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (multiset<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_equal.
>>      * include/bits/stl_map.h (map<>::operator=(map<>&&): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (map<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_unique.
>>      * include/bits/stl_multimap.h
>>      (multimap<>::operator=(multimap<>&&)): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (multimap<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_equal.
>> Tested under Linux x86_64.
>> Happy new year.
>> François

More information about the Gcc-patches mailing list