[PATCH] Remove lambdas from _Rb_tree

François Dumont frs.dumont@gmail.com
Thu Nov 19 06:46:29 GMT 2020 

On 18/11/20 12:50 am, Jonathan Wakely wrote:
> On 17/11/20 21:51 +0100, François Dumont via Libstdc++ wrote:
>> This is a change that has been done to _Hashtable and that I forgot 
>> to propose for _Rb_tree.
>>
>> The _GLIBCXX_XREF macro can be easily removed of course.
>>
>>     libstdc++: _Rb_tree code cleanup, remove lambdas.
>>
>>     Use an additional template parameter on the clone method to 
>> propagate if the values must be
>>     copy or move rather than lambdas.
>>
>>     libstdc++-v3/ChangeLog:
>>
>>             * include/bits/move.h (_GLIBCXX_XREF): New.
>>             * include/bits/stl_tree.h: Adapt to use latter.
>>             (_Rb_tree<>::_S_fwd_value_for): New.
>>             (_Rb_tree<>::_M_clone_node): Add _Tree 
>> template parameter.
>>             Use _S_fwd_value_for.
>>             (_Rb_tree<>::_M_cbegin): New.
>>             (_Rb_tree<>::_M_begin): Use latter.
>>             (_Rb_tree<>::_M_copy): Add _Tree template 
>> parameter.
>>             (_Rb_tree<>::_M_move_data): Use rvalue 
>> reference for _Rb_tree parameter.
>>             (_Rb_tree<>::_M_move_assign): Likewise.
>>
>> Tested under Linux x86_64.
>>
>> Ok to commit ?
>
> GCC is in stage 3 now, so this should have been posted last week
> really.

Ok, no problem, it can wait.

Still, following your advises here is what I come up with, much simpler 
indeed.

I just run a few tests for the moment but so far so good.

Thanks

