From owner-freebsd-fs Mon Jul 2 8:14: 9 2001 Delivered-To: freebsd-fs@freebsd.org Received: from peorth.iteration.net (peorth.iteration.net [208.190.180.178]) by hub.freebsd.org (Postfix) with ESMTP id 0451137B401; Mon, 2 Jul 2001 08:14:05 -0700 (PDT) (envelope-from keichii@iteration.net) Received: by peorth.iteration.net (Postfix, from userid 1001) id 7338859229; Mon, 2 Jul 2001 10:14:02 -0500 (CDT) Date: Mon, 2 Jul 2001 10:14:02 -0500 From: "Michael C . Wu" To: Ian Dowse Cc: freebsd-fs@freebsd.org, mckusick@mckusick.com, dillon@freebsd.org Subject: Re: CFR: UFS directory hashing Message-ID: <20010702101401.B98201@peorth.iteration.net> Reply-To: "Michael C . Wu" Mail-Followup-To: "Michael C . Wu" , Ian Dowse , freebsd-fs@freebsd.org, mckusick@mckusick.com, dillon@freebsd.org References: <200106192016.aa70837@salmon.maths.tcd.ie> <200107020122.aa66571@salmon.maths.tcd.ie> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200107020122.aa66571@salmon.maths.tcd.ie>; from iedowse@maths.tcd.ie on Mon, Jul 02, 2001 at 01:22:27AM +0100 X-PGP-Fingerprint: 5025 F691 F943 8128 48A8 5025 77CE 29C5 8FA1 2E20 X-PGP-Key-ID: 0x8FA12E20 Sender: owner-freebsd-fs@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org 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