ext2 directory operations (Re: Debbugs: The Next Generation)
On Sat, Aug 18, 2001 at 02:53:35PM -0700, Daniel Jacobowitz wrote:
> On Sat, Aug 18, 2001 at 09:01:08AM -0400, tytso@mit.edu wrote:
> > 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.
> >
> > Thanks for bringing this to my attention; here's the very simple kernel
> > patch which should speed up a du or find of very large directories
> > significantly.
>
> I'm guessing this will have no real effect. In an effort to optimize, glibc
> does not call readdir(); instead it calls getdents64() and gets buffers.
> You'll go just past the one you want and always have to loop all the way
> around.
>
> Perhaps if you keep the search start at the beginning of the entries returned
> by the last getdents64() call? Is that feasible? It should not penalize as
> badly.
Unless I misunderstand, it will still do the right thing. The offset saved is
that of the last successful name lookup, not the last read dentry. So as long
as the names are looked up in directory order, the offset should always be in
the right place, regardless of how many entries were read.
--
- mdz
Reply to: