MurmurHash 2.0 is over 100% faster than SuperFastHash and Lookup3

[Austin Appleby]

OneAtATime - 354.163715 mb/sec
FNV - 443.668038 mb/sec
SuperFastHash - 985.335173 mb/sec
lookup3 - 988.080652 mb/sec
MurmurHash 1.0 - 1363.293480 mb/sec
MurmurHash 2.0 - 2056.885653 mb/sec


That's not a typo. :)

So, most hashes do this -

while(WeHaveKeybits)
Hash += GetSomeKeybits()
Mix(Hash)

But it turns out it's faster to do this -

while(WeHaveKeybits)
Temp = GetSomeKeybits()
Mix1(Temp)
Hash += Temp
Mix2(Hash)

because the two mixes can run in parallel inside the cpu. Due to some
bizarre instruction ordering / dispatch rules / etc in the Core 2 Duo,
this actually can be _much_ faster.

Vroom!

-Austin

[Paolo Bonzini]

> But it turns out it's faster to do this -
>
> while(WeHaveKeybits)
> Temp = GetSomeKeybits()
> Mix1(Temp)
> Hash += Temp
> Mix2(Hash)
>
> because the two mixes can run in parallel inside the cpu. Due to some
> bizarre instruction ordering / dispatch rules / etc in the Core 2 Duo,
> this actually can be _much_ faster.

Wow. Since it took me a while to understand this I'll notice that it
the parallel mixes are from *different* iterations so you have

Temp = GetSomeKeybits()
Mix1(Temp)
Hash += Temp

Mix2(Hash) **

Temp = GetSomeKeybits()
Mix1(Temp) **
Hash += Temp
Mix2(Hash)

and it is the two asterisk-ed mixes that run in parallel.

I noticed that your mixing function is now

#define MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h += k; h *= m; }
^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^
Mix1 Mix2

Are the two multiplications really necessary?

Paolo

[Austin Appleby]

They're absolutely necessary (removing any one of them causes one of
my tests to fail), and due to some strange CPU-related reason if I
remove the second k *= m performance actually goes _down_ to 1600 megs/
sec.

[Austin Appleby]

Oh, I forgot to post the link - the website is http://murmurhash.googlepages.com
(hasn't changed, but just in case someone stumbles across this thread
somewhere else...)