4

I would like to know whether std::unordered_map< int, float > still has to hash the given integer to get to the value or just uses it straight away. I need to perform this operation very fast many times a second and as std::hash<int> isn't guaranteed to be the identity function, how would I go about redefining it? (obviously not using STL and writing my own containers is possible, but I doubt those written by me will be more efficient (likely much, much slower)). Thanks!

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Max
  • 95
  • 1
  • 11
  • Have you tested if this is a problem with your application? –  Oct 02 '17 at 21:31
  • Can't speak for every compiler, but G++ has a set of "Trivial Hash" specializations which basically `static_cast` the number given to a` size_t`. – user4581301 Oct 02 '17 at 21:35
  • I'm not sure how to go about testing it, as I do not know if std::hash is being called at all (and IF it is the identity function, which I can't know either, it just seems to me that the function overhead is a waste of resources). Otherwise, no, it isn't actually a problem for the speed of the app at the moment, just wanted to know what's going on. – Max Oct 02 '17 at 21:35
  • It won't be identity (need a cast), but it will be close. Is this any help (If not a duplicate): [What is the default hash function used in C++ std::unordered_map?](https://stackoverflow.com/questions/19411742/what-is-the-default-hash-function-used-in-c-stdunordered-map) – user4581301 Oct 02 '17 at 21:38
  • In that post it says that the hashing functions are implementation dependent and from what I've read on SO so far, they only need to adhere to the standard. So while it may be close to the identity function for g++ would it be the same on clang or MSVS for example? – Max Oct 02 '17 at 21:46
  • I can't find a guarantee in the standard that it be written as a simple cast. Looking at the MSVC implementation, it looks a bit like a CRC calculation. Somebody probably did the math and found they get a better distribution, even if it means they sacrifice some time on the computation. Nothing stops you from providing your own simple cast version, but I'd profile to make sure whoever wrote the MSVC hash function wasn't smarter first. – user4581301 Oct 02 '17 at 21:59
  • 1
    At cppcon 17 someone from Google showed how to create a fast hash map: it *requires* that the hash of `int` is **not** the identity (for typical use of `int` values)! The key observation is that hashing a value is cheap compared to even one extra memory access and the key approach to make hash maps faster consists of reduced number of memory access. Just saying... I don't think the videos are live, yet, nor did I find the slides. – Dietmar Kühl Oct 02 '17 at 22:13
  • @DietmarKühl Thanks for the info, will check those out when I can find them – Max Oct 02 '17 at 22:19

2 Answers2

2

I would like to know whether std::unordered_map< int, float > still has to hash the given integer

Yes it does.

I need to perform this operation very fast many times

Did you complete your project and witnessed that this is the bottleneck of it? If not, then watch out, since you might end up as a victim of premature optimization!

how would I go about redefining it?

You have to write your own code then. Example: C++ unordered_map using a custom class type as the key, where you would use struct Key { int value; };.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • It is at the moment not a bottleneck, I just like it when things go as fast as I can make them go (I know, I know, premature optimization), this question was just bugging me. – Max Oct 02 '17 at 22:12
  • Max I understand your excitement, and your approach, but you being a victim of premature optimization is not fun, trust me! ;) – gsamaras Oct 02 '17 at 22:35
2

I very much doubt any sane compiler does it any other way than straight-through. Even then, you'd have to test to see if it has any actual detrimental performance impact (if they do it, they probably have good reason - e.g. their hash function is designed to work with their unordered_map). If you want to force your hashing function, you can have:

struct Key{
 int value;
};

then look at this answer to check how to make it work with an unordered_map.

maniek
  • 7,087
  • 2
  • 20
  • 43
  • (face-palm) Thanks to you I now realized I can just put the int in a struct and define a hash for that, no need to redefine std::hash globally. Unfortunately, one answer (this one) says it's done straight through, and the other one (from gsamaras) says it must still be hashed, so I'm a bit confused. – Max Oct 02 '17 at 22:05
  • @Max It must be hashed, but that the hash function may compile away completely if the hashing logic is trivial. A `static_cast` is pretty darn trivial, so you shouldn't see a thing. The XOR and multiply loop in MSVC, not so much, but it should unroll nicely. – user4581301 Oct 02 '17 at 22:10
  • Got it, I guess I should try redefining the function myself and see how that does against just not doing anything. – Max Oct 02 '17 at 22:17