[lkml]   [2001]   [Feb]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [rfc] Near-constant time directory index for Ext2
    Linus Torvalds wrote:
    > On Tue, 20 Feb 2001, Daniel Phillips wrote:
    > >
    > > You mean full_name_hash? I will un-static it and try it. I should have
    > > some statistics tomorrow. I have a couple of simple metrics for
    > > measuring the effectiveness of the hash function: the uniformity of
    > > the hash space splitting (which in turn affects the average fullness
    > > of directory leaves) and speed.
    > I was more thinking about just using "dentry->d_name->hash" directly, and
    > not worrying about how that hash was computed. Yes, for ext2 it will have
    > the same value as "full_name_hash" - the difference really being that
    > d_hash has already been precomputed for you anyway.
    > > Let the hash races begin.
    > Note that dentry->d_name->hash is really quick (no extra computation), but
    > I'm not claiming that it has anything like a CRC quality. And it's
    > probably a bad idea to use it, because in theory at least the VFS layer
    > might decide to switch the hash function around. I'm more interested in
    > hearing whether it's a good hash, and maybe we could improve the VFS hash
    > enough that there's no reason to use anything else..

    In the first heat of hash races - creating 20,000 files in one directory
    - dentry::hash lost out to my original hack::dx_hash, causing a high
    percentage of leaf blocks to remain exactly half full and slowing down
    the whole thing by about 5%. (This was under uml - I haven't tried it
    native yet but I expect the results to be similar.)

    Contender Result
    ========= ======
    dentry::hash Average fullness = 2352 (57%)
    hack::dx_hash Average fullness = 2758 (67%)

    This suggests that dentry::hash is producing distinctly non-dispersed
    results and needs to be subjected to further scrutiny. I'll run the
    next heat of hash races tomorrow, probably with R5, and CRC32 too if I
    have time.

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:17    [W:0.022 / U:9.264 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site