Re: Submssions for 2.4.19-pre [Fibonacci Hashing (William Lee Irwin)]

Rik van Riel (riel@conectiva.com.br)
Mon, 25 Feb 2002 23:04:58 -0300 (BRT)


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/