On 11/13/2012 11:53 PM, Paolo Carlini wrote:
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)?
We do not cache if the following conditions are all met:
- key type is an integral
- hash functor is empty and not final
- hash functor doesn't throw
As you can see we cache in most of the cases.
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?
yes, because types are not integral.
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 std::string (or maybe everything
else, for simplicity) -> cache
c- user defined functor -> cache or not basing on __is_noexcept_hash
I don't understand why we would make a distinction between
std::hash specialization and user defined functor, especially because
hash specialization can throw. I like the idea of caching based on
noexcept as its the only way users can tweak this behavior. Of course it
will mean that we will need to check for std::string explicitly.
François