stat() order performance issues

[Phillip Susi]

I have noticed that performing commands such as ls ( even with -U ) and 
du in a Maildir with many thousands of small files takes ages to 
complete.  I have investigated and believe this is due to the order in 
which the files are stat()ed.  I believe that these utilities are simply 
stat()ing the files in the order that they are returned by readdir(), 
and this causes a lot of random disk reads to fetch the inodes from disk 
out of order.

My initial testing indicates that sorting the files into inode order and 
calling stat() on them in order is around an order of magnitude faster, 
so I would suggest that utilities be modified to behave this way.

Questions/comments?