lkml.org 
[lkml]   [1998]   [Sep]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectImproved dcache name hash
I asked Bob Jenkins, a great developer of hash functions, for
a good hash for dentry lookup. The main cosntraint is that
to work in the paring loop, it has to operate a byte at
a time, which his other hashes don't achieve.

Here is what he came up with:

word32 one_at_a_time(unsigned char const *key, size_t len)
{
word32 hash = 0x9e3779b9; /* Or any arbitrary value */
size_t i;

for (i=0; i < len; ++i) {
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);

return hash;
}

Pretty simple, but much more effective and thorough that
what's there now.

The last three steps are to make sure the low 10 bits or so,
as currently used, are an effective hash of the whole thing.
Obviously, if you're comparing all 32 bits, you don't need them.

A trickier question is where to include the parent dentry
pointer. The current code does this after the hash is computed
on the name. It could be added in using this algorithm, just
like it was a character, but that breaks some of the assumptions
the hash is based on.

An alternative which might do better is to include it at
the *beginning*, in the initial hash value.

Question: other than messing up the qstr abstraction, is there
any reason why the dcache can't just have one kind of hash,
a hash of the name plus the parent dentry?
--
-Colin

-
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/faq.html

\
 
 \ /
  Last update: 2005-03-22 13:44    [W:0.042 / U:0.136 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site