From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id BF7B4386F44B for ; Tue, 17 Nov 2020 23:50:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org BF7B4386F44B Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-370-3hdSzIS6Oha2msxyy1vwlw-1; Tue, 17 Nov 2020 18:50:33 -0500 X-MC-Unique: 3hdSzIS6Oha2msxyy1vwlw-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id A1B7A809DED; Tue, 17 Nov 2020 23:50:32 +0000 (UTC) Received: from localhost (unknown [10.33.36.170]) by smtp.corp.redhat.com (Postfix) with ESMTP id 27D915D9CD; Tue, 17 Nov 2020 23:50:32 +0000 (UTC) Date: Tue, 17 Nov 2020 23:50:31 +0000 From: Jonathan Wakely To: =?iso-8859-1?Q?Fran=E7ois?= Dumont Cc: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: [PATCH] Remove lambdas from _Rb_tree Message-ID: <20201117235031.GC503596@redhat.com> References: <7c66cd1c-3f62-5f2c-fb75-2641d672a3d2@gmail.com> MIME-Version: 1.0 In-Reply-To: <7c66cd1c-3f62-5f2c-fb75-2641d672a3d2@gmail.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Disposition: inline Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 17 Nov 2020 23:50:38 -0000 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. >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 > _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 > _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 >+#if __cplusplus >= 201103L >+ template >+ static constexpr >+ typename conditional::value, >+ const value_type&, value_type&&>::type >+ _S_fwd_value_for(value_type& __val) noexcept >+ { return std::move(__val); } >+#else >+ template >+ static const value_type& >+ _S_fwd_value_for(value_type& __val) >+ { return __val; } >+#endif >+ >+ template > _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 _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::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 >+ template > _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 >+ template > _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 _Compare, typename _Alloc> >- template >+ template > 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); > }