Re: [PATCH][Hashtable 6/6] PR 68303 small size optimization

[Jonathan Wakely <jwakely@redhat.com>]

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 <bits/functional_hash.h> 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<typename _Hash>
+       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.