lkml.org 
[lkml]   [2002]   [Feb]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: Submssions for 2.4.19-pre [Fibonacci Hashing (William Lee Irwin)] [Discuss :) ]
    On Mon, 25 Feb 2002, Michael Cohen wrote:

    > This one was given to me by WLI himself;

    Are you sure these are the latest bit-sparse primes ?


    > +++ linux-patched/include/asm-alpha/param.h Mon Feb 25 20:44:35 2002

    > +/* SPARSE_GOLDEN_RATIO_PRIME ought to be different for non-32bit arches. */
    > +
    > +#ifndef SPARSE_GOLDEN_RATIO_PRIME
    > +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL
    > +#endif

    > +++ linux-patched/include/asm-arm/param.h Mon Feb 25 20:43:13 2002
    > +#ifndef SPARSE_GOLDEN_RATIO_PRIME
    > +#define SPARSE_GOLDEN_RATIO_PRIME 0x9e004001UL
    > +#endif

    Yuck, the fact that you're defining the exact same constant in
    many .h files is ugly. Could you move this to one place ?

    (maybe linux/hash.h like Rusty is doing for 2.5?)

    > + unsigned long hash;
    > + hash = (unsigned long) mapping + index;
    > + hash *= SPARSE_GOLDEN_RATIO_PRIME;
    > + hash >>= BITS_PER_LONG - PAGE_HASH_BITS;
    > + hash &= PAGE_HASH_SIZE - 1;
    > + return hash;

    For 64-bit systems you'll want:

    1) a 64-bit golden ratio prime
    2) expanding the bit ops by hand because gcc doesn't do
    it for you


    These last 2 points are easy, you can just copy the stuff
    from the struct page patch I sent earlier.

    cheers,

    Rik
    --
    "Linux holds advantages over the single-vendor commercial OS"
    -- Microsoft's "Competing with Linux" document

    http://www.surriel.com/ http://distro.conectiva.com/

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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