Date: Wed, 3 Dec 2003 19:58:34 -0800 (PST) From: Nate Lawson <nate@root.org> To: Don Lewis <truckman@FreeBSD.org> Cc: cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/kern vfs_bio.c Message-ID: <20031203195731.G21901@root.org> In-Reply-To: <20031203214943.4CDC516A565@hub.freebsd.org> References: <20031203214943.4CDC516A565@hub.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20031203195731.G21901>