From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 86964 invoked by alias); 10 Jan 2020 17:54:39 -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 86947 invoked by uid 89); 10 Jan 2020 17:54:39 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.9 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,SPF_PASS autolearn=ham version=3.3.1 spammy=We've, Weve X-HELO: mail-wr1-f46.google.com Received: from mail-wr1-f46.google.com (HELO mail-wr1-f46.google.com) (209.85.221.46) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 10 Jan 2020 17:54:37 +0000 Received: by mail-wr1-f46.google.com with SMTP id c14so2644622wrn.7; Fri, 10 Jan 2020 09:54:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=zzENFkYe53C/0wc8fYjhJmLo88xu67toFzCeCVCoq7k=; b=tvCHRl3kPxyUhhXfwgaOXnWgsKJvoL+IRBb+CZK127JoeoQzds7QPBV8pe4kGxJWHb LurZ3eIb/G+4hUIfvvKy6yd9LSCJgSHTtv27/b9t6V1+ZpqonNmmN2MYS6wgZJUiQz7n R+iMcxHhiIwtz2/FuCl1w8oK5EPRTt3v5cmzZP3j5gizzc1u2sM1p4ZCYMSjb41QL+47 ib6wEHsyztC8O0pVwl0cTkBlicUQM7+BVfxqaS0VBL6W5a+HCBJZb7rBDt2tkaqN2tyr 9v+6ABL0ZhMIZuJtZs6oi60EpW10x99O7Ot+1iXsFlX9ipfmAAPAPTag3mpOKntFjwI/ F7Bw== Return-Path: Received: from [10.1.5.220] ([109.190.253.14]) by smtp.googlemail.com with ESMTPSA id d10sm3090305wrw.64.2020.01.10.09.54.32 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 10 Jan 2020 09:54:33 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: [PATCH] libstdc++/91223 Improve unordered containers == operator Message-ID: <25edbd87-809b-9c75-48a0-294852ea40f2@gmail.com> Date: Fri, 10 Jan 2020 17:58:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.2 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------F38BD00DA8B37C5BB08AC892" X-SW-Source: 2020-01/txt/msg00622.txt.bz2 This is a multi-part message in MIME format. --------------F38BD00DA8B37C5BB08AC892 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 1925 Hi     Here is my attempt to improve == operator.     There is a small optimization for the std::unordered_mutiXXX containers but the main enhancement rely on some partial template specialization of the _Equality type. I limit it to usage of unordered containers with std::equal_to to be sure that the container _Equal functor is like the key type ==.     Do I need to also consider user partial template specialization of std::equal_to ? It is a well know bad practice so I hope the Standard says that such a partial specialization leads to undefined behavior.     I saw that the _S_is_permutation has been done in 2012, before std::is_permutation has been added in 2013. I'll try to replace it in a future patch.     PR libstdc++/91223     * include/bits/hashtable_policy.h     (_Equality<_Key, std::pair, _Alloc,     __detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,     _RehashPolicy, _Traits, true>): New partial template spetialization.     (_Equality<_Value, _Value, _Alloc, __detail::_Identity,     std::equal_to<_Value>, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>):     Likewise.     (_Equality<_Key, std::pair, _Alloc,     __detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,     _RehashPolicy, _Traits, false>): Likewise.     (_Equality<_Key, std::pair, _Alloc,     __detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash)     (_RehashPolicy, _Traits, false>): Likewise.     * src/c++11/hashtable_c++0x.cc: Include .     * testsuite/23_containers/unordered_multiset/operators/1.cc     (Hash, Equal, test02, test03): New.     * testsuite/23_containers/unordered_set/operators/1.cc     (Hash, Equal, test02, test03): New. unordered tests run under Linux x86_64. Ok to commit after running all tests ? François --------------F38BD00DA8B37C5BB08AC892 Content-Type: text/x-patch; charset=UTF-8; name="pr91263.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="pr91263.patch" Content-length: 12891 diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 7bbfdfd375b..2ac3e959320 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1959,11 +1959,18 @@ namespace __detail for (auto __itx = __this->begin(); __itx != __this->end();) { - const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); + std::size_t __x_count = 1; + auto __itx_end = __itx; + for (++__itx_end; __itx_end != __this->end() + && __this->key_eq()(_ExtractKey()(*__itx_end), + _ExtractKey()(*__itx)); + ++__itx_end) + ++__x_count; + + const auto __xrange = std::make_pair(__itx, __itx_end); const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); - if (std::distance(__xrange.first, __xrange.second) - != std::distance(__yrange.first, __yrange.second)) + if (__x_count != std::distance(__yrange.first, __yrange.second)) return false; if (!_S_is_permutation(__xrange.first, __xrange.second, @@ -1975,6 +1982,242 @@ namespace __detail return true; } + /// Specialization. + template + struct _Equality<_Key, std::pair, _Alloc, + __detail::_Select1st, std::equal_to<_Key>, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + { + using __hashtable = _Hashtable<_Key, std::pair, _Alloc, + __detail::_Select1st, std::equal_to<_Key>, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + bool + _M_equal(const __hashtable&) const; + }; + + template + bool + _Equality<_Key, std::pair, _Alloc, __detail::_Select1st, + std::equal_to<_Key>, _H1, _H2, + _Hash, _RehashPolicy, _Traits, true>:: + _M_equal(const __hashtable& __other) const + { + const __hashtable* __this = static_cast(this); + + if (__this->size() != __other.size()) + return false; + + for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) + { + const auto __ity = __other.find(__itx->first); + if (__ity == __other.end() || !bool(__ity->second == __itx->second)) + return false; + } + return true; + } + + /// Specialization. + template + struct _Equality<_Value, _Value, _Alloc, __detail::_Identity, + std::equal_to<_Value>, _H1, _H2, + _Hash, _RehashPolicy, _Traits, true> + { + using __hashtable = _Hashtable<_Value, _Value, _Alloc, + __detail::_Identity, std::equal_to<_Value>, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + bool + _M_equal(const __hashtable&) const; + }; + + template + bool + _Equality<_Value, _Value, _Alloc, __detail::_Identity, + std::equal_to<_Value>, _H1, _H2, + _Hash, _RehashPolicy, _Traits, true>:: + _M_equal(const __hashtable& __other) const + { + const __hashtable* __this = static_cast(this); + + if (__this->size() != __other.size()) + return false; + + for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) + if (__other.find(*__itx) == __other.end()) + return false; + + return true; + } + + /// Specialization. + template + struct _Equality<_Key, std::pair, _Alloc, + __detail::_Select1st, std::equal_to<_Key>, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false> + { + using __hashtable = _Hashtable<_Key, std::pair, _Alloc, + __detail::_Select1st, std::equal_to<_Key>, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + bool + _M_equal(const __hashtable&) const; + + private: + using __hash_cached = typename _Traits::__hash_cached; + using __constant_iterators = typename _Traits::__constant_iterators; + using const_iterator = + __detail::_Node_const_iterator, + __constant_iterators::value, + __hash_cached::value>; + + static bool + _S_is_permutation(const_iterator, const_iterator, const_iterator); + }; + + template + bool + _Equality<_Key, std::pair, _Alloc, + __detail::_Select1st, std::equal_to<_Key>, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: + _S_is_permutation(const_iterator __first1, const_iterator __last1, + const_iterator __first2) + { + for (; __first1 != __last1; ++__first1, ++__first2) + if (!(__first1->second == __first2->second)) + break; + + if (__first1 == __last1) + return true; + + const_iterator __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + + for (const_iterator __it1 = __first1; __it1 != __last1; ++__it1) + { + const_iterator __tmp = __first1; + while (__tmp != __it1 && !bool(__tmp->second == __it1->second)) + ++__tmp; + + // We've seen this one before. + if (__tmp != __it1) + continue; + + std::ptrdiff_t __n2 = 0; + for (__tmp = __first2; __tmp != __last2; ++__tmp) + if (__tmp->second == __it1->second) + ++__n2; + + if (!__n2) + return false; + + std::ptrdiff_t __n1 = 0; + for (__tmp = __it1; __tmp != __last1; ++__tmp) + if (__tmp->second == __it1->second) + ++__n1; + + if (__n1 != __n2) + return false; + } + return true; + } + + template + bool + _Equality<_Key, std::pair, _Alloc, + __detail::_Select1st, std::equal_to<_Key>, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: + _M_equal(const __hashtable& __other) const + { + const __hashtable* __this = static_cast(this); + + if (__this->size() != __other.size()) + return false; + + for (auto __itx = __this->begin(); __itx != __this->end();) + { + std::size_t __x_count = 1; + auto __itx_end = __itx; + for (++__itx_end; __itx_end != __this->end() + && __this->key_eq()(__itx_end->first, __itx->first); + ++__itx_end) + ++__x_count; + + const auto __xrange = make_pair(__itx, __itx_end); + const auto __yrange = __other.equal_range(__itx->first); + + if (__x_count != std::distance(__yrange.first, __yrange.second)) + return false; + + if (!_S_is_permutation(__xrange.first, __xrange.second, + __yrange.first)) + return false; + + __itx = __xrange.second; + } + return true; + } + + /// Specialization. + template + struct _Equality<_Value, _Value, _Alloc, __detail::_Identity, + std::equal_to<_Value>, _H1, _H2, + _Hash, _RehashPolicy, _Traits, false> + { + using __hashtable = _Hashtable<_Value, _Value, _Alloc, + __detail::_Identity, std::equal_to<_Value>, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + bool + _M_equal(const __hashtable&) const; + }; + + template + bool + _Equality<_Value, _Value, _Alloc, __detail::_Identity, + std::equal_to<_Value>, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: + _M_equal(const __hashtable& __other) const + { + const __hashtable* __this = static_cast(this); + + if (__this->size() != __other.size()) + return false; + + for (auto __itx = __this->begin(); __itx != __this->end();) + { + std::size_t __x_count = 1; + auto __itx_end = __itx; + for (++__itx_end; __itx_end != __this->end() + && __this->key_eq()(*__itx_end, *__itx); ++__itx_end) + ++__x_count; + + if (__x_count != __other.count(*__itx)) + return false; + + __itx = __itx_end; + } + return true; + } + /** * This type deals with all allocation and keeps an allocator instance * through inheritance to benefit from EBO when possible. diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index de8e2c7cb91..2054791e13a 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -30,6 +30,7 @@ #include #include #include +#include // equal_to, _Identity, _Select1st #include namespace std _GLIBCXX_VISIBILITY(default) diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc index 4b87f62b74a..7252cad29c2 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc @@ -99,8 +99,64 @@ void test01() VERIFY( !(ums1 != cums2) ); } +void test02() +{ + std::unordered_multiset us1 + { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 }; + std::unordered_multiset us2 + { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + + VERIFY( us1 == us2 ); +} + +struct Hash +{ + std::size_t + operator()(const std::pair& p) const + { return p.first; } +}; + +struct Equal +{ + bool + operator()(const std::pair& lhs, const std::pair& rhs) const + { return lhs.first == rhs.first; } +}; + +void test03() +{ + std::unordered_multiset, Hash, Equal> us1 + { + { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, + { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 }, + { 5, 0 }, { 6, 0 }, { 7, 0 }, { 8, 0 }, { 9, 0 }, + { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 }, { 9, 1 } + }; + std::unordered_multiset, Hash, Equal> us2 + { + { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 }, { 9, 1 }, + { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 }, + { 5, 0 }, { 6, 0 }, { 7, 0 }, { 8, 0 }, { 9, 0 }, + { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 } + }; + + VERIFY( us1 == us2 ); + + std::unordered_multiset, Hash, Equal> us3 + { + { 5, 1 }, { 6, 1 }, { 7, 1 }, { 8, 1 }, { 9, 1 }, + { 0, 1 }, { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 }, + { 5, 0 }, { 6, 0 }, { 7, 1 }, { 8, 0 }, { 9, 0 }, + { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 } + }; + + VERIFY( us1 != us3 ); +} + int main() { test01(); + test02(); + test03(); return 0; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc index d841246e2c1..36a45dfa099 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc @@ -99,8 +99,56 @@ void test01() VERIFY( !(us1 != cus2) ); } +void test02() +{ + std::unordered_set us1 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + std::unordered_set us2 { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }; + + VERIFY( us1 == us2 ); +} + +struct Hash +{ + std::size_t + operator()(const std::pair& p) const + { return p.first; } +}; + +struct Equal +{ + bool + operator()(const std::pair& lhs, const std::pair& rhs) const + { return lhs.first == rhs.first; } +}; + +void test03() +{ + std::unordered_set, Hash, Equal> us1 + { + { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }, + { 5, 5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 } + }; + std::unordered_set, Hash, Equal> us2 + { + { 5, 5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 }, + { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } + }; + + VERIFY( us1 == us2 ); + + std::unordered_set, Hash, Equal> us3 + { + { 5, -5 }, { 6, 6 }, { 7, 7 }, { 8, 8 }, { 9, 9 }, + { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } + }; + + VERIFY( us1 != us3 ); +} + int main() { test01(); + test02(); + test03(); return 0; } --------------F38BD00DA8B37C5BB08AC892--