From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 35040 invoked by alias); 19 Oct 2017 05:39:55 -0000 Mailing-List: contact libstdc++-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libstdc++-owner@gcc.gnu.org Received: (qmail 35011 invoked by uid 89); 19 Oct 2017 05:39:54 -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=16457 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wm0-f42.google.com Received: from mail-wm0-f42.google.com (HELO mail-wm0-f42.google.com) (74.125.82.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 19 Oct 2017 05:39:51 +0000 Received: by mail-wm0-f42.google.com with SMTP id f4so13911035wme.0; Wed, 18 Oct 2017 22:39:51 -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:cc:references:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=ZvbrMcP+Ud+jDhkSa2XG7nhHUXuVb/cGDjhxtQYFak4=; b=ItMDxFmAM6XRgZ6ulLmMjl9Oa27/y0tDP1jLaa7Vsub3/vpMM1wSYJDQqWlkgJvboH y0PRW9Xef/FevlPH9ePxSe9fPfOzrVthEQztS7HcsQCeEQTUtwjh19RPEOZdN7UQH22b XHg83EtC2/bjyztGD7I2KIfM0HRXDl/XnET5XOTLX9Vc6aKRQ7ufOMrJeCMy4WEIFLSv d3SjPtOaNP7xT+dcEHdZFimcHniRbhQw2IrlT7p1PKftMV4vpPJiMjBMysTQldJZdbys DgWkQNrCJ7hZLUSMsJIdmc0D1bkB5LM4TRvHDpaHPFQFKfVFwrN6iO9Tq7RcIjruPice q48A== X-Gm-Message-State: AMCzsaWp7P/G1dwS47B30bqWdrCctP7tzx2bw9H9OxK770A0tHsUfzLg +GbX0iLst/V7qf6Od6I3rGeOHQ== X-Google-Smtp-Source: ABhQp+QaE3dn6y4Y3WoC6IeanNTyx90MmTxbduh2nZknd7TlKbPHv4ese6bmx3Of2nc/ykPGafKX+Q== X-Received: by 10.80.195.74 with SMTP id q10mr984329edb.144.1508391589200; Wed, 18 Oct 2017 22:39:49 -0700 (PDT) Received: from [10.24.8.66] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id d49sm9703567edb.79.2017.10.18.22.39.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 18 Oct 2017 22:39:48 -0700 (PDT) Subject: Re: Rb_tree constructor optimization From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: Jonathan Wakely Cc: "libstdc++@gcc.gnu.org" , gcc-patches References: <4026eacd-cb49-e756-c855-627cd5a40206@gmail.com> <20170908155011.GE4582@redhat.com> <5f54e6fb-0394-d13b-0e62-617cf0a2dbed@gmail.com> Message-ID: <501d0d42-07b2-d8ce-01a0-0dc29ddc3fed@gmail.com> Date: Thu, 19 Oct 2017 05:39:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 In-Reply-To: <5f54e6fb-0394-d13b-0e62-617cf0a2dbed@gmail.com> Content-Type: multipart/mixed; boundary="------------84444AA808AA295D98197CA1" X-IsSubscribed: yes X-SW-Source: 2017-10/txt/msg00053.txt.bz2 This is a multi-part message in MIME format. --------------84444AA808AA295D98197CA1 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 1434 Hi     Any feedback regarding this patch ? Thanks, François On 14/09/2017 22:04, François Dumont wrote: > I realized there was no test on the noexcept qualification of the move > constructor with allocator. > > I added some and found out that patch was missing a noexcept > qualification at _Rb_tree level. > > Here is the updated patch fully tested, ok to commit ? > > François > > > On 13/09/2017 21:57, François Dumont wrote: >> On 08/09/2017 17:50, Jonathan Wakely wrote: >>> >>> Since we know __a == __x.get_allocator() we could just do: >>> >>>      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type) >>> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value) >>>      : _M_impl(std::move(__x._M_impl)) >>>      { } >>> >>> This means we don't need the new constructor. >> >>     You want to consider that a always equal allocator is stateless >> and so that the provided allocator rvalue reference do not need to be >> moved. IMHO you can have allocator with state that do not participate >> in comparison like some monitoring info. >> >>     I'm not confortable with that and prefer to keep current behavior >> so I propose this new patch considering all your other remarks. >> >>     I change noexcept qualification on [multi]map/set constructors to >> just rely on _Rep_type constructor noexcept qualification to not >> duplicate it. >> >> François >> >> > > > --------------84444AA808AA295D98197CA1 Content-Type: text/x-patch; name="rb_tree.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="rb_tree.patch" Content-length: 11520 diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index bad6020..e343f04 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -235,8 +235,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Allocator-extended move constructor. map(map&& __m, const allocator_type& __a) - noexcept(is_nothrow_copy_constructible<_Compare>::value - && _Alloc_traits::_S_always_equal()) + noexcept( noexcept( + _Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) ) : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { } /// Allocator-extended initialier-list constructor. diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index 6f5cb7a..8c7ae2c 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -232,8 +232,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Allocator-extended move constructor. multimap(multimap&& __m, const allocator_type& __a) - noexcept(is_nothrow_copy_constructible<_Compare>::value - && _Alloc_traits::_S_always_equal()) + noexcept( noexcept( + _Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) ) : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { } /// Allocator-extended initialier-list constructor. diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index 517e77e..9ab4ab7 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -244,8 +244,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Allocator-extended move constructor. multiset(multiset&& __m, const allocator_type& __a) - noexcept(is_nothrow_copy_constructible<_Compare>::value - && _Alloc_traits::_S_always_equal()) + noexcept( noexcept( + _Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) ) : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { } /// Allocator-extended initialier-list constructor. diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index e804a7c..6b64bcd 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -248,8 +248,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Allocator-extended move constructor. set(set&& __x, const allocator_type& __a) - noexcept(is_nothrow_copy_constructible<_Compare>::value - && _Alloc_traits::_S_always_equal()) + noexcept( noexcept( + _Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) ) : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { } /// Allocator-extended initialier-list constructor. diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index c2417f1..ebfc3f9 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #else _Rb_tree_impl(_Rb_tree_impl&&) = default; + _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) + : _Node_allocator(std::move(__a)), + _Base_key_compare(std::move(__x)), + _Rb_tree_header(std::move(__x)) + { } + _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) : _Node_allocator(std::move(__a)), _Base_key_compare(__comp) { } @@ -944,10 +950,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree(_Rb_tree&&) = default; _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) + noexcept( noexcept( + _Rb_tree(declval<_Rb_tree>(), declval<_Node_allocator>())) ) : _Rb_tree(std::move(__x), _Node_allocator(__a)) { } - _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); + private: + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type) + noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value) + : _M_impl(std::move(__x._M_impl), std::move(__a)) + { } + + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type) + : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) + { + if (__x._M_root() != nullptr) + _M_move_data(__x, false_type{}); + } + + public: + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) + noexcept( noexcept( + _Rb_tree(declval<_Rb_tree>(), declval<_Node_allocator>(), + declval()) ) ) + : _Rb_tree(std::move(__x), std::move(__a), + typename _Alloc_traits::is_always_equal{}) + { } #endif ~_Rb_tree() _GLIBCXX_NOEXCEPT @@ -1347,22 +1375,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Move elements from container with equal allocator. void - _M_move_data(_Rb_tree& __x, std::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&, std::false_type); + _M_move_data(_Rb_tree&, false_type); // Move assignment from container with equal allocator. void - _M_move_assign(_Rb_tree&, std::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&, std::false_type); + _M_move_assign(_Rb_tree&, false_type); #endif #if __cplusplus > 201402L @@ -1590,23 +1618,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus >= 201103L template - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) - : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) - { - using __eq = typename _Alloc_traits::is_always_equal; - if (__x._M_root() != nullptr) - _M_move_data(__x, __eq()); - } - - template void _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_move_data(_Rb_tree& __x, std::false_type) + _M_move_data(_Rb_tree& __x, false_type) { if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) - _M_move_data(__x, std::true_type()); + _M_move_data(__x, true_type()); else { _Alloc_node __an(*this); @@ -1628,7 +1645,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { clear(); if (__x._M_root() != nullptr) - _M_move_data(__x, std::true_type()); + _M_move_data(__x, true_type()); std::__alloc_on_move(_M_get_Node_allocator(), __x._M_get_Node_allocator()); } diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc index b172df7..97c1a47 100644 --- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc +++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc @@ -23,4 +23,25 @@ typedef std::map mtype; -static_assert(std::is_nothrow_move_constructible::value, "Error"); +static_assert( std::is_nothrow_move_constructible::value, + "noexcept move constructor" ); +static_assert( noexcept( mtype(std::declval(), + std::declval()) ), + "noexcept move constructor with allocator" ); + +struct ExceptLess +{ + ExceptLess() = default; + ExceptLess(const ExceptLess&) /* noexcept */ + { } + + bool + operator()(int l, int r) const + { return l < r; } +}; + +typedef std::map emtype; + +static_assert( !noexcept( emtype(std::declval(), + std::declval()) ), + "except move constructor with allocator" ); diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc index 03ef459..9acfbb5 100644 --- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc +++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc @@ -23,4 +23,25 @@ typedef std::multimap mmtype; -static_assert(std::is_nothrow_move_constructible::value, "Error"); +static_assert( std::is_nothrow_move_constructible::value, + "noexcept move constructor" ); +static_assert( noexcept( mmtype(std::declval(), + std::declval()) ), + "noexcept move constructor with allocator" ); + +struct ExceptLess +{ + ExceptLess() = default; + ExceptLess(const ExceptLess&) /* noexcept */ + { } + + bool + operator()(int l, int r) const + { return l < r; } +}; + +typedef std::multimap emmtype; + +static_assert( !noexcept( emmtype(std::declval(), + std::declval()) ), + "except move constructor with allocator" ); diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc index 49878e0..adc7a72 100644 --- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc +++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc @@ -23,4 +23,25 @@ typedef std::multiset mstype; -static_assert(std::is_nothrow_move_constructible::value, "Error"); +static_assert( std::is_nothrow_move_constructible::value, + "noexcept move constructor" ); +static_assert( noexcept( mstype(std::declval(), + std::declval()) ), + "noexcept move constructor with allocator" ); + +struct ExceptLess +{ + ExceptLess() = default; + ExceptLess(const ExceptLess&) /* noexcept */ + { } + + bool + operator()(int l, int r) const + { return l < r; } +}; + +typedef std::multiset emstype; + +static_assert( !noexcept( emstype(std::declval(), + std::declval()) ), + "except move constructor with allocator" ); diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc index 95b5100..0e1f2fa 100644 --- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc +++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc @@ -23,4 +23,25 @@ typedef std::set stype; -static_assert(std::is_nothrow_move_constructible::value, "Error"); +static_assert( std::is_nothrow_move_constructible::value, + "noexcept move constructor" ); +static_assert( noexcept( stype(std::declval(), + std::declval()) ), + "noexcept move constructor with allocator" ); + +struct ExceptLess +{ + ExceptLess() = default; + ExceptLess(const ExceptLess&) /* noexcept */ + { } + + bool + operator()(int l, int r) const + { return l < r; } +}; + +typedef std::set estype; + +static_assert( !noexcept( estype(std::declval(), + std::declval()) ), + "except move constructor with allocator" ); --------------84444AA808AA295D98197CA1--