Date: Sat, 4 Sep 2004 13:31:26 -0700 (PDT) From: Matthew Dillon <dillon@apollo.backplane.com> To: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=) Cc: freebsd-current@FreeBSD.org Subject: Re: what is fsck's "slowdown"? Message-ID: <200409042031.i84KVQFc047187@apollo.backplane.com> References: <200409041834.i84IYVrk032267@gw.catspoiler.org> <xzpk6v9oo2u.fsf@dwp.des.no>
next in thread | previous in thread | raw e-mail | index | archive | help
:
:Don Lewis <truckman@FreeBSD.org> 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
<dillon@backplane.com>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200409042031.i84KVQFc047187>