what is fsck's "slowdown"?

[Matthew Dillon]

:
:Don Lewis <truckman at 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 at 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 at backplane.com>