[Sheepdog] [PATCH 2/5] sheep: add some candy helpers in util.c

[MORITA Kazutaka]

At Wed, 16 Nov 2011 14:59:12 +0800,
Liu Yuan wrote:
> 
> On 11/16/2011 02:45 PM, MORITA Kazutaka wrote:
> 
> > At Wed, 16 Nov 2011 13:58:26 +0800,
> > Liu Yuan wrote:
> >>
> >> On 11/16/2011 01:50 PM, MORITA Kazutaka wrote:
> >>
> >>>>>
> >>>>> We already have a hash function, fnv_64a_buf().  How about using it
> >>>>> instead of introducing new one?
> >>>>>
> >>>>
> >>>>
> >>>> When I need a hash function that inputs an integer and outputs an
> >>>> integer for specified bits, I looked at the fnv_64a_buf(), it seems to
> >>>> me it tries to hash an string to integer. So I think these hash
> >>>> functions do a different thing, no?
> >>>
> >>> We already use it to calculate a hash value from a 64 bit object id:
> >>>
> >>>   fnv_64a_buf(&oid, sizeof(uint64_t), FNV1A_64_INIT);
> >>>
> >>> I guess this generates a less random value than hash_64(), though.
> >>
> >>
> >> Umm, I didn't go over usage close enough, and this interface is more
> >> named to handle string hash, at least to me.
> >>
> >> So even we use it to hash integer, we need to further bit operation to
> >> remove extra bits. hash_long(hval, bits) has a nicer and more intuitive
> >> interface to handle integer.
> > 
> > static inline uint64_t hash_64(uint64_t val, unsigned int bits)
> > {
> >         uint64_t hash = fnv_64a_buf(&val, sizeof(uint64_t), FNV1A_64_INIT);
> > 
> >         return hash >> (64 - bits);
> > }
> > 
> > Isn't this good for you?
> > 
> 
> 
> I am not against it.
> 
> >>
> >> How about coexisting these two? fnv_64a_buf() is supposed to handle
> >> string hash and hash_long() is supposed to handle integer otherwise.
> > 
> > If you need a better randomized function for integers, I'm not against
> > introducing a new hash.  But otherwise, FNV hash looks enough to me.
> > 
> 
> 
> I really need an hash function that distribute OID to different hash
> lists, this is quite performance sensitive, since farm use it to lookup
> object hash table lists for every write operation to mark object dirty.
> 
> mind do a test to show how well it perform on OID hash? If distributed
> randomly enough, I am happy to use it.

FNV hash is one of the famous hash functions.  Although I don't know
its mathematical background so much, I think it would work well.  Many
software use it.  See also http://www.isthe.com/chongo/tech/comp/fnv/

Of course, testing would be appreciated. :)

Thanks,

Kazutaka