From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 90A3A387542F for ; Thu, 21 Dec 2023 21:55:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 90A3A387542F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 90A3A387542F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1703195730; cv=none; b=fdhZDzEhe+eEx8Lg7YCZUeZv7W+nQVLldh31psUbbOeM025a7zVhL97ZXAK8Dzp7+QLehaxwE0Px3Z79H8EijeSlbIWtdEXPzuEh97XZ931vrOicgSRLTmVRN+7wS6l7jOhAnts9rARaRHlA2gVGKnM+IFu53cps63Q+aSukNuI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1703195730; c=relaxed/simple; bh=KH6O7XFvhpLgiUrP7FjEzMynrYLDxnziNWE/uT4t8zg=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=WuJWP2WCXx4Ck/ip1UkzXZ5w/c5Nnl772nayCa/NDfnaLWMxjkk0tiChMe7XyBdhtcMmtlxCsX66K3+UUwVMwT5N027uXbwn/6CcNIGiEvrYyt+Z8OiKYd6vvLr6bmPdjXElaDjjaNXLaxPsARLG0ze7caQRwncPN7NXWjGIiAQ= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1703195727; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=MkNu5npuNEGCxAk1mlCtzlurfwjadfnY63QC+YeoXDs=; b=AkCKpGRyF6tVz3mksCKHCR7cxAsOiI87/jVkCS4Ce+tYjMeHaPYLgkVcNCEiLOCpaC5Mbg FyLrJNXxzZTJfvm/hPRDuA/uV4p+LLuDk0a+tz1izZM1KMvLFy2GK7Pr3jQXBMtBuPeiqo Ue1UNB617H7aYJsxq/NiQsV4Lq2aCu8= Received: from mail-yb1-f199.google.com (mail-yb1-f199.google.com [209.85.219.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-339-usEsUvr0MjOw5VQaVYcujQ-1; Thu, 21 Dec 2023 16:55:25 -0500 X-MC-Unique: usEsUvr0MjOw5VQaVYcujQ-1 Received: by mail-yb1-f199.google.com with SMTP id 3f1490d57ef6-dbdae873882so1434059276.3 for ; Thu, 21 Dec 2023 13:55:25 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1703195724; x=1703800524; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=MkNu5npuNEGCxAk1mlCtzlurfwjadfnY63QC+YeoXDs=; b=ize+qaLlU4yzWHlqeXAu2ZjJ128RpHxd91vcuf1U3U6bhgci9Ony8PguvWQGanlDp9 JQWu4iQv0E1OHplUQjYuXhqcVoIIX5lwLbhgv2/DyBHDBqSaLj2SHugxkL0RgyEfZTb+ 3/VnTgUYWOt1Hg8r2sTS7RnLy2KqXikwXptgd/oVVIunceiRdcA6KiEZ7mxwL3gYsJ19 DXomVu7rHeD39ChtUUjXt00MbeHLVqy9Z1drGQG0XEecOAkiQfG5En5yiO+ADtPx4J1U X75t/tKrZDUtEEtSj9BaG0gP1pLMlI9N2YsMm5HfSouUbrHneCeoJnEx0/U4FAHGOGf0 qDJQ== X-Gm-Message-State: AOJu0Yw4+9zQwFqV72Mm6bqvMLbah+rUe1iqB81j69C0fjnf8+pfEA4O eP8xQfcr1eVuE94H1Cjv/AoQj0MceqmVOfwe1ltN2OIFK3IcBCItph9tYrGhqPB2UMz4I9+IuxQ l7O4Om8EjG2vMkMk7iCQ2PAIA16pMyl7N7ZuBfyBjCvQ6zBr2WQ== X-Received: by 2002:a5b:d4d:0:b0:dbd:739c:48ef with SMTP id f13-20020a5b0d4d000000b00dbd739c48efmr380967ybr.19.1703195723987; Thu, 21 Dec 2023 13:55:23 -0800 (PST) X-Google-Smtp-Source: AGHT+IH6mK3lmt30fg+olHly1DxHEC9NyYZiPojvsL96qulEhu1e/gZapgxPVeHyrvtudvmMO5XYPU8/5rHOO4yLMvI= X-Received: by 2002:a5b:d4d:0:b0:dbd:739c:48ef with SMTP id f13-20020a5b0d4d000000b00dbd739c48efmr380959ybr.19.1703195723663; Thu, 21 Dec 2023 13:55:23 -0800 (PST) MIME-Version: 1.0 References: <84461179-cc39-4b74-8e61-b5199946f608@gmail.com> In-Reply-To: <84461179-cc39-4b74-8e61-b5199946f608@gmail.com> From: Jonathan Wakely Date: Thu, 21 Dec 2023 21:55:07 +0000 Message-ID: Subject: Re: [PATCH 5/5][_Hashtable] Prefer to insert after last node To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: "libstdc++" , gcc-patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-6.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: I think this should wait for the next stage 1. It's a big patch affecting the default -std mode (not just experimental C++20/23/26 material), and was first posted after the end of stage 1. Do we really need the changes for versioned namespace? How much difference does that extra member make to performance, compared with the version for the default config? On Wed, 20 Dec 2023 at 06:10, Fran=C3=A7ois Dumont w= rote: > > Here is a new version of this patch. > > The previous one had some flaws that were unnoticed by testsuite tests, > only the performance tests were spotting it. So I'm adding checks on the > consistency of the unordered containers in this patch. > > I also forget to signal that after this patch gnu versioned namespace > version is supposed to be bump. But I hope it's already the plan because > of the move to the cxx11 abi in this mode. > > Note for reviewer, after application of the patch, a 'git diff -b' is > much more readable. > > And some benches results: > > before: > > unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000 > inserts individually 19999990 calls 44r 44u 0s 95999760mem 0= pf > unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000 > inserts in range 20000000 calls 43r 43u 0s 95999760mem 0pf > unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X > inserts individually 19999990 calls 44r 44u 0s 95999760mem 0pf > unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X > inserts in range 20000000 calls 43r 43u 0s 95999760mem 0pf > unordered_set_range_insert.cc-thread hash code cached 2 X 1000000 > inserts individually 10000000 calls 30r 30u 0s 111999328mem > 0pf > unordered_set_range_insert.cc-thread hash code cached 2 X 1000000 > inserts in range 10000010 calls 33r 32u 0s 111999328mem 0pf > unordered_set_range_insert.cc-thread hash code cached 1000000 X > inserts individually 10000000 calls 30r 31u 0s 111999328mem > 0pf > unordered_set_range_insert.cc-thread hash code cached 1000000 X > inserts in range 10000010 calls 32r 32u 0s 111999328mem 0pf > > after: > > unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000 > inserts individually 19999990 calls 44r 44u 0s 95999760mem 0= pf > unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000 > inserts in range 10000020 calls 26r 25u 0s 95999760mem 0pf > unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X > inserts individually 19999990 calls 43r 44u 0s 95999760mem 0pf > unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X > inserts in range 10000020 calls 26r 26u 0s 95999760mem 0pf > unordered_set_range_insert.cc-thread hash code cached 2 X 1000000 > inserts individually 10000000 calls 35r 35u 0s 111999328mem > 0pf > unordered_set_range_insert.cc-thread hash code cached 2 X 1000000 > inserts in range 10000010 calls 32r 33u 0s 111999328mem 0pf > unordered_set_range_insert.cc-thread hash code cached 1000000 X > inserts individually 10000000 calls 31r 32u 0s 111999328mem > 0pf > unordered_set_range_insert.cc-thread hash code cached 1000000 X > inserts in range 10000010 calls 31r 31u 0s 111999328mem 0pf > > > 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 has 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<>::_LastNodeManager): New. > (_Hashtable<>::_M_get_last(__node_ptr)): New. > (_Hashtable<>::_M_get_last_node_mgr(__node_ptr)): New. > (_Hashtable<>::_M_check_for_last(__node_base_ptr)): New. > (_Hashtable<>::_M_set_last(__node_ptr)): New. > (_Hashtable<>::_M_compute_hash_code(__node_ptr, const > key_type&)): Remove. > (_Hashtable<>::operator=3D(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(__node_ptr, > __hash_code, __node_ptr)): Replace by... > (_Hashtable<>::_M_insert_multi_node(_HintPolicy&, const key_type&, > __node_ptr, __node_ptr)): ... this. > (_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. > * > testsuite/23_containers/unordered_map/consistency_check.cc: New test case= . > * > testsuite/23_containers/unordered_multimap/consistency_check.cc: New > test case. > * > testsuite/23_containers/unordered_multiset/consistency_check.cc: New > test case. > * > testsuite/23_containers/unordered_set/consistency_check.cc: New test case= . > * testsuite/libstdc++-prettyprinters/cxx11.cc (main): Adapt > expectations on element > order in unordered_map instance. >