From patchwork Fri Jul 28 16:42:06 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 794980 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-459279-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="xhSSNlco"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3xJvmg4Xmqz9s4q for ; Sat, 29 Jul 2017 02:43:29 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:from:to:references:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=NRLKGWRPgxWxB3VKj tRwzpp1l7mtvam9M91uC4Mu5y/0IkjLdfqxBAxUgLPvDr+u/hqXgAKnM1+KZeB3J xoNjcu8qTYEpz4dGKqqk+RtD2z9SwpMipKxhubMQ/MAVsDiDQxx9k+pOznfFCMCx 0OlpLLTlcKkjfZQu1aEDZDfWs4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:from:to:references:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=UJa9CYZv7hqPEeLIg8GQz4z Z4Rc=; b=xhSSNlcoFAUzx1dRhDbzyU3IT2mFyxfWh9fjJR8GT5W8/A8Ug7fe3FT n+w+T/SJgrD0EaCJs8xADVf/uj+TDYlvmybE9Z1tEyVtH6MylYBQ7/WMozPbrp7O wfblGiIH0umYdaM7YzSf6QSR9LSx3bU13nYXgl7azJn8MPypZeDs= Received: (qmail 6702 invoked by alias); 28 Jul 2017 16:43:16 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 6679 invoked by uid 89); 28 Jul 2017 16:43:15 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=franois, Franois, _tp, HX-Received:10.28.197.135 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wm0-f43.google.com Received: from mail-wm0-f43.google.com (HELO mail-wm0-f43.google.com) (74.125.82.43) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 28 Jul 2017 16:43:13 +0000 Received: by mail-wm0-f43.google.com with SMTP id t201so130499276wmt.1; Fri, 28 Jul 2017 09:43:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:references:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=9QOdhqzR/I7TsckkVkadK2fG3s455L9oERDhGNlqW4Y=; b=EIZKCMIH7qX+wSjbdCrkoeYRYzso6ztuItCoxePa3Xv1EiqJSVW03+AlKM1frFhn+s I6a1EIG2Y9x45JbtGLcMCMW+xI/AqEpbj16P4kSQimsJvneqTkL3SKlygmcDT9uWiyC1 RcHYonq5ETRRwRTdTQKp6zH+pl0XY1P/lcFsl5CentuVekMQd1MxGBzAvu0zNygWoi7r Lk0N6zJ/FX84b/n0aVLUzrHDl19agJ3XTg3Pa0x/R3bqzQI3QxrUZAAyZymxVnfntcTF yDYllciV7tG7IAmKnYt4mw9Ed1rBXDIsbotqx+FCE01xp5gBPXjLXrZ58pSWDgd9ddjC YbDw== X-Gm-Message-State: AIVw111aajizmQoLOBo8DAwYqnxgJbmvKupQnQmYzIY8D+9nz0gS7KAI TSKGB2mpuIaD4SmD X-Received: by 10.28.197.135 with SMTP id v129mr6603006wmf.79.1501260190711; Fri, 28 Jul 2017 09:43:10 -0700 (PDT) Received: from [10.31.9.59] ([137.74.104.57]) by smtp.googlemail.com with ESMTPSA id 23sm4032858wrz.8.2017.07.28.09.42.33 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Jul 2017 09:43:09 -0700 (PDT) Subject: Re: std::list optimizations From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: "libstdc++@gcc.gnu.org" , gcc-patches References: <11158ff8-dcec-d34e-a1e4-288719ff35ca@gmail.com> Message-ID: <6b5b0901-6673-54d4-0e86-cdbc7f84ac67@gmail.com> Date: Fri, 28 Jul 2017 18:42:06 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 In-Reply-To: <11158ff8-dcec-d34e-a1e4-288719ff35ca@gmail.com> 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; - } - 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);