lkml.org 
[lkml]   [1999]   [May]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: large directory handling speed
On Sat, May 29, 1999 at 07:39:04PM -0400, Alexander Viro wrote:
> On Sun, 30 May 1999, Alexander V. Lukyanov wrote:
> > ls -l > /dev/null in a smaller (but still huge) directory:
> > 2.2.9:
> > 1.32user 489.66system
> > 2.3.3:
> > 1.14user 240.97system
> >
> > wow, 2x improvement! But as it is quadratic algorithm, the readdir must be 1.4
> > times faster.
>
> > It is certainly nice improvement, but ls is still quadratic.
>
> Hmm... It is quadratic on ext2 too.

But it is much faster:
ls -l > /dev/null in the same directory copyed to ext2 (about 8000 files)
2.2.9:
0.94user 14.29system

That is readdir on ext2 is sqrt(20)~=4.5 times faster than that on vfat.

> I'm very sceptical about populating
> dcache on readdir() for any filesystem, mostly because it will be useless
> on small directories and will trigger cache reaping on the large ones.

dcache has an age, I'd add entries with age depending on entry
position in directory, the farther the entry is from directory
beginning, the less tha age is, e.g. age=1/X/log(P)+Y, where X is cost
of readdir (smaller for ext2, larger for vfat), and P is position starting
from 1. Y would make the relation between normal dentry and readdir-made
dentry.

Of course, this would not apply to future b-tree directories :)

> The
> same applies to icache. We can (somewhat) speed the things up if we'll
> play with a small cache for unicode translation buffers and it's probably
> worth doing, but I'm not sure that it will give any dramatic improvement.

The directory I try contains only long ascii filenames.

> The thing will remain quadratic anyway... We might keep a directory cache
> as it is done for NFS &co, but it would hardly help in case of ls -l...
> Another possible change would be to remember the postion of last lookup
> and on further lookups do a cyclic search from the next one. That can be
> done, but I'm not sure that it is worth doing. I will do an update to
> FAT when the thing will go to 2.2. Then I'll try those variants. The last
> one seems to be the most promising and could be applied to other
> filesystems too. Possible drawback being that with the current setup we
> can slightly optimize things if we know which files are likely to be
> accessed - put them in the beginning. With such change we lose it. OTOH
> dcache may be enough here...

Cyclic search looks good. At least it would make better the common
case of readdir/stat. But what if a stupid program sort file name list
before stat's :) (fortunately it is not common)

Alexander.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:52    [W:0.037 / U:0.148 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site