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)
or:
#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.
Peter
--
_ x ___
/ \_/_\_ /,--' p.steiner@t-online.de (Peter Steiner)
\/>'~~~~//
\_____/ signature V0.2 alpha
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/