From owner-freebsd-current Thu Sep 26 11:17:55 2002 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 9405D37B401 for ; Thu, 26 Sep 2002 11:17:53 -0700 (PDT) Received: from snipe.mail.pas.earthlink.net (snipe.mail.pas.earthlink.net [207.217.120.62]) by mx1.FreeBSD.org (Postfix) with ESMTP id 12A4443E65 for ; Thu, 26 Sep 2002 11:17:53 -0700 (PDT) (envelope-from tlambert2@mindspring.com) Received: from pool0400.cvx40-bradley.dialup.earthlink.net ([216.244.43.145] helo=mindspring.com) by snipe.mail.pas.earthlink.net with esmtp (Exim 3.33 #1) id 17udCn-0002TL-00; Thu, 26 Sep 2002 11:17:42 -0700 Message-ID: <3D934F03.EB9A6616@mindspring.com> Date: Thu, 26 Sep 2002 11:16:35 -0700 From: Terry Lambert X-Mailer: Mozilla 4.79 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: David Malone Cc: freebsd-current@FreeBSD.ORG Subject: Re: Journaled filesystem in CURRENT References: <200209251319.g8PDJYoD047918@ib.com.ua> <20020925111232.B3686@Odin.AC.HMC.Edu> <20020926111949.5c0da160.Alexander@Leidinger.net> <20020926090325.A24614@zardoc.esmtp.org> <3D93459B.E4405568@mindspring.com> <20020926174727.GA89135@walton.maths.tcd.ie> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG David Malone wrote: > On Thu, Sep 26, 2002 at 10:36:27AM -0700, Terry Lambert wrote: > > I think that what you were probably testing was directory entry > > layout and O(N) (linear) vs. O(log2(N)+1) search times for both > > non-existant entries on creates, and for any entry on lookup > > ( / 2 on lookup) . > > Though dirhash should eliminate most of this... Everybody alsways says that, and then backs off, when they realize that a traversal of a mail queue of 100,000 entries, in which the destination is known by the contents of the file, rather than the file name, is involved. 8-). IMO, dirhash is useful in small cases, particularly where locality of reference is important... which means "not during linear traversals of 100% of a directory on create/iterate" and "not during linear traversals of 50% of a directory on lookup of a specific file which exists or 100% of a directory for a specific file that ends up not existing". Cranking the size of the hash up only works to a certain point. Claus would have to answer this, but I'm pretty sure that the machines he tested on would have had dirhash, and still ended up getting bad results for his application (sendmail queue directories). -- Terry To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message