From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by sourceware.org (Postfix) with ESMTPS id 265D03853815; Mon, 17 May 2021 19:24:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 265D03853815 Received: by mail-wm1-x335.google.com with SMTP id l18-20020a1ced120000b029014c1adff1edso168796wmh.4; Mon, 17 May 2021 12:24:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:references:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=2eyaSOeB0z3j4XjKlDj8pZ8kIciqnV49zPYYtMBWhlY=; b=Y/Il5kiw1NTDTS1a7m+013GIx/CVHtTrf2XCvPipIH8tWQan1RnDMF/GK1CvVbrEnq QTQWt6lrOmi+D8jZmnr3HeJVKvc41/+4i9MTaCV9G6rg9kWtDH6IqPJWW476vOB//mQT MGoP1APKqa0LjUFbOPK/wOjSOc1cyH1V94dedox9f8FHTUr1ueA06cOlJCvGpsPwoQq1 6Qr1BuhtMqvn7UDhHNXjGnlwpzpJSN2jNmN0OB3WPJfUR+0C5tEZjeOJbQYbrsrCIUbg pUV66DsGLrbc/cS9p5F1GTKWa5vzvuKHekR9yrcq5Q2NPnEs/4ePS/Bwp/qUgjc2Zm3z L3og== X-Gm-Message-State: AOAM532fKmKPKyCzo7xiup5hAT8Z0JbewJXZcWEubF8e+6HxVdD3mtlN P+kEGewrre7u746V686IPfY3bkohIO7LGw== X-Google-Smtp-Source: ABdhPJxpYwyYd1XCLxvAnZB0A5Y/VcFYpNUDi7AnZARqIyoH1PBj/lcxfakxUNvf4YMsKjBNzKJ76g== X-Received: by 2002:a1c:50:: with SMTP id 77mr1073064wma.111.1621279450792; Mon, 17 May 2021 12:24:10 -0700 (PDT) Received: from ?IPv6:2a01:e0a:1dc:b1c0:e059:97ae:2f7b:8d44? ([2a01:e0a:1dc:b1c0:e059:97ae:2f7b:8d44]) by smtp.googlemail.com with ESMTPSA id n10sm18361613wrw.37.2021.05.17.12.24.09 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 17 May 2021 12:24:09 -0700 (PDT) Subject: Re: [PATCH] Hashtable PR96088 From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: "libstdc++@gcc.gnu.org" , gcc-patches References: <5b198dd5-cb89-91a0-9070-13927ac263a4@gmail.com> <524e2eee-a4ee-a05e-087f-6000c8274eff@gmail.com> <21854fd0-ad6b-1eaa-adaa-2074421fc107@gmail.com> <7bd748f6-77bd-fdcc-f925-1700ac9da3de@gmail.com> Message-ID: <764a5e3a-941f-a5ed-1a78-59f5fe9182fc@gmail.com> Date: Mon, 17 May 2021 21:24:09 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: fr X-Spam-Status: No, score=-2.2 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, KAM_NUMSUBJECT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=no autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 17 May 2021 19:24:14 -0000 Hi     No chance yet to review this proposal ? François On 06/05/21 10:03 pm, François Dumont wrote: > Hi > >     Considering your feedback on backtrace in debug mode is going to > take me some time so here is another one. > >     Compared to latest submission I've added a _Hash_arg_t partial > specialization for std::hash<>. It is not strictly necessary for the > moment but when we will eventually remove its nested argument_type it > will be. I also wonder if it is not easier to handle for the compiler, > not sure about that thought. > > Tested under Linux x86_64, ok to commit ? > > François > > > On 04/12/20 10:10 am, François Dumont wrote: >> Following submission of the heterogeneous lookup in unordered >> containers I rebased this patch on top of it. >> >> Appart from reducing its size because of some code reuse the >> heterogeneous lookup had no impact on this one. This is because when >> I cannot find out if conversion from inserted element type to hash >> functor can throw then I pass the element as-is, like if hash functor >> was transparent. >> >>     libstdc++: Limit allocation on iterator insertion in Hashtable >> [PR 96088] >> >>     Detect Hash functor argument type to find out if it is different >> to the >>     container key_type and if a temporary instance needs to be >> generated to invoke >>     the functor from the iterator value_type key part. If this >> temporary generation >>     can throw a key_type instance is generated at Hashtable level and >> used to call >>     the functors and, if necessary, moved to the storage. >> >>     libstdc++-v3/ChangeLog: >> >>             PR libstdc++/96088 >>             * include/bits/hashtable_policy.h (_Select2nd): New. >>             (_NodeBuilder<>): New. >>             (_ReuseOrAllocNode<>::operator()): Use variadic template >> args. >>             (_AllocNode<>::operator()): Likewise. >>             (_Hash_code_base<>::_M_hash_code): Add _Kt template >> parameter. >>             (_Hashtable_base<>::_M_equals): Add _Kt template parameter. >>             * include/bits/hashtable.h >>             (_Hashtable<>::__node_builder_t): New. >>             (_Hashtable<>::_M_find_before_node): Add _Kt template >> parameter. >>             (_Hashtable<>::_M_find_node): Likewise. >>             (_Hashtable<>::_Hash_arg_t): New. >>             (_Hashtable<>::_S_forward_key): New. >> (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const >> _NodeGenerator&)): >>              New. >>             (_Hashtable<>::_M_insert): Use latter. >>             * testsuite/23_containers/unordered_map/96088.cc: New test. >>             * testsuite/23_containers/unordered_multimap/96088.cc: >> New test. >>             * testsuite/23_containers/unordered_multiset/96088.cc: >> New test. >>             * testsuite/23_containers/unordered_set/96088.cc: New test. >>             * testsuite/util/replacement_memory_operators.h >>             (counter::_M_increment): New. >>             (counter::_M_decrement): New. >>             (counter::reset()): New. >> >> Note that I plan to change counter type name to something more >> meaningful but only when back to stage 1. >> >> François >> >> On 24/10/20 4:25 pm, François Dumont wrote: >>> Hi >>> >>>     Just a rebase of this patch. >>> >>> François >>> >>> On 17/10/20 6:21 pm, François Dumont wrote: >>>> I eventually would like to propose the following resolution. >>>> >>>> For multi-key containers I kept the same resolution build the node >>>> first and compute has code from the node key. >>>> >>>> For unique-key ones I change behavior when I can't find out hash >>>> functor argument type. I am rather using the iterator key type and >>>> just hope that the user's functors are prepared for it. >>>> >>>> For now I am using functor argument_type which is deprecated. I >>>> just hope that the day we remove it we will have a compiler >>>> built-in to get any functor argument type given an input type. >>>> >>>>     libstdc++: Limit allocation on iterator insertion in Hashtable >>>> [PR 96088] >>>> >>>>     Detect Hash functor argument type to find out if it is >>>> different to the >>>>     container key_type and if a temporary instance needs to be >>>> generated to invoke >>>>     the functor from the iterator value_type key part. If this >>>> temporary generation >>>>     can throw a key_type instance is generated at Hashtable level >>>> and use to call >>>>     the functors and, if needed, move it to the storage. >>>> >>>>     libstdc++-v3/ChangeLog: >>>> >>>>             PR libstdc++/96088 >>>>             * include/bits/hashtable_policy.h (_Select2nd): New. >>>>             (_NodeBuilder<>): New. >>>>             (_ReuseOrAllocNode<>::operator()): Use varriadic >>>> template args. >>>>             (_AllocNode<>::operator()): Likewise. >>>>             (_Hash_code_base<>::_M_hash_code): Add _KType template >>>> parameter. >>>>             (_Hashtable_base<>::_M_equals): Add _KType template >>>> parameter. >>>>             * include/bits/hashtable.h >>>>             (_Hashtable<>::__node_builder_t): New. >>>>             (_Hashtable<>::_M_find_before_node): Add _KType >>>> template parameter. >>>>             (_Hashtable<>::_M_find_node): Likewise. >>>>             (_Hashtable<>::_Hash_arg_t): New. >>>>             (_Hashtable<>::_S_forward_key): New. >>>> (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const >>>> _NodeGenerator&)): >>>>              New. >>>>             (_Hashtable<>::_M_insert): Use latter. >>>>             * testsuite/23_containers/unordered_map/96088.cc: New >>>> test. >>>>             * testsuite/23_containers/unordered_multimap/96088.cc: >>>> New test. >>>>             * testsuite/23_containers/unordered_multiset/96088.cc: >>>> New test. >>>>             * testsuite/23_containers/unordered_set/96088.cc: New >>>> test. >>>>             * testsuite/util/replacement_memory_operators.h >>>>             (counter::_M_increment): New. >>>>             (counter::_M_decrement): New. >>>>             (counter::reset()): New. >>>> >>>> Tested under Linux x86_64. >>>> >>>> Ok to commit ? >>>> >>>> François >>>> >>>> On 01/09/20 2:36 pm, François Dumont wrote: >>>>> Hi >>>>> >>>>>     I started working on PR96088 problem in Hashtable implementation. >>>>> >>>>>     In the case of multi-key containers the problem is easy to >>>>> manage. Now that we have _Scoped_node we can easily allocate the >>>>> node first and then extract the key from it to compute hash code. >>>>> It is quite safe as computating a hash code is rarely going to >>>>> throw especially if there is no allocation anymore to invoke the >>>>> hasher. >>>>> >>>>>     In the unique-key case it is more tricky. First I only >>>>> consider the hasher invocation, the equal_to shall be consistent >>>>> with it. My approach is to consider that if the operation needed >>>>> transform the inserted element key part into the hasher argument >>>>> can throw then I better generate a key_type instance myself and >>>>> move it to the node if it is eventually to be inserted. Note that >>>>> any allocation needed to call the hasher from the key_type is user >>>>> fault. >>>>> >>>>>     Of course the tricky part here is to find out what is the >>>>> hasher argument_type. For the moment I support hasher with a >>>>> nested argument_type typedef and function pointer. But, as pointed >>>>> out by the tests which are failing for the moment I am missing the >>>>> support for a classic functor. I am pretty sure that if I support >>>>> it I will still be missing some use cases (like std::function). So >>>>> I am looking for help on how to determine it. Or maybe the whole >>>>> approach it wrong ? >>>>> >>>>> For now I am still working on it, thanks, >>>>> >>>>> François >>>>> >>>> >>> >> >