Messages in this thread | | | Date | Sun, 9 May 1999 23:26:57 +0200 | From | Peter Steiner <> | Subject | Re: 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)
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/
| |