This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
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.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.
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.
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: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:
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.
1- std::hash<int> 2- std::hash<std::string> 3- user_defined_hash<xxx> which cannot throw
Thanks! Paolo.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |