From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52c.google.com (mail-ed1-x52c.google.com [IPv6:2a00:1450:4864:20::52c]) by sourceware.org (Postfix) with ESMTPS id 726A23858403; Mon, 15 Nov 2021 06:00:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 726A23858403 Received: by mail-ed1-x52c.google.com with SMTP id e3so30324430edu.4; Sun, 14 Nov 2021 22:00:23 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:subject:to:cc:references:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=bz/kxbz/ohZKW8WRIIE4jiBAEHLV8mb57fp+f/8aCgg=; b=tfwcWRCWDjzndK+OlmRFRA/3SSaZadNqYiL8fPRMfq03Z/Z3kG9Fhx6C052rMssipq 6i/OAW3+CPHUA+PgIRfm6WKlhKkQL4Pi9u1ClZrStrCpPriGZIEuhagbCcMBf4k0Maej a/5cAVDXgMM0SkPgCdbbEf94Bslcm3MN3GE8MAw3Xc9faIzbXRQxxg0SQ24+5sNdznIq a46ahm9W5kGP/UzS8QVb+A6t19a42cwVrKAczVwZsmb3hZP0aVivTPHJ7hrEDLS4wY0o 3F1OcYfB9yVPPoQq8Onkf47zbtyTkjk/W4CSWV6xbFsAPcOuKKp89yEI4IHk00K1CP9R nTLw== X-Gm-Message-State: AOAM532KhySMwEHnOXMEf7C54QvI3hXV4ND6YinIlaW6eo5lEUF4r+UQ 2e8MLIvnhT7K2LZmbnUpPEx8gpmyPmw= X-Google-Smtp-Source: ABdhPJzXCGCQ6H+HltgB66/FogiywUo8e9bHA37PZMlx5lTkVUz86KvEAgHd8PKcwJDfbXLkOtiiqQ== X-Received: by 2002:a05:6402:3492:: with SMTP id v18mr50627562edc.398.1636956022391; Sun, 14 Nov 2021 22:00:22 -0800 (PST) Received: from [10.62.5.153] ([109.190.253.15]) by smtp.googlemail.com with ESMTPSA id di4sm5987098ejc.11.2021.11.14.22.00.20 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 14 Nov 2021 22:00:21 -0800 (PST) From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: Re: [PATCH] Enhance unordered container merge To: Jonathan Wakely Cc: "libstdc++@gcc.gnu.org" , gcc-patches References: Message-ID: <3e66557c-131e-eed0-fc7c-3d1eefd1dcf9@gmail.com> Date: Mon, 15 Nov 2021 07:00:19 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------CF63A73A6446B01C34D4449C" Content-Language: fr X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 15 Nov 2021 06:00:25 -0000 This is a multi-part message in MIME format. --------------CF63A73A6446B01C34D4449C Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit On 15/11/21 12:25 am, Jonathan Wakely wrote: > On Sun, 14 Nov 2021 at 13:31, François Dumont via Libstdc++ > wrote: >> libstdc++: Unordered containers merge re-use hash code. >> >> When merging between 2 unordered containers with same hasher we can >> re-use >> the cached hash code if any. > Instead of introducing the _ReuseOrComputeHash type, wouldn't it be > simpler to just overload _M_hash_code? > > > // Same hash function, use the cached hash code. > __hash_code > _M_hash_code(const _Hash&, > const _Hash_node_value<_Value, true>& __n) const > { return __n._M_hash_code; } > > // Compute hash code using a different hash function, _H2 > template > __hash_code > _M_hash_code(const _H2&, > const _Hash_node_value<_Value, __cache_hash_code>& __n) const > { return this->_M_hash_code(_ExtractKey{}(__n._M_v()); } > > The first overload is more specialized, so will be chosen when the > first argument is the same type as _Hash and the cache_has_code > boolean is true. Yes, it is simpler. Ok to commit ? François --------------CF63A73A6446B01C34D4449C Content-Type: text/x-patch; charset=UTF-8; name="hashtable_merge.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="hashtable_merge.patch" diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 0e949d73614..6e2d4c10cfe 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1076,7 +1076,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { auto __pos = __i++; const key_type& __k = _ExtractKey{}(*__pos); - __hash_code __code = this->_M_hash_code(__k); + __hash_code __code + = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); size_type __bkt = _M_bucket_index(__code); if (_M_find_node(__bkt, __k, __code) == nullptr) { @@ -1099,14 +1100,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + __node_ptr __hint = nullptr; this->reserve(size() + __src.size()); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; - const key_type& __k = _ExtractKey{}(*__pos); - __hash_code __code = this->_M_hash_code(__k); + __hash_code __code + = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); auto __nh = __src.extract(__pos); - _M_insert_multi_node(nullptr, __code, __nh._M_ptr); + __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; __nh._M_ptr = nullptr; } } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index c0295b75963..0b5443fc187 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1250,6 +1250,19 @@ namespace __detail return _M_hash()(__k); } + __hash_code + _M_hash_code(const _Hash&, + const _Hash_node_value<_Value, true>& __n) const + { return __n._M_hash_code; } + + // Compute hash code using _Hash as __n _M_hash_code, if present, was + // computed using _H2. + template + __hash_code + _M_hash_code(const _H2&, + const _Hash_node_value<_Value, __cache_hash_code>& __n) const + { return _M_hash_code(_ExtractKey{}(__n._M_v())); } + std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const { return _RangeHash{}(__c, __bkt_count); } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc index 1ed2ce234a1..07b8a344169 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc @@ -17,6 +17,7 @@ // { dg-do run { target c++17 } } +#include #include #include #include @@ -105,6 +106,26 @@ test04() VERIFY( c2.empty() ); } +void +test05() +{ + const std::unordered_multiset c0{ "abcd", "abcd", "efgh", "efgh", "ijkl", "ijkl" }; + std::unordered_multiset c1 = c0; + std::unordered_set c2( c0.begin(), c0.end() ); + + c1.merge(c2); + VERIFY( c1.size() == (1.5 * c0.size()) ); + for (auto& i : c1) + VERIFY( c1.count(i) == (1.5 * c0.count(i)) ); + VERIFY( c2.empty() ); + + c1.clear(); + c2.insert( c0.begin(), c0.end() ); + c1.merge(std::move(c2)); + VERIFY( c1.size() == (0.5 * c0.size()) ); + VERIFY( c2.empty() ); +} + int main() { @@ -112,4 +133,5 @@ main() test02(); test03(); test04(); + test05(); } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc index c9c8a60fd54..0e184b10c60 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc @@ -17,6 +17,7 @@ // { dg-do run { target c++17 } } +#include #include #include #include @@ -125,10 +126,52 @@ test03() VERIFY( c2.empty() ); } +void +test04() +{ + const std::unordered_set c0{ "abcd", "efgh", "ijkl", }; + std::unordered_set c1 = c0; + std::unordered_multiset c2( c0.begin(), c0.end() ); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( equal_elements(c2, c0) ); + + c1 = c0; + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2.size() == (2 * c0.size()) ); + VERIFY( c2.count("abcd") == 2 ); + VERIFY( c2.count("efgh") == 2 ); + VERIFY( c2.count("ijkl") == 2 ); + + c1.merge(c2); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( equal_elements(c2, c0) ); + + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c0 ); + VERIFY( c2.empty() ); +} + int main() { test01(); test02(); test03(); + test04(); } --------------CF63A73A6446B01C34D4449C--