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

[Liu Yuan]

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.

Thanks,
Yuan