Date: Wed, 3 Dec 2003 20:29:45 -0800 (PST) From: Don Lewis <truckman@FreeBSD.org> To: nate@root.org Cc: cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/kern vfs_bio.c Message-ID: <200312040429.hB44TjeF033327@gw.catspoiler.org> In-Reply-To: <20031203195731.G21901@root.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 3 Dec, Nate Lawson wrote: > 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) :) Nope, -CURRENT uses a splay tree instead of a hash table here. > 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. >> + * Grumble ... actually two. Fix committed.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200312040429.hB44TjeF033327>