Re: more on hash functions
Andi Kleen (ak@muc.de)
08 Apr 1999 16:27:26 +0200
cel@monkey.org (Chuck Lever) writes:
>
> the buffer hash function i used is this:
>
> #define _hashfn(dev,block) \
> ((((unsigned long)(block) * (40499UL * 65543UL)) >> 17) & bh_hash_mask)
>
> this is the same number of instructions as the old function, except that
> one of the instructions is IMUL. i haven't looked up how expensive this
> might be. however, i believe a fixed expense is better than a higher
> loops/lookup average, since IMUL with a constant multiplier doesn't incur
> any memory overhead once it's in the instruction cache, whereas an extra
> iteration of find_buffer might be another 2 memory references, either or
> both of which might be cache misses.
This is correct for the x86 picture, but breaks e.g. on earlier sparcs
or some m68ks where multiplication is very slow. Remember Linux is not x86
only.
-Andi
--
This is like TV. I don't like TV.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/