Why linux filesystems (ext2, ext3) get slow when >1K files in a directory

I know that, but don't know in detail.
(this article is English version of my Japanese blog)

Especially, ls command is very slow, so I thought readdir system call is too slow. But, I was WRONG.
Overhead is in ls command's algorithm.
Mailing List article in linux-users ( http://his.luky.org/ML/linux-users.6/msg08919.html ) taught me that.
ls command collects information not only the list of filenames but also each file's attributes (size, permission.. etc.).
So, ls command checks attributes for each files. That takes long time.

In my application, only the list of filenames is required. So, readdir system call just works fine.
Here is the sample code (almost the same as manpage of readdir!)

#include <dirent.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
  DIR *dirp;
  struct dirent *dp;

  if (argc != 2 ) {
      printf("coundn't open dir\n");
      return;
  }


  if ( (dirp = opendir(argv[1]) ) == NULL) {
      printf("coundn't open dir\n");
      return;
  }

  do {
      errno = 0;
      if ( (dp = readdir(dirp) ) != NULL) {
          (void) printf("%s\n", dp->d_name);
      }
  } while (dp != NULL);

  if (errno != 0)
      perror("error reading directory ");

  (void) closedir(dirp);
  return(0);
}

Now, I checked the performance of readdir itself.
In the case of over 10K files in a directory, it takes 300msec (Kernel 2.6.9-42.ELsmp: Cent OS4.4 4800 bogomips)
Here is the result of 'strace -c'

# strace -c readdir . > /dev/null
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
80.44    0.442220          14     30821           getdents64
19.48    0.107076           8     13018           write
0.03    0.000149         149         1           execve
0.01    0.000054          11         5           old_mmap
0.01    0.000038          13         3           open
0.01    0.000035          35         1           read
0.01    0.000031           8         4           fstat64
0.01    0.000030           8         4           brk
0.00    0.000022          11         2           mprotect
0.00    0.000014           5         3           close
0.00    0.000013          13         1           munmap
0.00    0.000011          11         1         1 access
0.00    0.000008           8         1           mmap2
0.00    0.000008           8         1           fcntl64
0.00    0.000007           7         1         1 ioctl
0.00    0.000007           7         1           uname
0.00    0.000003           3         1           set_thread_area
------ ----------- ----------- --------- --------- ----------------
100.00    0.549726                 43869         2 total

The most time-consuming system-call is getdents64. System(Disk) cache speed up the systemcall.
If cache is full-hit, getdents64 takes only 10usecs for 1M files in a directory.

If you tried this on NFS-mounted directory, cache-effect maybe small.