Re: [Ext2-devel] Re: Debbugs: The Next Generation

[Christoph Hellwig <hch@ns.caldera.de>]

On Sat, Aug 18, 2001 at 04:19:06AM -0500, Adam Heath wrote:
> On Sat, 18 Aug 2001, Adam Heath wrote:
> 
> > > Doing a directory list is indeed O(N) for ext2.
> > >
> > > However, iterating through the directory using readdir() and then
> > > stating or opening each file in readdir order is O(N**2).  There's a
> > > very obvious optimization which makes this O(N), which I thought ext2
> > > was using, but as it turns out, we weren't.
> >
> > How does this patch affect the case where you don't stat in readdir order?
> 
> Actually, this patch will not help the following perl-snipet/pseudo code:
> 
> @list = sort readdir( DIR );

	^^^^^^^^

If you randomly sort the items, the last position cache won't help.

	Christoph

-- 
Of course it doesn't work. We've performed a software upgrade.