[Bug libstdc++/54075] [4.7.1] unordered_map insert still slower than 4.6.2

[Paolo Carlini]

Hi,

On 11/13/2012 10:40 PM, François Dumont wrote:
> Here is the proposal to remove shrinking feature from hash policy. I 
> have also considered your remark regarding usage of lower_bound so 
> _M_bkt_for_elements doesn't call _M_next_bkt (calling lower_bound) 
> anymore. For 2 of the 3 calls it was only a source of redundant 
> lower_bound invocations, in the last case I call _M_next_bkt explicitly.
>
> 2012-11-13  François Dumont  <fdumont@gcc.gnu.org>
>
>     * include/bits/hashtable_policy.h (_Prime_rehash_policy): Remove
>     automatic shrink.
>     (_Prime_rehash_policy::_M_bkt_for_elements): Do not call
>     _M_next_bkt anymore.
>     (_Prime_rehash_policy::_M_next_bkt): Move usage of
>     _S_growth_factor ...
>     (_Prime_rehash_policy::_M_need_rehash): ... here.
>     * include/bits/hashtable.h (_Hashtable<>): Adapt.
>
> Tested under linux x86_64, normal and debug modes.
Thanks. First blush the patch looks good but please give us a few days 
to analyze the details of it, we don't want to make mistakes for 4.8.
> Regarding performance, I have done a small evolution of the 54075.cc 
> test proposed last time. It is now checking performance with and 
> without cache of hash code. Result is:
>
> 54075.cc                     std::unordered_set 300000 Foo insertions 
> without cache       9r    9u    0s 13765616mem    0pf
> 54075.cc                     std::unordered_set 300000 Foo insertions 
> with cache      14r   13u    0s 18562064mem    0pf
> 54075.cc                     std::tr1::unordered_set 300000 Foo 
> insertions without cache       9r    8u    1s 13765616mem    0pf
> 54075.cc                     std::tr1::unordered_set 300000 Foo 
> insertions with cache      14r   13u    0s 18561952mem    0pf
>
>     So the difference of performance in this case only seems to come 
> from caching the hash code or not. In reported use case default 
> behavior of std::unordered_set is to cache hash codes and 
> std::tr1::unordered_set not to cache it. We should perhaps review 
> default behavior regarding caching the hash code. Perhaps cache it if 
> the hash functor can throw and not cache it otherwise, not easy to 
> find out what's best to do.
Ah good. I think we finally have nailed the core performance issue. And, 
as it turns out, I'm a bit confused about the logic we have in place now 
for the defaults: can you please summarize what we are doing and which 
are the trade offs (leaving out the technicalities having to do with the 
final types)? I think the most interesting are three:

     1- std::hash<int>
     2- std::hash<std::string>
     3- user_defined_hash<xxx> which cannot throw

In the first we should normally not cache; in the second, from a 
performance point of view (from the exception safety point of view we 
could do both, because std::hash<std::string> doesn't throw anyway) it 
would be better to cache; the third case is rather tricky, because, like 
the case of std::string, from the exception safety point of view we 
could do both, thus it's purely a performance issue. Do I understand 
correctly that currently we handle 2- and 3- above in the same way, thus 
we cache? It seems to me that whereas that kind of default makes a lot 
of sense for std::string, doesn't necessarily make sense for everything 
else, and it seems to me that such kind of default makes a suboptimal 
use of the knowledge we have via __is_noexcept_hash that the functor 
doesn't throw. That seems instead a sort of user-hint to not cache! 
Given the unfortunate situation that the user has no way to explicitly 
pick a behavior when instantiating the container, we can imagine that he 
can anyway provide a strong if indirect hint by decorating or not with 
noexcept the call operator. We could even document that as part of our 
implementation defined behavior. How does it sound? Do we have a way to 
figure out what other implementations are doing? Outside std::hash, it 
should be pretty easy to instantiate with a special functor which 
internally keeps a counter... if we have evidence that the other best 
implementations don't cache for 3- we should definitely do the same.

To summarize my intuitions are (again, leaving out the final technicalities)

     a- std::hash specializations for scalar types -> no cache
     b- std::hash specialization for for std::string (or maybe 
everything else, for simplicity) -> cache
     c- user defined functor -> cache or not basing on __is_noexcept_hash

Jon?

Thanks!
Paolo.