[PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Barnabás Pőcze]

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 = m.find(key);
  if (it != 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.

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/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 >= 201103L
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/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 >= 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 >= 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 _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_erase_unique(const _Key& __x)
+    {
+      iterator __it = find(__x);
+      if (__it == end())
+	return 0;
+
+      _M_erase_aux(__it);
+      return 1;
+    }
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KeyOfValue,
-- 
2.44.0

Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Jonathan Wakely]

On Mon, 11 Mar 2024 at 23:36, Barnabás Pőcze <pobrn@protonmail.com> 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 = m.find(key);
>   if (it != 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/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 >= 201103L
>        // _GLIBCXX_RESOLVE_LIB_DEFECTS
> diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/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 >= 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 >= 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 _Key, typename _Val, typename _KeyOfValue,
> +          typename _Compare, typename _Alloc>
> +    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
> +    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
> +    _M_erase_unique(const _Key& __x)
> +    {
> +      iterator __it = find(__x);
> +      if (__it == end())
> +       return 0;
> +
> +      _M_erase_aux(__it);
> +      return 1;
> +    }
> +
>    template<typename _Key, typename _Val, typename _KeyOfValue,
>            typename _Compare, typename _Alloc>
>      typename _Rb_tree<_Key, _Val, _KeyOfValue,
> --
> 2.44.0
>
>

Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Barnabás Pőcze]

Hi


2024. március 13., szerda 12:43 keltezéssel, Jonathan Wakely <jwakely@redhat.com> írta:

> On Mon, 11 Mar 2024 at 23:36, Barnabás Pőcze <pobrn@protonmail.com> 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 = m.find(key);
> >   if (it != 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.

OK; I didn't know that, thanks for telling me.


> 
> I assume you ran the testsuite with no regressions. [...]


I hope so. I ran `make check-target-libstdc++-v3`, and it did not note any
unexpected failures as far as I can see:

  Native configuration is x86_64-pc-linux-gnu

  		=== libstdc++ tests ===

  Schedule of variations:
      unix

  Running target unix
  Using /usr/share/dejagnu/baseboards/unix.exp as board description file for target.
  Using /usr/share/dejagnu/config/unix.exp as generic interface file for target.
  Using /gcc/libstdc++-v3/testsuite/config/default.exp as tool-and-target-specific interface file.
  Running /gcc/libstdc++-v3/testsuite/libstdc++-abi/abi.exp ...
  Running /gcc/libstdc++-v3/testsuite/libstdc++-dg/conformance.exp ...
  Running /gcc/libstdc++-v3/testsuite/libstdc++-prettyprinters/prettyprinters.exp ...
  Running /gcc/libstdc++-v3/testsuite/libstdc++-xmethods/xmethods.exp ...

  		=== libstdc++ Summary ===

  # of expected passes		18646
  # of expected failures		126
  # of unsupported tests		672

> [...] Do you have benchmarks to show this making a difference?


As for benchmarks, I do not have any. But even if the performance does not
improve appreciably, the size of the generated code will definitely be smaller.
And in the end, the excessive code was the reason I opened the mentioned issue[0]
in the first place, which should be eliminated hopefully.


> [...]


Regards,
Barnabás Pőcze


[0]: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112934

Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Barnabás Pőcze]

Hi


2024. március 13., szerda 12:43 keltezéssel, Jonathan Wakely <jwakely@redhat.com> írta:

> On Mon, 11 Mar 2024 at 23:36, Barnabás Pőcze <pobrn@protonmail.com> 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 = m.find(key);
> >   if (it != 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 test suite
again:

  make check-target-libstdc++-v3 RUNTESTFLAGS="conformance.exp=23_containers/*"

and it reported no failures. Is there anything else I should do?


Regards,
Barnabás Pőcze

> 
> 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/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 >= 201103L
> >        // _GLIBCXX_RESOLVE_LIB_DEFECTS
> > diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/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 >= 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 >= 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 _Key, typename _Val, typename _KeyOfValue,
> > +          typename _Compare, typename _Alloc>
> > +    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
> > +    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
> > +    _M_erase_unique(const _Key& __x)
> > +    {
> > +      iterator __it = find(__x);
> > +      if (__it == end())
> > +       return 0;
> > +
> > +      _M_erase_aux(__it);
> > +      return 1;
> > +    }
> > +
> >    template<typename _Key, typename _Val, typename _KeyOfValue,
> >            typename _Compare, typename _Alloc>
> >      typename _Rb_tree<_Key, _Val, _KeyOfValue,
> > --
> > 2.44.0
> >
> >
>

Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Barnabás Pőcze]

