[ovs-dev] [classifier-opt] hash: Introduce an implementation of murmurhash.

[Ben Pfaff]

On Mon, Aug 20, 2012 at 07:15:33PM -0700, Ethan Jackson wrote:
> I verified that the code you've written matches up with:
> 
> http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp

Thanks.

> Because you're only hashing words you leave out the following section of code:
> 
> 
> ------------------------------------------
>   //----------
>   // tail
> 
>   const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
> 
>   uint32_t k1 = 0;
> 
>   switch(len & 3)
>   {
>   case 3: k1 ^= tail[2] << 16;
>   case 2: k1 ^= tail[1] << 8;
>   case 1: k1 ^= tail[0];
>           k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
>   };
> 
> -----------------------------------
> 
> I would like to see an XXX comment noting it's absence so that we
> remember to fold it in when/if we replace hash_bytes() with murmur.

I'm not sure of the benefit.  When/if we do that, we'll obviously need
to add some code to deal with the one-to-three byte tail, and the
obvious way to do that is to look at the URL.

> I want to replace the implementation of flow_hash_symmetric_l4() with
> this because it's in the fast path for bundle actions, and it's
> current implementation is particularly inefficient.  Any reason I
> shouldn't?

I actually tried to reformulate the Jenkins hash to work out better
there, and failed, and that's why I started looking for a new hash in
the first place, so yes I think that's appropriate.

> Also, I'm going to start doing Acked-bys
> 
> Acked-by: Ethan Jackson <ethan at nicira.com>

Thanks.