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.129.124]) by sourceware.org (Postfix) with ESMTPS id E85A03858C66 for ; Mon, 6 Mar 2023 17:36:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E85A03858C66 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1678124209; 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=WIfD0qOva7P8b2WiXpY98KHuzxEdAd4Kc0d4tm2Zih0=; b=e9qwCOU5u8wpJ8caJXu+031aSiIHNdEy5ut3HiRoJTC5OR9c2rKgpuVz2r6fTcwpQBIXh9 Cpnj+wyJNle5roBTbRx7LUPntF6qksycUuqe4FlTBqQVNrZyIlK/jpTNwxe/Q++VE+IeFT sJSSz9PvkYe02DLFxpJDMZ0+rCLEL+g= Received: from mail-lf1-f70.google.com (mail-lf1-f70.google.com [209.85.167.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-21-uci4HGEoOWK0y0FQvRa9Rw-1; Mon, 06 Mar 2023 12:36:48 -0500 X-MC-Unique: uci4HGEoOWK0y0FQvRa9Rw-1 Received: by mail-lf1-f70.google.com with SMTP id o22-20020a056512051600b004db26d37741so3023525lfb.19 for ; Mon, 06 Mar 2023 09:36:48 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678124207; 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=WIfD0qOva7P8b2WiXpY98KHuzxEdAd4Kc0d4tm2Zih0=; b=zqck5p/rtUhSY1NDuKobLin0bVGGiFG4+LrtrFPX/z9pq+ScnFQl30yQ2zr0QvcKi3 P1lnntgWJOoLU459Au8K1sAuMMd++walJ7hlm61aYiVCr7dha5fabWuL3sSp1rAou1KY gP6ewzJ3GBVS4871r2cF9tmxrgdUkr8+hpQ/oUET/bXKGLpKGtccWkUpG2fGTt4WDMua mScvCpNMf2JiMZb+/iLRjEpqFzO7e+d70/pKvUt3C9PvrwxGUusZf+DKAfuXDqLFWJyI YXHoPLAcG9+NR1bwnvift9cw+A172ORwo10VgywW6xXXSN0o2kP7Lca9jiRjYcxWj687 WaHw== X-Gm-Message-State: AO0yUKVL2zTLyqaQQ/2ZA9oOtbquUoLlb+HVlAMI7Q/JmT8dVkukmSBc REiQ7ZBkyksYnrzzWuE7Z39fV4gTEi0JiA3cz9/YIeFZc04iYhDu6emGnn+IqkbfdwyWQsm5vW6 jZC2xEc3D44aMtWzH5Jm2WlgooF0wwB5g1A== X-Received: by 2002:a05:6512:68:b0:4d8:5f47:e4d3 with SMTP id i8-20020a056512006800b004d85f47e4d3mr3395868lfo.8.1678124207017; Mon, 06 Mar 2023 09:36:47 -0800 (PST) X-Google-Smtp-Source: AK7set8D2cFN+loWN72UXM5dwIm84rhjN8uxv2e+2B1Ucpd5lIXDJBH0ZWnXJPqWCXLoXYkhO9w9n4GuSJ5JyKRlbpc= X-Received: by 2002:a05:6512:68:b0:4d8:5f47:e4d3 with SMTP id i8-20020a056512006800b004d85f47e4d3mr3395859lfo.8.1678124206667; Mon, 06 Mar 2023 09:36:46 -0800 (PST) MIME-Version: 1.0 References: <43172ea5-6729-02c5-d374-9537fff7eb4c@gmail.com> <7313d189-ae56-4582-6f23-9263dbf57dd3@gmail.com> In-Reply-To: <7313d189-ae56-4582-6f23-9263dbf57dd3@gmail.com> From: Jonathan Wakely Date: Mon, 6 Mar 2023 17:36:35 +0000 Message-ID: Subject: Re: [PATCH] libstdc++: Limit allocations in _Rb_tree 1/2 To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: "libstdc++@gcc.gnu.org" , gcc-patches 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=-5.9 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,KAM_NUMSUBJECT,KAM_SHORT,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=no 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 Wed, 22 Feb 2023 at 06:06, Fran=C3=A7ois Dumont via Libstdc++ 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 comparer we would > create a string_view instance on each comparer call and so each time do > a strlen. That's what std::less is for. I don't think we need to spend time trying to solve the problem against for std::less when std::less 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=3D96088#c1 (keeping https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D96088#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 960= 88] > > 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 operat= or. > (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=C3=A7ois