DragonFly kernel List (threaded) for 2008-11
Re: HEADS UP - HAMMER work
:Just curious what the new directory hash will be. Is it "just" a
:different, improved hash-function with less collisions, or something
:And in general (for my personal understanding of how things work),
:how does hashing work together with the b-tree? There is no hash-table
:at all, I guess. What you do is to compare a 64-bit hash-key instead of
:doing a string-comparison of the file name. Is that correct?
It's a hash with semi-sorted characteristics.
I'll post it as soon as I hear back from an expert I emailed it
to, unless he shoots it down in which case it will never see the
light of day :-)
The current HAMMER hash key is just a crc, which means it is essentially
a random number with no sorting relationship to the filename. If you
have a very large directory which does not fit in cache and you are
stat()ing it in sorted order the current hash will cause inefficient
seeks on every lookup. This is still better then UFS (UFS has to scan
nearly the whole directory to find a filename if it blows out its
dirhash cache), but not as good as it could be.
I still have some work to do on it. There is a lookup-miss case which
I am not handling properly which I have to fix.