Date: Mon, 2 Jul 2001 10:14:02 -0500 From: "Michael C . Wu" <keichii@iteration.net> To: Ian Dowse <iedowse@maths.tcd.ie> Cc: freebsd-fs@freebsd.org, mckusick@mckusick.com, dillon@freebsd.org Subject: Re: CFR: UFS directory hashing Message-ID: <20010702101401.B98201@peorth.iteration.net> In-Reply-To: <200107020122.aa66571@salmon.maths.tcd.ie>; from iedowse@maths.tcd.ie on Mon, Jul 02, 2001 at 01:22:27AM %2B0100 References: <200106192016.aa70837@salmon.maths.tcd.ie> <200107020122.aa66571@salmon.maths.tcd.ie>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, Jul 02, 2001 at 01:22:27AM +0100, Ian Dowse scribbled: | In message <200106192016.aa70837@salmon.maths.tcd.ie>, Ian Dowse writes: | Kirk McKusick ran some filesystem benchmark code with the dirhash | code enabled. He found that if the dirhash memory limit was set | too small relative to the working set of directories, dirhash would | cause a significant performance reduction as compared with the | non-dirhash case. I believe this is caused by a thrashing effect; | if the hash structures are discarded after only a tiny number of | accesses, then the hashing gains are lost by the increased cost of | building the hashes. I think the situation here can be improved by | using something better than LRU for recycling, and by waiting for | a few accesses before going to the trouble of building the hash. I forget the name for this algorithm. (It is usually listed right next to the LRU in books.) How about this? Just retire the oldest access and keep putting the newest access onto the cache. e.g. Elements A B C D E F G 1. Try to read B D C A in that order hash now has BDCA, and hash only has space for 4 elements 2. read D G E in that order Hash now goes like this Read D Hash: B D C A (Note that we don't do anything to the hash since it already has D.) Read G Hash: D C A G Read E Hash: C A G E Thanks, Michael -- +-----------------------------------------------------------+ | keichii@iteration.net | keichii@freebsd.org | | http://iteration.net/~keichii | Yes, BSD is a conspiracy. | +-----------------------------------------------------------+ To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-fs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20010702101401.B98201>