DragonFly kernel List (threaded) for 2008-11
DragonFly BSD
DragonFly kernel List (threaded) for 2008-11
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: HEADS UP - HAMMER work


From: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>
Date: Thu, 13 Nov 2008 07:48:21 -0800 (PST)

:Just curious what the new directory hash will be. Is it "just" a 
:different, improved hash-function with less collisions, or something 
:completely different.
:
: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?
:
:Regards,
:
:   Michael

    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.

					-Matt
					Matthew Dillon 
					<dillon@backplane.com>



[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]