From patchwork Thu Nov 23 21:58:31 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1867983 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=Xpb8cGIc; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsSx70ZHz1yS0 for ; Fri, 24 Nov 2023 08:58:57 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BE6663857734 for ; Thu, 23 Nov 2023 21:58:51 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by sourceware.org (Postfix) with ESMTPS id 9DE733858C60; Thu, 23 Nov 2023 21:58:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9DE733858C60 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 9DE733858C60 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::32f ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776719; cv=none; b=DgGVXf5tZsaz499diRQkzr9r/1dEvU4pa9l4HJTwVRkntSOxs2Z+VhuZPNUJutuorN53Tc2OCGVQS5kB87aGrigg+pewyLfYgkojGBKgUXBObU5meJxEZSiexe+gnwl+W0yZ7c62YIdWGLB1LJZcA5ltGFUwAefL2LotkXFiavk= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776719; c=relaxed/simple; bh=jAM5uJ8LSMkS52ssC/PAMUPma36VykYajWAl9jkMTCQ=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=L4TUBnmHQhH4XxB4GbfZ+pGxHKqRNHIQOvQV5EeZrBPNmfZJdXr69wMzadwJ3J0StXDnY0qI5xzAdi69h5d/Uqvj60wXZMAioDo8p7A9/KT2OA7os72wa9mogb+A9ZSUbgcDnWg+Az6TWDnyytVXE6LZJ2JQDaUSqT2BZeD1voI= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x32f.google.com with SMTP id 5b1f17b1804b1-40b399314aaso1734605e9.0; Thu, 23 Nov 2023 13:58:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776712; x=1701381512; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=jAM5uJ8LSMkS52ssC/PAMUPma36VykYajWAl9jkMTCQ=; b=Xpb8cGIcBPDdtqkFUfospvkziJ6W2WlmfJTRz071KVrBeqTPM/JG2V9MyKc+AH/JsA xLXvnL5r/jnDQIE+oq7UVj/xktMjUW7n0hnlxGAT5Mn0dx52Za2iW6RPiDqzuRFxU2UC Dgi/qxZESwhmr0qWbLAA1b1F6rkbRCt4a8QxW6RAfTwjkiCRTCE7PrSdv0aC4qVgL5G2 FwcRtwG6oklf+zXXsHeAAsBIyPGZKlPngn3aHgWb7eYjIJzvMbuIK1fu6hNwf9oCFZPF Vz3JR9Dt66oo7dspX4sB0/5vKypEiLy6gO/oEFuSXwDcrRjjpJr0d+1dv5f5B6kQKPmZ kSfw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776712; x=1701381512; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=jAM5uJ8LSMkS52ssC/PAMUPma36VykYajWAl9jkMTCQ=; b=By4BH6K16c/obD2HJv7an0Z1HtQ6zJqmozgG+NkDba5hnTIHxES0Z2iw5vPD2vgjdZ tN3yXNoDrHnIOBuX04nOPTi2EI8u8RcmO8dfvO9KfL7QgvlEeCylNAEuPqZVS7qs1VDO 7trNuu2fUHmWPr6ul25SzPfl8kNIKyV4aaCV+2TVLLRf+lAJNEGomXHd59GiiWFvOf8p /CK5ceDiHoBlXn4qvmEzeE56L36+S7FpA0CFn/Rg0Z6wW9GJ2GpmeHFKMfPZqKwzsKZ7 61nSVlWQjYM2NxYxQYWoxOt8B9IR2pCXpKzi4MHYowGJ/FJFAUOuN1OokcpOuNxgvURs Q9Rw== X-Gm-Message-State: AOJu0Ywio0TDvOwyRlnV0XoKIlHGGQFPQFC9+0gH5tCbosHEYa1Rh3Gc h4K3aJIzx7IYKnBJFNX1twYDt/nzJII= X-Google-Smtp-Source: AGHT+IH/NSd0ZcLnlH0FUxrJDADC0+diclN3Nc731UsQllAMz+pmnYgceWL+5tZcXTTU3MoKqh2O0Q== X-Received: by 2002:a1c:7910:0:b0:409:5d7d:b26d with SMTP id l16-20020a1c7910000000b004095d7db26dmr643791wme.15.1700776712269; Thu, 23 Nov 2023 13:58:32 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.58.31 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:58:31 -0800 (PST) Message-ID: Date: Thu, 23 Nov 2023 22:58:31 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 1/5][_Hashtable] Add benches To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, URIBL_SBL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org libstdc++: [_Hashtable] Enhance/Add performance benches diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc index f8fcce31609..f2d975ecdaf 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc @@ -17,12 +17,14 @@ // { dg-do run { target c++11 } } -#include +#include #include #include #include #include +#include + #define USE_MY_FOO 1 struct Foo @@ -71,10 +73,13 @@ struct HashFunction }; const int sz = 300000; +const int usz = sz / 2; template void - bench(const char* container_desc, const typename _ContType::value_type* foos) + bench(const char* container_desc, + const typename _ContType::value_type* foos, + const typename _ContType::value_type* ufoos) { using namespace __gnu_test; @@ -106,6 +111,51 @@ template ostr << container_desc << nb_loop << " times insertion of " << sz << " elements"; report_performance(__FILE__, ostr.str().c_str(), time, resource); + + // Try to lookup for mostly unknown entries. + start_counters(time, resource); + + int fcount = 0; + for (int j = 0; j != nb_loop; ++j) + for (int i = 0; i != usz; ++i) + fcount += s.find(ufoos[i]) != s.end() ? 1 : 0; + + stop_counters(time, resource); + ostr.str(""); + ostr << container_desc << nb_loop << " times lookup of " + << usz << " elements " << fcount / nb_loop << " found"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); + + // Try again the previous operations but on a copy with potentially + // less memory fragmentation. + _ContType scopy(s); + + // Try to insert again to check performance of collision detection + start_counters(time, resource); + + for (int j = 0; j != nb_loop; ++j) + for (int i = 0; i != sz; ++i) + scopy.insert(foos[i]); + + stop_counters(time, resource); + ostr.str(""); + ostr << container_desc << nb_loop << " times insertion of " + << sz << " elements in copy"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); + + // Try to lookup for mostly unknown entries. + start_counters(time, resource); + + fcount = 0; + for (int j = 0; j != nb_loop; ++j) + for (int i = 0; i != usz; ++i) + fcount += scopy.find(ufoos[i]) != scopy.end() ? 1 : 0; + + stop_counters(time, resource); + ostr.str(""); + ostr << container_desc << nb_loop << " times lookup of " + << usz << " elements " << fcount / nb_loop << " found"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); } template @@ -155,67 +205,78 @@ int main() { int bars[sz]; + int ubars[usz]; for (int i = 0; i != sz; ++i) bars[i] = i; + for (int i = 0; i != usz; ++i) + ubars[i] = sz + i; bench>( - "std::tr1::unordered_set ", bars); + "std::tr1::unordered_set ", bars, ubars); bench>( - "std::unordered_set ", bars); + "std::unordered_set ", bars, ubars); } - Foo foos[sz]; -#if USE_MY_FOO { - std::random_device randev; - for (int i = 0; i != sz; ++i) - foos[i].init(randev); - } + Foo foos[sz]; + Foo ufoos[usz]; +#if USE_MY_FOO + { + std::random_device randev; + for (int i = 0; i != sz; ++i) + foos[i].init(randev); + for (int i = 0; i != usz; ++i) + ufoos[i].init(randev); + } #endif - time_counter time; - resource_counter resource; - start_counters(time, resource); - - bench<__tr1_uset>( - "std::tr1::unordered_set without hash code cached ", foos); - bench<__tr1_uset>( - "std::tr1::unordered_set with hash code cached ", foos); - bench<__tr1_umset>( - "std::tr1::unordered_multiset without hash code cached ", foos); - bench<__tr1_umset>( - "std::tr1::unordered_multiset with hash code cached ", foos); - - stop_counters(time, resource); - report_performance(__FILE__, "tr1 benches", time, resource); - - start_counters(time, resource); - bench<__uset>( - "std::unordered_set without hash code cached ", foos); - bench<__uset>( - "std::unordered_set with hash code cached ", foos); - bench<__umset>( - "std::unordered_multiset without hash code cached ", foos); - bench<__umset>( - "std::unordered_multiset with hash code cached ", foos); - - stop_counters(time, resource); - report_performance(__FILE__, "std benches", time, resource); - - start_counters(time, resource); - bench<__uset2>( - "std::unordered_set2 without hash code cached ", foos); - bench<__uset2>( - "std::unordered_set2 with hash code cached ", foos); - bench<__umset2>( - "std::unordered_multiset2 without hash code cached ", foos); - bench<__umset2>( - "std::unordered_multiset2 with hash code cached ", foos); - - stop_counters(time, resource); - report_performance(__FILE__, "std2 benches", time, resource); - - bench>( - "std::unordered_set default cache ", foos); - bench>( - "std::unordered_multiset default cache ", foos); + time_counter time; + resource_counter resource; + start_counters(time, resource); + + bench<__tr1_uset>( + "std::tr1::unordered_set without hash code cached ", foos, ufoos); + bench<__tr1_uset>( + "std::tr1::unordered_set with hash code cached ", foos, ufoos); + bench<__tr1_umset>( + "std::tr1::unordered_multiset without hash code cached ", foos, ufoos); + bench<__tr1_umset>( + "std::tr1::unordered_multiset with hash code cached ", foos, ufoos); + + stop_counters(time, resource); + report_performance(__FILE__, "tr1 benches", time, resource); + + start_counters(time, resource); + bench<__uset>( + "std::unordered_set without hash code cached ", foos, ufoos); + bench<__uset>( + "std::unordered_set with hash code cached ", foos, ufoos); + bench<__umset>( + "std::unordered_multiset without hash code cached ", foos, ufoos); + bench<__umset>( + "std::unordered_multiset with hash code cached ", foos, ufoos); + + stop_counters(time, resource); + report_performance(__FILE__, "std benches", time, resource); + + start_counters(time, resource); + bench<__uset2>( + "std::unordered_set2 without hash code cached ", foos, ufoos); + bench<__uset2>( + "std::unordered_set2 with hash code cached ", foos, ufoos); + bench<__umset2>( + "std::unordered_multiset2 without hash code cached ", foos, ufoos); + bench<__umset2>( + "std::unordered_multiset2 with hash code cached ", foos, ufoos); + + stop_counters(time, resource); + report_performance(__FILE__, "std2 benches", time, resource); + + bench>( + "std::unordered_set default cache ", foos, ufoos); + bench>( + "std::unordered_multiset default cache ", foos, ufoos); + } + + { + } } diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc index 125a8a615b7..1e2502209f1 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc @@ -27,310 +27,170 @@ namespace { const int sz = 2000000; - const std::string pattern = "test string #"; - const int nb_copies = 100; + const std::string pattern = "long enough test string #"; - // Special std::string hasher based on std::hash but not tag as - // slow so that hash code is not cached. It is easier to show impact of - // hinting in this context. + // Perfect std::string hasher knowing how string instances have been + // generated. It is not tag as slow so that hash code is not cached. + // It is easier to show impact of hint in this context. struct hasher { std::size_t operator()(const std::string& str) const noexcept { - //std::istringstream istr(str.substr(pattern.size())); - //std::size_t str_index; - //istr >> str_index; - //return str_index; std::hash std_hasher; - return std_hasher(str); + auto hash = std_hasher(pattern); + std::istringstream isstr(str.substr(pattern.length())); + int idx; + isstr >> idx; + return (std::size_t)(hash / sz) * sz + idx; } }; - using ums_t = std::unordered_multiset; - - void - insert_with_perfect_hint1(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(str)); - - for (int j = 1; j != nb_copies; ++j) - for (std::size_t i = 0; i != strs.size(); ++i) - ms.insert(hints[i], strs[i]); - } - - void - insert_with_perfect_hint2(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(str)); - - for (std::size_t i = 0; i != strs.size(); ++i) - for (int j = 1; j != nb_copies; ++j) - ms.insert(hints[i], strs[i]); - } - - // Always insert with the result of the previous insertion. The result of - // the previous insertion will never be followed by an equivalent node - // resulting in a re-computation of its hash code which is expensive. - void - insert_with_good_hint(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(str)); - - for (int j = 1; j != nb_copies; ++j) - for (std::size_t i = 0; i != strs.size(); ++i) - hints[i] = ms.insert(hints[i], strs[i]); - } - - // Note that the following use case is particularly bad especially compared to - // the solution without hint because without hint the first insertion will put - // it first in the bucket and following insertions will detect it and insert - // just before. By giving a hint insertion will be done just after forcing to - // check if it has no impact on the following bucket. - void - insert_with_bad_hint(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(str)); - - for (std::size_t i = 0; i != strs.size(); ++i) - for (int j = 1; j != nb_copies; ++j) - hints[i] = ms.insert(hints[i], strs[i]); - } - - void - insert_without_hint1(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(str)); - - for (int j = 1; j != nb_copies; ++j) - for (std::size_t i = 0; i != strs.size(); ++i) - hints[i] = ms.insert(strs[i]); - } - - // This version is the best one if you insert all equivalent elements at the - // same time. It demonstrates that most of the time it is better not to give - // any hint unless you have written a benchmark for your application showing - // that it does have a positive effect. - void - insert_without_hint2(const std::vector& strs, - ums_t& ms) + // Like previous hasher but tagged as slow. + struct slow_hasher { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(str)); - - for (std::size_t i = 0; i != strs.size(); ++i) - for (int j = 1; j != nb_copies; ++j) - hints[i] = ms.insert(strs[i]); - } + std::size_t + operator()(const std::string& str) const noexcept + { return hasher{}(str); } + }; - void - insert_with_any_hint1(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(ms.begin(), str)); + template + using ums_t = std::unordered_multiset; - std::size_t offset = strs.size() / 2; - for (int j = 1; j != nb_copies; ++j) - for (std::size_t i = 0; i != strs.size(); ++i) + template + void + insert_with_perfect_hint(const std::vector& strs, + ums_t<_Hash>& ms) + { + auto hint = ms.end(); + for (auto str : strs) { - ms.insert(hints[(i + offset) % hints.size()], strs[i]); - ++offset; + auto insert_pos = ms.insert(hint, str); + if (std::next(insert_pos) == ms.end()) + hint = insert_pos; } - } - - void - insert_with_any_hint2(const std::vector& strs, - ums_t& ms) - { - std::vector hints; - hints.reserve(strs.size()); - for (auto str : strs) - hints.push_back(ms.insert(ms.begin(), str)); + } - std::size_t offset = strs.size() / 2; - for (std::size_t i = 0; i != strs.size(); ++i) - for (int j = 1; j != nb_copies; ++j) + template + void + insert_with_bad_hint(const std::vector& strs, + ums_t<_Hash>& ms) + { + auto hint = ms.begin(); + for (auto str : strs) { - ms.insert(hints[(i + offset) % hints.size()], strs[i]); - ++offset; + auto insert_pos = ms.insert(hint, str); + if (std::next(insert_pos) == hint) + hint = ms.begin(); } - } -} - -int main() -{ - using namespace __gnu_test; - - const int nb_iter = 10; - - std::vector strs; - strs.reserve(sz / nb_copies); + } - for (int i = 0; i != sz / nb_copies; ++i) + template + void + insert_without_hint(const std::vector& strs, + ums_t<_Hash>& ms) { - std::ostringstream osstr; - osstr << pattern << i; - strs.push_back(osstr.str()); + for (auto str : strs) + ms.insert(str); } - ums_t ms; - // Use a large load factor to make the context ideal for using hint because we - // will have many elements per bucket. - ms.max_load_factor(10.0f); - ms.reserve(sz); + template + void + insert_range(const std::vector& strs, + ums_t<_Hash>& ms) + { ms.insert(strs.begin(), strs.end()); } +} - // Warm up. +template + void bench(const char* ctx) { - for (auto str : strs) - for (int j = 0; j != nb_copies; ++j) - ms.insert(str); - } - - time_counter time_no_hint1, time_any_hint1, time_bad_hint, time_perfect_hint1; - time_counter time_no_hint2, time_any_hint2, time_good_hint, time_perfect_hint2; - resource_counter resource_no_hint1, resource_any_hint1, resource_bad_hint, - resource_perfect_hint1; - resource_counter resource_no_hint2, resource_any_hint2, resource_good_hint, - resource_perfect_hint2; - - for (int i = 0; i != nb_iter; ++i) - { - // Bad hint - { - ms.clear(); - start_counters(time_bad_hint, resource_bad_hint); - insert_with_bad_hint(strs, ms); - stop_counters(time_bad_hint, resource_bad_hint); - } + using namespace __gnu_test; - // No hint - { - ms.clear(); - start_counters(time_no_hint1, resource_no_hint1); - insert_without_hint1(strs, ms); - stop_counters(time_no_hint1, resource_no_hint1); - } - - // Any hint - { - ms.clear(); - start_counters(time_any_hint1, resource_any_hint1); - insert_with_any_hint1(strs, ms); - stop_counters(time_any_hint1, resource_any_hint1); - } + const int nb_iter = 10; - // Good hint - { - ms.clear(); - start_counters(time_good_hint, resource_good_hint); - insert_with_good_hint(strs, ms); - stop_counters(time_good_hint, resource_good_hint); - } - - // No hint - { - ms.clear(); - start_counters(time_no_hint2, resource_no_hint2); - insert_without_hint2(strs, ms); - stop_counters(time_no_hint2, resource_no_hint2); - } + std::vector strs; + strs.reserve(sz); - // Perfect hint + for (int i = 0; i != sz; ++i) { - ms.clear(); - start_counters(time_perfect_hint2, resource_perfect_hint2); - insert_with_perfect_hint2(strs, ms); - stop_counters(time_perfect_hint2, resource_perfect_hint2); + std::ostringstream osstr; + osstr << pattern << i; + strs.push_back(osstr.str()); } - // Any hint - { - ms.clear(); - start_counters(time_any_hint2, resource_any_hint2); - insert_with_any_hint2(strs, ms); - stop_counters(time_any_hint2, resource_any_hint2); - } + ums_t<_Hash> ms; + ms.reserve(sz); - // Perfect hint - { - ms.clear(); - start_counters(time_perfect_hint1, resource_perfect_hint1); - insert_with_perfect_hint1(strs, ms); - stop_counters(time_perfect_hint1, resource_perfect_hint1); - } + // Warm up. + { + for (auto str : strs) + ms.insert(str); } - std::ostringstream ostr; - ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies - << " insertions w/o hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_no_hint1, resource_no_hint1); - - ostr.str(""); - ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies - << " insertions with any hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_any_hint1, resource_any_hint1); + time_counter time_no_hint, time_bad_hint, time_perfect_hint, + time_range; + resource_counter resource_no_hint, resource_bad_hint, resource_perfect_hint, + resource_range; - ostr.str(""); - ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies - << " insertions with good hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_good_hint, resource_good_hint); + for (int i = 0; i != nb_iter; ++i) + { + // Bad hint + { + ms.clear(); + start_counters(time_bad_hint, resource_bad_hint); + insert_with_bad_hint(strs, ms); + stop_counters(time_bad_hint, resource_bad_hint); + } - ostr.str(""); - ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies - << " insertions with perfect hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_perfect_hint1, resource_perfect_hint1); + // No hint + { + ms.clear(); + start_counters(time_no_hint, resource_no_hint); + insert_without_hint(strs, ms); + stop_counters(time_no_hint, resource_no_hint); + } - ostr.str(""); - ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies - << " insertions w/o hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_no_hint2, resource_no_hint2); + // Perfect hint + { + ms.clear(); + start_counters(time_perfect_hint, resource_perfect_hint); + insert_with_perfect_hint(strs, ms); + stop_counters(time_perfect_hint, resource_perfect_hint); + } - ostr.str(""); - ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies - << " insertions with any hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_any_hint2, resource_any_hint2); + // Range insert + { + ms.clear(); + start_counters(time_range, resource_range); + insert_range(strs, ms); + stop_counters(time_range, resource_range); + } + } - ostr.str(""); - ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies - << " insertions with bad hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_bad_hint, resource_bad_hint); + std::ostringstream ostr; + ostr << ctx << ' ' << sz << " insertions w/o hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_no_hint, resource_no_hint); + + ostr.str(""); + ostr << ctx << ' ' << sz << " insertions with perfect hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_perfect_hint, resource_perfect_hint); + + ostr.str(""); + ostr << ctx << ' ' << sz << " insertions with bad hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_bad_hint, resource_bad_hint); + + ostr.str(""); + ostr << ctx << ' ' << sz << " range insertions"; + report_performance(__FILE__, ostr.str().c_str(), + time_range, resource_range); + } - ostr.str(""); - ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies - << " insertions with perfect hint"; - report_performance(__FILE__, ostr.str().c_str(), - time_perfect_hint2, resource_perfect_hint2); +int main() +{ + bench("hash code NOT cached"); + bench("hash code cached"); return 0; } diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set_hint.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set_hint.cc new file mode 100644 index 00000000000..0197ba31b8b --- /dev/null +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set_hint.cc @@ -0,0 +1,186 @@ +// { dg-do run { target c++11 } } + +#include + +#include +#include +#include +#include + +namespace +{ + const int sz = 2000000; + const std::string pattern = "long enough test string #"; + + // Perfect std::string hasher knowing how string instances have been + // generated. It is not tag as slow so that hash code is not cached. + // It is easier to show impact of hint in this context. + struct hasher + { + std::size_t + operator()(const std::string& str) const noexcept + { + std::hash std_hasher; + auto hash = std_hasher(pattern); + std::istringstream isstr(str.substr(pattern.length())); + int idx; + isstr >> idx; + return (std::size_t)(hash / sz) * sz + idx; + } + }; + + // Like previous hasher but tagged as slow. + struct slow_hasher + { + std::size_t + operator()(const std::string& str) const noexcept + { return hasher{}(str); } + }; + + template + using us_t = std::unordered_set; + + template + void + insert_with_perfect_hint(const std::vector& strs, + us_t<_Hash>& s) + { + auto hint = s.end(); + for (auto str : strs) + { + auto insert_pos = s.insert(hint, str); + if (std::next(insert_pos) == s.end()) + hint = insert_pos; + } + } + + template + void + insert_with_bad_hint(const std::vector& strs, + us_t<_Hash>& s) + { + auto hint = s.begin(); + for (auto str : strs) + { + auto insert_pos = s.insert(hint, str); + if (std::next(insert_pos) == hint) + hint = s.begin(); + } + } + + template + void + insert_without_hint(const std::vector& strs, + us_t<_Hash>& s) + { + for (auto str : strs) + s.insert(str); + } + + template + void + insert_range(const std::vector& strs, + us_t<_Hash>& s) + { s.insert(strs.begin(), strs.end()); } +} + +template + void bench(const char* ctx) + { + using namespace __gnu_test; + + const int nb_iter = 10; + + std::vector strs; + strs.reserve(sz); + + for (int i = 0; i != sz; ++i) + { + std::ostringstream osstr; + osstr << pattern << i; + strs.push_back(osstr.str()); + } + + us_t<_Hash> s; + s.reserve(sz); + + // Warm up. + { + for (auto str : strs) + s.insert(str); + } + + time_counter time_no_hint, time_bad_hint, time_perfect_hint, + time_range; + resource_counter resource_no_hint, resource_bad_hint, resource_perfect_hint, + resource_range; + + for (int i = 0; i != nb_iter; ++i) + { + // Bad hint + { + s.clear(); + start_counters(time_bad_hint, resource_bad_hint); + insert_with_bad_hint(strs, s); + stop_counters(time_bad_hint, resource_bad_hint); + } + + // No hint + { + s.clear(); + start_counters(time_no_hint, resource_no_hint); + insert_without_hint(strs, s); + stop_counters(time_no_hint, resource_no_hint); + } + + // Perfect hint + { + s.clear(); + start_counters(time_perfect_hint, resource_perfect_hint); + insert_with_perfect_hint(strs, s); + stop_counters(time_perfect_hint, resource_perfect_hint); + } + + // Range insert + { + s.clear(); + start_counters(time_range, resource_range); + insert_range(strs, s); + stop_counters(time_range, resource_range); + } + } + + std::ostringstream ostr; + ostr << ctx << ' ' << sz << " insertions w/o hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_no_hint, resource_no_hint); + + ostr.str(""); + ostr << ctx << ' ' << sz << " insertions with perfect hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_perfect_hint, resource_perfect_hint); + + ostr.str(""); + ostr << ctx << ' ' << sz << " insertions with bad hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_bad_hint, resource_bad_hint); + + ostr.str(""); + ostr << ctx << ' ' << sz << " range insertions"; + report_performance(__FILE__, ostr.str().c_str(), + time_range, resource_range); + } + +namespace std +{ + template<> + struct __is_fast_hash : std::false_type + { }; +} + +int main() +{ + bench("hash code NOT cached"); + bench("hash code cached"); + return 0; +} diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set_range_insert.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set_range_insert.cc new file mode 100644 index 00000000000..a4860cc04fe --- /dev/null +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_set_range_insert.cc @@ -0,0 +1,211 @@ +// { dg-do run { target c++11 } } + +#include + +#include +#include +#include +#include + +namespace +{ + const int sz = 2000000; + const std::string pattern = "long enough test string #"; + const int nb_copies = 2; + + // Perfect std::string hasher knowing how string instances have been + // generated. It is not tag as slow so that hash code is not cached. + // It is easier to show impact of hint in this context. + struct hasher + { + static int nb_calls; + + std::size_t + operator()(const std::string& str) const noexcept + { + ++nb_calls; + std::hash std_hasher; + auto hash = std_hasher(pattern); + std::istringstream isstr(str.substr(pattern.length())); + int idx = -1; + isstr >> idx; + if (idx != -1) + return (std::size_t)(hash / sz) * sz + idx; + + return hash; + } + }; + + // Like previous hasher but tagged as slow. + struct slow_hasher + { + std::size_t + operator()(const std::string& str) const noexcept + { return hasher{}(str); } + }; + + int hasher::nb_calls = 0; + + template + using us_t = std::unordered_set; + + template + void + insert_once_individually(const std::vector& strs, + us_t<_Hash>& s) + { + for (std::size_t i = 0; i != strs.size(); ++i) + s.insert(strs[i]); + } + + template + void + insert_once_range(const std::vector& strs, + us_t<_Hash>& s) + { + s.insert("initial string to not leave s empty"); + s.insert(strs.begin(), strs.end()); + } + + template + void + insert_individually(const std::vector& strs, + us_t<_Hash>& s) + { + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + s.insert(strs[i]); + } + + template + void + insert_range(const std::vector& strs, + us_t<_Hash>& s) + { + s.insert("initial string to not leave s empty"); + for (int j = 1; j != nb_copies; ++j) + s.insert(strs.begin(), strs.end()); + } +} + +template + void bench(const char* ctx) + { + using namespace __gnu_test; + + const int nb_iter = 10; + + std::vector strs; + strs.reserve(sz / nb_copies); + + for (int i = 0; i != sz / nb_copies; ++i) + { + std::ostringstream osstr; + osstr << pattern << i; + strs.push_back(osstr.str()); + } + + us_t<_Hash> s; + s.reserve(sz / nb_copies); + + // Warm up. + { + for (auto str : strs) + for (int j = 0; j != nb_copies; ++j) + s.insert(str); + } + + int nb_calls_once_individually = 0; + int nb_calls_once_range = 0; + int nb_calls_individually = 0; + int nb_calls_range = 0; + time_counter time_once_individually, time_once_range; + time_counter time_individually, time_range; + resource_counter resource_once_individually, resource_once_range; + resource_counter resource_individually, resource_range; + + for (int i = 0; i != nb_iter; ++i) + { + { + hasher::nb_calls = 0; + s.clear(); + start_counters(time_once_individually, resource_once_individually); + insert_once_individually(strs, s); + stop_counters(time_once_individually, resource_once_individually); + nb_calls_once_individually += hasher::nb_calls; + } + + { + hasher::nb_calls = 0; + s.clear(); + start_counters(time_once_range, resource_once_range); + insert_once_range(strs, s); + stop_counters(time_once_range, resource_once_range); + nb_calls_once_range += hasher::nb_calls; + } + + { + hasher::nb_calls = 0; + s.clear(); + start_counters(time_individually, resource_individually); + insert_individually(strs, s); + stop_counters(time_individually, resource_individually); + nb_calls_individually += hasher::nb_calls; + } + + { + hasher::nb_calls = 0; + s.clear(); + start_counters(time_range, resource_range); + insert_range(strs, s); + stop_counters(time_range, resource_range); + nb_calls_range += hasher::nb_calls; + } + } + + std::ostringstream ostr; + ostr << ctx << ' ' + << nb_copies << " X " << sz / nb_copies << " inserts individually"; + if (nb_calls_individually != 0) + ostr << ' ' << nb_calls_individually << " calls"; + report_performance(__FILE__, ostr.str().c_str(), + time_individually, resource_individually); + + ostr.str(""); + ostr << ctx << ' ' + << nb_copies << " X " << sz / nb_copies << " inserts in range"; + if (nb_calls_range) + ostr << ' ' << nb_calls_range << " calls"; + report_performance(__FILE__, ostr.str().c_str(), + time_range, resource_range); + + ostr.str(""); + ostr << ctx << ' ' + << sz / nb_copies << " X inserts individually"; + if (nb_calls_once_individually != 0) + ostr << ' ' << nb_calls_once_individually << " calls"; + report_performance(__FILE__, ostr.str().c_str(), + time_once_individually, resource_once_individually); + + ostr.str(""); + ostr << ctx << ' ' + << sz / nb_copies << " X inserts in range"; + if (nb_calls_once_range != 0) + ostr << ' ' << nb_calls_once_range << " calls"; + report_performance(__FILE__, ostr.str().c_str(), + time_once_range, resource_once_range); + } + +namespace std +{ + template<> + struct __is_fast_hash : std::false_type + { }; +} + +int main() +{ + bench("hash code NOT cached"); + bench("hash code cached"); + return 0; +} diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc index 0a119645fbc..955504491a9 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc @@ -26,10 +26,10 @@ namespace { const int nb_elements = 20; - const int nb_insts = 150000; + const int nb_insts = 15000; template - void bench(const char* desc, const std::vector<_ElemType>& elems) + void bench(const char* desc, const std::vector<_ElemType>& elems, bool with_copy) { using namespace __gnu_test; @@ -52,6 +52,19 @@ namespace ostr << desc << " 1st insert"; report_performance(__FILE__, ostr.str().c_str(), time, resource); + if (with_copy) + { + start_counters(time, resource); + + std::vector>(insts).swap(insts); + + stop_counters(time, resource); + + ostr.str(""); + ostr << desc << " copy"; + report_performance(__FILE__, ostr.str().c_str(), time, resource); + } + start_counters(time, resource); for (auto& us : insts) @@ -103,7 +116,8 @@ int main() for (int i = 0; i != nb_elements; ++i) elems.push_back(i); - bench("std::unordered_set: ", elems); + bench("std::unordered_set: ", elems, false); + bench("std::unordered_set: ", elems, true); } { @@ -118,7 +132,8 @@ int main() } } - bench("std::unordered_set: ", elems); + bench("std::unordered_set: ", elems, false); + bench("std::unordered_set: ", elems, true); } return 0; From patchwork Thu Nov 23 21:58:40 2023 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: 1867984 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=lpaxfHlo; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsT13x4Bz1yS0 for ; Fri, 24 Nov 2023 08:59:01 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1FCC53857C60 for ; Thu, 23 Nov 2023 21:58:59 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by sourceware.org (Postfix) with ESMTPS id BD62A38582A5; Thu, 23 Nov 2023 21:58:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org BD62A38582A5 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org BD62A38582A5 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::335 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776726; cv=none; b=c19XefIksEyIgXFoXS3RWYm3tVA3UD7bN9v+Y5sf6iDU2166K+E/G7F8IFLXZrZU6ykSidr/nvuXjmCzq6+Voz8G9z3k78MSqTAwu93NzpGk82sxZzamovdNrPL82uHsJeYMBIJS5UQXxkOJVnWTefZQkFADHLm6HI1VyJ5/q5I= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776726; c=relaxed/simple; bh=Chw4+PBM/6T90QUTMv2lKNKcHp+0vC3aI0kbEQNhi7Y=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=VwAkcEfWi6LxLoQCsFTPaKgEoUPkOL2CVR38TuzXWg78Tdz6LInEr4IWzDug+hhkEf5W+AD2sTsh/lbt4i7dhSrmMUckwcfFH+M2XbcGmYljdeVqchHu042zCjGZk1LOCRenV6PIVqmyOYjIXJfjESVnW9Xl4SqLTbeyiaoJUu8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x335.google.com with SMTP id 5b1f17b1804b1-40790b0a224so8683935e9.0; Thu, 23 Nov 2023 13:58:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776721; x=1701381521; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=d1bZAoN21BhFLqrDdrtHn2KjnFkKSSuSu9ElmYnJc0w=; b=lpaxfHloLXMhYcCTtoB1bf05XJEz7IqRImmUEGu2SbFSrn+MBcTnn1q4E4RytT5fU/ KxrqmSjftw3MR5P4nYp7y+ExJC0w7FiqevF0z+wJ18kgF7CIPT53xzzdHPdAxH22upXR FBwNMi6moHdlx7C6Qx/YH8fBWJGkWHhYXUgyjRifeVL1Crq5ZzAyf3kjZSjXxU9/KKun X3HJ+00/IIU8ALdC7iBHI+B7vePR3DrzR32OHffhdFI7p6EY4kdVAAOIcbTCOJX9Ua/e HlhUlnycjGw4k0R1mKscUEr6aINZepcoHxOitqyv/FLdgh1Fxu21OXpmRzVNc+u4/Lve g+9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776721; x=1701381521; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=d1bZAoN21BhFLqrDdrtHn2KjnFkKSSuSu9ElmYnJc0w=; b=AcR4GBwyTNnTfVWIZYatcFxxVlRTKiGnSt3LsTsYWuG93aDqQLal1Ifxay41yLH+Eg 2hKbzYF/yZ87c90XzodBuPtfhjhJLHArotZPyBEOl65TmiImCHAGT/AWCZchsGy5frqc GPawlfF1+lTzs6tYcsU34QamPzpctnLuLqWrsZMX/xuojzIaIYQDYEtxqT54DyniHuYU +CR3tEqB7vxlhrh3sjJL7EQfEigxEyi6LKFVYXcD+G7lErzzA+r3boENOLEGtqsvD/6b jNRPAky6hzJZE456wWdJX6xV/6qnREim71D4x8UbJh/MMUQ7lDwU0v9loWgyh4MdqFel cqmA== X-Gm-Message-State: AOJu0Ywq1OF/gfoeWR9bYX8uh6A4YkRkwkJux/31TUt6c9g3RrqEUIoh d8q+flXRtY8dhVhNw3DNe2cp0QT2kqc= X-Google-Smtp-Source: AGHT+IECKX34si0iUaGsIi84PVdxK4PYj6F8nGmGoMNL8/4aaEjkG/p1HUxPV6NAooIofC7ENlQxiA== X-Received: by 2002:a05:6000:b03:b0:332:cada:84a with SMTP id dj3-20020a0560000b0300b00332cada084amr534240wrb.61.1700776721265; Thu, 23 Nov 2023 13:58:41 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.58.40 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:58:40 -0800 (PST) Message-ID: <1e319e88-62ae-476f-bae0-afa8ba126310@gmail.com> Date: Thu, 23 Nov 2023 22:58:40 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 2/5][_Hashtable] Fix implementation inconsistencies To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.1 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org libstdc++: [_Hashtable] Fix some implementation inconsistencies     Get rid of the different usages of the mutable keyword. For     _Prime_rehash_policy methods are exported from the library, we need to     keep their const qualifier, so adapt implementation to update previously     mutable member.     Remove useless noexcept qualification on _Hashtable _M_bucket_index overload.     Fix comment to explain that we need the computation of bucket index to be     noexcept to be able to rehash the container when needed. For Standard     instantiations through std::unordered_xxx containers we already force     usage of hash code cache when hash functor is not noexcep so it is guarantied.     The static_assert purpose in _Hashtable on _M_bucket_index is thus limited     to usages of _Hashtable with exotic _Hashtable_traits.     libstdc++-v3/ChangeLog:             * include/bits/hashtable_policy.h (_NodeBuilder<>::_S_build): Remove             const qualification on _NodeGenerator instance. (_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const qualification.             (_ReuseOrAllocNode<>::_M_nodes): Remove mutable.             (_Prime_rehash_policy::max_load_factor()): Remove noexcept.             (_Prime_rehash_policy::_M_reset()): Remove noexcept.             (_Prime_rehash_policy::_M_next_resize): Remove mutable.             (_Power2_rehash_policy::_M_next_bkt(size_t)): Remove noexcept.             (_Power2_rehash_policy::_M_bkt_for_elements(size_t)): Remove noexcept.             (_Power2_rehash_policy::_M_neeed_rehash): Remove noexcept.             (_Power2_rehash_policy::_M_reset): Remove noexcept.             (_Insert_base<>::_M_insert_range): Remove _NodeGetter const qualification.             (_Hash_code_base<>::_M_bucket_index(const _Hash_node_value<>&, size_t)):             Simplify noexcept declaration, we already static_assert that _RangeHash functor             is noexcept.             * include/bits/hashtable.h: Rework comments. Remove const qualifier on             _NodeGenerator& arguments.             (_Hashtable<>::_M_bucket_index(const __node_value_type&)): Remove useless             noexcept qualification.             * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy): Workaround             _M_next_resize not being mutable anymore. Tested under Linux x86_64, ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9ff9104a2ab..8329d32e68e 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -48,7 +48,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __cache_default = __not_<__and_, - // Mandatory to have erase not throwing. + // Mandatory for the rehash process. __is_nothrow_invocable>>; // Helper to conditionally delete the default constructor. @@ -477,7 +477,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template void - _M_assign(_Ht&&, const _NodeGenerator&); + _M_assign(_Ht&&, _NodeGenerator&); void _M_move_assign(_Hashtable&&, true_type); @@ -792,7 +792,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Bucket index computation helpers. size_type - _M_bucket_index(const __node_value_type& __n) const noexcept + _M_bucket_index(const __node_value_type& __n) const { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } size_type @@ -920,7 +920,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&); + _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&); template static __conditional_t< @@ -940,7 +940,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen) + _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen) { return _M_insert_unique( _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), @@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, + _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, true_type /* __uks */) { using __to_value @@ -960,7 +960,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator - _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, + _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, false_type __uks) { using __to_value @@ -973,7 +973,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator _M_insert(const_iterator, _Arg&& __arg, - const _NodeGenerator& __node_gen, true_type __uks) + _NodeGenerator& __node_gen, true_type __uks) { return _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first; @@ -983,7 +983,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator _M_insert(const_iterator, _Arg&&, - const _NodeGenerator&, false_type __uks); + _NodeGenerator&, false_type __uks); size_type _M_erase(true_type __uks, const key_type&); @@ -1378,7 +1378,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) + _M_assign(_Ht&& __ht, _NodeGenerator& __node_gen) { __buckets_ptr __buckets = nullptr; if (!_M_buckets) @@ -1620,8 +1620,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION ~_Hashtable() noexcept { // Getting a bucket index from a node shall not throw because it is used - // in methods (erase, swap...) that shall not throw. Need a complete - // type to check this, so do it in the destructor not at class scope. + // during the rehash process. This static_assert purpose is limited to usage + // of _Hashtable with _Hashtable_traits requesting non-cached hash code. + // Need a complete type to check this, so do it in the destructor not at + // class scope. static_assert(noexcept(declval() ._M_bucket_index(declval(), (std::size_t)0)), @@ -2222,7 +2224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_unique(_Kt&& __k, _Arg&& __v, - const _NodeGenerator& __node_gen) + _NodeGenerator& __node_gen) -> pair { if (size() <= __small_size_threshold()) @@ -2259,7 +2261,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert(const_iterator __hint, _Arg&& __v, - const _NodeGenerator& __node_gen, + _NodeGenerator& __node_gen, false_type /* __uks */) -> iterator { diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index c67eebd3b2b..5c40be2cb72 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -155,7 +155,7 @@ namespace __detail { template static auto - _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) + _S_build(_Kt&& __k, _Arg&& __arg, _NodeGenerator& __node_gen) -> typename _NodeGenerator::__node_ptr { return __node_gen(std::forward<_Kt>(__k), @@ -168,7 +168,7 @@ namespace __detail { template static auto - _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) + _S_build(_Kt&& __k, _Arg&&, _NodeGenerator& __node_gen) -> typename _NodeGenerator::__node_ptr { return __node_gen(std::forward<_Kt>(__k)); } }; @@ -212,7 +212,7 @@ namespace __detail template __node_ptr - operator()(_Args&&... __args) const + operator()(_Args&&... __args) { if (!_M_nodes) return _M_h._M_allocate_node(std::forward<_Args>(__args)...); @@ -230,7 +230,7 @@ namespace __detail } private: - mutable __node_ptr _M_nodes; + __node_ptr _M_nodes; __hashtable_alloc& _M_h; }; @@ -551,10 +551,11 @@ namespace __detail : _M_max_load_factor(__z), _M_next_resize(0) { } float - max_load_factor() const noexcept + max_load_factor() const { return _M_max_load_factor; } // Return a bucket size no smaller than n. + // TODO: 'const' qualifier is kept for abi compatibility reason. std::size_t _M_next_bkt(std::size_t __n) const; @@ -567,6 +568,7 @@ namespace __detail // and __n_ins is number of elements to be inserted. Do we need to // increase bucket count? If so, return make_pair(true, n), where n // is the new bucket count. If not, return make_pair(false, 0). + // TODO: 'const' qualifier is kept for abi compatibility reason. std::pair _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const; @@ -578,7 +580,7 @@ namespace __detail { return _M_next_resize; } void - _M_reset() noexcept + _M_reset() { _M_next_resize = 0; } void @@ -588,7 +590,7 @@ namespace __detail static const std::size_t _S_growth_factor = 2; float _M_max_load_factor; - mutable std::size_t _M_next_resize; + std::size_t _M_next_resize; }; /// Range hashing function assuming that second arg is a power of 2. @@ -629,13 +631,13 @@ namespace __detail : _M_max_load_factor(__z), _M_next_resize(0) { } float - max_load_factor() const noexcept + max_load_factor() const { return _M_max_load_factor; } // Return a bucket size no smaller than n (as long as n is not above the // highest power of 2). std::size_t - _M_next_bkt(std::size_t __n) noexcept + _M_next_bkt(std::size_t __n) { if (__n == 0) // Special case on container 1st initialization with 0 bucket count @@ -669,7 +671,7 @@ namespace __detail // Return a bucket count appropriate for n elements std::size_t - _M_bkt_for_elements(std::size_t __n) const noexcept + _M_bkt_for_elements(std::size_t __n) const { return __builtin_ceil(__n / (double)_M_max_load_factor); } // __n_bkt is current bucket count, __n_elt is current element count, @@ -678,7 +680,7 @@ namespace __detail // is the new bucket count. If not, return make_pair(false, 0). std::pair _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, - std::size_t __n_ins) noexcept + std::size_t __n_ins) { if (__n_elt + __n_ins > _M_next_resize) { @@ -708,11 +710,11 @@ namespace __detail { return _M_next_resize; } void - _M_reset() noexcept + _M_reset() { _M_next_resize = 0; } void - _M_reset(_State __state) noexcept + _M_reset(_State __state) { _M_next_resize = __state; } static const std::size_t _S_growth_factor = 2; @@ -931,12 +933,12 @@ namespace __detail template void _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter&, true_type __uks); + _NodeGetter&, true_type __uks); template void _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter&, false_type __uks); + _NodeGetter&, false_type __uks); public: using iterator = _Node_iterator<_Value, __constant_iterators::value, @@ -1012,7 +1014,7 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter& __node_gen, true_type __uks) + _NodeGetter& __node_gen, true_type __uks) { __hashtable& __h = _M_conjure_hashtable(); for (; __first != __last; ++__first) @@ -1029,7 +1031,7 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter& __node_gen, false_type __uks) + _NodeGetter& __node_gen, false_type __uks) { using __rehash_guard_t = typename __hashtable::__rehash_guard_t; using __pair_type = std::pair; @@ -1359,9 +1361,7 @@ namespace __detail std::size_t _M_bucket_index(const _Hash_node_value<_Value, false>& __n, std::size_t __bkt_count) const - noexcept( noexcept(declval()(declval())) - && noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) + noexcept( noexcept(declval()(declval())) ) { return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())), __bkt_count); @@ -1369,9 +1369,7 @@ namespace __detail std::size_t _M_bucket_index(const _Hash_node_value<_Value, true>& __n, - std::size_t __bkt_count) const - noexcept( noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) + std::size_t __bkt_count) const noexcept { return _RangeHash{}(__n._M_hash_code, __bkt_count); } void diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index 9673d867402..e75b09a31bb 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -45,6 +45,7 @@ namespace __detail std::size_t _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const { + auto __mutable_this = const_cast<_Prime_rehash_policy*>(this); // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) static const unsigned char __fast_bkt[] @@ -58,7 +59,7 @@ namespace __detail // want to add an element allocation will take place. return 1; - _M_next_resize = + __mutable_this->_M_next_resize = __builtin_floor(__fast_bkt[__n] * (double)_M_max_load_factor); return __fast_bkt[__n]; } @@ -79,9 +80,9 @@ namespace __detail // Set next resize to the max value so that we never try to rehash again // as we already reach the biggest possible bucket number. // Note that it might result in max_load_factor not being respected. - _M_next_resize = size_t(-1); + __mutable_this->_M_next_resize = size_t(-1); else - _M_next_resize = + __mutable_this->_M_next_resize = __builtin_floor(*__next_bkt * (double)_M_max_load_factor); return *__next_bkt; @@ -101,6 +102,7 @@ namespace __detail _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const { + auto __mutable_this = const_cast<_Prime_rehash_policy*>(this); if (__n_elt + __n_ins > _M_next_resize) { // If _M_next_resize is 0 it means that we have nothing allocated so @@ -114,7 +116,7 @@ namespace __detail _M_next_bkt(std::max(__builtin_floor(__min_bkts) + 1, __n_bkt * _S_growth_factor)) }; - _M_next_resize + __mutable_this->_M_next_resize = __builtin_floor(__n_bkt * (double)_M_max_load_factor); return { false, 0 }; } From patchwork Thu Nov 23 21:58:49 2023 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: 1867985 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=X0r+Lm40; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsTX5mDmz1yS0 for ; Fri, 24 Nov 2023 08:59:28 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2EB10386C5A9 for ; Thu, 23 Nov 2023 21:59:26 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x32c.google.com (mail-wm1-x32c.google.com [IPv6:2a00:1450:4864:20::32c]) by sourceware.org (Postfix) with ESMTPS id 2221D3857C7A; Thu, 23 Nov 2023 21:58:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2221D3857C7A Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 2221D3857C7A Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::32c ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776734; cv=none; b=WKfWxkzH7mQxKQq7EnIb5KbOcm0vaUNjxHGJHBi26EsM+POFMABjbckbDgegdoIvQtCz6pFbeC2yJRVKhKLexlYdbcJZlID9N5jBSJrPyeTWIGkZGP7egyht95UxMGhOY6+Rogj+7kIUJH6rluwUaBBRpWEH6UyCfjxnFx/Vcbo= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776734; c=relaxed/simple; bh=5u3aRgQQUrpjaIsTxW5I2qaNtXU1sCZ5AUE5MgqRH+o=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=rN5Az13pKYghFP7mfjagG2XCv2h6FmpaZ2lt1iNXU/n6irsXRobvvcfuYpT7kPL6IMzoUIQqHXzRkS0T8L8vWWvIk9mfN9SC+tCTEU7TfLXdArkYquAfTj0cyuqK9jKbF4eZtQB9Bb0j95jxv2dyjh+iEF/y9yknd3tuhHvU+bE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x32c.google.com with SMTP id 5b1f17b1804b1-4083f613275so9067385e9.2; Thu, 23 Nov 2023 13:58:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776730; x=1701381530; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=0ghFbxsL3Qi4zPZHDFPGxU8AZoEZ9uFJsnDbR1QFzbI=; b=X0r+Lm40RnkqcK40d7BZbCtIxo1QYXLrn1ei25zbWfUZUT5rE6CsR7BrciD6YPzLn1 ZfTY6UMf57jMRkJxJW/H3og/ezhhPTna+Av2kuxklXFyiYJEMHb7Vdi6+W/4wOg8wMbX 4wZrW9tVxVnq21K9cwJihK+1a07FqEnU/ZvhHKYVuDA0lp/OUu7DKE2HP8XV3gSWpVT0 rXfJnGIwg7jZyWYXsqspU/W/fuY9rcjphE8VaHTTMs+UNcF4jEP/tc1phcnOKTME0N9Q 5BTeTb4OmNDWr428W5qoyr5ZH0oB3lpH53hvPNuLcWAZDHSJdvgjEER6RZ1EHTyDXdKf LWkA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776730; x=1701381530; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=0ghFbxsL3Qi4zPZHDFPGxU8AZoEZ9uFJsnDbR1QFzbI=; b=kL2mg+pJUt2N0CCetOpJAbx31lNxBZxGx9qX2nODu+GQkVr7vxyg/PrwtFpXc+ABua l+HKaCZ8wwyNKHQto+75xyKV1CW0xtzFKax3vdJ0HuET3xd5cLfcRCg3x71eiBElstCS XnciK5T6F9xGs3mCoBFbygLNZKp84EzxlbDb6rx2hkhlaUTg7FqoeXKgENhx7tjFXoRo wViP446GGw0tJdoPBc16PheQTooqeudV3ldcx5bHezWYcrs+Ys2UgY+pJefiNMhC2HYz OMoKi/L0ZwuMdjuxdSqi+jqFj/mKjlfcG7VrMNLOSJHRzAzS89ftpUhifBOJdE+3C4Ij iPlg== X-Gm-Message-State: AOJu0Yw6aC34S/XCze7soPnuurlgXfaFedrCRWMrcXKdHzkU77DXTbLx Evx3pjI076h/iTN/DXFFMxBd8eCRi8c= X-Google-Smtp-Source: AGHT+IFpTQv/c3zluLzQmeIt1OfRQvzlryNC0avP6xtDJ6mDabSQLHKjdYYhkojOI1pWf516G34HKA== X-Received: by 2002:a05:600c:1d06:b0:40a:3e13:22b0 with SMTP id l6-20020a05600c1d0600b0040a3e1322b0mr715682wms.41.1700776729830; Thu, 23 Nov 2023 13:58:49 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.58.49 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:58:49 -0800 (PST) Message-ID: <7d985892-3188-4b35-8f3f-1a3a12e09012@gmail.com> Date: Thu, 23 Nov 2023 22:58:49 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 3/5][_Hashtable] Avoid redundant usage of rehash policy To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.2 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org libstdc++: [_Hashtable] Avoid redundant usage of rehash policy     Bypass call to __detail::__distance_fwd and the check if rehash is needed when     assigning an initializer_list to an unordered_multimap or unordered_multiset.     libstdc++-v3/ChangeLog:             * include/bits/hashtable.h             (_Hashtable<>::_M_insert_range(_InputIte, _InputIte, _NodeGen&)): New. (_Hashtable<>::operator=(initializer_list)): Use latter.             (_Hashtable<>::_Hashtable(_InputIte, _InputIte, size_type, const _Hash&, const _Equal&,             const allocator_type&, false_type)): Use latter.             * include/bits/hashtable_policy.h             (_Insert_base<>::_M_insert_range(_InputIte, _InputIte, true_type)): Use latter.             (_Insert_base<>::_M_insert_range(_InputIte, _InputIte, false_type)): Likewise. Tested under Linux x64 Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 8329d32e68e..771ed9968f7 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -612,7 +612,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (_M_bucket_count < __l_bkt_count) rehash(__l_bkt_count); - this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{}); + _M_insert_range(__l.begin(), __l.end(), __roan); return *this; } @@ -985,6 +985,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(const_iterator, _Arg&&, _NodeGenerator&, false_type __uks); + template + void + _M_insert_range(_InputIterator __first, _InputIterator __last, + _NodeGenerator&); + size_type _M_erase(true_type __uks, const key_type&); @@ -1263,8 +1268,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __alloc_node_gen_t __node_gen(*this); - for (; __f != __l; ++__f) - _M_insert(*__f, __node_gen, __uks); + _M_insert_range(__f, __l, __node_gen); } template + template + void + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_insert_range(_InputIterator __first, _InputIterator __last, + _NodeGenerator& __node_gen) + { + for (; __first != __last; ++__first) + _M_insert(*__first, __node_gen, __unique_keys{}); + } + template(this)); } - template + template void _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGetter&, true_type __uks); + true_type __uks); - template + template void _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGetter&, false_type __uks); + false_type __uks); public: using iterator = _Node_iterator<_Value, __constant_iterators::value, @@ -997,41 +997,37 @@ namespace __detail template void insert(_InputIterator __first, _InputIterator __last) - { - __hashtable& __h = _M_conjure_hashtable(); - __node_gen_type __node_gen(__h); - return _M_insert_range(__first, __last, __node_gen, __unique_keys{}); - } + { _M_insert_range(__first, __last, __unique_keys{}); } }; template - template + template void _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGetter& __node_gen, true_type __uks) + true_type /* __uks */) { __hashtable& __h = _M_conjure_hashtable(); - for (; __first != __last; ++__first) - __h._M_insert(*__first, __node_gen, __uks); + __node_gen_type __node_gen(__h); + __h._M_insert_range(__first, __last, __node_gen); } template - template + template void _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGetter& __node_gen, false_type __uks) + false_type __uks) { using __rehash_guard_t = typename __hashtable::__rehash_guard_t; using __pair_type = std::pair; @@ -1051,8 +1047,8 @@ namespace __detail __h._M_rehash(__do_rehash.second, __uks); __rehash_guard._M_guarded_obj = nullptr; - for (; __first != __last; ++__first) - __h._M_insert(*__first, __node_gen, __uks); + __node_gen_type __node_gen(__h); + __h._M_insert_range(__first, __last, __node_gen); } /** From patchwork Thu Nov 23 21:58:56 2023 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: 1867987 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=fQt4RGPw; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsV43btvz1yS0 for ; Fri, 24 Nov 2023 08:59:56 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0FF123838F08 for ; Thu, 23 Nov 2023 21:59:54 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) by sourceware.org (Postfix) with ESMTPS id 99F4A38582B1; Thu, 23 Nov 2023 21:58:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 99F4A38582B1 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 99F4A38582B1 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::42e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776741; cv=none; b=hnu6YyOJjGuhnBLmU3H6qXiLbTHYInmRDF1mjD6qQ3+5VW1rKL2f6jWMfrLRFkR28vIXtqz6o962EhiAp+hkgfua3zQxScouPs5CLBd4FHOtDv7ojgTuJg9X5lTb9cfO2m27Kt04sZlCPxag2xrQn/SnCr0AyA7Rm+Y9+17pIZE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776741; c=relaxed/simple; bh=VDONBI+jMCCYt+ZZ6rmIwvSmtNZl7KNloXe0JZG7NaU=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=svNJEkAK+sBT3ZNm9SlSCcHMnWKo3tzhNF6Q25AdBq1XzTID1JkuqbsRrXgI+srwigWrB3/0zOWAw1uOxuP8dVUgSs4ZtWm+AEBBRbg3iYeFvFgdYCJxZRWIOfZNdUXnYFjRp4UcRPFfs4FG7plQeY+wxPSttVh0p/1YUyXqYOs= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wr1-x42e.google.com with SMTP id ffacd0b85a97d-32deb2809daso840902f8f.3; Thu, 23 Nov 2023 13:58:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776737; x=1701381537; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=K6jR/1SwepJehWBq5T9g315UngWcYYg3UiaWcBEHsIs=; b=fQt4RGPwFXHGeA5EWxPCRnjDTaGKVjkCs9oLi0+meQBH0HT/v7EziauuUc4i0lBo2x JrpkdtUQP7SnONz6nwA5nISJJ1BMdPCRgiU1OflmSVrB6r/a5vJ8u/jxH5k+/7AGiFcK lf7+mLpkH/EJ4Hs+0wkXQI63DfSJ5TuubLf5nl88cXNKyJGhVQfCOywFdJqdyImZ4x6P dsbJMWbSU/okOp5GZxijsMaViJOSGCnds7lYVhwv42PnXHiXxW237NDCaafrALMc84Qa StE9MaY9i0GzVW2ssnmlq+/GiTCQKjIV+0ol2r94Gh2Qx+9Ja8iYcUf7tFzklqqYwD/l yn0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776737; x=1701381537; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=K6jR/1SwepJehWBq5T9g315UngWcYYg3UiaWcBEHsIs=; b=aM2SvRZi6IjlEGpbBy/zHPHrGc6dsvdYTHCL4e/++ajUsAuQyTN3VyiS2Y4sxQRWH0 66LPVmPX4me4KCy2K8A1HD1TVacSFrW7Fx/Cj7xeU09DbZNXG5Phvdsciq8RXqFIDAw8 LAJKd1dnklgBOvkJU5EVfWo0P7gEP2hf9Emuy6P3I6YtNuPND6gLpmD/sbjX7G7WBz4U O1Zmz8LWvBfbWXbvbTehVwXAFq7Hhtun4NB+5KccmX6UktI3LudrPHZFZvzIBIJ2nh0f vAdIhepOmAuSPhmXuCrc212Smu7GPNd3HGkdBlGeFyz4yN0ZBvq0hEe93q29SyD1JIsN 5qeA== X-Gm-Message-State: AOJu0YwPjHLCd1V+Of/C0TPy3T+y9VrnfdtEw4r1jOO9hnRaAI+8RK6P joyynSu1pScyIG4h6+EdKfCo7oJK41g= X-Google-Smtp-Source: AGHT+IENCuOYVReASfg0J1r/7hGjcfakAu1lu/0OtsIhRLz/p4xHVs7dIUjtsJYi44rlw7u971yGuw== X-Received: by 2002:adf:f48d:0:b0:332:e4cc:6a38 with SMTP id l13-20020adff48d000000b00332e4cc6a38mr496164wro.57.1700776737450; Thu, 23 Nov 2023 13:58:57 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.58.56 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:58:56 -0800 (PST) Message-ID: <6472c80c-7ea1-427c-9046-d46fd1121f34@gmail.com> Date: Thu, 23 Nov 2023 22:58:56 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 4/5][_Hashtable] Generalize the small size optimization To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org libstdc++: [_Hashtable] Extend the small size optimization     A number of methods were still not using the small size optimization which     is to prefer an O(N) research to a hash computation as long as N is small.     libstdc++-v3/ChangeLog:             * include/bits/hashtable.h: Move comment about all equivalent values             being next to each other in the class documentation header.             (_M_reinsert_node, _M_merge_unique): Implement small size optimization.             (_M_find_tr, _M_count_tr, _M_equal_range_tr): Likewise. Tested under Linux x64 Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 771ed9968f7..aec77c34a58 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -152,6 +152,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * _M_before_begin, if any, is updated to point to its new before * begin node. * + * Note that all equivalent values, if any, are next to each other, if + * we find a non-equivalent value after an equivalent one it means that + * we won't find any new equivalent value. + * * On erase, the simple iterator design requires using the hash * functor to get the index of the bucket to update. For this * reason, when __cache_hash_code is set to false the hash functor must @@ -1054,10 +1058,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __nh.get_allocator()); + __node_ptr __n = nullptr; const key_type& __k = __nh._M_key(); - __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__code); - if (__node_ptr __n = _M_find_node(__bkt, __k, __code)) + const size_type __size = size(); + if (__size <= __small_size_threshold()) + { + for (__n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + break; + } + + __hash_code __code; + size_type __bkt; + if (!__n) + { + __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + if (__size > __small_size_threshold()) + __n = _M_find_node(__bkt, __k, __code); + } + + if (__n) { __ret.node = std::move(__nh); __ret.position = iterator(__n); @@ -1161,11 +1182,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; + const size_type __size = size(); const key_type& __k = _ExtractKey{}(*__pos); + if (__size <= __small_size_threshold()) + { + bool __found = false; + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + { + __found = true; + break; + } + + if (__found) + { + if (__n_elt != 1) + --__n_elt; + continue; + } + } + __hash_code __code = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur); size_type __bkt = _M_bucket_index(__code); - if (_M_find_node(__bkt, __k, __code) == nullptr) + if (__size <= __small_size_threshold() + || _M_find_node(__bkt, __k, __code) == nullptr) { auto __nh = __src.extract(__pos); _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); @@ -1743,6 +1784,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_find_tr(const _Kt& __k) -> iterator { + if (size() <= __small_size_threshold()) + { + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals_tr(__k, *__n)) + return iterator(__n); + return end(); + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); return iterator(_M_find_node_tr(__bkt, __k, __code)); @@ -1759,6 +1808,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_find_tr(const _Kt& __k) const -> const_iterator { + if (size() <= __small_size_threshold()) + { + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals_tr(__k, *__n)) + return const_iterator(__n); + return end(); + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); return const_iterator(_M_find_node_tr(__bkt, __k, __code)); @@ -1782,9 +1839,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__unique_keys::value) return 1; - // All equivalent values are next to each other, if we find a - // non-equivalent value after an equivalent one it means that we won't - // find any new equivalent value. size_type __result = 1; for (auto __ref = __it++; __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur); @@ -1806,15 +1860,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_count_tr(const _Kt& __k) const -> size_type { + if (size() <= __small_size_threshold()) + { + size_type __result = 0; + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + { + if (this->_M_key_equals_tr(__k, *__n)) + { + ++__result; + continue; + } + + if (__result) + break; + } + + return __result; + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); auto __n = _M_find_node_tr(__bkt, __k, __code); if (!__n) return 0; - // All equivalent values are next to each other, if we find a - // non-equivalent value after an equivalent one it means that we won't - // find any new equivalent value. iterator __it(__n); size_type __result = 1; for (++__it; @@ -1844,9 +1913,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__unique_keys::value) return { __beg, __ite }; - // All equivalent values are next to each other, if we find a - // non-equivalent value after an equivalent one it means that we won't - // find any new equivalent value. while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur)) ++__ite; @@ -1871,9 +1937,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__unique_keys::value) return { __beg, __ite }; - // All equivalent values are next to each other, if we find a - // non-equivalent value after an equivalent one it means that we won't - // find any new equivalent value. while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur)) ++__ite; @@ -1892,6 +1955,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_equal_range_tr(const _Kt& __k) -> pair { + if (size() <= __small_size_threshold()) + { + __node_ptr __n, __beg = nullptr; + for (__n = _M_begin(); __n; __n = __n->_M_next()) + { + if (this->_M_key_equals_tr(__k, *__n)) + { + if (!__beg) + __beg = __n; + continue; + } + + if (__beg) + break; + } + + return { iterator(__beg), iterator(__n) }; + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); auto __n = _M_find_node_tr(__bkt, __k, __code); @@ -1899,9 +1981,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__n) return { __ite, __ite }; - // All equivalent values are next to each other, if we find a - // non-equivalent value after an equivalent one it means that we won't - // find any new equivalent value. auto __beg = __ite++; while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) ++__ite; @@ -1920,6 +1999,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_equal_range_tr(const _Kt& __k) const -> pair { + if (size() <= __small_size_threshold()) + { + __node_ptr __n, __beg = nullptr; + for (__n = _M_begin(); __n; __n = __n->_M_next()) + { + if (this->_M_key_equals_tr(__k, *__n)) + { + if (!__beg) + __beg = __n; + continue; + } + + if (__beg) + break; + } + + return { const_iterator(__beg), const_iterator(__n) }; + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); auto __n = _M_find_node_tr(__bkt, __k, __code); @@ -1927,9 +2025,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__n) return { __ite, __ite }; - // All equivalent values are next to each other, if we find a - // non-equivalent value after an equivalent one it means that we won't - // find any new equivalent value. auto __beg = __ite++; while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) ++__ite; @@ -2058,7 +2153,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First build the node to get access to the hash code _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); - if (size() <= __small_size_threshold()) + const size_type __size = size(); + if (__size <= __small_size_threshold()) { for (auto __it = _M_begin(); __it; __it = __it->_M_next()) if (this->_M_key_equals(__k, *__it)) @@ -2068,7 +2164,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); - if (size() > __small_size_threshold()) + if (__size > __small_size_threshold()) if (__node_ptr __p = _M_find_node(__bkt, __k, __code)) // There is already an equivalent node, no insertion return { iterator(__p), false }; @@ -2231,7 +2327,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _NodeGenerator& __node_gen) -> pair { - if (size() <= __small_size_threshold()) + const size_type __size = size(); + if (__size <= __small_size_threshold()) for (auto __it = _M_begin(); __it; __it = __it->_M_next()) if (this->_M_key_equals_tr(__k, *__it)) return { iterator(__it), false }; @@ -2239,7 +2336,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hash_code __code = this->_M_hash_code_tr(__k); size_type __bkt = _M_bucket_index(__code); - if (size() > __small_size_threshold()) + if (__size > __small_size_threshold()) if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code)) return { iterator(__node), false }; From patchwork Thu Nov 23 21:59:03 2023 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: 1867986 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=OtaUoYUN; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsV03FCWz1yS0 for ; Fri, 24 Nov 2023 08:59:52 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 618DB3838F29 for ; Thu, 23 Nov 2023 21:59:49 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x32e.google.com (mail-wm1-x32e.google.com [IPv6:2a00:1450:4864:20::32e]) by sourceware.org (Postfix) with ESMTPS id 415C9385E449; Thu, 23 Nov 2023 21:59:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 415C9385E449 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 415C9385E449 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::32e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776752; cv=none; b=gx2N2WdL+Oh6fxVKW+hRWOQl3ml3nEoW/gicr5ZVbziatCu2CLOK1MiGutvhe2KHeKB1mnVS8Ek4LBoYAbwXbyF7QnuWILFfvN+p7VJHnaSSbMNp7QvFZQyY8dbmkdwJjjAf8+xMmKATlE2IQ4EXKqD7ALqVtMfaTs+QrkpN+7s= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776752; c=relaxed/simple; bh=3kIgpqVCpddrjE/C2Fi1wlxHvco1EB/m/hv7X7n3R5E=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=sSlWlLWOjuWKIvruO2nWC7vMKAa64P4XJQyPhM1J1F7+NziA2eKSuff5W9fFoF6NJ6xUtwVn7MevTUaysKrSe8c5O8adKFj0q8YKhqm9rPlb8ArAl8RlJmUOXWgI9MuBXzhX35+17GWfupMyaQtniSTlEkEtr7VgTwNjYchKM6Q= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x32e.google.com with SMTP id 5b1f17b1804b1-40b30308c67so8846675e9.0; Thu, 23 Nov 2023 13:59:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776745; x=1701381545; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=++R3xHiXiZVILwc0f1OXVd7xn/bHtLNzEmZWFUbiS8w=; b=OtaUoYUNVwEaNImDRQyZy6g65ETjoABLdmxi0b8SsWK1/szh2oM9TXtLlKXkXUGfXl jRP6kns3TePCRXLMxI0B1tjyOWdViEzfTc6CwNEuUJMPz7neMEJEMTXzj77IpAkzrVyP XFhDmgk+UXpjf41ZukrMZe87APaFDyVhgoJBCDuO1nHYBRrjiZ4FhlxTUZDK45ZL4xs+ aj8EtyR7AZWtl4pzdCgsdAtVfxBzO4slJKy9iWceMey8rBt9vg+Uv6kK5od85cniMDAK aQmTupgfT13a0s2VfxbkT9bb7V1d0amrwLjKJ/kWFTihheTM1Lu8wZwqllXJz9ivwdQJ iZoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776745; x=1701381545; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=++R3xHiXiZVILwc0f1OXVd7xn/bHtLNzEmZWFUbiS8w=; b=dLa2ci+UEdzvGk387zfQ90HSLV+YnyFBEv2NPK+ezEIOrSMQ4aBqx1s2ttfxv2GTFP EpV/osa3+QHKhq/gttWBdzNjFOpONzD/sl0BTqJNk9TseVr8GFMhAZ+xYDBXIQfSsp/3 +N8Gfw7PTH8EeVbyDi1fb/2qOurXesmkUg8Xr6XT8YkrBPZlwwnzSEdZ+lA+L0HqJrOB 3Fxp9heNnkNjqeCafZGYrLjKe7om+OjYdy1CVTWV3N+TYp0urk/e91dlLHhw2s78uHWt RsTTgOBQFtm36U9SKxvpNluXyjFdGwtv99nadTG5WMrtqvKq4/u2R8Nu1G2Y4l1/d2uQ +eXg== X-Gm-Message-State: AOJu0YxFtgWxJwOdxvG2SMOTFZw1CHCu8OHJZE/QGYrd2i+i/XgtXdzq dr9l4Qp1veIxGsLXOveGnTaTXnyV6Ek= X-Google-Smtp-Source: AGHT+IHw3RXzxrHumO0PLCij09Fx4mBvbjVE0KusBHHue8zL8GHu36J5whrPoL84poRm2Peb0CjQoQ== X-Received: by 2002:a05:600c:458d:b0:405:4776:735a with SMTP id r13-20020a05600c458d00b004054776735amr649859wmo.2.1700776744986; Thu, 23 Nov 2023 13:59:04 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.59.03 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:59:04 -0800 (PST) Message-ID: Date: Thu, 23 Nov 2023 22:59:03 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 5/5][_Hashtable] Prefer to insert after last node To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org libstdc++: [_Hashtable] Prefer to insert after last node     When inserting an element into an empty bucket we currently insert the new node     after the before-begin node so in first position. The drawback of doing this is     that we are forced to update the bucket that was containing this before-begin     node to point to the newly inserted node. To do so we need at best to do a modulo     to find this bucket and at worst, when hash code is not cached, also compute it.     To avoid this side effect it is better to insert after the last node. To do so     we are introducing a helper type _HintPolicy that have 3 resposibilities.     1. When the gnu versioned namespace is used we add a _M_last member to _Hashtable,     _HintPolicy is then in charge of maintaining it. For this purpose _HintPolicy is     using the RAII pattern, it resets the _M_last at destruction level. It also maintain     its own _M_last, all mutable operations are updating it when needed.     2. When the gnu versioned namespace is not used _HintPolicy will still maintain its     _M_last member using initially the user provided hint if any and if it is actually     the container last node that is to say a dereferenceable node with its next node being     null. All mutable operations can also update the contextual _HintPolicy instance     whenever they detect the last node during their process.     3. As long as we haven't been able to detect the container last node _HintPolicy     is used to keep a cache of the before-begin bucket index so that we do not need to     compute it afterward for example in the context of range insertion.     libstdc++-v3/ChangeLog:             * include/bits/hashtable.h [_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container last node.             (_Hashtable<>::_HintPolicy): New.             (_Hashtable<>::_M_get_hint(__node_ptr)): New.             (_Hashtable<>::_M_get_hint_policy(__node_ptr)): New. (_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.             (_Hashtable<>::_M_set_last(__node_ptr)): New.             (_Hashtable<>::_M_get_last()): New.             (_Hashtable<>::_M_compute_hash_code(__node_ptr, const key_type&)): Remove.             (_Hashtable<>::_InsertInfo): New struct.             (_Hashtable<>::_M_get_insert_info): New, return latter. (_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a _HintPolicy.             (_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy& parameter and use it             to optimize insertion in an empty bucket.             (_Hashtable<>::_M_insert_unique_node): Add _HintPolicy& parameter.             (_Hashtable<>::_M_insert_multi_node): Likewise and add _InsertInfo parameter. (_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New. (_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.             (_Hashtable<>::_M_emplace): Adapt to use latters.             (_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.             (_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy& parameter.             (_Hashtable<>::_M_insert): Adapt to use latter.             (_Hashtable<>::emplace_hint(const_iterator, _Args&&...)): Adapt.             (_hashtable<>::rehash(size_type)): Adapt.             (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):             Add hint parameter, adapt to use it for _HintPolicy instantiation.             (_Hashtable<>::_M_reinsert_node_multi): Likewise.             (_Hashtable<>::_M_merge_unique): Adapt.             (_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.             (_Hashtable<>::_Hashtable<_InputIte>()): Adapt.             (_Hashtable<>::_M_assign): Call _M_set_last.             (_Hashtable<>::_M_reset()): Reset _M_last. (_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, true_type)): Copy _M_last.             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, false_type)): Copy _M_last.             (_Hashtable<>::_M_insert_range): Adapt.             (_Hashtable<>::_M_erase): Call _M_check_for_last.             (_Hashtable<>::erase): Likewise.             * include/bits/hashtable_policy.h:             (_Map_base<>::operator[](const key_type&)): Use hint policy.             (_Map_base<>::operator[](key_type&&)): Likewise.             (_Insert_base<>::insert(const_iterator, const value_type&)): Likewise using hint.             (_Insert_base<>::try_emplace): Likewise. (_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)): Use hint policy. (_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)): Use hint policy.             (_Insert<>::insert(const_iterator, value_type&&)): Likewise.             * include/bits/unordered_map.h (unordered_map<>::insert(node_type&&)): Pass cend as             hint.             (unordered_map<>::insert(const_iterator, node_type&&)): Adapt to use hint.             * include/bits/unordered_set.h (unordered_set<>::insert(node_type&&)): Pass cend as             hint.             (unordered_set<>::insert(const_iterator, node_type&&)): Adapt to use hint.             * testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt implementation             specific tests. Tested under Linux x64 Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index aec77c34a58..d758b054b00 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -403,6 +403,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // numerous checks in the code to avoid 0 modulus. __node_base_ptr _M_single_bucket = nullptr; +#if _GLIBCXX_INLINE_VERSION + // The last container node to optimize insertion in empty buckets. + __node_ptr _M_last = nullptr; +#endif + + class _HintPolicy + { + _Hashtable& _M_htb; + __node_ptr _M_last; + std::size_t _M_bbegin_index; + bool _M_initialized = false; + + public: + _HintPolicy(_Hashtable& __htbl, __node_ptr __last) + : _M_htb(__htbl), _M_last(__last) + { } + +#if _GLIBCXX_INLINE_VERSION + ~_HintPolicy() + { _M_htb._M_last = _M_last; } +#endif + + std::size_t + _M_get_bbegin_bkt(__node_ptr __n) const + { + if (!_M_initialized) + return _M_htb._M_bucket_index(*__n); + return _M_bbegin_index; + } + + void + _M_store_bbegin_bkt(std::size_t __bkt) + { + _M_bbegin_index = __bkt; + _M_initialized = true; + } + + constexpr __node_ptr + _M_get_hint() + { return _M_last; } + + void + _M_set_last(__node_ptr __n) + { _M_last = __n; } + + void + _M_checked_set(__node_ptr __n) + { + if (!__n || !__n->_M_nxt) + _M_last = __n; + } + }; + void _M_update_bbegin() { @@ -425,6 +478,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_uses_single_bucket() const { return _M_uses_single_bucket(_M_buckets); } + __node_ptr + _M_get_hint([[maybe_unused]] __node_ptr __usr_hint = nullptr) const + { +#if _GLIBCXX_INLINE_VERSION + return _M_last; +#else + return __usr_hint && !__usr_hint->_M_nxt ? __usr_hint : nullptr; +#endif + } + + _HintPolicy + _M_get_hint_policy(__node_ptr __usr_hint = nullptr) + { return _HintPolicy(*this, _M_get_hint(__usr_hint)); } + + void + _M_check_for_last([[maybe_unused]] __node_base_ptr __prev_n) + { +#if _GLIBCXX_INLINE_VERSION + if (!__prev_n->_M_nxt) + { + _M_last = __prev_n == &_M_before_begin + ? nullptr + : static_cast<__node_ptr>(__prev_n); + } +#endif + } + + void + _M_set_last([[maybe_unused]] __node_ptr __n) + { +#if _GLIBCXX_INLINE_VERSION + _M_last = __n; +#endif + } + + constexpr __node_ptr + _M_get_last() + { +#if _GLIBCXX_INLINE_VERSION + return _M_last; +#else + return nullptr; +#endif + } + static constexpr size_t __small_size_threshold() noexcept { @@ -612,11 +710,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // We consider that all elements of __l are going to be inserted. auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size()); + auto __hint_policy = _M_get_hint_policy(); + // Do not shrink to keep potential user reservation. if (_M_bucket_count < __l_bkt_count) - rehash(__l_bkt_count); + _M_rehash(__hint_policy, __l_bkt_count); - _M_insert_range(__l.begin(), __l.end(), __roan); + _M_insert_range(__l.begin(), __l.end(), __hint_policy, __roan); return *this; } @@ -838,30 +938,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert a node at the beginning of a bucket. void - _M_insert_bucket_begin(size_type __bkt, __node_ptr __node) + _M_insert_bucket_begin(_HintPolicy& __hint_policy, + size_type __bkt, __node_ptr __node) { + __node_base_ptr __prev; if (_M_buckets[__bkt]) { // Bucket is not empty, we just need to insert the new node // after the bucket before begin. - __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; - _M_buckets[__bkt]->_M_nxt = __node; + __prev = _M_buckets[__bkt]; + if (!__prev->_M_nxt) + __hint_policy._M_set_last(__node); } else { - // The bucket is empty, the new node is inserted at the - // beginning of the singly-linked list and the bucket will - // contain _M_before_begin pointer. - __node->_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __node; - - if (__node->_M_nxt) - // We must update former begin bucket that is pointing to - // _M_before_begin. - _M_buckets[_M_bucket_index(*__node->_M_next())] = __node; - - _M_buckets[__bkt] = &_M_before_begin; + // If we have a hint, the last container node, insert after. + __node_ptr __hint = __hint_policy._M_get_hint(); + if (__hint) + { + __prev = __hint; + __hint_policy._M_set_last(__node); + } + else + { + // The bucket is empty, the new node is inserted at the + // beginning of the singly-linked list and the bucket will + // contain _M_before_begin pointer. + __prev = &_M_before_begin; + + if (__prev->_M_nxt) + { + // We must update former begin bucket that is pointing to + // _M_before_begin. + size_type __bb_bkt = __hint_policy._M_get_bbegin_bkt( + static_cast<__node_ptr>(__prev->_M_nxt)); + _M_buckets[__bb_bkt] = __node; + } + else + __hint_policy._M_set_last(__node); + + __hint_policy._M_store_bbegin_bkt(__bkt); + } + + _M_buckets[__bkt] = __prev; } + + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } // Remove the bucket first node @@ -887,44 +1010,76 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base_ptr _M_get_previous_node(size_type __bkt, __node_ptr __n); - pair<__node_ptr, __hash_code> - _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const; + struct _InsertInfo + { + __node_base_ptr _M_prev; + __node_ptr _M_equi_n; + __hash_code _M_code; + }; + + _InsertInfo + _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k, + __node_ptr __n = nullptr) const; // Insert node __n with hash code __code, in bucket __bkt if no // rehash (assumes no element with same key already present). // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_unique_node(size_type __bkt, __hash_code, + _M_insert_unique_node(_HintPolicy& __hint_policy, + size_type __bkt, __hash_code, __node_ptr __n, size_type __n_elt = 1); - // Insert node __n with key __k and hash code __code. + // Insert node __n after __prev if any. // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_multi_node(__node_ptr __hint, - __hash_code __code, __node_ptr __n); + _M_insert_multi_node(_HintPolicy& __hint_policy, + const _InsertInfo& __info, __node_ptr __n); + + template + std::pair + _M_emplace_unique(_HintPolicy&, _Args&&... __args); + + template + iterator + _M_emplace_multi(_HintPolicy&, _Args&&... __args); template std::pair - _M_emplace(true_type __uks, _Args&&... __args); + _M_emplace(true_type /*__uks*/, _Args&&... __args) + { + auto __hint_policy = _M_get_hint_policy(); + return _M_emplace_unique(__hint_policy, + std::forward<_Args>(__args)...); + } template iterator - _M_emplace(false_type __uks, _Args&&... __args) - { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } + _M_emplace(false_type /*__uks*/, _Args&&... __args) + { + auto __hint_policy = _M_get_hint_policy(); + return _M_emplace_multi(__hint_policy, + std::forward<_Args>(__args)...); + } - // Emplace with hint, useless when keys are unique. template iterator - _M_emplace(const_iterator, true_type __uks, _Args&&... __args) - { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; } + _M_emplace(_HintPolicy& __hint_policy, + true_type /*__uks*/, _Args&&... __args) + { + return _M_emplace_unique(__hint_policy, + std::forward<_Args>(__args)...).first; + } template iterator - _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + _M_emplace(_HintPolicy& __hint_policy, + false_type /*__uks*/, _Args&&... __args) + { return _M_emplace_multi(__hint_policy, std::forward<_Args>(__args)...); } template std::pair - _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&); + _M_insert_unique(_HintPolicy& __hint_policy, + _Kt&&, _Arg&&, _NodeGenerator&); template static __conditional_t< @@ -944,9 +1099,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen) + _M_insert_unique_aux(_HintPolicy& __hint_policy, + _Arg&& __arg, _NodeGenerator& __node_gen) { - return _M_insert_unique( + return _M_insert_unique(__hint_policy, _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), std::forward<_Arg>(__arg), __node_gen); } @@ -956,9 +1112,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, true_type /* __uks */) { + auto __hint_policy = _M_get_hint_policy(); using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert_unique_aux( + return _M_insert_unique_aux(__hint_policy, __to_value{}(std::forward<_Arg>(__arg)), __node_gen); } @@ -967,32 +1124,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, false_type __uks) { + auto __hint_policy = _M_get_hint_policy(); using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert(cend(), + return _M_insert(__hint_policy, __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks); } - // Insert with hint, not used when keys are unique. + // Insert with hint when keys are unique. template iterator - _M_insert(const_iterator, _Arg&& __arg, - _NodeGenerator& __node_gen, true_type __uks) + _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg, + _NodeGenerator& __node_gen, true_type /* __uks */) { - return - _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first; + using __to_value + = __detail::_ConvertToValueType<_ExtractKey, value_type>; + return _M_insert_unique_aux(__hint_policy, + __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first; } // Insert with hint when keys are not unique. template iterator - _M_insert(const_iterator, _Arg&&, + _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg, _NodeGenerator&, false_type __uks); template void _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGenerator&); + _HintPolicy&, _NodeGenerator&); size_type _M_erase(true_type __uks, const key_type&); @@ -1014,7 +1174,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator emplace_hint(const_iterator __hint, _Args&&... __args) { - return _M_emplace(__hint, __unique_keys{}, + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); + return _M_emplace(__hint_policy, __unique_keys{}, std::forward<_Args>(__args)...); } @@ -1041,7 +1202,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Set number of buckets keeping it appropriate for container's number // of elements. - void rehash(size_type __bkt_count); + void rehash(size_type __bkt_count) + { + auto __hint_policy = _M_get_hint_policy(); + _M_rehash(__hint_policy, __bkt_count); + } // DR 1189. // reserve, if present, comes from _Rehash_base. @@ -1049,7 +1214,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus > 201402L /// Re-insert an extracted node into a container with unique keys. insert_return_type - _M_reinsert_node(node_type&& __nh) + _M_reinsert_node(const_iterator __hint, node_type&& __nh) { insert_return_type __ret; if (__nh.empty()) @@ -1058,14 +1223,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __nh.get_allocator()); + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); __node_ptr __n = nullptr; const key_type& __k = __nh._M_key(); const size_type __size = size(); if (__size <= __small_size_threshold()) { - for (__n = _M_begin(); __n; __n = __n->_M_next()) - if (this->_M_key_equals(__k, *__n)) - break; + __node_ptr __last_n = nullptr; + for (__n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) + { + if (this->_M_key_equals(__k, *__n)) + break; + } + + if (!__n) + __hint_policy._M_set_last(__last_n); } __hash_code __code; @@ -1086,8 +1259,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } else { - __ret.position - = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + __ret.position = _M_insert_unique_node( + __hint_policy, __bkt, __code, __nh._M_ptr); __nh._M_ptr = nullptr; __ret.inserted = true; } @@ -1104,10 +1277,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); const key_type& __k = __nh._M_key(); - auto __code = this->_M_hash_code(__k); - auto __ret - = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr); + auto __info = _M_get_insert_info(__hint_policy, __k); + auto __ret = _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr); __nh._M_ptr = nullptr; return __ret; } @@ -1147,6 +1320,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return this->_M_hash_code(__k); } + template + _InsertInfo + _M_get_insert_info(const _H2&, _HintPolicy& __hint_policy, + __node_ptr __n, const key_type& __k) + { + if constexpr (std::is_same_v<_H2, _Hash>) + if constexpr (std::is_empty_v<_Hash>) + return _M_get_insert_info(__hint_policy, __k, __n); + + return _M_get_insert_info(__hint_policy, __k); + } + public: // Extract a node. node_type @@ -1178,6 +1363,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + auto __hint_policy = _M_get_hint_policy(); auto __n_elt = __src.size(); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { @@ -1186,8 +1372,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = _ExtractKey{}(*__pos); if (__size <= __small_size_threshold()) { + __node_ptr __last_n = nullptr; bool __found = false; - for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + for (auto __n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) if (this->_M_key_equals(__k, *__n)) { __found = true; @@ -1200,6 +1388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION --__n_elt; continue; } + else + __hint_policy._M_set_last(__last_n); } __hash_code __code @@ -1209,7 +1399,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION || _M_find_node(__bkt, __k, __code) == nullptr) { auto __nh = __src.extract(__pos); - _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); + _M_insert_unique_node( + __hint_policy, __bkt, __code, __nh._M_ptr, __n_elt); __nh._M_ptr = nullptr; __n_elt = 1; } @@ -1227,27 +1418,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); - __node_ptr __hint = nullptr; + auto __hint_policy = _M_get_hint_policy(); 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 - = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur); + auto __info = _M_get_insert_info(__src.hash_function(), + __hint_policy, __pos._M_cur, __k); auto __nh = __src.extract(__pos); - __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; + _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr); __nh._M_ptr = nullptr; } } #endif // C++17 private: + void _M_rehash(_HintPolicy&, size_type __bkt_count); + // Helper rehash method used when keys are unique. - void _M_rehash(size_type __bkt_count, true_type __uks); + void _M_rehash(_HintPolicy&, size_type __bkt_count, true_type __uks); // Helper rehash method used when keys can be non-unique. - void _M_rehash(size_type __bkt_count, false_type __uks); + void _M_rehash(_HintPolicy&, size_type __bkt_count, false_type __uks); }; // Definitions of class template _Hashtable's out-of-line member functions. @@ -1308,8 +1501,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __bkt_count; } + auto __hint_policy = _M_get_hint_policy(); __alloc_node_gen_t __node_gen(*this); - _M_insert_range(__f, __l, __node_gen); + _M_insert_range(__f, __l, __hint_policy, __node_gen); } template_M_node_allocator(), __ht._M_node_allocator()); + _M_set_last(__ht._M_get_last()); // Fix bucket containing the _M_before_begin pointer that can't be moved. _M_update_bbegin(); + __ht._M_reset(); } @@ -1575,6 +1774,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_before_begin(__ht._M_before_begin._M_nxt), _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) +#if _GLIBCXX_INLINE_VERSION + , _M_last(__ht._M_last) +#endif { // Update buckets if __ht is using its single bucket. if (__ht._M_uses_single_bucket()) @@ -1638,6 +1840,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else _M_buckets = __ht._M_buckets; + _M_set_last(__ht._M_get_last()); + // Fix bucket containing the _M_before_begin pointer that can't be // moved. _M_update_bbegin(__ht._M_begin()); @@ -2147,7 +2351,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_emplace(true_type /* __uks */, _Args&&... __args) + _M_emplace_unique(_HintPolicy& __hint_policy, _Args&&... __args) -> pair { // First build the node to get access to the hash code @@ -2156,10 +2360,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const size_type __size = size(); if (__size <= __small_size_threshold()) { - for (auto __it = _M_begin(); __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) + __node_ptr __last_n = nullptr; + for (auto __n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) // There is already an equivalent node, no insertion - return { iterator(__it), false }; + return { iterator(__n), false }; + + __hint_policy._M_set_last(__last_n); } __hash_code __code = this->_M_hash_code(__k); @@ -2170,7 +2378,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { iterator(__p), false }; // Insert the node - auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); + auto __pos = _M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return { __pos, true }; } @@ -2183,17 +2392,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_emplace(const_iterator __hint, false_type /* __uks */, - _Args&&... __args) + _M_emplace_multi(_HintPolicy& __hint_policy, _Args&&... __args) -> iterator { // First build the node to get its hash code. _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); - auto __res = this->_M_compute_hash_code(__hint._M_cur, __k); - auto __pos - = _M_insert_multi_node(__res.first, __res.second, __node._M_node); + auto __info = _M_get_insert_info(__hint_policy, __k); + auto __pos = _M_insert_multi_node(__hint_policy, __info, __node._M_node); __node._M_node = nullptr; return __pos; } @@ -2205,26 +2412,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const - -> pair<__node_ptr, __hash_code> + _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k, + __node_ptr __equi_n) const + -> _InsertInfo { if (size() <= __small_size_threshold()) { - if (__hint) - { - for (auto __it = __hint; __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - return { __it, this->_M_hash_code(*__it) }; - } - - for (auto __it = _M_begin(); __it != __hint; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - return { __it, this->_M_hash_code(*__it) }; + __node_ptr __last_n = nullptr; + __node_base_ptr __prev + = const_cast<__node_base_ptr>(&_M_before_begin); + for (auto __n = static_cast<__node_ptr>(__prev->_M_nxt); __n; + __prev = __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + return + { + __prev, __n, + __hash_cached::value ? this->_M_hash_code(*__n) : 0 + }; - __hint = nullptr; + __hint_policy._M_set_last(__last_n); } - return { __hint, this->_M_hash_code(__k) }; + return + { + nullptr, nullptr, + __equi_n ? this->_M_hash_code(*__equi_n) : this->_M_hash_code(__k) + }; } template:: - _M_insert_unique_node(size_type __bkt, __hash_code __code, + _M_insert_unique_node(_HintPolicy& __hint_policy, + size_type __bkt, __hash_code __code, __node_ptr __node, size_type __n_elt) -> iterator { @@ -2245,7 +2459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { - _M_rehash(__do_rehash.second, true_type{}); + _M_rehash(__hint_policy, __do_rehash.second, true_type{}); __bkt = _M_bucket_index(__code); } @@ -2253,7 +2467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION this->_M_store_code(*__node, __code); // Always insert at the beginning of the bucket. - _M_insert_bucket_begin(__bkt, __node); + _M_insert_bucket_begin(__hint_policy, __bkt, __node); ++_M_element_count; return iterator(__node); } @@ -2265,8 +2479,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__node_ptr __hint, - __hash_code __code, __node_ptr __node) + _M_insert_multi_node(_HintPolicy& __hint_policy, + const _InsertInfo& __info, __node_ptr __node) -> iterator { __rehash_guard_t __rehash_guard(_M_rehash_policy); @@ -2274,42 +2488,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); if (__do_rehash.first) - _M_rehash(__do_rehash.second, false_type{}); + _M_rehash(__hint_policy, __do_rehash.second, false_type{}); __rehash_guard._M_guarded_obj = nullptr; + auto __code = __info._M_code; this->_M_store_code(*__node, __code); const key_type& __k = _ExtractKey{}(__node->_M_v()); - size_type __bkt = _M_bucket_index(__code); + auto __prev = __info._M_prev; + const bool __has_prev = __prev != nullptr; + size_type __bkt; // Find the node before an equivalent one or use hint if it exists and // if it is equivalent. - __node_base_ptr __prev - = __builtin_expect(__hint != nullptr, false) - && this->_M_equals(__k, __code, *__hint) - ? __hint - : _M_find_before_node(__bkt, __k, __code); + if (!__has_prev) + { + __bkt = _M_bucket_index(__code); + __prev = _M_find_before_node(__bkt, __k, __code); + } if (__prev) { // Insert after the node before the equivalent one. __node->_M_nxt = __prev->_M_nxt; __prev->_M_nxt = __node; - if (__builtin_expect(__prev == __hint, false)) - // hint might be the last bucket node, in this case we need to - // update next bucket. - if (__node->_M_nxt - && !this->_M_equals(__k, __code, *__node->_M_next())) - { - size_type __next_bkt = _M_bucket_index(*__node->_M_next()); - if (__next_bkt != __bkt) - _M_buckets[__next_bkt] = __node; - } + + // __hint might be the last bucket node, in this case we need to + // update next bucket. + if (__has_prev && __node->_M_nxt != __info._M_equi_n) + { + const auto __nxt = __node->_M_next(); + if (!this->_M_equals(__k, __code, *__nxt)) + { + size_type __next_bkt = _M_bucket_index(*__nxt); + if (__next_bkt != _M_bucket_index(__code)) + _M_buckets[__next_bkt] = __node; + } + } + + __hint_policy._M_checked_set(__node); } else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements' relative positions. - _M_insert_bucket_begin(__bkt, __node); + { + // The inserted node has no equivalent in the hashtable. We must + // insert the new node at the beginning of the bucket to preserve + // equivalent elements' relative positions. + _M_insert_bucket_begin(__hint_policy, __bkt, __node); + } + ++_M_element_count; return iterator(__node); } @@ -2323,15 +2548,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_unique(_Kt&& __k, _Arg&& __v, + _M_insert_unique(_HintPolicy& __hint_policy, _Kt&& __k, _Arg&& __v, _NodeGenerator& __node_gen) -> pair { const size_type __size = size(); if (__size <= __small_size_threshold()) - for (auto __it = _M_begin(); __it; __it = __it->_M_next()) - if (this->_M_key_equals_tr(__k, *__it)) - return { iterator(__it), false }; + { + __node_ptr __last_n = nullptr; + for (auto __n = _M_begin(); __n; + __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals_tr(__k, *__n)) + return { iterator(__n), false }; + + __hint_policy._M_set_last(__last_n); + } __hash_code __code = this->_M_hash_code_tr(__k); size_type __bkt = _M_bucket_index(__code); @@ -2346,8 +2577,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_gen), this }; + auto __pos - = _M_insert_unique_node(__bkt, __code, __node._M_node); + = _M_insert_unique_node(__hint_policy, __bkt, __code, __node._M_node); __node._M_node = nullptr; return { __pos, true }; } @@ -2361,20 +2593,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert(const_iterator __hint, _Arg&& __v, - _NodeGenerator& __node_gen, - false_type /* __uks */) + _M_insert(_HintPolicy& __hint_policy, _Arg&& __v, + _NodeGenerator& __node_gen, false_type /* __uks */) -> iterator { // First allocate new node so that we don't do anything if it throws. - _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; + _Scoped_node __node { __node_gen(std::forward<_Arg>(__v)), this }; // Second compute the hash code so that we don't rehash if it throws. - auto __res = this->_M_compute_hash_code( - __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v())); - - auto __pos - = _M_insert_multi_node(__res.first, __res.second, __node._M_node); + auto __info = + _M_get_insert_info(__hint_policy, + _ExtractKey{}(__node._M_node->_M_v())); + auto __pos = _M_insert_multi_node(__hint_policy, + __info, __node._M_node); __node._M_node = nullptr; return __pos; } @@ -2388,10 +2619,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGenerator& __node_gen) + _HintPolicy& __hint_policy, _NodeGenerator& __node_gen) { for (; __first != __last; ++__first) - _M_insert(*__first, __node_gen, __unique_keys{}); + _M_insert(__hint_policy, *__first, __node_gen, __unique_keys{}); } template_M_next()); this->_M_deallocate_node(__n); --_M_element_count; - + _M_check_for_last(__prev_n); return __result; } @@ -2547,7 +2778,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); else if (__n_last_bkt != __bkt) _M_buckets[__n_last_bkt] = __prev_n; + __prev_n->_M_nxt = __n_last; + _M_check_for_last(__prev_n); return __result; } @@ -2595,6 +2828,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__n && (__n_bkt != __bkt || __is_bucket_begin)) _M_buckets[__n_bkt] = __prev_n; __prev_n->_M_nxt = __n; + _M_check_for_last(__prev_n); return iterator(__n); } @@ -2612,6 +2846,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count * sizeof(__node_base_ptr)); _M_element_count = 0; _M_before_begin._M_nxt = nullptr; + _M_set_last(nullptr); } template:: - rehash(size_type __bkt_count) + _M_rehash(_HintPolicy& __hint_policy, size_type __bkt_count) { __rehash_guard_t __rehash_guard(_M_rehash_policy); __bkt_count @@ -2631,7 +2866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__bkt_count != _M_bucket_count) { - _M_rehash(__bkt_count, __unique_keys{}); + _M_rehash(__hint_policy, __bkt_count, __unique_keys{}); __rehash_guard._M_guarded_obj = nullptr; } } @@ -2644,9 +2879,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_rehash(size_type __bkt_count, true_type /* __uks */) + _M_rehash(_HintPolicy& __hint_policy, + size_type __bkt_count, true_type /* __uks */) { __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); + __node_ptr __prev_p = nullptr; __node_ptr __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; @@ -2670,12 +2907,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } + __prev_p = __p; __p = __next; } _M_deallocate_buckets(); _M_bucket_count = __bkt_count; _M_buckets = __new_buckets; + __hint_policy._M_set_last(__prev_p); } // Rehash when there can be equivalent elements, preserve their relative @@ -2687,7 +2926,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_rehash(size_type __bkt_count, false_type /* __uks */) + _M_rehash(_HintPolicy& __hint_policy, + size_type __bkt_count, false_type /* __uks */) { __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); __node_ptr __p = _M_begin(); @@ -2750,6 +2990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } } + __prev_p = __p; __prev_bkt = __bkt; __p = __next; @@ -2767,6 +3008,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_deallocate_buckets(); _M_bucket_count = __bkt_count; _M_buckets = __new_buckets; + __hint_policy._M_set_last(__prev_p); } #if __cplusplus > 201402L diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 9f775522cff..c8905f59289 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -848,8 +848,9 @@ namespace __detail std::tuple(__k), std::tuple<>() }; - auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h->_M_get_hint_policy(); + auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return __pos->second; } @@ -875,8 +876,9 @@ namespace __detail std::forward_as_tuple(std::move(__k)), std::tuple<>() }; - auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h->_M_get_hint_policy(); + auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return __pos->second; } @@ -964,13 +966,14 @@ namespace __detail insert(const_iterator __hint, const value_type& __v) { __hashtable& __h = _M_conjure_hashtable(); - __node_gen_type __node_gen(__h); - return __h._M_insert(__hint, __v, __node_gen, __unique_keys{}); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + __node_gen_type __node_gen(__h); + return __h._M_insert(__hint_policy, __v, __node_gen, __unique_keys{}); } template std::pair - try_emplace(const_iterator, _KType&& __k, _Args&&... __args) + try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args) { __hashtable& __h = _M_conjure_hashtable(); auto __code = __h._M_hash_code(__k); @@ -984,8 +987,9 @@ namespace __detail std::forward_as_tuple(std::forward<_KType>(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...) }; - auto __it - = __h._M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + auto __it = __h._M_insert_unique_node(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return { __it, true }; } @@ -1013,8 +1017,9 @@ namespace __detail true_type /* __uks */) { __hashtable& __h = _M_conjure_hashtable(); + auto __hint_policy = __h._M_get_hint_policy(); __node_gen_type __node_gen(__h); - __h._M_insert_range(__first, __last, __node_gen); + __h._M_insert_range(__first, __last, __hint_policy, __node_gen); } template_M_conjure_hashtable(); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); __node_gen_type __node_gen(__h); - return __h._M_insert(__hint, std::move(__v), __node_gen, + return __h._M_insert(__hint_policy, std::move(__v), __node_gen, __unique_keys{}); } }; @@ -1153,7 +1160,8 @@ namespace __detail insert(const_iterator __hint, _Pair&& __v) { __hashtable& __h = this->_M_conjure_hashtable(); - return __h._M_emplace(__hint, __unique_keys{}, + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + return __h._M_emplace(__hint_policy, __unique_keys{}, std::forward<_Pair>(__v)); } }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 1c99a83bc1e..e5df97c9229 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -443,12 +443,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Re-insert an extracted node. insert_return_type insert(node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)); } + { return _M_h._M_reinsert_node(cend(), std::move(__nh)); } /// Re-insert an extracted node. iterator - insert(const_iterator, node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)).position; } + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; } #endif // C++17 #ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index f3b0c078baa..915cd4fb700 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -504,12 +504,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Re-insert an extracted node. insert_return_type insert(node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)); } + { return _M_h._M_reinsert_node(cend(), std::move(__nh)); } /// Re-insert an extracted node. iterator - insert(const_iterator, node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)).position; } + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; } #endif // C++17 ///@{ diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc index d0ed60c6799..1db71b8f30b 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc @@ -40,11 +40,12 @@ void test01() VERIFY( it2 != m.end() ); VERIFY( it2 != it1 ); VERIFY( it2->second == 2 ); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); + it1 = it2; Pair p(0, 1); it2 = m.insert(it1, p); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); } struct hasher @@ -71,13 +72,13 @@ void test02() VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); auto it4 = m.insert(it1, Pair(0, 1)); - VERIFY( it4 == std::next(it1) ); + VERIFY( std::next(it4) == it1 ); VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 ); VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); Pair p(1, 1); it4 = m.insert(it2, p); - VERIFY( it4 == std::next(it2) ); + VERIFY( std::next(it4) == it2 ); VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 ); auto range = m.equal_range(0); VERIFY( std::distance(range.first, range.second) == 2 ); @@ -104,11 +105,12 @@ void test03() VERIFY( it2 != m.end() ); VERIFY( it2 != it1 ); VERIFY( it2->second == 2 ); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); + it1 = it2; Pair p(0, 1); it2 = m.emplace_hint(it1, p); - VERIFY( it2 == std::next(it1) ); + VERIFY( std::next(it2) == it1 ); } int main()