On Fri, Apr 4, 2025 at 6:21 PM Patrick Palka <ppa...@redhat.com> wrote:
> On Fri, 4 Apr 2025, Patrick Palka wrote:
>
> > On Fri, 4 Apr 2025, Tomasz Kaminski wrote:
> >
> > >
> > >
> > > On Fri, Apr 4, 2025 at 6:07 PM Tomasz Kaminski <tkami...@redhat.com>
> wrote:
> > >
> > >
> > > On Fri, Apr 4, 2025 at 5:50 PM Patrick Palka <ppa...@redhat.com>
> wrote:
> > > flat_set::emplace (and flat_multiset) currently unconditionally
> > > constructs an object outside of the container, but if we're
> passed
> > > a value_type object we can and should avoid that.
> > >
> > > PR libstdc++/119620
> > >
> > > libstdc++-v3/ChangeLog:
> > >
> > > * include/std/flat_set (_Flat_set_impl::_M_try_emplace):
> Split
> > > out into two overloads, one taking at least one argument
> and one
> > > taking zero arguments. Turn __k into an auto&&
> reference bound
> > > to __arg if it's already a value_type otherwise bound to
> a
> > > lifetime-extended value_type temporary.
> > > * testsuite/23_containers/flat_multiset/1.cc (test08):
> New test.
> > > * testsuite/23_containers/flat_set/1.cc (test08): New
> test.
> > > ---
> > > libstdc++-v3/include/std/flat_set | 20
> +++++++++++++----
> > > .../23_containers/flat_multiset/1.cc | 22
> +++++++++++++++++++
> > > .../testsuite/23_containers/flat_set/1.cc | 20
> +++++++++++++++++
> > > 3 files changed, 58 insertions(+), 4 deletions(-)
> > >
> > > diff --git a/libstdc++-v3/include/std/flat_set
> b/libstdc++-v3/include/std/flat_set
> > > index a7b0b8aef15..3e15d1af416 100644
> > > --- a/libstdc++-v3/include/std/flat_set
> > > +++ b/libstdc++-v3/include/std/flat_set
> > > @@ -350,12 +350,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > > { return _M_cont.max_size(); }
> > >
> > > // modifiers
> > > - template<typename... _Args>
> > > + template<typename _Arg, typename... _Args>
> > > pair<iterator, bool>
> > > - _M_try_emplace(optional<const_iterator> __hint,
> _Args&&... __args)
> > > + _M_try_emplace(optional<const_iterator> __hint, _Arg&&
> __arg, _Args&&... __args)
> > >
> > > map.try_emplace(key) is valid construct, and commonly used to value
> construct value type. For example operator[] is defined in terms of it.
> > > {
> > > // TODO: Simplify and audit the hint handling.
> > > - value_type __k(std::forward<_Args>(__args)...);
> > > + auto&& __k = [&] -> decltype(auto) {
> > > + if constexpr (sizeof...(_Args) == 0
> > > + && same_as<remove_cvref_t<_Arg>,
> value_type>)
> > > + return std::forward<_Arg>(__arg);
> > >
> > > I think you can do sizeof..(_Args) == 1 and return
> (std::forward<_Args>(__args), ...);
>
> I tried something like that, but I think it'd mean we'd have to
> then change the same_as check to
>
> same_as<remove_cvref_t<_Args...>, value_type>
>
> or
>
> same_as<remove_cvref_t<_Args>..., value_type>
>
> both of which are ill-formed because we can't pass a pack expansion
> to a non-variadic template parameter of an alias template or concept.
>
Thanks for the explanation. LGTM.
>
> > > + else
> > > + return value_type(std::forward<_Arg>(__arg),
> > > + std::forward<_Args>(__args)...);
> > > + }();
> > > typename container_type::iterator __it;
> > > int __r = -1, __s = -1;
> > > if (__hint.has_value()
> > > @@ -397,11 +404,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > > return {__it, false};
> > >
> > > auto __guard = _M_make_clear_guard();
> > > - __it = _M_cont.insert(__it, std::move(__k));
> > > + __it = _M_cont.insert(__it,
> std::forward<decltype(__k)>(__k));
> > > __guard._M_disable();
> > > return {__it, true};
> > > }
> > >
> > > + template<typename... _Args>
> > > + pair<iterator, bool>
> > > + _M_try_emplace(optional<const_iterator> __hint)
> > > + { return _M_try_emplace(__hint, value_type()); }
> > >
> > > Ah, I haven't noticed this overload that restores _M_try_empalce. But
> this causes additional move, so I think I prefer my suggestion.
> >
> > I'd expect there would be just one move in that case, when __k is moved
> > from in the _M_cont.insert call? There should be no move when we e.g.
> > bind __k to the default-constructed value_type.
>
Yes, indeed, we are binding to `auto&&`, not to value_type. I am ok with
the approach.
> >
> > > +
> > > template<typename... _Args>
> > > requires is_constructible_v<value_type, _Args...>
> > > __emplace_result_t
> > > diff --git
> a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> > > index dc3cecd9720..7d9a33c6b00 100644
> > > ---
> a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> > > +++
> b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> > > @@ -214,6 +214,27 @@ void test07()
> > > #endif
> > > }
> > >
> > > +void
> > > +test08()
> > > +{
> > > + // PR libstdc++/119620 -- flat_set::emplace always
> constructs element on the stack
> > > + static int copy_counter;
> > > + struct A {
> > > + A() { }
> > > + A(const A&) { ++copy_counter; }
> > > + A& operator=(const A&) { ++copy_counter; return
> *this; }
> > > + auto operator<=>(const A&) const = default;
> > > + };
> > > + std::vector<A> v;
> > > + v.reserve(2);
> > > + std::flat_multiset<A> s(std::move(v));
> > > + A a;
> > > + s.emplace(a);
> > > + VERIFY( copy_counter == 1 );
> > > + s.emplace(a);
> > > + VERIFY( copy_counter == 2 );
> > > +}
> > > +
> > > int
> > > main()
> > > {
> > > @@ -225,4 +246,5 @@ main()
> > > test05();
> > > test06();
> > > test07();
> > > + test08();
> > > }
> > > diff --git
> a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> > > index 90f5855859f..ed24fab785b 100644
> > > --- a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> > > +++ b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> > > @@ -229,6 +229,25 @@ void test07()
> > > #endif
> > > }
> > >
> > > +void
> > > +test08()
> > > +{
> > > + // PR libstdc++/119620 -- flat_set::emplace always
> constructs element on the stack
> > > + static int copy_counter;
> > > + struct A {
> > > + A() { }
> > > + A(const A&) { ++copy_counter; }
> > > + A& operator=(const A&) { ++copy_counter; return
> *this; }
> > > + auto operator<=>(const A&) const = default;
> > > + };
> > > + std::flat_set<A> s;
> > > + A a;
> > > + s.emplace(a);
> > > + VERIFY( copy_counter == 1 );
> > > + s.emplace(a);
> > > + VERIFY( copy_counter == 1 );
> > > +}
> > > +
> > > int
> > > main()
> > > {
> > > @@ -240,4 +259,5 @@ main()
> > > test05();
> > > test06();
> > > test07();
> > > + test08();
> > > }
> > > --
> > > 2.49.0.111.g5b97a56fa0
> > >
> > >
> > >
