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.133.124]) by sourceware.org (Postfix) with ESMTPS id 0EBA63858C3A for ; Wed, 13 Mar 2024 11:44:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0EBA63858C3A 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 0EBA63858C3A Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1710330259; cv=none; b=O6Ujhu73+Qxb/ZipiRvEolKPAhP3blJ178Dju7Q8RtT+BukDrFun4MUbLcFD2VNM0gQNiVKfhB6G88fjpGBgkvCN+7zGMOSvznQj/gURrVXZcO3IKY7f7akyGKuq2N3Wwwbm6TGKJ5Ue4PruEas3Xrwn4dlozlbZlX37RZ+JJ/8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1710330259; c=relaxed/simple; bh=0CXOj6j+aSjUm3At7aKdnjox8NI1XMs13C0f03gjUUs=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=M0Eh1LpB2NqCyjcwbEq+S6cPYrZYqC+722mgMwQ2IExZwP6G/a+6rJvr0YZHYzboyd0ouOL62/VBkqc5a8Ivjajm2/LwcDOuzA17UWxLrKrIssGigY1kMOoFm/TulB5C9g2i3svMEGVyZ9tgMi9wfFJAewEJZfTduD+NbjxDFfo= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1710330255; 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=0/Yh7dstSHLdBglkb40AvDrEVlqHhEzcBzbOW7bnFzU=; b=QMna7ua+TI7KX2eIM0y3bI0vMBv41ltPnfd79CyStITw1fULmjQmqc3An35PEpgPOHZ7+M 8aRIuyu92HPua2rpy1txRdm1C6DxcW5QnCKBPe0G/0IEz/q3sT3zkBCYlQm7icDzEmedeV 2IS2zCL0lW/28Ut+luQns1uZT8fRcFc= Received: from mail-yb1-f198.google.com (mail-yb1-f198.google.com [209.85.219.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-178-V2WDcHt5PoqUq715Dnx5NQ-1; Wed, 13 Mar 2024 07:44:14 -0400 X-MC-Unique: V2WDcHt5PoqUq715Dnx5NQ-1 Received: by mail-yb1-f198.google.com with SMTP id 3f1490d57ef6-dced704f17cso1433710276.1 for ; Wed, 13 Mar 2024 04:44:14 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710330254; x=1710935054; 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=0/Yh7dstSHLdBglkb40AvDrEVlqHhEzcBzbOW7bnFzU=; b=GH0HXG5mfv0k+gMxCX/rR70Cf+cpjNEhfrXXirrr2Wdbbmc9WPZk2Dp/E92z49WTFn SvaSpaNHE5dmDa7e6tnEEcZc3o5sgoHxsFlwqQg/4OKQsf1BvqCwbwg+CYv9dGS7NQO9 MGHjQsqD3g6wB0W2IwnbfX5V1IMHOV0OTe2FtJhesGaUzdR+N/XNJqrKej1DzmwH8H2t qfNWutrtaEGTEs6gSVJdg57JuQt+GZdH1LiBW9+MDg2VMw10lSDygetmJUaXU9+vG9tt S3ZcA/0pOQmor3YlZdU15ysTq279VMSNKMIg6gh6vnnAehUqc2p1VW823VXi8Ry0c6Ch msaw== X-Gm-Message-State: AOJu0YxyzVnZLD3CBlrfO7GdEXqbz/0nfiAVOag3E7fUWiiAKm8yLsBy fZbxk1+d8EYLRCDuS02hB/SsJo7oKdoUkD8SOZHyLRutHnN7pbAG4vXreIxvNDyDh61QxkiOCPO T77afUQ8RNqbi5g/+adpGQr5t34Ni9Cx4r8RVyVCY5V+kr6/sRMc6sFKiYfBB4/DtVxtQX/e6S9 p43oUQafttJUF8rMm/fvEHFqZKuPA= X-Received: by 2002:a25:c483:0:b0:dc2:4397:6ad3 with SMTP id u125-20020a25c483000000b00dc243976ad3mr2304288ybf.44.1710330253951; Wed, 13 Mar 2024 04:44:13 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGl/ouxUlvPTM2b6CbJtcWaVwzFFDn1IjKRvzYDDaDQGmw3x1/2qgPrHZwRzUHkZLNEnaCht/O1L73Lw9e/qcA= X-Received: by 2002:a25:c483:0:b0:dc2:4397:6ad3 with SMTP id u125-20020a25c483000000b00dc243976ad3mr2304273ybf.44.1710330253677; Wed, 13 Mar 2024 04:44:13 -0700 (PDT) MIME-Version: 1.0 References: <20240311233548.3705328-1-pobrn@protonmail.com> In-Reply-To: <20240311233548.3705328-1-pobrn@protonmail.com> From: Jonathan Wakely Date: Wed, 13 Mar 2024 11:43:57 +0000 Message-ID: Subject: Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934] To: =?UTF-8?B?QmFybmFiw6FzIFDFkWN6ZQ==?= Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org 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=-12.8 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,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: 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. 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/include/b= its/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/include/b= its/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/include/= 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>::size_t= ype > + _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 > >