From owner-freebsd-current Thu Sep 26 11:30:19 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 53F4137B401 for ; Thu, 26 Sep 2002 11:30:18 -0700 (PDT) Received: from salmon.maths.tcd.ie (salmon.maths.tcd.ie [134.226.81.11]) by mx1.FreeBSD.org (Postfix) with SMTP id 0628243E6A for ; Thu, 26 Sep 2002 11:30:17 -0700 (PDT) (envelope-from dwmalone@maths.tcd.ie) Received: from astro.maths.tcd.ie by salmon.maths.tcd.ie with SMTP id ; 26 Sep 2002 19:30:16 +0100 (BST) To: Terry Lambert Cc: freebsd-current@FreeBSD.ORG Subject: Re: Journaled filesystem in CURRENT In-reply-to: Your message of "Thu, 26 Sep 2002 11:16:35 PDT." <3D934F03.EB9A6616@mindspring.com> X-Request-Do: Date: Thu, 26 Sep 2002 19:30:11 +0100 From: David Malone Message-ID: <200209261930.aa30657@salmon.maths.tcd.ie> 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 > > 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-). If you are searching based on contents of a file, then any directory layout scheme will require mean N/2 probes on success and N on failure surely? And if these probes are linear (ie. in the order they are in the directory) then this really is O(N) both with and without dirhash 'cos the probles will be O(1). David. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message