Re: Debbugs: The Next Generation
On Sat, 18 Aug 2001 tytso@mit.edu wrote:
> On Sat, Aug 18, 2001 at 01:52:56AM -0400, Matt Zimmerman wrote:
> > On Tue, Aug 14, 2001 at 04:24:33PM +1000, Anthony Towns wrote:
> > > That's not true: ext2 queries and directory lists are the problem here,
> > > in that they're O(N) and O(N^2) rather than O(1)/O(N). Using reiser or
> > > subdirectories would reduce those to O(lg(N)) and O(N lg(N)).
> >
> > Why on earth are directory lists O(N^2)? I don't know much about ext2
> > internals, but that should be an O(N) operation in any sane filesystem.
>
> 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?
I'm currently compiling 2.4.9 with this patch. It took 8-9minuts to find/stat
db/ on my home box. We shall see what this does after I reboot.
Reply to: