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

[Michael Cohen <me@ohdarn.net>]

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

> 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 ?

WLI has yet to update me, and I've yet to see anything new from him in this area.  I could be mistaken.

> > +++ 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?)

Possible.  Take a look at HZ though. It's an arch-specific parameter similar to HZ (different for some arches, but not all) and it looks like it belongs in params.h for that reason.
 
> > +	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.

Great, thanks :)

> 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/