Re: Rb tree node recycling patch

[Christopher Jefferson <chris at bubblescope dot net>]

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
>