Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

From: Thomas Gleixner
Date: Sat Apr 30 2016 - 09:05:07 EST


On Thu, 28 Apr 2016, Linus Torvalds wrote:
> It's the hashes that _look_ like they might be good hashes, but
> there's not a lot of analysis behind it, that I would worry about. The
> simple prime modulus _should_ be fine, but at the same time I kind of
> suspect we can do better. Especially since it has two multiplications.
>
> Looking around, there's
>
> http://burtleburtle.net/bob/hash/integer.html
>
> and that 32-bit "full avalanche" hash in six shifts looks like it
> could be better. You wouldn't want to inline it, but the point of a
> full avalanche bit mixing _should_ be that you could avoid the whole
> "upper bits" part, and it should work independently of the target set
> size.

Yes. So I tested those two:

u32 hash_64(u64 key)
{
key = ~key + (key << 18);
key ^= key >> 31;
key += (key << 2)) + (key << 4);
key ^= key >> 11;
key += key << 6;
key ^= key >> 22;
return (u32) key;
}

u32 hash_32(u32 key)
{
key = (key + 0x7ed55d16) + (key << 12);
key = (key ^ 0xc761c23c) ^ (key >> 19);
key = (key + 0x165667b1) + (key << 5);
key = (key + 0xd3a2646c) ^ (key << 9);
key = (key + 0xfd7046c5) + (key << 3);
key = (key ^ 0xb55a4f09) ^ (key >> 16);
return key;
}

They are really good and the results are similar to the simple modulo prime
hash. hash64 is slightly faster as the modulo prime as it does not have the
multiplication.

I'll send a patch to replace hash_64 and hash_32.

Text size:
x86_64 i386 arm
hash_64 88 148 128
hash_32 88 84 112

So probably slightly too large to inline.

Thanks,

tglx