Re: [PATCH] Remove lambdas from _Rb_tree

Thu, 19 Nov 2020 03:31:47 -0800 

On 19/11/20 07:46 +0100, François Dumont via Libstdc++ wrote:

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.


Yes, this simpler patch looks promising even though it's stage 3.


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);
          }







diff --git a/libstdc++-v3/include/bits/move.h b/libstdc++-v3/include/bits/move.h
index 5a4dbdc823c..b33c22a4374 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_FWDREF(_Tp) _Tp&&
#define _GLIBCXX_MOVE(__val) std::move(__val)
#define _GLIBCXX_FORWARD(_Tp, __val) std::forward<_Tp>(__val)
#else
+#define _GLIBCXX_FWDREF(_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..baa4c81a7ed 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_FWDREF(_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_FWDREF(_Arg) __arg) const
          { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }

      private:
@@ -655,11 +647,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        _M_put_node(__p);
      }

-      template<typename _NodeGen>
+      template<bool _Move, typename _NodeGen>
        _Link_type
-       _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
+       _M_clone_node(_Link_type __x, _NodeGen& __node_gen)
        {
-         _Link_type __tmp = __node_gen(*__x->_M_valptr());
+#if __cplusplus >= 201103L
+         using _Vp =
+           typename conditional<_Move, value_type&&, const value_type&>::type;
+#endif
+         _Link_type __tmp
+           = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));


Oh this is nice, I forgot that _GLIBCXX_FORWARD doesn't use the first
argument at all for C++98, so we don't need _Vp.


          __tmp->_M_color = __x->_M_color;
          __tmp->_M_left = 0;
          __tmp->_M_right = 0;
@@ -748,9 +745,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      { return this->_M_impl._M_header._M_right; }

      _Link_type
-      _M_begin() _GLIBCXX_NOEXCEPT
+      _M_mbegin() const _GLIBCXX_NOEXCEPT


Nice.


      { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }

+      _Link_type
+      _M_begin() _GLIBCXX_NOEXCEPT
+      { return _M_mbegin(); }
+
      _Const_Link_type
      _M_begin() const _GLIBCXX_NOEXCEPT
      {
@@ -889,15 +890,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      _M_insert_equal_lower(const value_type& __x);
#endif

-      template<typename _NodeGen>
+      template<bool _Move, typename _NodeGen>
        _Link_type
-       _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
+       _M_copy(_Link_type, _Base_ptr, _NodeGen&);

-      template<typename _NodeGen>
+      template<bool _Move, typename _NodeGen>
        _Link_type
        _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
        {
-         _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
+         _Link_type __root = _M_copy<_Move>(__x._M_mbegin(), _M_end(), __gen);
          _M_leftmost() = _S_minimum(__root);
          _M_rightmost() = _S_maximum(__root);
          _M_impl._M_node_count = __x._M_impl._M_node_count;
@@ -908,7 +909,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      _M_copy(const _Rb_tree& __x)
      {
        _Alloc_node __an(*this);
-       return _M_copy(__x, __an);
+       return _M_copy<false>(__x, __an);
      }

      void
@@ -1655,13 +1656,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      else
        {
          _Alloc_node __an(*this);
-         auto __lbd =
-           [&__an](const value_type& __cval)
-           {
-             auto& __val = const_cast<value_type&>(__cval);
-             return __an(std::move_if_noexcept(__val));
-           };
-         _M_root() = _M_copy(__x, __lbd);
+         _M_root() =
+           _M_copy<__move_if_noexcept_cond<value_type>::value>(__x, __an);


Should this be !__move_if_noexcept_cond<value_type>::value ?

The condition is confusing. Maybe we should replace
__move_if_noexcept_cond with something like:

  // True if copying should be used for strong exception-safety guarantee.
  // False if the type has nothrow move, or isn't copyable.
  template<typename _Tp>
    using __use_copy_for_exception_safety
      = typename __and_<__not_<is_nothrow_move_constructible<_Tp>>,
                        is_copy_constructible<_Tp>>::type;




        }
    }

@@ -1693,13 +1689,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      _M_impl._M_reset();
      if (__x._M_root() != nullptr)
        {
-         auto __lbd =
-           [&__roan](const value_type& __cval)
-           {
-             auto& __val = const_cast<value_type&>(__cval);
-             return __roan(std::move(__val));
-           };
-         _M_root() = _M_copy(__x, __lbd);
+         _M_root() = _M_copy<true>(__x, __roan);


I've realised the downside of my suggestion: _M_copy<true> does a move
and _M_copy<false> does a copy. Maybe we should do:

  enum _CopyType { __as_lvalue, __as_rvalue };

And then _M_copy<__as_rvalue> or _M_copy<__as_lvalue>

We can't use typedefs for true_type and false_type here because the
code needs to be valid in C++98.



          __x.clear();
        }
    }
@@ -1773,7 +1763,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          _M_impl._M_reset();
          _M_impl._M_key_compare = __x._M_impl._M_key_compare;
          if (__x._M_root() != 0)
-           _M_root() = _M_copy(__x, __roan);
+           _M_root() = _M_copy<false>(__x, __roan);
        }

      return *this;
@@ -1859,29 +1849,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

  template<typename _Key, typename _Val, typename _KoV,
           typename _Compare, typename _Alloc>
-    template<typename _NodeGen>
+    template<bool _Move, 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(_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<_Move>(__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<_Move>(_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<_Move>(__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<_Move>(_S_right(__x), __y, 
__node_gen);
                __p = __y;
                __x = _S_left(__x);
              }
























					Reply via email to