* std::list optimizations @ 2017-07-21 17:14 François Dumont 2017-07-28 16:43 ` François Dumont 0 siblings, 1 reply; 5+ messages in thread From: François Dumont @ 2017-07-21 17:14 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1411 bytes --] Hi Here is a proposal for 2 optimizations in the std::list implementation. Optimization on the move constructor taking an allocator for always equal allocators. Compare to the version in my previous std::list patch I am now doing it at std::list level rather than at _List_base level. This way we won't instantiate the insert call and we won't check for empty list when the allocator always compare equal. 2nd optimization, I replace the _S_distance method by the std::distance algo which benefit from the nice [begin(), end()) range optimization when cxx11 abi is being used. Note that I am proposing the 2 change in 1 patch to save some review time but I can commit those separately. Tested under x86_64 Linux normal mode. * include/bits/stl_list.h (_List_base<>::_S_distance): Remove. (_List_impl(_List_impl&&, _Node_alloc_type&&)): New. (_List_base(_List_base&&, _Node_alloc_type&&)): Use latter. (_List_base(_Node_alloc_type&&)): New. (_List_base<>::_M_distance, _List_base<>::_M_node_count): Move... (list<>::_M_distance, list<>::_M_node_count): ...here. Replace calls to _S_distance with calls to std::distance. (list(list&&, const allocator_type&, true_type)): New. (list(list&&, const allocator_type&, false_type)): New. (list(list&&, const allocator_type&)): Adapt to call latters. Ok to commit ? François [-- Attachment #2: list.patch --] [-- Type: text/x-patch, Size: 5293 bytes --] diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index cef94f7..aaff500 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -364,19 +364,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 rebind<_List_node<_Tp> >::other _Node_alloc_type; typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; - static size_t - _S_distance(const __detail::_List_node_base* __first, - const __detail::_List_node_base* __last) - { - size_t __n = 0; - while (__first != __last) - { - __first = __first->_M_next; - ++__n; - } - return __n; - } - struct _List_impl : public _Node_alloc_type { @@ -393,6 +380,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 #if __cplusplus >= 201103L _List_impl(_List_impl&&) = default; + _List_impl(_List_impl&& __x, _Node_alloc_type&& __a) + : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node)) + { } + _List_impl(_Node_alloc_type&& __a) noexcept : _Node_alloc_type(std::move(__a)) { } @@ -409,28 +400,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; } void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; } - - size_t - _M_distance(const __detail::_List_node_base* __first, - const __detail::_List_node_base* __last) const - { return _S_distance(__first, __last); } - - // return the stored size - size_t _M_node_count() const { return _M_get_size(); } #else // dummy implementations used when the size is not stored size_t _M_get_size() const { return 0; } void _M_set_size(size_t) { } void _M_inc_size(size_t) { } void _M_dec_size(size_t) { } - size_t _M_distance(const void*, const void*) const { return 0; } - - // count the number of nodes - size_t _M_node_count() const - { - return _S_distance(_M_impl._M_node._M_next, - std::__addressof(_M_impl._M_node)); - } #endif typename _Node_alloc_traits::pointer @@ -466,12 +441,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _List_base(_List_base&&) = default; _List_base(_List_base&& __x, _Node_alloc_type&& __a) + : _M_impl(std::move(__x), std::move(__a)) + { } + + _List_base(_Node_alloc_type&& __a) : _M_impl(std::move(__a)) - { - if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) - _M_move_nodes(std::move(__x)); - // else caller must move individual elements. - } + { } void _M_move_nodes(_List_base&& __x) @@ -616,6 +591,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 } #endif +#if _GLIBCXX_USE_CXX11_ABI + size_t + _M_distance(const_iterator __first, const_iterator __last) const + { return std::distance(__first, __last); } + + // return the stored size + size_t + _M_node_count() const + { return this->_M_get_size(); } +#else + // dummy implementations used when the size is not stored + size_t _M_distance(const_iterator, const_iterator) const { return 0; } + + // count the number of nodes + size_t + _M_node_count() const + { return std::distance(begin(), end()); } +#endif + public: // [23.2.2.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) @@ -718,15 +712,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 : _Base(_Node_alloc_type(__a)) { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } - list(list&& __x, const allocator_type& __a) - noexcept(_Node_alloc_traits::_S_always_equal()) + private: + list(list&& __x, const allocator_type& __a, true_type) noexcept : _Base(std::move(__x), _Node_alloc_type(__a)) + { } + + list(list&& __x, const allocator_type& __a, false_type) + : _Base(_Node_alloc_type(__a)) { - // If __x is not empty it means its allocator is not equal to __a, - // so we need to move from each element individually. - insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), - std::__make_move_if_noexcept_iterator(__x.end())); + if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) + this->_M_move_nodes(std::move(__x)); + else + insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), + std::__make_move_if_noexcept_iterator(__x.end())); } + + public: + list(list&& __x, const allocator_type& __a) + noexcept(_Node_alloc_traits::_S_always_equal()) + : list(std::move(__x), __a, + typename _Node_alloc_traits::is_always_equal{}) + { } #endif /** @@ -1000,7 +1006,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 /** Returns the number of elements in the %list. */ size_type size() const _GLIBCXX_NOEXCEPT - { return this->_M_node_count(); } + { return _M_node_count(); } /** Returns the size() of the largest possible %list. */ size_type @@ -1578,7 +1584,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 if (this != std::__addressof(__x)) _M_check_equal_allocators(__x); - size_t __n = this->_M_distance(__first._M_node, __last._M_node); + size_t __n = _M_distance(__first, __last); this->_M_inc_size(__n); __x._M_dec_size(__n); ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: std::list optimizations 2017-07-21 17:14 std::list optimizations François Dumont @ 2017-07-28 16:43 ` François Dumont 2017-08-18 21:17 ` Jonathan Wakely 0 siblings, 1 reply; 5+ messages in thread From: François Dumont @ 2017-07-28 16:43 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1636 bytes --] Hi Completing execution of the testsuite revealed a bug. So here is the correct version of this patch. François On 21/07/2017 19:14, François Dumont wrote: > Hi > > Here is a proposal for 2 optimizations in the std::list > implementation. > > Optimization on the move constructor taking an allocator for > always equal allocators. Compare to the version in my previous > std::list patch I am now doing it at std::list level rather than at > _List_base level. This way we won't instantiate the insert call and we > won't check for empty list when the allocator always compare equal. > > 2nd optimization, I replace the _S_distance method by the > std::distance algo which benefit from the nice [begin(), end()) range > optimization when cxx11 abi is being used. > > Note that I am proposing the 2 change in 1 patch to save some > review time but I can commit those separately. > > Tested under x86_64 Linux normal mode. > > > * include/bits/stl_list.h > (_List_base<>::_S_distance): Remove. > (_List_impl(_List_impl&&, _Node_alloc_type&&)): New. > (_List_base(_List_base&&, _Node_alloc_type&&)): Use latter. > (_List_base(_Node_alloc_type&&)): New. > (_List_base<>::_M_distance, _List_base<>::_M_node_count): Move... > (list<>::_M_distance, list<>::_M_node_count): ...here. Replace > calls to > _S_distance with calls to std::distance. > (list(list&&, const allocator_type&, true_type)): New. > (list(list&&, const allocator_type&, false_type)): New. > (list(list&&, const allocator_type&)): Adapt to call latters. > > Ok to commit ? > > François > [-- Attachment #2: list.patch --] [-- Type: text/x-patch, Size: 5300 bytes --] diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index cef94f7..eb71a5e 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -364,19 +364,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 rebind<_List_node<_Tp> >::other _Node_alloc_type; typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; - static size_t - _S_distance(const __detail::_List_node_base* __first, - const __detail::_List_node_base* __last) - { - size_t __n = 0; - while (__first != __last) - { - __first = __first->_M_next; - ++__n; - } - return __n; - } - struct _List_impl : public _Node_alloc_type { @@ -393,6 +380,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 #if __cplusplus >= 201103L _List_impl(_List_impl&&) = default; + _List_impl(_List_impl&& __x, _Node_alloc_type&& __a) + : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node)) + { } + _List_impl(_Node_alloc_type&& __a) noexcept : _Node_alloc_type(std::move(__a)) { } @@ -409,28 +400,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; } void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; } - - size_t - _M_distance(const __detail::_List_node_base* __first, - const __detail::_List_node_base* __last) const - { return _S_distance(__first, __last); } - - // return the stored size - size_t _M_node_count() const { return _M_get_size(); } #else // dummy implementations used when the size is not stored size_t _M_get_size() const { return 0; } void _M_set_size(size_t) { } void _M_inc_size(size_t) { } void _M_dec_size(size_t) { } - size_t _M_distance(const void*, const void*) const { return 0; } - - // count the number of nodes - size_t _M_node_count() const - { - return _S_distance(_M_impl._M_node._M_next, - std::__addressof(_M_impl._M_node)); - } #endif typename _Node_alloc_traits::pointer @@ -466,12 +441,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _List_base(_List_base&&) = default; _List_base(_List_base&& __x, _Node_alloc_type&& __a) + : _M_impl(std::move(__x._M_impl), std::move(__a)) + { } + + _List_base(_Node_alloc_type&& __a) : _M_impl(std::move(__a)) - { - if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) - _M_move_nodes(std::move(__x)); - // else caller must move individual elements. - } + { } void _M_move_nodes(_List_base&& __x) @@ -616,6 +591,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 } #endif +#if _GLIBCXX_USE_CXX11_ABI + size_t + _M_distance(const_iterator __first, const_iterator __last) const + { return std::distance(__first, __last); } + + // return the stored size + size_t + _M_node_count() const + { return this->_M_get_size(); } +#else + // dummy implementations used when the size is not stored + size_t _M_distance(const_iterator, const_iterator) const { return 0; } + + // count the number of nodes + size_t + _M_node_count() const + { return std::distance(begin(), end()); } +#endif + public: // [23.2.2.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) @@ -718,15 +712,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 : _Base(_Node_alloc_type(__a)) { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } - list(list&& __x, const allocator_type& __a) - noexcept(_Node_alloc_traits::_S_always_equal()) + private: + list(list&& __x, const allocator_type& __a, true_type) noexcept : _Base(std::move(__x), _Node_alloc_type(__a)) + { } + + list(list&& __x, const allocator_type& __a, false_type) + : _Base(_Node_alloc_type(__a)) { - // If __x is not empty it means its allocator is not equal to __a, - // so we need to move from each element individually. - insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), - std::__make_move_if_noexcept_iterator(__x.end())); + if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) + this->_M_move_nodes(std::move(__x)); + else + insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), + std::__make_move_if_noexcept_iterator(__x.end())); } + + public: + list(list&& __x, const allocator_type& __a) + noexcept(_Node_alloc_traits::_S_always_equal()) + : list(std::move(__x), __a, + typename _Node_alloc_traits::is_always_equal{}) + { } #endif /** @@ -1000,7 +1006,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 /** Returns the number of elements in the %list. */ size_type size() const _GLIBCXX_NOEXCEPT - { return this->_M_node_count(); } + { return _M_node_count(); } /** Returns the size() of the largest possible %list. */ size_type @@ -1578,7 +1584,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 if (this != std::__addressof(__x)) _M_check_equal_allocators(__x); - size_t __n = this->_M_distance(__first._M_node, __last._M_node); + size_t __n = _M_distance(__first, __last); this->_M_inc_size(__n); __x._M_dec_size(__n); ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: std::list optimizations 2017-07-28 16:43 ` François Dumont @ 2017-08-18 21:17 ` Jonathan Wakely 2017-08-21 23:34 ` François Dumont 0 siblings, 1 reply; 5+ messages in thread From: Jonathan Wakely @ 2017-08-18 21:17 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 28/07/17 18:42 +0200, François Dumont wrote: >Hi > > Completing execution of the testsuite revealed a bug. So here is >the correct version of this patch. > >François > >On 21/07/2017 19:14, François Dumont wrote: >>Hi >> >> Here is a proposal for 2 optimizations in the std::list >>implementation. >> >> Optimization on the move constructor taking an allocator for >>always equal allocators. Compare to the version in my previous >>std::list patch I am now doing it at std::list level rather than at >>_List_base level. This way we won't instantiate the insert call and >>we won't check for empty list when the allocator always compare >>equal. >> >> 2nd optimization, I replace the _S_distance method by the >>std::distance algo which benefit from the nice [begin(), end()) >>range optimization when cxx11 abi is being used. >> >> Note that I am proposing the 2 change in 1 patch to save some >>review time but I can commit those separately. >> >>Tested under x86_64 Linux normal mode. >> >> >> * include/bits/stl_list.h >> (_List_base<>::_S_distance): Remove. >> (_List_impl(_List_impl&&, _Node_alloc_type&&)): New. >> (_List_base(_List_base&&, _Node_alloc_type&&)): Use latter. >> (_List_base(_Node_alloc_type&&)): New. >> (_List_base<>::_M_distance, _List_base<>::_M_node_count): Move... >> (list<>::_M_distance, list<>::_M_node_count): ...here. Replace >>calls to >> _S_distance with calls to std::distance. >> (list(list&&, const allocator_type&, true_type)): New. >> (list(list&&, const allocator_type&, false_type)): New. >> (list(list&&, const allocator_type&)): Adapt to call latters. >> >>Ok to commit ? >> >>François >> > >diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h >index cef94f7..eb71a5e 100644 >--- a/libstdc++-v3/include/bits/stl_list.h >+++ b/libstdc++-v3/include/bits/stl_list.h >@@ -364,19 +364,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > rebind<_List_node<_Tp> >::other _Node_alloc_type; > typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; > >- static size_t >- _S_distance(const __detail::_List_node_base* __first, >- const __detail::_List_node_base* __last) >- { >- size_t __n = 0; >- while (__first != __last) >- { >- __first = __first->_M_next; >- ++__n; >- } >- return __n; >- } >- Removing this function will break code that expects it to exist in an explicit instantiation. The function could be left there, but unused. > struct _List_impl > : public _Node_alloc_type > { >@@ -393,6 +380,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > #if __cplusplus >= 201103L > _List_impl(_List_impl&&) = default; > >+ _List_impl(_List_impl&& __x, _Node_alloc_type&& __a) >+ : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node)) >+ { } >+ This is fine. > _List_impl(_Node_alloc_type&& __a) noexcept > : _Node_alloc_type(std::move(__a)) > { } >@@ -409,28 +400,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; } > > void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; } >- >- size_t >- _M_distance(const __detail::_List_node_base* __first, >- const __detail::_List_node_base* __last) const >- { return _S_distance(__first, __last); } >- >- // return the stored size >- size_t _M_node_count() const { return _M_get_size(); } > #else > // dummy implementations used when the size is not stored > size_t _M_get_size() const { return 0; } > void _M_set_size(size_t) { } > void _M_inc_size(size_t) { } > void _M_dec_size(size_t) { } >- size_t _M_distance(const void*, const void*) const { return 0; } >- >- // count the number of nodes >- size_t _M_node_count() const >- { >- return _S_distance(_M_impl._M_node._M_next, >- std::__addressof(_M_impl._M_node)); >- } > #endif Same problem again: these will no longer be defined by explicit instantiations. > > typename _Node_alloc_traits::pointer >@@ -466,12 +441,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > _List_base(_List_base&&) = default; > > _List_base(_List_base&& __x, _Node_alloc_type&& __a) >+ : _M_impl(std::move(__x._M_impl), std::move(__a)) >+ { } >+ >+ _List_base(_Node_alloc_type&& __a) > : _M_impl(std::move(__a)) >- { >- if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) >- _M_move_nodes(std::move(__x)); >- // else caller must move individual elements. >- } >+ { } > I like this change in principle, but it alters the behaviour of an existing constructor. Existing code might use the constructor and get broken by this. You can avoid that by leaving the existing constructor alone and adding two new ones for new code to use. Reordering the parameters will make the new one distinct from the old one: // Used when is_always_equal _List_base(_Node_alloc_type&& __a, _List_base&& __x)) : _M_impl(std::move(__x._M_impl), std::move(__a)) { } // Used when !is_always_equal _List_base(_Node_alloc_type&& __a) : _M_impl(std::move(__a)) { } Or: // Used when is_always_equal _List_base(_List_base&& __x, _Node_alloc_type&& __a, true_type) : _M_impl(std::move(__x._M_impl), std::move(__a)) { } // Used when !is_always_equal _List_base(_Node_alloc_type&& __a) : _M_impl(std::move(__a)) { } Either of these forms will add new constructors for the new semantics. > void > _M_move_nodes(_List_base&& __x) >@@ -616,6 +591,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > } > #endif > >+#if _GLIBCXX_USE_CXX11_ABI >+ size_t >+ _M_distance(const_iterator __first, const_iterator __last) const >+ { return std::distance(__first, __last); } >+ >+ // return the stored size >+ size_t >+ _M_node_count() const >+ { return this->_M_get_size(); } >+#else >+ // dummy implementations used when the size is not stored >+ size_t _M_distance(const_iterator, const_iterator) const { return 0; } >+ >+ // count the number of nodes >+ size_t >+ _M_node_count() const >+ { return std::distance(begin(), end()); } >+#endif Adding these is fine. New code will use them. Old code relying on explicit instantiations will still find the definitions of the old functions and use them. _M_distance could be static though, neither version uses the 'this' pointer, so it would be called _S_distance. >+ > public: > // [23.2.2.1] construct/copy/destroy > // (assign() and get_allocator() are also listed in this section) >@@ -718,15 +712,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > : _Base(_Node_alloc_type(__a)) > { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } > >- list(list&& __x, const allocator_type& __a) >- noexcept(_Node_alloc_traits::_S_always_equal()) >+ private: >+ list(list&& __x, const allocator_type& __a, true_type) noexcept > : _Base(std::move(__x), _Node_alloc_type(__a)) Either reorder the arguments, or add true_type{} to the end, to call the new constructor suggested above. >+ { } >+ >+ list(list&& __x, const allocator_type& __a, false_type) >+ : _Base(_Node_alloc_type(__a)) > { >- // If __x is not empty it means its allocator is not equal to __a, >- // so we need to move from each element individually. >- insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), >- std::__make_move_if_noexcept_iterator(__x.end())); >+ if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) >+ this->_M_move_nodes(std::move(__x)); >+ else >+ insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), >+ std::__make_move_if_noexcept_iterator(__x.end())); > } >+ >+ public: >+ list(list&& __x, const allocator_type& __a) >+ noexcept(_Node_alloc_traits::_S_always_equal()) >+ : list(std::move(__x), __a, >+ typename _Node_alloc_traits::is_always_equal{}) >+ { } > #endif > > /** >@@ -1000,7 +1006,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > /** Returns the number of elements in the %list. */ > size_type > size() const _GLIBCXX_NOEXCEPT >- { return this->_M_node_count(); } >+ { return _M_node_count(); } > > /** Returns the size() of the largest possible %list. */ > size_type >@@ -1578,7 +1584,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 > if (this != std::__addressof(__x)) > _M_check_equal_allocators(__x); > >- size_t __n = this->_M_distance(__first._M_node, __last._M_node); >+ size_t __n = _M_distance(__first, __last); > this->_M_inc_size(__n); > __x._M_dec_size(__n); > If _M_distance becomes static this would call _S_distance instead. Do those suggestions make sense? The idea is to ensure that a given function signature continues to have the same effects. To introduce new effects, use a new signature. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: std::list optimizations 2017-08-18 21:17 ` Jonathan Wakely @ 2017-08-21 23:34 ` François Dumont 2017-08-22 10:31 ` Jonathan Wakely 0 siblings, 1 reply; 5+ messages in thread From: François Dumont @ 2017-08-21 23:34 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 3637 bytes --] On 18/08/2017 22:04, Jonathan Wakely wrote: > On 28/07/17 18:42 +0200, François Dumont wrote: >> Hi >> >> Completing execution of the testsuite revealed a bug. So here is >> the correct version of this patch. >> >> François >> >> On 21/07/2017 19:14, François Dumont wrote: >>> Hi >>> >>> Here is a proposal for 2 optimizations in the std::list >>> implementation. >>> >>> Optimization on the move constructor taking an allocator for >>> always equal allocators. Compare to the version in my previous >>> std::list patch I am now doing it at std::list level rather than at >>> _List_base level. This way we won't instantiate the insert call and >>> we won't check for empty list when the allocator always compare equal. >>> >>> 2nd optimization, I replace the _S_distance method by the >>> std::distance algo which benefit from the nice [begin(), end()) >>> range optimization when cxx11 abi is being used. >>> >>> Note that I am proposing the 2 change in 1 patch to save some >>> review time but I can commit those separately. >>> >>> Tested under x86_64 Linux normal mode. >>> >>> >>> * include/bits/stl_list.h >>> (_List_base<>::_S_distance): Remove. >>> (_List_impl(_List_impl&&, _Node_alloc_type&&)): New. >>> (_List_base(_List_base&&, _Node_alloc_type&&)): Use latter. >>> (_List_base(_Node_alloc_type&&)): New. >>> (_List_base<>::_M_distance, _List_base<>::_M_node_count): Move... >>> (list<>::_M_distance, list<>::_M_node_count): ...here. Replace >>> calls to >>> _S_distance with calls to std::distance. >>> (list(list&&, const allocator_type&, true_type)): New. >>> (list(list&&, const allocator_type&, false_type)): New. >>> (list(list&&, const allocator_type&)): Adapt to call latters. >>> >>> Ok to commit ? >>> >>> François >>> >> > >> _List_base(_List_base&&) = default; >> >> _List_base(_List_base&& __x, _Node_alloc_type&& __a) >> + : _M_impl(std::move(__x._M_impl), std::move(__a)) >> + { } >> + >> + _List_base(_Node_alloc_type&& __a) >> : _M_impl(std::move(__a)) >> - { >> - if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) >> - _M_move_nodes(std::move(__x)); >> - // else caller must move individual elements. >> - } >> + { } >> > > I like this change in principle, but it alters the behaviour of an > existing constructor. Existing code might use the constructor and get > broken by this. > > You can avoid that by leaving the existing constructor alone and > adding two new ones for new code to use. Reordering the parameters > will make the new one distinct from the old one: > > // Used when is_always_equal > _List_base(_Node_alloc_type&& __a, _List_base&& __x)) > : _M_impl(std::move(__x._M_impl), std::move(__a)) > { } I have chosen this approach and also adapt the _List_impl class to have same signature which moreover correspond to order of members so maybe not so bad. > > _M_distance could be static though, neither version uses the 'this' > pointer, so it would be called _S_distance. Applied. > > Do those suggestions make sense? The idea is to ensure that a given > function signature continues to have the same effects. To introduce > new effects, use a new signature. > Sure, I didn't consider the explicit instantiation use case, makes sens. So here is a new version. I propose to "mark" code kept for backward abi compatibility with the _GLIBCXX_INLINE_VERSION. Next time we decide to break abi we will just need to look for this macro to know what code can be removed. Ok to commit if tests are successful ? François [-- Attachment #2: list.patch --] [-- Type: text/x-patch, Size: 5469 bytes --] diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index cef94f7..e545996 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -364,6 +364,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 rebind<_List_node<_Tp> >::other _Node_alloc_type; typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; +#if !_GLIBCXX_INLINE_VERSION static size_t _S_distance(const __detail::_List_node_base* __first, const __detail::_List_node_base* __last) @@ -376,6 +377,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 } return __n; } +#endif struct _List_impl : public _Node_alloc_type @@ -393,6 +395,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 #if __cplusplus >= 201103L _List_impl(_List_impl&&) = default; + _List_impl(_Node_alloc_type&& __a, _List_impl&& __x) + : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node)) + { } + _List_impl(_Node_alloc_type&& __a) noexcept : _Node_alloc_type(std::move(__a)) { } @@ -410,6 +416,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; } +# if !_GLIBCXX_INLINE_VERSION size_t _M_distance(const __detail::_List_node_base* __first, const __detail::_List_node_base* __last) const @@ -417,12 +424,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 // return the stored size size_t _M_node_count() const { return _M_get_size(); } +# endif #else // dummy implementations used when the size is not stored size_t _M_get_size() const { return 0; } void _M_set_size(size_t) { } void _M_inc_size(size_t) { } void _M_dec_size(size_t) { } + +# if !_GLIBCXX_INLINE_VERSION size_t _M_distance(const void*, const void*) const { return 0; } // count the number of nodes @@ -432,6 +442,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 std::__addressof(_M_impl._M_node)); } # endif +#endif typename _Node_alloc_traits::pointer _M_get_node() @@ -465,6 +476,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 #if __cplusplus >= 201103L _List_base(_List_base&&) = default; +# if !_GLIBCXX_INLINE_VERSION _List_base(_List_base&& __x, _Node_alloc_type&& __a) : _M_impl(std::move(__a)) { @@ -472,6 +484,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 _M_move_nodes(std::move(__x)); // else caller must move individual elements. } +# endif + + // Used when allocator is_always_equal. + _List_base(_Node_alloc_type&& __a, _List_base&& __x) + : _M_impl(std::move(__a), std::move(__x._M_impl)) + { } + + // Used when allocator !is_always_equal. + _List_base(_Node_alloc_type&& __a) + : _M_impl(std::move(__a)) + { } void _M_move_nodes(_List_base&& __x) @@ -616,6 +639,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 } #endif +#if _GLIBCXX_USE_CXX11_ABI + static size_t + _S_distance(const_iterator __first, const_iterator __last) const + { return std::distance(__first, __last); } + + // return the stored size + size_t + _M_node_count() const + { return this->_M_get_size(); } +#else + // dummy implementations used when the size is not stored + static size_t + _S_distance(const_iterator, const_iterator) const + { return 0; } + + // count the number of nodes + size_t + _M_node_count() const + { return std::distance(begin(), end()); } +#endif + public: // [23.2.2.1] construct/copy/destroy // (assign() and get_allocator() are also listed in this section) @@ -718,15 +762,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 : _Base(_Node_alloc_type(__a)) { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } - list(list&& __x, const allocator_type& __a) - noexcept(_Node_alloc_traits::_S_always_equal()) - : _Base(std::move(__x), _Node_alloc_type(__a)) + private: + list(list&& __x, const allocator_type& __a, true_type) noexcept + : _Base(_Node_alloc_type(__a), std::move(__x)) + { } + + list(list&& __x, const allocator_type& __a, false_type) + : _Base(_Node_alloc_type(__a)) { - // If __x is not empty it means its allocator is not equal to __a, - // so we need to move from each element individually. + if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) + this->_M_move_nodes(std::move(__x)); + else insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), std::__make_move_if_noexcept_iterator(__x.end())); } + + public: + list(list&& __x, const allocator_type& __a) + noexcept(_Node_alloc_traits::_S_always_equal()) + : list(std::move(__x), __a, + typename _Node_alloc_traits::is_always_equal{}) + { } #endif /** @@ -1000,7 +1056,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 /** Returns the number of elements in the %list. */ size_type size() const _GLIBCXX_NOEXCEPT - { return this->_M_node_count(); } + { return _M_node_count(); } /** Returns the size() of the largest possible %list. */ size_type @@ -1578,7 +1634,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 if (this != std::__addressof(__x)) _M_check_equal_allocators(__x); - size_t __n = this->_M_distance(__first._M_node, __last._M_node); + size_t __n = _S_distance(__first, __last); this->_M_inc_size(__n); __x._M_dec_size(__n); ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: std::list optimizations 2017-08-21 23:34 ` François Dumont @ 2017-08-22 10:31 ` Jonathan Wakely 0 siblings, 0 replies; 5+ messages in thread From: Jonathan Wakely @ 2017-08-22 10:31 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 21/08/17 21:14 +0200, François Dumont wrote: >On 18/08/2017 22:04, Jonathan Wakely wrote: >>On 28/07/17 18:42 +0200, François Dumont wrote: >>>Hi >>> >>> Completing execution of the testsuite revealed a bug. So here >>>is the correct version of this patch. >>> >>>François >>> >>>On 21/07/2017 19:14, François Dumont wrote: >>>>Hi >>>> >>>> Here is a proposal for 2 optimizations in the std::list >>>>implementation. >>>> >>>> Optimization on the move constructor taking an allocator for >>>>always equal allocators. Compare to the version in my previous >>>>std::list patch I am now doing it at std::list level rather than >>>>at _List_base level. This way we won't instantiate the insert >>>>call and we won't check for empty list when the allocator always >>>>compare equal. >>>> >>>> 2nd optimization, I replace the _S_distance method by the >>>>std::distance algo which benefit from the nice [begin(), end()) >>>>range optimization when cxx11 abi is being used. >>>> >>>> Note that I am proposing the 2 change in 1 patch to save some >>>>review time but I can commit those separately. >>>> >>>>Tested under x86_64 Linux normal mode. >>>> >>>> >>>> * include/bits/stl_list.h >>>> (_List_base<>::_S_distance): Remove. >>>> (_List_impl(_List_impl&&, _Node_alloc_type&&)): New. >>>> (_List_base(_List_base&&, _Node_alloc_type&&)): Use latter. >>>> (_List_base(_Node_alloc_type&&)): New. >>>> (_List_base<>::_M_distance, _List_base<>::_M_node_count): Move... >>>> (list<>::_M_distance, list<>::_M_node_count): ...here. >>>>Replace calls to >>>> _S_distance with calls to std::distance. >>>> (list(list&&, const allocator_type&, true_type)): New. >>>> (list(list&&, const allocator_type&, false_type)): New. >>>> (list(list&&, const allocator_type&)): Adapt to call latters. >>>> >>>>Ok to commit ? >>>> >>>>François >>>> >>> >> >>> _List_base(_List_base&&) = default; >>> >>> _List_base(_List_base&& __x, _Node_alloc_type&& __a) >>>+ : _M_impl(std::move(__x._M_impl), std::move(__a)) >>>+ { } >>>+ >>>+ _List_base(_Node_alloc_type&& __a) >>> : _M_impl(std::move(__a)) >>>- { >>>- if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) >>>- _M_move_nodes(std::move(__x)); >>>- // else caller must move individual elements. >>>- } >>>+ { } >>> >> >>I like this change in principle, but it alters the behaviour of an >>existing constructor. Existing code might use the constructor and get >>broken by this. >> >>You can avoid that by leaving the existing constructor alone and >>adding two new ones for new code to use. Reordering the parameters >>will make the new one distinct from the old one: >> >> // Used when is_always_equal >> _List_base(_Node_alloc_type&& __a, _List_base&& __x)) >> : _M_impl(std::move(__x._M_impl), std::move(__a)) >> { } > >I have chosen this approach and also adapt the _List_impl class to >have same signature which moreover correspond to order of members so >maybe not so bad. > >> >>_M_distance could be static though, neither version uses the 'this' >>pointer, so it would be called _S_distance. > >Applied. > >> >>Do those suggestions make sense? The idea is to ensure that a given >>function signature continues to have the same effects. To introduce >>new effects, use a new signature. >> >Sure, I didn't consider the explicit instantiation use case, makes sens. > >So here is a new version. I propose to "mark" code kept for backward >abi compatibility with the _GLIBCXX_INLINE_VERSION. Next time we >decide to break abi we will just need to look for this macro to know >what code can be removed. Great, thanks. > Ok to commit if tests are successful ? Yes, thanks. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-08-22 9:54 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-07-21 17:14 std::list optimizations François Dumont 2017-07-28 16:43 ` François Dumont 2017-08-18 21:17 ` Jonathan Wakely 2017-08-21 23:34 ` François Dumont 2017-08-22 10:31 ` Jonathan Wakely
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).