[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
    In article <>,
    Davide Libenzi <> wrote:
    >Yep, 4 is not good as a shifting factor. Prime number are the better choice for
    >this stuff.

    Oh, absolutely.

    It looks like the hash function was done rather early on in the dcache
    lifetime (one of the first things), back when nobody cared about whether
    it was really good or not because there were many much more complicated
    questions like "how the h*ll will this all ever work" ;)

    And at no point did anybody ever go back and verify whether the hash
    function made much sense or not.

    We had another boo-boo with the actual _folding_ of the "full" hash
    value into the actual hash chain pointer that is done when the name
    cache is actually looked up, which was even more embarrassing: even if
    the hash ended up being ok, we would remove most of the valid bits from
    it because it would under certain circumstances (512MB of RAM on x86)
    basically xor itself with itself.

    That took quite a while to find too - the code still worked fine, it
    just had a horrible distribution on machines with half a gig of memory.

    >The issue to have a good distribution is not only to have a good hashing
    >function, but also to give this function not correlated data.
    >Good hashing function for a Domain A may not be so good for a Domain B.

    This is not something we can do all that much about. The data we get is
    generated by the user, and can basically be a random string of
    characters. HOWEVER, there are certainly tons of _usual_ data, and
    while there's no way to select the data we can at least try to make sure
    that the distribution is good for the normal case (ie regular ASCII
    filenames, not forgetting the fact that many people use more interesting

    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:38.408 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site