lkml.org 
[lkml]   [1999]   [May]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    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)

    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/

    \
     
     \ /
      Last update: 2005-03-22 13:51    [W:0.022 / U:31.704 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site