1

Background

I use a small static hash table (linear probing) which I need in a stage in a OpenGL rendering pipeline, where I must retrieve and update int64_t type keys and some data as fast as possible. In short, this stage is about translating large IDs to small local indices that subsequent stages use (so here in this stage I relly need to deal with 64 bit keys once, and can't use 32 bit keys).

I've experimented long to find a hash function that works fast on both 32 bit and 64 bit arm architectures (iOS and Android smartphones). Naturally, on 32 bit devices hashing of 64 bit keys is much slower than hashing 32 bit keys (almost 10 times in my test case).

I'm now very confident with the hash I found here on SO, which outperforms the MurmurHash3 32 bit finalizer in my case (with some more collissions, but doesn't matter in my case): https://stackoverflow.com/a/12996028/1708349

All works fine and well for now, but here s the catch: I naively assign the 64 bit key to an int32_t type before hashing it - this is done for performance reasons for the 32 bit platforms. This seems to work, large data is wrapped around. But the catch is of course that this behavior is not defined.

So, my question is: What is the best (e.g. defined compiler behavior) to assign an int64_t type to an int32_t type, so it wraps around - and is for example not just assigned the lower 32 bit of the 64 bit int?

This is my actual hash function:

inline int32_t hash2(int64_t k) {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wconversion"
    int32_t x = k;
#pragma clang diagnostic pop
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x);

    return x;
}
Community
  • 1
  • 1
benjist
  • 2,740
  • 3
  • 31
  • 58
  • 1
    behaviour of casting int64_t to int32-t is well-defined , and does take lowest 32 bits. For hashing purposes, you probably don't want it, but as a rough approximation, you could calculate your x twice - once for (int32_t)k, then for (int32_t)(k>>32), and xor these two halves later. Not the best thing, but in many cases it would do. – No-Bugs Hare May 30 '15 at 13:26
  • 1
    "so it wraps around - and is for example not just assigned the lower 32 bit" - what? That's the same thing isn't it? – harold May 30 '15 at 13:56
  • Sorry for my english. Indeed I should rephrase my question mean. I mean for example it could have like a sine-curve behavior, like going from positive to negative range based on the upper bits set (with differing intervals to make some sort of distribution). – benjist May 30 '15 at 14:41

0 Answers0