Daniel James wrote:
Pete Bartlett wrote:
I have a performance hotspot when merging a few unordered_maps of the same type into a master unordered_map (also of the same type)
Currently I am doing
foreach( auto const& submap ,submaps ) master.insert( submap.begin() , submap.end() );
This seems to be somewhat wasteful because the insert is (I think) computing hashes that the >>submaps already "know".
Can I improve on this - without changing Boost?
Not as far as I know.
Thank you very much for your very helpful comments. I realise now that in my case, where the hash calculation is expensive relative to node insertion cost, it is worthwhile doing a sort of memoization technique: If my original key type is K and hash is h, I can change the key type to pair<K,size_t> where the keys are now (k,h(k)) and then give the unordered_map an adapted hash that simply returns pair.second. I now only pay the hash calculation cost when first inserting into the submaps. As you point out below, this is only safe for non-random hashes but works for me.
- some more intrusive change?
Maybe. Could write a function that inserts from another container, rather than using >iterators. It is now possible to tell if the same hash function type was used, but it isn't >possible to tell that they're equal (eg. when using a randomized hash function, the hash >values might not be the same for two different instances). It might be possible to create a >type trait to detect if the hash function has an equality operator - and assume they're not >equal if it doesn't.
Having said the above, I fancy a crack at this just for my own education. I'll let you know if I get anywhere. Thanks again, Pete