From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yw1-x1132.google.com (mail-yw1-x1132.google.com [IPv6:2607:f8b0:4864:20::1132]) by sourceware.org (Postfix) with ESMTPS id 7533A3858413; Wed, 17 Jan 2024 08:11:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7533A3858413 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 7533A3858413 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::1132 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705479083; cv=none; b=PWV0OSKzyjou853hNVFCvZKp2PjcifTgc1Bq8nanhXjh4oDNb7LShjEAAmUOx2bRDOjCnyGxP2kkRhh9VMXWFdDDtGjaF/7VcuxDJqbjIDnGGj8v1wdVF0a6x6BlCQvQnC2X5mNUYfIyQjSiXZCrNnK9w64fj56/BzU+aqt/fz8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705479083; c=relaxed/simple; bh=o/g338ygzVvwcHY7NqODbJyq1xLcuKDW2esSGwBIoM8=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=obWnyj8ERvPSzf2UzfFOOqJ9dW0d1+Cr/u26HKPTuCxr/u+3zehGDtr1cTmSVOewUkyN0DtQEEZLCpXauHaEpxAVEhzG3Na/9+h2WSCM3daeWOJFoOyEZTPKJuwUJ2WIDNkOC2cc9irhWHxvmKo1kD0BLski4t+lwgdWEgsnG5Q= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-yw1-x1132.google.com with SMTP id 00721157ae682-5ed10316e22so98750907b3.3; Wed, 17 Jan 2024 00:11:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705479079; x=1706083879; darn=gcc.gnu.org; h=cc:to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=SDTtGec254DzLvzo9sUloqy8a2WgvjMp7TLbgiludEI=; b=VBqaOufz//ruDBqjB1lj8Vj5USVYeTwO/j8w6wm0DgG+dE/MvVu7uALmPRSEosIeuI pAgg1ukJl+WaHaqiISQHo/73r/5EPPbSsIkcv/4OlnkelRVoCISz0gh6fMLvluOsVMnE TWU6iF1IXXVOawJUxBZ75ObvLO6IaiFb9qG4yQeRJCOwMa/5B4UWmzm/37UwFXU54Yd6 gjJAutN71YgNKwUgXKdRcu5e2itochH7NlKGBb+8k3Vph3UlLs79bEzivqHyfKqrohYT kK5aF0PG4BsEGoCIuXUD+8QgYz64ePQ3FDRqB0pp2heyZLiY4y4sThRoPRzC/DK0V3pe 425w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705479079; x=1706083879; h=cc:to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=SDTtGec254DzLvzo9sUloqy8a2WgvjMp7TLbgiludEI=; b=Li8PqAdMj7bvQBD3rK0KlMEfSZY5ZL/reMypIW215lFfFM+Bielr20OgfG6cz1cUUh 9C/SkuLwkWB6Ty4XdFYI3XAC4NO0OX+0xDJV6rOtTQvquQL8M6tNFo+b+8gdQqBoScfj tEMUAdUmW6gzttHehURpp5GlGmbmaZfq6EA605LUgBDhfsr4WLkN1fVqEyUjeyVeba9b TxoWVSRxQrcXM39bdEcuN11ASDafByBqGFUiABIATrYmVQSRgy9ywAluY9Zy+8GwOc/I K4L8vSRy2QruR4xMM/HmrG6Di3PqtfriIfiF250bCKW09F0bmeZ6P0Lb4WGEJqTep3rM H0Lw== X-Gm-Message-State: AOJu0Ywk6oh87DzbQy/j4s4leJrVRtRd9bP2DDgO+KuVwHfh6FKjdtLP frkr7w7WxGbsg79RY4T9Ld/UdcqKPZ73C8LZ3PHmV2V82DWtjl/XmzQ= X-Google-Smtp-Source: AGHT+IHDOXJBIsh4gZjgW5sDgtjDhmLJKQEBdl3rcac5YFSLn807Pnt7t8IqD4T4bA62MSZJf3dhVC2KvNXgoiQooEE= X-Received: by 2002:a81:ca11:0:b0:5fb:1350:a004 with SMTP id p17-20020a81ca11000000b005fb1350a004mr6133030ywi.81.1705479079687; Wed, 17 Jan 2024 00:11:19 -0800 (PST) MIME-Version: 1.0 From: Huanghui Nie Date: Wed, 17 Jan 2024 16:11:08 +0800 Message-ID: Subject: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org, gcc@gcc.gnu.org Cc: paolo.carlini@oracle.com, drepper@gmail.com, Benjamin De Kosnik , jwakely@redhat.com Content-Type: multipart/alternative; boundary="000000000000b77b8b060f1fca50" X-Spam-Status: No, score=-8.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,HK_RANDOM_ENVFROM,HK_RANDOM_FROM,HTML_MESSAGE,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 List-Id: --000000000000b77b8b060f1fca50 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi. When I implemented a hash table with reference to the C++ STL, I found that when the hash table in the C++ STL deletes elements, if the first element deleted is the begin element, the before begin node is repeatedly assigned. This creates unnecessary performance overhead. First, let=E2=80=99s see the code implementation: In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when &_M_before_begin =3D=3D _M_buckets[__bkt]. That also means _M_buckets[__bkt]->_M_nxt is assigned under some conditions. _M_remove_bucket_begin is called by _M_erase and _M_extract_node: 1. Case _M_erase a range: _M_remove_bucket_begin is called in a for loop when __is_bucket_begin is true. And if __is_bucket_begin is true and &_M_before_begin =3D=3D _M_buckets[__bkt], __prev_n must be &_M_before_b= egin. __prev_n->_M_nxt is always assigned in _M_erase. That means _M_before_begin._M_nxt is always assigned, if _M_remove_bucket_begin is called and &_M_before_begin =3D=3D _M_buckets[__bkt]. So there=E2=80=99s= no need to assign _M_before_begin._M_nxt in _M_remove_bucket_begin. 2. Other cases: _M_remove_bucket_begin is called when __prev_n =3D=3D _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in _M_erase a= nd _M_before_begin. That means _M_buckets[__bkt]->_M_nxt is always assigned. So there's no need to assign _M_buckets[__bkt]->_M_nxt in _M_remove_bucket_begin. In summary, there=E2=80=99s no need to check &_M_before_begin =3D=3D _M_buc= kets[__bkt] and assign _M_before_begin._M_nxt in _M_remove_bucket_begin. Then let=E2=80=99s see the responsibility of each method: The hash table in the C++ STL is composed of hash buckets and a node list. The update of the node list is responsible for _M_erase and _M_extract_node method. _M_remove_bucket_begin method only needs to update the hash buckets. The update of _M_before_begin belongs to the update of the node list. So _M_remove_bucket_begin doesn=E2=80=99t need to update _M_before_be= gin. Existing tests listed below cover this change: 23_containers/unordered_set/allocator/copy.cc 23_containers/unordered_set/allocator/copy_assign.cc 23_containers/unordered_set/allocator/move.cc 23_containers/unordered_set/allocator/move_assign.cc 23_containers/unordered_set/allocator/swap.cc 23_containers/unordered_set/erase/1.cc 23_containers/unordered_set/erase/24061-set.cc 23_containers/unordered_set/modifiers/extract.cc 23_containers/unordered_set/operations/count.cc 23_containers/unordered_set/requirements/exception/basic.cc 23_containers/unordered_map/allocator/copy.cc 23_containers/unordered_map/allocator/copy_assign.cc 23_containers/unordered_map/allocator/move.cc 23_containers/unordered_map/allocator/move_assign.cc 23_containers/unordered_map/allocator/swap.cc 23_containers/unordered_map/erase/1.cc 23_containers/unordered_map/erase/24061-map.cc 23_containers/unordered_map/modifiers/extract.cc 23_containers/unordered_map/modifiers/move_assign.cc 23_containers/unordered_map/operations/count.cc 23_containers/unordered_map/requirements/exception/basic.cc Regression tested on x86_64-pc-linux-gnu. Is it OK to commit? --- ChangeLog: libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin 2024-01-16 Huanghui Nie gcc/ * libstdc++-v3/include/bits/hashtable.h --- diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index b48610036fa..6056639e663 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__next_n || __next_bkt !=3D __bkt) { // Bucket is now empty - // First update next bucket if any + // Update next bucket if any if (__next_n) _M_buckets[__next_bkt] =3D _M_buckets[__bkt]; - // Second update before begin node if necessary - if (&_M_before_begin =3D=3D _M_buckets[__bkt]) - _M_before_begin._M_nxt =3D __next_n; _M_buckets[__bkt] =3D nullptr; } } --000000000000b77b8b060f1fca50--