Re: [PATCH] libstdc++: Limit allocations in _Rb_tree 1/2

[Jonathan Wakely <jwakely@redhat.com>]

On Wed, 22 Feb 2023 at 06:06, François Dumont via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Here is eventually a working proposal.
>
> Compared to the unordered container approach we need to find out what
> type is going to be used to call the comparer. Otherwise we might
> reinstantiate a temporary each time we call the comparer. For example in
> case of const char* insertion with a less<string_view> comparer we would
> create a string_view instance on each comparer call and so each time do
> a strlen.

That's what std::less<void> is for. I don't think we need to spend
time trying to solve the problem against for std::less<T> when
std::less<void> already exists.

If the concern is strings vs const char*, we could explore your
suggestion in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088#c1
(keeping https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088#c4 in
mind) so that we optimize that specific case.

> This code is tricky and do not cover all use cases. For those uncovered
> cases the default behavior is to create a key_type instance which will
> be moved to storage if needed.

Yes, it's tricky, and don't handle all cases, but slows down
compilation for all cases.

Also, I think you'll get ambiguous overloads for a comparison type
that has both first_argument_type and is_transparent defined, because
it will match two overloads.

I don't think we should be recreating the logic of transparent
comparison functions, and we shouldn't be reintroducing dependencies
on first_argument_type (in C++20 users should be able to use that
typedef for anything, e.g. make it a typedef for void, and the library
shouldn't care ... I think that would break with your patch).


> Is there any plan to create a builtin function to get help from the
> compiler to find out this type ? Something like std::invoke_result but
> giving also the actual argument types.

No, I don't think so.


>
>      libstdc++: [_Rb_tree] Limit allocations on unique insertions [PR 96088]
>
>      Detect when invoking the comparer requires an allocation using the
> noexcept
>      qualification of the functor. In this case guess the type needed to
> invoke
>      the comparer and create a temporary instance used for all comparer
> invocations.
>      This temporary instance will be eventually moved to storage
> location if it is to
>      insert. Avoid to allocate a node and construct the stored value
> otherwise.
>
>      libstdc++-v3/ChangeLog:
>
>              PR libstdc++/96088
>              * include/bits/stl_function.h
>              (std::less<>::operator()): Add noexcept qualification.
>              (std::greater::operator()): Likewise.
> (std::_Identity<>::operator<_Tp2>(_Tp2&&)): New perfect forwarding operator.
> (std::_Select1st<>::operator<_Pair2>(_Pair2&&)): New move operator.
>              * include/bits/stl_tree.h
> (_Rb_tree<>::_ConvertToValueType<>): New helper type.
>              (_Rb_tree<>::__has_firstargument): Likewise.
>              (_Rb_tree<>::_S_get_key_type_aux): New helper method, use
> latter.
>              (_Rb_tree<>::_S_get_key_type): New helper method, use latter.
>              (_Rb_tree<>::__key_type_t): New.
>              (_Rb_tree<>::__is_comparable_lhs): New.
>              (_Rb_tree<>::__is_comparable_rhs): New.
>              (_Rb_tree<>::__is_comparable): New, use latters.
>              (_Rb_tree<>::__is_nothrow_comparable_lhs): New.
>              (_Rb_tree<>::__is_nothrow_comparable_rhs): New.
>              (_Rb_tree<>::__is_nothrow_comparable): New, use latters.
>              (_Rb_tree<>::_S_forward_key): New.
>              (_Rb_tree<>::_M_get_insert_unique_pos_tr): New.
>              (_Rb_tree<>::_M_emplace_unique_kv): New.
>              (_Rb_tree<>::_M_emplace_unique_aux): New, use latter.
>              (_Rb_tree<>::_M_emplace_unique): New, use latter.
>              (_Rb_tree<>::_Auto_node::_S_build): New.
>              * testsuite/23_containers/map/96088.cc: New test case.
>              * testsuite/23_containers/multimap/96088.cc: New test case.
>              * testsuite/23_containers/multiset/96088.cc: New test case.
>              * testsuite/23_containers/set/96088.cc: New test case.
>
> François