[llvm-dev] Default hashing function for integers (DenseMapInfo.h)

Francois Fayard via llvm-dev llvm-dev at lists.llvm.org
Tue Jan 10 00:19:22 PST 2017

> On Jan 10, 2017, at 8:56 AM, Mehdi Amini <mehdi.amini at apple.com> wrote
> Some tests I can suggest is to replace the hash function with your favorite and:

Thanks. I’ll give it a try. It will take some time as I need to rewrite DenseMap if I want to use the Knuth multiplicative hash.

> ultimately I believe real-world impact is the best way to get a change in.

That’s exactly what I think. I was just trying to get some hints on what parts of the code could benefit from a better hash function for integers, in order to find a benchmark which is relevant.

> If this is used for having pointers, then it is likely gonna be used *everywhere*.
> Even simple test like “time to deserialize a large bitcode file” would be a good start.

It is not used for pointers, as this function would be truly awful for them: because of alignments, pointers are of the form 2^a * k0. The hash function used for pointers is (k >> 4) ^ (k >> 9). My guess is that the k >> 4 is here because pointers returned by malloc are 16 bytes aligned. I don’t have any guess for the 9 though.
So the hashing function for pointers is not flawed like the one for integers.

François Fayard

More information about the llvm-dev mailing list