[lkml]   [1999]   [May]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Hash functions (was Re: 2.2.6_andrea2.bz2)
>>I really don't understand why. For example the hashfn for SHIFT=11
>>(best SHIFT for the buffer cache) could be written as ('normalized'):
>> i = (hash * 0x1BBCD880 ) >> (32 - HASH_BITS)
>>This is not even near the golden ratio nor in one of Knuth's
>>recommended intervals...

Andrea, may I reorder your questions?

>And what is `hash'? The input of the hashfn of buffers are blocks and dev.

Chuck tuned various hash functions, and only the buffer cache uses
blocks and dev. hash is a generic substitution. In my description I
used 'k' up to this point.

>I don't follow you in this last point. Where does 0x1BBCD880 came from?

Oh yes, I see. I missed an important step here.

The hash function for the buffer cache Chuck suggests is:

#define _hashfn(dev,block) ((((block) * 2654435761UL) >> SHIFT) &bh_hash_mask)
with SHIFT = 11. That's a really good _hashfn even for various hash
table sizes, but if we want to analyse this function we must set
SHIFT = (32 - HASH_BITS) and adjust the multiplier accordingly.

Since my hash table size is 16384 and thus (32 - HASH_BITS) = 18 the
'normalized' hashfn is:

i = ((k * 2654435761UL) >> 11) & bh_hash_mask
= ((k * 2654435761UL) << ((32 - HASH_BITS) - 11)) >> (32 - HASH_BITS)
= (k * (2654435761UL << (18 - 11))) >> (32 - HASH_BITS)

i = (k * 465361024UL) >> (32 - HASH_BITS)


#define _hashfn(dev,block) ( ((block) * 0x1BBCD880 ) >> (32 - HASH_BITS) )

So instead of using the golden ratio we set M=465361024 (m=0.108350306).
Using exactly the golden ratio can have some disadvantages and Knuth
gives some hints how to find better m. However, I'd never expect a
multiplier that way off to be that good.

_ x ___
/ \_/_\_ /,--' (Peter Steiner)
\_____/ signature V0.2 alpha
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:51    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean