Messages in this thread | | | Date | Mon, 26 Oct 2009 20:53:51 -0700 | From | Stephen Hemminger <> | Subject | Re: [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] | |