From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-1.mimecast.com (us-smtp-2.mimecast.com [205.139.110.61]) by sourceware.org (Postfix) with ESMTP id 9788D393BC1A for ; Fri, 17 Jul 2020 12:58:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9788D393BC1A Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-304-RQaAqwQqPae9HgU8UeFQGA-1; Fri, 17 Jul 2020 08:58:11 -0400 X-MC-Unique: RQaAqwQqPae9HgU8UeFQGA-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id A4E65801E6A; Fri, 17 Jul 2020 12:58:10 +0000 (UTC) Received: from localhost (unknown [10.33.37.45]) by smtp.corp.redhat.com (Postfix) with ESMTP id 2A40219C58; Fri, 17 Jul 2020 12:58:10 +0000 (UTC) Date: Fri, 17 Jul 2020 13:58:09 +0100 From: Jonathan Wakely To: =?iso-8859-1?Q?Fran=E7ois?= Dumont Cc: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: [PATCH][Hashtable 6/6] PR 68303 small size optimization Message-ID: <20200717125809.GC2827066@redhat.com> References: <88d3aa39-2146-3ea5-8bb2-a4d9b70accbd@gmail.com> MIME-Version: 1.0 In-Reply-To: <88d3aa39-2146-3ea5-8bb2-a4d9b70accbd@gmail.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.84 on 10.5.11.23 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Transfer-Encoding: 8bit Content-Disposition: inline X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable 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: Fri, 17 Jul 2020 12:58:16 -0000 On 17/11/19 22:31 +0100, François Dumont wrote: >This is an implementation of PR 68303. > >I try to use this idea as much as possible to avoid computation of >hash codes. > >Note that tests are not showing any gain. I guess hash computation >must be quite bad to get a benefit from it. So I am only activating it >when hash code is not cached and/or when computation is not fast. If the tests don't show any benefit, why bother making the change? Does it help the example in the PR? >    PR libstdc++/68303 >    * include/bits/hashtable_policy.h >    (_Small_size_threshold<_Hash>): New. >    (_Hashtable_traits<>): Add _Small_size_threshold std::size_t template >    parameter, default to 0. >    (_Hashtable_traits<>::__small_size_threshold): New. >    (_Hash_code_base<>::_M_hash_code(const __node_type*)): New. >    (_Equal_helper<>::_S_node_equals): New. >    * include/bits/hashtable.h: >    (__small_size_threshold_default<>): New template alias. >    (_Hashtable<>::find): Add linear lookup when size is lower or equal to >    _Small_size_threshold. >    (_Hashtable<>::_M_emplace<_Args>(true_type, _Args&&...)): Add linear >    lookup when size is lower or equal to _Small_size_threshold. >    (_Hashtable<>::_M_insert<>(_Arg&&, const _NodeGenerator&, true_type, >    size_type)): Likewise. >    (_Hashtable<>::_M_compute_hash_code(const_iterator, const key_type&)): >    New. >    (_Hashtable<>::_M_emplace<_Args>(false_type, _Args&&...)): Use latter. >    (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&, >    false_type)): Likewise. >    (_Hashtable<>::_M_find_before_node(const key_type&)): New. >    (_Hashtable<>::_M_erase(true_type, const key_type&)): Use latter >if size >    is lower or equal to _Small_size_threshold. >    (_Hashtable<>::_M_erase(false_type, const key_type&)): Likewise. >    * include/bits/unordered_map.h (__umaps_traits): Adapt using small size >    threshold set to 20. >    (__ummap_traits): Likewise. >    * include/bits/unordered_set.h (__uset_traits, __ummset_traits): >Likewise. >    * src/c++11/hashtable_c++0x.cc: Add include. The implementation of this seems unnecessarily complicated, and it changes the mangled name of the _Hashtable_traits type, which changes the mangled name of _Hashtable too. It seems to me that instead of __traits_type::__small_size_threshold being a typedef inside the traits class, we could just use a constexpr function, maybe as a member of the _Hashtable_traits class template: --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -201,6 +201,14 @@ namespace __detail using __hash_cached = __bool_constant<_Cache_hash_code>; using __constant_iterators = __bool_constant<_Constant_iterators>; using __unique_keys = __bool_constant<_Unique_keys>; + + template + static constexpr size_t + __small_size_threshold() + { + return _Cache_hash_code ? 0 + : __detail::_Small_size_threshold<_Hash>::value; + } }; Regarding the new _Small_size_threshold class template, do we really need yet another customization point? Can't we just use __is_fast_hash? e.g. return _Cache_hash_code || __is_fast_hash ? 0 : 20; As an aside, it seems like a terrible design that _Hashtable_traits doesn't actually depend on the hash function, so any time we want to extend it to detect some other property of the hash function we need to add extra template parameters. Far too late to fix now, but we can extend it by adding members, not by changing its type.