From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 18546 invoked by alias); 21 Jul 2017 17:14:10 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 18516 invoked by uid 89); 21 Jul 2017 17:14:09 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.4 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 spammy= X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wr0-f180.google.com Received: from mail-wr0-f180.google.com (HELO mail-wr0-f180.google.com) (209.85.128.180) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 21 Jul 2017 17:14:08 +0000 Received: by mail-wr0-f180.google.com with SMTP id 33so28303090wrz.4; Fri, 21 Jul 2017 10:14:07 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:subject:to:message-id:date:user-agent :mime-version:content-language; bh=2TjKcmcorDwWRg2axgzXXL2381mnxvgREZ30IlL6Mo0=; b=eluE/aWTHzYZoPCeZ+IWucGfR+AMZtOleTpOyTlVB5OEAJZ0jHEsqeeIa+YHO3l8ak v+jhh6khlWmfu/de8BcArxVxMbFcZXEIxL9fuZIp+FO88TYFDzYo6IuZu6xG/ugDbTOO uE5Fj0uc2KDxDnOMsoSk7JnUoI7hUAFi9wznRkZgsbobZIIp9vTvCqRcW3SUDBL8pXtH a0zEAkHej6ZBzly9odv8/muHnpuiNp2CeJyc6Vb9DBr0nx1Ula3FEfXbxOiacpsmtim/ l4kr0uQFkN3JTKgvP1nAa5Knsjz8Tu3ehETIjDXqycM4x54nBUxmMIjcZTxYGTu2RaBN bzJg== X-Gm-Message-State: AIVw110dnGaHch4DRJYjQWFtCPFyd5K8XX9hF3OsYJamb7xQ3QiOLJRu Jht/o2wHt9VSyNkj X-Received: by 10.223.166.109 with SMTP id k100mr10808580wrc.209.1500657245523; Fri, 21 Jul 2017 10:14:05 -0700 (PDT) Received: from [192.168.0.23] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by smtp.googlemail.com with ESMTPSA id a31sm23273031wrc.64.2017.07.21.10.14.03 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 21 Jul 2017 10:14:03 -0700 (PDT) From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: std::list optimizations To: "libstdc++@gcc.gnu.org" , gcc-patches Message-ID: <11158ff8-dcec-d34e-a1e4-288719ff35ca@gmail.com> Date: Fri, 21 Jul 2017 17:14:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.1 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------3C061DA1E7D5D35853C67BAD" X-SW-Source: 2017-07/txt/msg01322.txt.bz2 This is a multi-part message in MIME format. --------------3C061DA1E7D5D35853C67BAD Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 1409 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 --------------3C061DA1E7D5D35853C67BAD Content-Type: text/x-patch; name="list.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="list.patch" Content-length: 5293 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); --------------3C061DA1E7D5D35853C67BAD--