lkml.org 
[lkml]   [2009]   [Oct]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH] dcache: better name hash function
    On Tue, 27 Oct 2009 03:45:50 +0100
    Eric Dumazet <eric.dumazet@gmail.com> wrote:

    > Stephen Hemminger <shemminger@vyatta.com>, Al Viro a écrit :
    > > --- a/include/linux/dcache.h 2009-10-26 14:58:45.220347300 -0700
    > > +++ b/include/linux/dcache.h 2009-10-26 15:12:15.004160122 -0700
    > > @@ -45,15 +45,28 @@ struct dentry_stat_t {
    > > };
    > > extern struct dentry_stat_t dentry_stat;
    > >
    > > -/* Name hashing routines. Initial hash value */
    > > -/* Hash courtesy of the R5 hash in reiserfs modulo sign bits */
    > > -#define init_name_hash() 0
    > > +/*
    > > + * Fowler / Noll / Vo (FNV) Hash
    > > + * see: http://www.isthe.com/chongo/tech/comp/fnv/
    > > + */
    > > +#ifdef CONFIG_64BIT
    > > +#define FNV_PRIME 1099511628211ull
    > > +#define FNV1_INIT 14695981039346656037ull
    > > +#else
    > > +#define FNV_PRIME 16777619u
    > > +#define FNV1_INIT 2166136261u
    > > +#endif
    > > +
    > > +#define init_name_hash() FNV1_INIT
    > >
    > > -/* partial hash update function. Assume roughly 4 bits per character */
    > > +/* partial hash update function. */
    > > static inline unsigned long
    > > -partial_name_hash(unsigned long c, unsigned long prevhash)
    > > +partial_name_hash(unsigned char c, unsigned long prevhash)
    > > {
    > > - return (prevhash + (c << 4) + (c >> 4)) * 11;
    > > + prevhash ^= c;
    > > + prevhash *= FNV_PRIME;
    > > +
    > > + return prevhash;
    > > }
    > >
    > > /*
    >
    > OK, but thats strlen(name) X (long,long) multiplies.
    >
    > I suspect you tested on recent x86_64 cpu.
    >
    > Some arches might have slow multiplies, no ?
    >
    > jhash() (and others) are optimized by compiler to use basic and fast operations.
    > jhash operates on blocs of 12 chars per round, so it might be a pretty good choice once
    > out-of-line (because its pretty large and full_name_hash() is now used by
    > a lot of call sites)
    >
    > Please provide your test program source, so that other can test on various arches.
    >
    > Thanks

    long on i386 is 32 bits so it is 32 bit multiply. There is also an optimization
    that uses shift and adds.




    --
    [unhandled content-type:application/x-bzip]
    \
     
     \ /
      Last update: 2009-10-27 04:57    [W:0.025 / U:30.720 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site