From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by sourceware.org (Postfix) with ESMTPS id D7D583858420; Mon, 22 Jan 2024 06:14:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D7D583858420 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 D7D583858420 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::42b ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705904079; cv=none; b=o/UZlUTShAAY0By8RJBffcO3AWKcc48NaRJRHfAtPzZpEn2A9smzst2FAYjn5jJU+dPk2S4OJk7vj+RiyYaD3Zdf7+WgxMQPIZ//iX24LVyGq5j6CDM5cJTmsfzoMZ8UaCxhVMSEv4PzgDLeD20o/7xg+8oFLFme3P00xgANjSM= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705904079; c=relaxed/simple; bh=za0hOl3KHzIG/ygs2d8nku/6tGgofDQvz7gWur37NJQ=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=o+eVLabFlHb09/hkikfp3d2ls2sztHji20IAPWHPXecDtgOoLSktImY0t7CC01IFLZiy6zIl1+sh4F63eEVjEpXJ4ZkemrswSofaeF7U59Vs36T7YFg0SWF8NDPah8hR1BBu24uqWJWXoLXyrbwVZXgssSOW8p7dfsJwlequdsk= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wr1-x42b.google.com with SMTP id ffacd0b85a97d-337b8da1f49so2560835f8f.0; Sun, 21 Jan 2024 22:14:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705904075; x=1706508875; darn=gcc.gnu.org; h=in-reply-to:from:content-language:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=CK7DZdIGp7ICfEgjhEzwu9C3khP4qodNUADA0AtmpRQ=; b=dUqI6svGrzBDzwhF97aU7ts4Bd0/G0D0hU/+nPpu+lTuHahUicNJqrDIZpzvrBjtNQ 5a8st9BieAkfbCmito8J3doGj2/5HUB06WtzoY4EXnTVrtmc5aVodw9tM5gVfUlaCJUO rA3t2VS14u0ZMc45Kyz85sEO8ZRRNnnkxweXz1lzNguoc0HCUvSg3+4t/44o5qcfNUF9 U+nBtZjT8k2xQY5VpyUGCMip8uv1fOWnWtLj8xW0gtsOvCP+vRqnEgfyifzfIRwUuZz1 qyCodqjGagFhzd8L2DrdGFZ0uebHJ8gg/b5slyO5eUFe3Ogt680jwHZ0YSIc+MgH28gH QjdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705904075; x=1706508875; h=in-reply-to:from:content-language:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=CK7DZdIGp7ICfEgjhEzwu9C3khP4qodNUADA0AtmpRQ=; b=Z8qdFEENnRFdZERp3qkpfp6YhuI2skcKY6AjnRQ/EPNwDjsuLi+sn2+Up232hQP/s0 IB0BeOsH4e77aAoV8wlEF0UROl24I+AXaF5MAJFZxuM6rJsh/2Qyljaahr68jBju9dhC 7+N4aEWe9lf/+UKRvH8l+Hvw3c7Wp6MyVvj63NxaW3VOCF/ggVB/qsRdr3/eaJ8C/TjV ncI7REiSiVmwpjrR8LMNM2cImXMPMXOIDLBF9D9s229Y9sB7Ol+TWGodYf0fRHisrcW9 8CWh09lrLMx06Ep7pY8XiVDZQZ8+gcXQe+6pX5mBxF0dPMxaoKMI3I873V1/t8I0fV/p Ldfg== X-Gm-Message-State: AOJu0YwvhFQPBNaeIPOGs6nSQaubpmwpy7jplJ98NQ5rR4NJe9Rp1nP3 CY9TX6l22v0oB7TxTmn3B/MBwGOn1NSJBAgmjNNybrgeak3nTzWg X-Google-Smtp-Source: AGHT+IFQ0DMrUB4s/ejzEsIItNt1cKc31MWzioipFPO1B1Z0HISrloAyMRiEWfUO/nOZmiVfAiE7Tg== X-Received: by 2002:a05:600c:3655:b0:40e:6ee8:c120 with SMTP id y21-20020a05600c365500b0040e6ee8c120mr1445077wmq.79.1705904075242; Sun, 21 Jan 2024 22:14:35 -0800 (PST) Received: from [10.47.0.51] ([89.207.171.122]) by smtp.gmail.com with ESMTPSA id e7-20020a5d65c7000000b00337d6db207dsm9338157wrw.30.2024.01.21.22.14.34 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 21 Jan 2024 22:14:34 -0800 (PST) Content-Type: multipart/alternative; boundary="------------vuc04ybyyA1rE4BiPS2ESVzA" Message-ID: <74164a9e-ae0b-4960-ae2c-ca84cd88eb91@gmail.com> Date: Mon, 22 Jan 2024 07:14:31 +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 To: Huanghui Nie Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org References: <5b87ddea-ba56-4173-bda3-652f038dcacc@gmail.com> Content-Language: en-US From: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= In-Reply-To: X-Spam-Status: No, score=-10.5 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. --------------vuc04ybyyA1rE4BiPS2ESVzA Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Thanks, nice result, I'll try to run the performance benchmarks that are coming with libstdc++ to see if they spot anything. That's tests in testsuite/performance folder in case you want to have a try yourself. François On 18/01/2024 10:26, Huanghui Nie wrote: > > Yes, I have. I did a benchmark today. > > The conclusion is: the time consumption can be reduced by 0.4% ~ 1.2% > when unordered_set erase(begin()), and 1.2% ~ 2.4% when erase(begin(), > end()). > > > My test environment: > > CPU: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz, 2393.365 MHz, 56 CPUs > > MEM: 256G > > OS: CentOS-8.2 > > g++: gcc version 8.3.1 20191121 (Red Hat 8.3.1-5) (GCC) > > Compile flags: -O3 -std=c++17 > > > Test conclusion data (time taken to delete every 100 million elements): > > erase(begin()): > > |size of unordered_set |100 |1,000 |10,000|100,000 |1,000,000|10,000,000| > > |base time consuming (ms)|3827.736|3807.725|3830.168|3807.373|3798.713 > |3854.168| > > |test time consuming (ms)|3783.406|3789.460|3791.146|3778.033|3783.494 > |3808.137| > > |Time-consuming reduction|1.16% |0.48% |1.02% |0.77% |0.40%|1.19% | > > erase(begin(),end()): > > |size of unordered_set |100 |1,000 |10,000|100,000 |1,000,000|10,000,000| > > |base time consuming (ms)|2779.229|2768.550|2795.778|2767.385|2761.521 > |2804.099| > > |test time consuming (ms)|2712.759|2726.578|2752.224|2732.140|2718.953 > |2739.727| > > |Time-consuming reduction|2.39% |1.52% |1.56% |1.27% |1.54%|2.30% | > > > Please see the attachment for test code and detailed test result. > > > 2024年1月18日(木) 4:04 François Dumont : > > 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; >> >>         } >> >>     } >> >> --------------vuc04ybyyA1rE4BiPS2ESVzA--