>
>
>> diff --git a/libstdc++-v3/include/bits/move.h 
>> b/libstdc++-v3/include/bits/move.h
>> index 5a4dbdc823c..e0d68ca9108 100644
>> --- a/libstdc++-v3/include/bits/move.h
>> +++ b/libstdc++-v3/include/bits/move.h
>> @@ -158,9 +158,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>   /// @} group utilities
>>
>> +#define _GLIBCXX_XREF(_Tp) _Tp&&
>
> I think this does improve the code that uses this. But the correct
> name for this is forwarding reference, so I think FWDREF would be
> better than XREF. XREF doesn't tell me anything about what it's for.
>
>> #define _GLIBCXX_MOVE(__val) std::move(__val)
>> #define _GLIBCXX_FORWARD(_Tp, __val) std::forward<_Tp>(__val)
>> #else
>> +#define _GLIBCXX_XREF(_Tp) const _Tp&
>> #define _GLIBCXX_MOVE(__val) (__val)
>> #define _GLIBCXX_FORWARD(_Tp, __val) (__val)
>> #endif
>> diff --git a/libstdc++-v3/include/bits/stl_tree.h 
>> b/libstdc++-v3/include/bits/stl_tree.h
>> index ec141ea01c7..128c7e2c892 100644
>> --- a/libstdc++-v3/include/bits/stl_tree.h
>> +++ b/libstdc++-v3/include/bits/stl_tree.h
>> @@ -478,11 +478,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>     template<typename _Arg>
>>       _Link_type
>> -#if __cplusplus < 201103L
>> -      operator()(const _Arg& __arg)
>> -#else
>> -      operator()(_Arg&& __arg)
>> -#endif
>> +      operator()(_GLIBCXX_XREF(_Arg) __arg)
>>       {
>>         _Link_type __node = static_cast<_Link_type>(_M_extract());
>>         if (__node)
>> @@ -544,11 +540,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>     template<typename _Arg>
>>       _Link_type
>> -#if __cplusplus < 201103L
>> -      operator()(const _Arg& __arg) const
>> -#else
>> -      operator()(_Arg&& __arg) const
>> -#endif
>> +      operator()(_GLIBCXX_XREF(_Arg) __arg) const
>>       { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
>>
>>       private:
>> @@ -655,11 +647,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>     _M_put_node(__p);
>>       }
>>
>> -      template<typename _NodeGen>
>> +#if __cplusplus >= 201103L
>> +      template<typename _Tree>
>> +    static constexpr
>> +    typename conditional<std::is_lvalue_reference<_Tree>::value,
>> +                 const value_type&, value_type&&>::type
>> +    _S_fwd_value_for(value_type& __val) noexcept
>> +    { return std::move(__val); }
>> +#else
>> +      template<typename _Tree>
>> +    static const value_type&
>> +    _S_fwd_value_for(value_type& __val)
>> +    { return __val; }
>> +#endif
>> +
>> +      template<typename _Tree, typename _NodeGen>
>>     _Link_type
>> -    _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
>> +    _M_clone_node(_GLIBCXX_XREF(_Tree),
>
> Since the _Tree type is only used to decide whether to copy or move,
> could it just be a bool instead?
>
>       template<bool _Move, typename _NodeGen>
>      _Link_type
>     _M_clone_node(_Link_type __x, _NodeGen& __node_gen)
>
> Then it would be called as _M_clone_node<_Move>(__x, __node_gen)
> instead of _M_clone_node(_GLIBCXX_FORWARD(_Tree, __t), __x, __node_gen).
> That seems easier to read.
>
>> +              _Link_type __x, _NodeGen& __node_gen)
>>     {
>> -      _Link_type __tmp = __node_gen(*__x->_M_valptr());
>> +      _Link_type __tmp
>> +        = __node_gen(_S_fwd_value_for<_Tree>(*__x->_M_valptr()));
>
> Is _S_fwd_value_for necessary? This would work:
>
> #if __cplusplus >= 201103L
>           using _Vp = typename 
> conditional<is_lvalue_reference<_Tree>::value,
>                                            const value_type&,
> value_type&&>::type;
> #else
>           typedef const value_type& _Vp;
> #endif
>           _Link_type __tmp
>             = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));
>
> Or with the suggestion above, the typedef would be:
>
>           using _Vp = typename conditional<_Move, value_type&&,
>                                            const value_type&>::type;
>
>
>>       __tmp->_M_color = __x->_M_color;
>>       __tmp->_M_left = 0;
>>       __tmp->_M_right = 0;
>> @@ -748,9 +756,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>       { return this->_M_impl._M_header._M_right; }
>>
>>       _Link_type
>> -      _M_begin() _GLIBCXX_NOEXCEPT
>> +      _M_cbegin() const _GLIBCXX_NOEXCEPT
>
> It's confusing that this is called cbegin but returns a non-const
> link. The standard cbegin() functions return a const_iterator. I would
> expect this to return a _Const_Link_type, based on the name.
>
>
>>       { return 
>> static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
>>
>> +      _Link_type
>> +      _M_begin() _GLIBCXX_NOEXCEPT
>> +      { return _M_cbegin(); }
>> +
>>       _Const_Link_type
>>       _M_begin() const _GLIBCXX_NOEXCEPT
>>       {
>> @@ -889,15 +901,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>       _M_insert_equal_lower(const value_type& __x);
>> #endif
>>
>> -      template<typename _NodeGen>
>> +      template<typename _Tree, typename _NodeGen>
>>     _Link_type
>> -    _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
>> +    _M_copy(_GLIBCXX_XREF(_Tree), _Link_type, _Base_ptr, _NodeGen&);
>
> This could use 'bool _Move' instead of 'typename _Tree'.
>
>> -      template<typename _NodeGen>
>> +      template<typename _Tree, typename _NodeGen>
>>     _Link_type
>> -    _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
>> +    _M_copy(_GLIBCXX_XREF(_Tree) __x, _NodeGen& __gen)
>
> This one gets called from _M_copy(const _Rb_tree&) with const _Rb_tree
> argument, so I think using the XREF macro (or FWDREF) does make sense
> here.
>
>>     {
>> -      _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
>> +      _Link_type __root = _M_copy(_GLIBCXX_FORWARD(_Tree, __x),
>> +                      __x._M_cbegin(), _M_end(), __gen);
>
> This would have to be:
>
> #if __cplusplus >= 201103L
>           constexpr bool __move = !is_reference<_Tree>::value;
> #else
>           const bool __move = false;
> #endif
>           _Link_type __root = _M_copy<__move>(__x._M_cbegin(), 
> _M_end(), __gen);
>
> Would doing it this way make sense?
>
>
>>       _M_leftmost() = _S_minimum(__root);
>>       _M_rightmost() = _S_maximum(__root);
>>       _M_impl._M_node_count = __x._M_impl._M_node_count;
>> @@ -1426,22 +1439,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>     private:
>>       // Move elements from container with equal allocator.
>>       void
>> -      _M_move_data(_Rb_tree& __x, true_type)
>> +      _M_move_data(_Rb_tree&& __x, true_type)
>>       { _M_impl._M_move_data(__x._M_impl); }
>>
>>       // Move elements from container with possibly non-equal allocator,
>>       // which might result in a copy not a move.
>>       void
>> -      _M_move_data(_Rb_tree&, false_type);
>> +      _M_move_data(_Rb_tree&&, false_type);
>>
>>       // Move assignment from container with equal allocator.
>>       void
>> -      _M_move_assign(_Rb_tree&, true_type);
>> +      _M_move_assign(_Rb_tree&&, true_type);
>>
>>       // Move assignment from container with possibly non-equal 
>> allocator,
>>       // which might result in a copy not a move.
>>       void
>> -      _M_move_assign(_Rb_tree&, false_type);
>> +      _M_move_assign(_Rb_tree&&, false_type);
>
> These changes don't seem necessary. While they might be preferable if
> we were writing this from scratch, changing them now means that
> binaries built with more than one version of GCC will be larger.
> Objects built with older versions of GCC will have instantiations of
> the old versions and objects built with newer versions will have
> instantiations of the new versions. The increase in executable size
> (and icache pressure) doesn't seem worthwhile.
>
> The other changes (to remove the lambdas) also have this consequence,
> but the benefits of simplifying the code do seem worthwhile. Just
> changing _Rb_tree& to _Rb_tree&& (and having to use std::move to call
> those functions) doesn't simplify anything. The functions already have
> "move" in the name, so it's pretty obvious they perform moves.
>
>
>
>
>> @@ -1859,29 +1864,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>   template<typename _Key, typename _Val, typename _KoV,
>>        typename _Compare, typename _Alloc>
>> -    template<typename _NodeGen>
>> +    template<typename _Tree, typename _NodeGen>
>>       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
>>       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
>> -      _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& 
>> __node_gen)
>> +      _M_copy(_GLIBCXX_XREF(_Tree) __t,
>
> The __t parameter is only needed below to be forwarded, so its type
> can be checked later on. Using bool _Move instead would work fine, and
> avoid having to pass an extra parameter on the stack which never gets
> used (only its type).
>
>> +          _Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
>>       {
>>     // Structural copy. __x and __p must be non-null.
>> -    _Link_type __top = _M_clone_node(__x, __node_gen);
>> +    _Link_type __top = _M_clone_node(_GLIBCXX_FORWARD(_Tree, __t),
>> +                     __x, __node_gen);
>>     __top->_M_parent = __p;
>>
>>     __try
>>       {
>>         if (__x->_M_right)
>> -          __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
>> +          __top->_M_right = _M_copy(_GLIBCXX_FORWARD(_Tree, __t),
>> +                    _S_right(__x), __top, __node_gen);
>>         __p = __top;
>>         __x = _S_left(__x);
>>
>>         while (__x != 0)
>>           {
>> -        _Link_type __y = _M_clone_node(__x, __node_gen);
>> +        _Link_type __y = _M_clone_node(_GLIBCXX_FORWARD(_Tree, __t),
>> +                           __x, __node_gen);
>>         __p->_M_left = __y;
>>         __y->_M_parent = __p;
>>         if (__x->_M_right)
>> -          __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
>> +          __y->_M_right = _M_copy(_GLIBCXX_FORWARD(_Tree, __t),
>> +                      _S_right(__x), __y, __node_gen);
>>         __p = __y;
>>         __x = _S_left(__x);
>>           }
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree.patch
Type: text/x-patch
Size: 5946 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20201119/846a12e5/attachment.bin>

More information about the Libstdc++ mailing list