From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-4322.protonmail.ch (mail-4322.protonmail.ch [185.70.43.22]) by sourceware.org (Postfix) with ESMTPS id 724BC387084B; Fri, 14 Jun 2024 22:00:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 724BC387084B Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=protonmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=protonmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 724BC387084B Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=185.70.43.22 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1718402412; cv=none; b=c+LJUgVXMxaP5vqRHDDZH7CQgkY5ycDTVRU2cvvKKxwrNoK3hryRgV9zl7E45gbxUkUvLSTffcqBeBJfjcRcwRSCCgRXXfWWpPdvAGgrzeKRp+dk+27M4C/u8SQUCvA70cfCIF1G7ADmz8oLOqOrTqegL7ZWuYLHrp6S/O2N6Sc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1718402412; c=relaxed/simple; bh=jEYHMU2KUGiDOwN9vVdLKsiTK8MfWskWMMsEIhSMu6Q=; h=DKIM-Signature:Date:To:From:Subject:Message-ID:MIME-Version; b=haXIgqHll8PBwCIY1RJJXO2Ckm4dzb1V+6TZXJ7uqDV9CTRqeo6tlKOeYWerG3nyFeqh5zN78Aj7nPj99ChJ3KprtGZGw/mf77Or2hGgS6eqQxDAihMF4gopgm1d4Kbk6lsh+UUvzLvvnkIG7vJ1XeTqsT2qbS4wZJZderSfXBM= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1718402408; x=1718661608; bh=1mPJQ3KfwsGEbiCHTmZp2ttQlLc6LrKO9vHdFeCge8w=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=iuTACyXe4feHv4mfzGURbdcIlGCsVl2Sj+/bkygTez1S9p9hRu1KZbKfJXGYVIBAa eyYLvy8FXMVbGLPr+eYIVJjN3qrFGKFWxiWfLwbZyKc21HKAJVPgGpEJr/ByJujb/n 4qbu1pU7Q8vdErcm9S2Z4V+0VDrIYpXJxIhzhh2LXOkozJXhysKaUB5aKRcaKEYYGN xS62YbHIUQZ/Sro+cTUvAVPaK13oFd9vlVCZGETCXdBxgc8B1D9PvcFMWGw6i79fwm /RKf8WziMaqdozCOXi2cU4KgZlyjeHMRlHcgBsoZ+xYiGdWV0bNMDE4LALNoZCFg2s KMrfvhj+2wBpw== Date: Fri, 14 Jun 2024 22:00:03 +0000 To: Jonathan Wakely From: =?utf-8?Q?Barnab=C3=A1s_P=C5=91cze?= Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934] Message-ID: In-Reply-To: References: <20240311233548.3705328-1-pobrn@protonmail.com> Feedback-ID: 20568564:user:proton X-Pm-Message-ID: 1f54e8649ebabaeab08bcb8e6169f779cc3daf01 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-11.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS,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: 2024. m=C3=A1jus 18., szombat 3:01 keltez=C3=A9ssel, Barnab=C3=A1s P=C5= =91cze =C3=ADrta: > Hi > > > 2024. m=C3=A1rcius 13., szerda 12:43 keltez=C3=A9ssel, Jonathan Wakely =C3=ADrta: > > > On Mon, 11 Mar 2024 at 23:36, Barnab=C3=A1s P=C5=91cze wrote: > > > > > > Previously, calling erase(key) on both std::map and std::set > > > would execute that same code that std::multi{map,set} would. > > > However, doing that is unnecessary because std::{map,set} > > > guarantee that all elements are unique. > > > > > > It is reasonable to expect that erase(key) is equivalent > > > or better than: > > > > > > auto it =3D m.find(key); > > > if (it !=3D m.end()) > > > m.erase(it); > > > > > > However, this was not the case. Fix that by adding a new > > > function _Rb_tree<>::_M_erase_unique() that is essentially > > > equivalent to the above snippet, and use this from both > > > std::map and std::set. > > > > Hi, this change looks reasonable, thanks for the patch. Please note > > that GCC is currently in "stage 3" of its dev process so this change > > would have to wait until after GCC 14 branches from trunk, due in a > > few weeks. > > As far as I can see GCC 14 has been released, so I pulled and ran the tes= t suite > again: > > make check-target-libstdc++-v3 RUNTESTFLAGS=3D"conformance.exp=3D23_con= tainers/*" > > and it reported no failures. Is there anything else I should do? Anything else I should do here? I apologize if the window for new changes has not opened yet, I don't know how that is done in gcc. Regards, Barnab=C3=A1s P=C5=91cze > > > Regards, > Barnab=C3=A1s P=C5=91cze > > > > > I assume you ran the testsuite with no regressions. Do you have > > benchmarks to show this making a difference? > > > > > > > > > > libstdc++-v3/ChangeLog: > > > > > > PR libstdc++/112934 > > > * include/bits/stl_tree.h (_Rb_tree<>::_M_erase_unique): Add. > > > * include/bits/stl_map.h (map<>::erase): Use _M_erase_unique. > > > * include/bits/stl_set.h (set<>::erase): Likewise. > > > --- > > > libstdc++-v3/include/bits/stl_map.h | 2 +- > > > libstdc++-v3/include/bits/stl_set.h | 2 +- > > > libstdc++-v3/include/bits/stl_tree.h | 17 +++++++++++++++++ > > > 3 files changed, 19 insertions(+), 2 deletions(-) > > > > > > diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/inclu= de/bits/stl_map.h > > > index ad58a631af5..229643b77fd 100644 > > > --- a/libstdc++-v3/include/bits/stl_map.h > > > +++ b/libstdc++-v3/include/bits/stl_map.h > > > @@ -1115,7 +1115,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > > > */ > > > size_type > > > erase(const key_type& __x) > > > - { return _M_t.erase(__x); } > > > + { return _M_t._M_erase_unique(__x); } > > > > > > #if __cplusplus >=3D 201103L > > > // _GLIBCXX_RESOLVE_LIB_DEFECTS > > > diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/inclu= de/bits/stl_set.h > > > index c0eb4dbf65f..51a1717ec62 100644 > > > --- a/libstdc++-v3/include/bits/stl_set.h > > > +++ b/libstdc++-v3/include/bits/stl_set.h > > > @@ -684,7 +684,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > > > */ > > > size_type > > > erase(const key_type& __x) > > > - { return _M_t.erase(__x); } > > > + { return _M_t._M_erase_unique(__x); } > > > > > > #if __cplusplus >=3D 201103L > > > // _GLIBCXX_RESOLVE_LIB_DEFECTS > > > diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/incl= ude/bits/stl_tree.h > > > index 6f470f04f6a..9e80d449c7e 100644 > > > --- a/libstdc++-v3/include/bits/stl_tree.h > > > +++ b/libstdc++-v3/include/bits/stl_tree.h > > > @@ -1225,6 +1225,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > size_type > > > erase(const key_type& __x); > > > > > > + size_type > > > + _M_erase_unique(const key_type& __x); > > > + > > > #if __cplusplus >=3D 201103L > > > // _GLIBCXX_RESOLVE_LIB_DEFECTS > > > // DR 130. Associative erase should return an iterator. > > > @@ -2518,6 +2521,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > return __old_size - size(); > > > } > > > > > > + template > > + typename _Compare, typename _Alloc> > > > + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::si= ze_type > > > + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > > + _M_erase_unique(const _Key& __x) > > > + { > > > + iterator __it =3D find(__x); > > > + if (__it =3D=3D end()) > > > + return 0; > > > + > > > + _M_erase_aux(__it); > > > + return 1; > > > + } > > > + > > > template > > typename _Compare, typename _Alloc> > > > typename _Rb_tree<_Key, _Val, _KeyOfValue, > > > -- > > > 2.44.0 > > > > > > > >