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

[Jonathan Wakely <jwakely@redhat.com>]

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
>
>