Re: Fastest way to "find / -mtime +7".....
On Wed, Jul 20, 2005 at 12:26:44PM -0400, Andreas Dilger wrote: > On Jul 19, 2005 16:00 -0600, Jonathan Briggs wrote: > > How about some kind of stat-data readahead logic? If the first two or > > three directory entries are stat'd, queue up the rest (or next > > hundred/thousand) of them. If the disk queue is given the whole pile of > > stat requests at once instead of one at a time, it should be able to > > sort them into a reasonable order. > > > > This might even be a VFS thing to do instead of per-FS. > > This is something I would be very interested in. Having a pipeline of > stats generated when an app does readdir + in-order stat would help > reduce latency a great deal for network filesystems. What about just adding an asyncron stat to aio ? -- Ragnar Kjørstad Software Engineer Scali - http://www.scali.com Scaling the Linux Datacenter
Re: Fastest way to "find / -mtime +7".....
On Jul 19, 2005 16:00 -0600, Jonathan Briggs wrote: > How about some kind of stat-data readahead logic? If the first two or > three directory entries are stat'd, queue up the rest (or next > hundred/thousand) of them. If the disk queue is given the whole pile of > stat requests at once instead of one at a time, it should be able to > sort them into a reasonable order. > > This might even be a VFS thing to do instead of per-FS. This is something I would be very interested in. Having a pipeline of stats generated when an app does readdir + in-order stat would help reduce latency a great deal for network filesystems. Cheers, Andreas -- Andreas Dilger Principal Software Engineer Cluster File Systems, Inc. pgprQT5yfDILL.pgp Description: PGP signature
Re: Fastest way to "find / -mtime +7".....
Jonathan Briggs wrote on Tue, 19 Jul 2005 16:00:23 -0600: > On Tue, 2005-07-19 at 22:09 +0200, Ragnar Kjørstad wrote: > > Readdir will return the filenames in hash order. Find will then go and > > stat each file, still in hash order. > > > > Problem is, the inodes are not sorted in directory hash order on the > > disk. They tend to be in approximate creation order. So, the disk access > > pattern is nearly random access, meaning every stat is likely to touch a > > new block and readahead is completely useless. > [snip] > How about some kind of stat-data readahead logic? If the first two or > three directory entries are stat'd, queue up the rest (or next > hundred/thousand) of them. If the disk queue is given the whole pile of > stat requests at once instead of one at a time, it should be able to > sort them into a reasonable order. > > This might even be a VFS thing to do instead of per-FS. I noticed the same limitation for reading large numbers of attributes in BeOS (like icons for all the files in a directory or in the result set from a query). My idea is to expand ReadDir to return more than just the file names in the directory/query. You would specify which metadata you wanted (mtime, filename, attribute name, etc) and then SuperReadDir would traverse the directory/query and pack all the requested data items into one memory buffer for the calling program to use. Thus avoiding the overhead of multiple kernel calls for each individual file. Suddenly displaying a file browser window with a directory with thousands of files is many times faster! But for full functionality this needs a global metadata naming and typing system, so you can find out what data types are available, and how to process them. It would describe mtime as being a 4 byte integer time, SMALL_ICON as being a bitmap, FILE_NAME as being a variable length string and so on. This can be related to the file type system (like the nice one Apple now has in OS X Tiger), so that file types and metadata types can be described by a common API. Unfortunately BeOS has them as separate systems (a list of four character codes for the metadata types, MIME strings for the files). Then there's the issue of cross platform type sharing, an enum with different values here and there for the metadata type codes will make it hard to share data discs, so something more sophisticated is needed... - Alex
Re: Fastest way to "find / -mtime +7".....
On Tue, 2005-07-19 at 22:09 +0200, Ragnar Kjørstad wrote: > On Tue, Jul 19, 2005 at 12:48:53PM -0600, Jonathan Briggs wrote: > > > this is pretty slow on reiser, at least compared with ext2/3, and I > > > understand that it may be because the find command returns the names > > > in a non-optimal order (ie readdir order?). > > > > I think Reiser3 is slow more because with mtime, find has to stat each > > file. > > The two issues are related. > > Readdir will return the filenames in hash order. Find will then go and > stat each file, still in hash order. > > Problem is, the inodes are not sorted in directory hash order on the > disk. They tend to be in approximate creation order. So, the disk access > pattern is nearly random access, meaning every stat is likely to touch a > new block and readahead is completely useless. [snip] How about some kind of stat-data readahead logic? If the first two or three directory entries are stat'd, queue up the rest (or next hundred/thousand) of them. If the disk queue is given the whole pile of stat requests at once instead of one at a time, it should be able to sort them into a reasonable order. This might even be a VFS thing to do instead of per-FS. -- Jonathan Briggs <[EMAIL PROTECTED]> eSoft, Inc. signature.asc Description: This is a digitally signed message part
Re: Fastest way to "find / -mtime +7".....
On Tue, Jul 19, 2005 at 12:48:53PM -0600, Jonathan Briggs wrote: > > this is pretty slow on reiser, at least compared with ext2/3, and I > > understand that it may be because the find command returns the names > > in a non-optimal order (ie readdir order?). > > I think Reiser3 is slow more because with mtime, find has to stat each > file. The two issues are related. Readdir will return the filenames in hash order. Find will then go and stat each file, still in hash order. Problem is, the inodes are not sorted in directory hash order on the disk. They tend to be in approximate creation order. So, the disk access pattern is nearly random access, meaning every stat is likely to touch a new block and readahead is completely useless. I once wrote a new hash for reiserfs3 specifically for maildir. This hash caused files to be order in approximate creating order, matching the inode order much closer. You will find both the patch and some benchmark results if you search the archive (messageid [EMAIL PROTECTED]), but speeded up my testcase by a factor of 6. (My testcase read all the data too though. I don't think I ever tested just "find . -ls") In reiserfs3 the usefullness of the hash is limited as hashes are per filesystem settings. (So it is only useful if you have a dedicated maildir filesystem). I've lost track of reiserfs4 features - maybe you can select hashes per directory now? Or maybe the whole thing is made obsolete by putting the inodes with the directoryentries? -- Ragnar Kjørstad Software Engineer Scali - http://www.scali.com Scaling the Linux Datacenter
Re: Fastest way to "find / -mtime +7".....
On Tue, 2005-07-19 at 10:55 -0700, Ed Walker wrote: > I've got a lot of small maildir files stored on a reiser-fs > partition. Currently we expire out the old stuff using > find /mail -mtime +7 -type f -print0 | xargs -0 rm -rf > > this is pretty slow on reiser, at least compared with ext2/3, and I > understand that it may be because the find command returns the names > in a non-optimal order (ie readdir order?). > > Is there something we can do to speed it up? Any suggestions? > > Thanks- > > Ed I think Reiser3 is slow more because with mtime, find has to stat each file. I did a couple ad-hoc tests and it seems to be about 40x slower on directory list with stat than just plain directory lists. I didn't try ext2/3. I believe the reiser3 directory order problems with maildir are related to something else, like not finding new mail at the end of the readdir()? -- Jonathan Briggs <[EMAIL PROTECTED]> eSoft, Inc. signature.asc Description: This is a digitally signed message part
Fastest way to "find / -mtime +7".....
I've got a lot of small maildir files stored on a reiser-fs partition. Currently we expire out the old stuff using find /mail -mtime +7 -type f -print0 | xargs -0 rm -rf this is pretty slow on reiser, at least compared with ext2/3, and I understand that it may be because the find command returns the names in a non-optimal order (ie readdir order?). Is there something we can do to speed it up? Any suggestions? Thanks- Ed