lkml.org 
[lkml]   [2009]   [Oct]   [27]   [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, Stephen Hemminger wrote:
>
> Rather than wasting space, or doing expensive, modulus; just folding
> the higher bits back with XOR redistributes the bits better.

Please don't make up any new hash functions without having a better input
set than the one you seem to use.

The 'fnv' function I can believe in, because the whole "multiply by big
prime number" thing to spread out the bits is a very traditional model.
But making up a new hash function based on essentially consecutive names
is absolutely the wrong thing to do. You need a much better corpus of path
component names for testing.

> The following seems to give best results (combination of 16bit trick
> and string17).

.. and these kinds of games are likely to work badly on some
architectures. Don't use 16-bit values, and don't use 'get_unaligned()'.
Both tend to work fine on x86, but likely suck on some other
architectures.

Also remember that the critical hash function needs to check for '/' and
'\0' while at it, which is one reason why it does things byte-at-a-time.
If you try to be smart, you'd need to be smart about the end condition
too.

The loop to optimize is _not_ based on 'name+len', it is this code:

this.name = name;
c = *(const unsigned char *)name;

hash = init_name_hash();
do {
name++;
hash = partial_name_hash(c, hash);
c = *(const unsigned char *)name;
} while (c && (c != '/'));
this.len = name - (const char *) this.name;
this.hash = end_name_hash(hash);

(which depends on us having already removed all slashed at the head, and
knowing that the string is not zero-sized)

So doing things multiple bytes at a time is certainly still possible, but
you would always have to find the slashes/NUL's in there first. Doing that
efficiently and portably is not trivial - especially since a lot of
critical path components are short.

(Remember: there may be just a few 'bin' directory names, but if you do
performance analysis, 'bin' as a path component is probably hashed a lot
more than 'five_slutty_bimbos_and_a_donkey.jpg'. So the relative weighting
of importance of the filename should probably include the frequency it
shows up in pathname lookup)

Linus


\
 
 \ /
  Last update: 2009-11-18 23:46    [W:0.063 / U:0.656 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site