From owner-freebsd-current@FreeBSD.ORG Sat Sep 4 20:31:29 2004 Return-Path: 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 42CE716A4CE; Sat, 4 Sep 2004 20:31:29 +0000 (GMT) Received: from apollo.backplane.com (apollo.backplane.com [216.240.41.2]) by mx1.FreeBSD.org (Postfix) with ESMTP id 2845243D39; Sat, 4 Sep 2004 20:31:29 +0000 (GMT) (envelope-from dillon@apollo.backplane.com) Received: from apollo.backplane.com (localhost [127.0.0.1]) i84KVQla047188; Sat, 4 Sep 2004 13:31:26 -0700 (PDT) (envelope-from dillon@apollo.backplane.com) Received: (from dillon@localhost) by apollo.backplane.com (8.12.9p2/8.12.9/Submit) id i84KVQFc047187; Sat, 4 Sep 2004 13:31:26 -0700 (PDT) (envelope-from dillon) Date: Sat, 4 Sep 2004 13:31:26 -0700 (PDT) From: Matthew Dillon Message-Id: <200409042031.i84KVQFc047187@apollo.backplane.com> To: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=) References: <200409041834.i84IYVrk032267@gw.catspoiler.org> cc: Don Lewis cc: freebsd-current@FreeBSD.org Subject: Re: what is fsck's "slowdown"? X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 04 Sep 2004 20:31:29 -0000 : :Don Lewis writes: :> At least it moves the buffer to the front of the list so that repeated :> accesses of the same buffer are fast. : :Sounds like it's just waiting to be converted into a splay tree... : :DES :-- :Dag-Erling Smørgrav - des@des.no From what Don says it looks like we know what this particular cpu issue is... that it is related to how fsck keeps track of 0-length directories (in a linear list). Coupled with the fact that many 0-length directories wind up occuring (probably due to upper/lowervp refs from unionfs preventing the underlying fs's inode from being completely deleted) and you have a recipe for severe cpu usage in fsck. As far as splay trees go. Well, I am not particularly fond of splay trees because they do a *LOT* of disparate (not on the same RAS line) writes to memory, even when doing simple lookups. I feel that a read-only data access methodology is ultimately going to be the better choice on modern cpus. A binary or a radix tree with a one entry inner node cache ought to perform far better then a splay tree IMHO, which is why I haven't been backporting any of the splay code into DragonFly. Also, the splay algorithm is not very MP friendly. That said, the splay code in FreeBSD is certainly better then the code that it replaced. -Matt Matthew Dillon