lkml.org 
[lkml]   [1999]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    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: <chuckl@netscape.com>
    personal: <chucklever@netscape.net> or <cel@monkey.org>

    The Linux Scalability project:
    http://www.citi.umich.edu/projects/linux-scalability/


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