cvs commit: src/sys/kern vfs_bio.c

[Nate Lawson]

On Wed, 3 Dec 2003, Don Lewis wrote:
>   Modified files:        (Branch: RELENG_4)
>     sys/kern             vfs_bio.c
>   Log:
>   The existing hash algorithm in bufhash() does not distribute entries
>   very well across buckets, especially in the case of cylinder group blocks
>   which are located at a sequence of locations that are a multiple of a large
>   power of two apart.  In the case of large file systems, one or possibly
>   a few of the hash chains can get excessively long.  Replace the existing
>   hash algorithm with a variation on the Fibonacci hash.
>
>   Tested by:      Ken Marx <kmarx at vicor.com>
>
>   Revision    Changes    Path
>   1.242.2.22  +37 -2     src/sys/kern/vfs_bio.c

This is excellent.  MTC?  (Merge To Current)  :)

Also, whitespace nit:

> +	 * Volume 3 / Sorting and Searching_
> +	 *
> +         * We reduce the argument to 32 bits before doing the hash to
> +	 * avoid the need for a slow 64x64 multiply on 32 bit platforms.
> +	 *

-Nate