<div dir="ltr">Both are not very sophisticated.<div><br></div><div>You should also look at the different MurmurHash versions, and descendants such as CityHash.</div><div><br></div><div>They are only very slightly more complex (e.g. two multiplies and a rotate) but of extremely good quality, approaching MD5 or SHA for randomness and independence of resulting bits (but not secure against malicious attacks like they are).</div><div><br></div><div>I've successfully used simply k (i.e. c =1) for both integers and pointers in hash tables with prime number sizes. It works fine, and they usually have non-overlapping ranges in practice. Hashing structures and strings is the more interesting challenge.</div><div><br></div><div>But if you're using power of two (or at least non-prime) table sizes then you should munch up the bits a lot more with multipliers with a lot more bits, not just something like 37.</div><div><br></div><div>It may be that these hash tables don't have many entries and don't have many collisions and 37 is fine, and a more expensive hash function would slow it down. Only testing can tell you.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 10, 2017 at 11:19 AM, Francois Fayard via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">> On Jan 10, 2017, at 8:56 AM, Mehdi Amini <<a href="mailto:mehdi.amini@apple.com">mehdi.amini@apple.com</a>> wrote<br>
<span class="">><br>
> Some tests I can suggest is to replace the hash function with your favorite and:<br>
<br>
</span>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.<br>
<span class=""><br>
> ultimately I believe real-world impact is the best way to get a change in.<br>
<br>
</span>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.<br>
<br>
> If this is used for having pointers, then it is likely gonna be used *everywhere*.<br>
> Even simple test like “time to deserialize a large bitcode file” would be a good start.<br>
<br>
<br>
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.<br>
So the hashing function for pointers is not flawed like the one for integers.<br>
<br>
François Fayard<br>
<div class="HOEnZb"><div class="h5">______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div>