Re: Off-Topic Question

[David Rhodus <sdrhodus@xxxxxxxxx>]

On Thu, 17 Feb 2005 21:36:45 +0100, Joerg Sonnenberger
<joerg@xxxxxxxxxxxxxxxxx> wrote:
> On Thu, Feb 17, 2005 at 11:03:54AM -0800, Matthew Dillon wrote:
> >     FFS also has a serious issue with the way it lays out directories.
> >     In particular, it cannot handle large directories efficiently.  The
> >     dirhash code works up to a point but is a pretty nasty hack to try to
> >     get around this limitation.
> 
> There was some discussion about that on the NetBSD lists including
> possible ways to improve this. The basic problem is that adding a
> file to a directory can result in a O(n) operation with n being the
> size of the directory.
> 
> Joerg
> 

Its not just adding directory entries, there is also a problem with
lookups inside the FFS/UFS code.  Yes, the dirhash code does help,
but, there is a lot of room for optimization still to be done in the
levels below that.

-- 
                                            -David
                                            Steven David Rhodus
                                            <drhodus@xxxxxxxxxxx>