2024. május 18., szombat 3:01 keltezéssel, Barnabás Pőcze <pobrn@protonmail.com> írta:

> Hi
>
>
> 2024. március 13., szerda 12:43 keltezéssel, Jonathan Wakely <jwakely@redhat.com> írta:
>
> > On Mon, 11 Mar 2024 at 23:36, Barnabás Pőcze <pobrn@protonmail.com> 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 = m.find(key);
> > >   if (it != 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 test suite
> again:
>
>   make check-target-libstdc++-v3 RUNTESTFLAGS="conformance.exp=23_containers/*"
>
> 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ás Pőcze


>
>
> Regards,
> Barnabás Pőcze
>
> >
> > 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/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 >= 201103L
> > >        // _GLIBCXX_RESOLVE_LIB_DEFECTS
> > > diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/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 >= 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 >= 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 _Key, typename _Val, typename _KeyOfValue,
> > > +          typename _Compare, typename _Alloc>
> > > +    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
> > > +    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
> > > +    _M_erase_unique(const _Key& __x)
> > > +    {
> > > +      iterator __it = find(__x);
> > > +      if (__it == end())
> > > +       return 0;
> > > +
> > > +      _M_erase_aux(__it);
> > > +      return 1;
> > > +    }
> > > +
> > >    template<typename _Key, typename _Val, typename _KeyOfValue,
> > >            typename _Compare, typename _Alloc>
> > >      typename _Rb_tree<_Key, _Val, _KeyOfValue,
> > > --
> > > 2.44.0
> > >
> > >
> >

Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Barnabás Pőcze]

Hi Jonathan


It seems this patch got stuck, is there any chance it could be ultimately accepted
or rejected some time in the future?


Regards,
Barnabás Pőcze


2024. március 13., szerda 12:43 keltezéssel, Jonathan Wakely <jwakely@redhat.com> írta:

> On Mon, 11 Mar 2024 at 23:36, Barnabás Pőcze <pobrn@protonmail.com> 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 = m.find(key);
> >   if (it != 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/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 >= 201103L
> >        // _GLIBCXX_RESOLVE_LIB_DEFECTS
> > diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/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 >= 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 >= 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 _Key, typename _Val, typename _KeyOfValue,
> > +          typename _Compare, typename _Alloc>
> > +    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
> > +    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
> > +    _M_erase_unique(const _Key& __x)
> > +    {
> > +      iterator __it = find(__x);
> > +      if (__it == end())
> > +       return 0;
> > +
> > +      _M_erase_aux(__it);
> > +      return 1;
> > +    }
> > +
> >    template<typename _Key, typename _Val, typename _KeyOfValue,
> >            typename _Compare, typename _Alloc>
> >      typename _Rb_tree<_Key, _Val, _KeyOfValue,
> > --
> > 2.44.0
> >
> >
>

Re: [PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Jonathan Wakely]

On Sun, 22 Sept 2024 at 20:08, Barnabás Pőcze <pobrn@protonmail.com> wrote:
>
> Hi Jonathan
>
>
> It seems this patch got stuck, is there any chance it could be ultimately accepted
> or rejected some time in the future?

Thanks for the reminder, it's still in my TODO list of patches to
merge. I'll look at it in the next few days.

>
>
> Regards,
> Barnabás Pőcze
>
>
> 2024. március 13., szerda 12:43 keltezéssel, Jonathan Wakely <jwakely@redhat.com> írta:
>
> > On Mon, 11 Mar 2024 at 23:36, Barnabás Pőcze <pobrn@protonmail.com> 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 = m.find(key);
> > >   if (it != 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/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 >= 201103L
> > >        // _GLIBCXX_RESOLVE_LIB_DEFECTS
> > > diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/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 >= 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 >= 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 _Key, typename _Val, typename _KeyOfValue,
> > > +          typename _Compare, typename _Alloc>
> > > +    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
> > > +    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
> > > +    _M_erase_unique(const _Key& __x)
> > > +    {
> > > +      iterator __it = find(__x);
> > > +      if (__it == end())
> > > +       return 0;
> > > +
> > > +      _M_erase_aux(__it);
> > > +      return 1;
> > > +    }
> > > +
> > >    template<typename _Key, typename _Val, typename _KeyOfValue,
> > >            typename _Compare, typename _Alloc>
> > >      typename _Rb_tree<_Key, _Val, _KeyOfValue,
> > > --
> > > 2.44.0
> > >
> > >
> >