Re: Debbugs: The Next Generation

[Adam Heath <doogie@brainfood.com>]

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 );
foreach ( @list ) {
	stat;
}

I feel the above code is probably quite common too.