[lkml]   [1999]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: random table-driven hash benchmarked
    On Sun, 25 Apr 1999, Peter Steiner wrote:
    > Here is an improved version of the multiplicative hash. It includes
    > some statistics (alt-SysRq-m). The size of the hash buffer can be
    > adjusted by changeing HASHBITS in the range of 10-15. On my system with
    > 64MB RAM a hash table size of 4096 entries is big enough
    > (#define HASHBITS 12). It's tested on 32 bit x86 processors, but I
    > tried to make it working on 64 bit systems too.

    > -#define _hashfn(dev,block) (((unsigned)(HASHDEV(dev)^block)) & bh_hash_mask)
    > +#define _hashfn(dev,block) ( \
    > + ( (((unsigned) (block)* 0x9E3779B1 )>>(32-HASHBITS))^HASHDEV(dev) ) & bh_hash_mask)

    in real world tests, 31 - HASHBITS works better. but for the buffer cache
    in specific, i have found that 11 is the best shift value. however, the
    best shift value can vary depending on the size of the hash table.

    - Chuck Lever
    corporate: <>
    personal: <> or <>

    The Linux Scalability project:

    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    [W:0.020 / U:13.756 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site