From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 2AD443858CDB; Wed, 17 Jan 2024 20:04:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2AD443858CDB 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 2AD443858CDB Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::634 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705521890; cv=none; b=SDJT11ROnoIDNQN7CcjBVKzLsKjLN0RQdLys2C+BEmh0Y/KhdrYPo4TR1aTibrfjwZ9jBkrwiW6kermlf4mJoQ9Upgajq+4tckiE28Ntx/8aqFYCC5CzQD27/Qzby00moz9IFRD6dafwV+4lZknuNCDgljSSv5x3f1ZUpyptzjc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705521890; c=relaxed/simple; bh=HOo8ZhOs+GFhzi5SOXmOLcNC+TXbNSFdOtBBiGb8a+A=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=hjbIYg1OuCAzwGgz9P9C7zY0B02xYJ9OrxJFQ92dKX3HYflOu356VWw6/JieIJYPoLUueOZyD28OTUJIqPYJ9+N9+QMob2CD/yKJZqfTIrPGnGs0zgr17a8XkAj1GHqvgul09k+HKfibMt+znSZ4gVPjdZVwXT3LmdoiOZPxFFc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ej1-x634.google.com with SMTP id a640c23a62f3a-a26fa294e56so1203730066b.0; Wed, 17 Jan 2024 12:04:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705521886; x=1706126686; darn=gcc.gnu.org; h=in-reply-to:from:references:to:content-language:subject:user-agent :mime-version:date:message-id:from:to:cc:subject:date:message-id :reply-to; bh=jukxAQkyQxATK4GBAXEonN0k8GQ/50qHbn55SlWOyE8=; b=aWV/P7L6ihjmjPeiWF3wgDJdzAhp29ibMd0DyZtOAM3vbeqQz7MeD4jUnnK00mLYiK sfMFhrGw4T5H6WLkSJ9Xf6t2JQ+GjSYjnnbKtb2zjKebSvUHs103BFVWzORR8oGd/8Qr jf2gJk0VRNyQ/KsV0gQfvMncKZNgZR9E7mk9hwtgvY5XjKj1XnfkPzV8h4Eo+1nL/Zr/ H8aXlxdJSS8U6EXJkonAA7feol0BqjQrxeZxDY9ajwAHfbIGZvmTdpGm2Xmqre98UVBJ gKxGIjLCYJQPnLm2IXWn9XnWNGtRDtP3CgIxPBpED5k6xjsRlk1hf2EbFbL2BoPFrjrx n8FQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705521886; x=1706126686; h=in-reply-to:from:references:to:content-language:subject:user-agent :mime-version:date:message-id:x-gm-message-state:from:to:cc:subject :date:message-id:reply-to; bh=jukxAQkyQxATK4GBAXEonN0k8GQ/50qHbn55SlWOyE8=; b=O2fsAcKGstDYKTESxR8Q5ttZ5+nWHVZ3ExyDsGRGheoKaen7kvjBrh2z6WrVu9Qosk m0Rqr51BNV/SBrPc1uVUj+YFvHkByu117toqzp90XghTAsFIez4dc7GB+UMqgGSdwNf6 oEvNTgDpmWfUiIwQYHSbVj2mwnuhgkSgyOE/hpXPYYWvJj54N8iqZlw1Q6FlI/2kM3pf BzsAbdQTw7pFQ6cYo+DmIXwsAxXczHd+822+NTz6yBoqt3xVhX5/+aHMCPeBxcEXjYv3 5EqOQOtP0uW9XHDRX5lF5vNCDHYDL4+z5DaJs98Np6sAeOY6JOaylHqyfCvwkBLiw4wb rH1g== X-Gm-Message-State: AOJu0YxDeEXEa+YVj5E6pqru/l/uSqqRvSo0gA60AS1IcupPj9TOtNBQ EYmklyoRP836wcDOb/A516FjQq/7/k8= X-Google-Smtp-Source: AGHT+IHB5b++msvanxbhJhMBQdPvCjDDcFeU5L1sifUVrcUg1w3nuwdj1WyTJ9Hj2dHsFEGYkH/gpQ== X-Received: by 2002:a17:906:b107:b0:a27:7cc5:b019 with SMTP id u7-20020a170906b10700b00a277cc5b019mr4610908ejy.92.1705521885620; Wed, 17 Jan 2024 12:04:45 -0800 (PST) Received: from [10.59.0.149] ([89.207.171.133]) by smtp.gmail.com with ESMTPSA id f25-20020a170906c09900b00a2e09ce0a57sm3547618ejz.142.2024.01.17.12.04.44 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 17 Jan 2024 12:04:45 -0800 (PST) Content-Type: multipart/alternative; boundary="------------IJJzXwkaXAx5c5I7FTf2Ik3T" Message-ID: <5b87ddea-ba56-4173-bda3-652f038dcacc@gmail.com> Date: Wed, 17 Jan 2024 21:04:43 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin Content-Language: en-US To: Huanghui Nie , libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org References: From: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= In-Reply-To: X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,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: This is a multi-part message in MIME format. --------------IJJzXwkaXAx5c5I7FTf2Ik3T Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Hi Looks like a great finding to me, this is indeed a useless check, thanks! Have you any figures on the performance enhancement ? It might help to get proper approval as gcc is currently in dev stage 4 that is to say only bug fixes normally. François On 17/01/2024 09:11, Huanghui Nie wrote: > > 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’s see the code implementation: > > In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when > &_M_before_begin == _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 == _M_buckets[__bkt], __prev_n must be > &_M_before_begin. __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 == > _M_buckets[__bkt]. So there’s 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 == > _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in > _M_erase and _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’s no need to check &_M_before_begin == > _M_buckets[__bkt] and assign _M_before_begin._M_nxt in > _M_remove_bucket_begin. > > > Then let’s 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’t need to > update _M_before_begin. > > > 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-16Huanghui 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 != __bkt) > >         { > >           // Bucket is now empty > > -         // First update next bucket if any > > +         // Update next bucket if any > >           if (__next_n) > >             _M_buckets[__next_bkt] = _M_buckets[__bkt]; > > -         // Second update before begin node if necessary > > -         if (&_M_before_begin == _M_buckets[__bkt]) > > -           _M_before_begin._M_nxt = __next_n; > >           _M_buckets[__bkt] = nullptr; > >         } > >     } > > --------------IJJzXwkaXAx5c5I7FTf2Ik3T--