C
GCC

俺のlsが遅すぎる


なぜ?

必要に迫られてオレオレなlsを書いたのだがなぜか遅い。大したことしていないのに遅い。


コード

特に変なところはないと思うのだけど...

#include <stdio.h>

#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <dirent.h>
#include <pwd.h>

int main(int argc, char** argv)
{
char fpath[PATH_MAX];
DIR* dir;
struct dirent* dp;
struct stat st;
struct passwd *pw;
char *dpath;

dpath = (argc != 2) ? "." : argv[1];

dir = opendir(dpath);
while ((dp = readdir(dir)) != NULL) {
memset(fpath, '\0', sizeof(fpath));
sprintf(fpath, "%s/%s", dpath, dp->d_name);
if (stat(fpath, &st) != -1) {
pw = getpwuid(st.st_uid);
fprintf(stdout, "{ filename = %s, username = %s }\n", fpath, pw->pw_name);
}
}
closedir(dir);
exit(EXIT_SUCCESS);
}


ベンチマーク

ゴミファイルを1万作っておく。

$ mkdir too_many_files.d

$ cd too_many_files.d
$ for x in `seq 1000`
> do
> touch testfile-${x}-{0,1,2,3,4,5,6,7,8,9}
> done
$ ls | wc -l
10000

なぜか遅い。lsは魔法でも使ってんのかよ。

$ time ./minls too_many_files.d/ > /dev/null

real 0m0.149s
user 0m0.063s
sys 0m0.086s

$ time ls too_many_files.d/ > /dev/null

real 0m0.046s
user 0m0.043s
sys 0m0.003s


調査

こういうのは自分のコードを疑うべきですから、ltraceで関数呼び出しを調べてましょうか。

$ ltrace -c ./minls too_many_files.d/ > /dev/null

% time seconds usecs/call calls function
------ ----------- ----------- --------- --------------------
53.28 6.174203 6174203 1 __libc_start_main
13.86 1.605601 160 10002 getpwuid
7.42 0.860083 85 10002 __xstat
6.52 0.755191 75 10002 fprintf
6.35 0.736116 73 10002 sprintf
6.31 0.731490 73 10003 readdir
6.25 0.724347 72 10002 memset
0.00 0.000177 177 1 exit
0.00 0.000174 174 1 opendir
0.00 0.000089 89 1 closedir
0.00 0.000084 84 1 exit_group
------ ----------- ----------- --------- --------------------
100.00 11.587555 60018 total

おおぅ、getpwuid()がめっちゃ遅い。

こいつが遅いのがわかったので、straceをかけてみる。

$ strace -f -e open ./minls .

open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
open("/lib64/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
open("/etc/nsswitch.conf", O_RDONLY|O_CLOEXEC) = 4
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 4
open("/lib64/libnss_files.so.2", O_RDONLY|O_CLOEXEC) = 4
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 4
{ filename = ./., username = dharry }
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 4
{ filename = ./.., username = dharry }
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 4
{ filename = ./minls, username = dharry }
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 4
{ filename = ./test.c, username = dharry }
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 4
{ filename = ./too_many_files.d, username = dharry }
+++ exited with 0 +++

つまり、getpwuid()を呼び出すたびに/etc/passwdをみているのか。これきっつい。


core-utilsのlsは何してんの?

getpwuid()を呼ぶたびに、パスワードファイル参照されるのは、あまり精神衛生的に気持ちのいいものじゃないね。普通に考えるとキャッシュする実装がいいのかな。

core-utils の ls でもキャッシュしていると。


idcache.c

struct userid

{
union
{
uid_t u;
gid_t g;
} id;
char *name;
struct userid *next;
};

static struct userid *user_alist;

/* The members of this list have names not in the local passwd file. */
static struct userid *nouser_alist;

/* Translate UID to a login name, with cache, or NULL if unresolved. */

char *
getuser (uid_t uid)
{
register struct userid *tail;
struct passwd *pwent;

for (tail = user_alist; tail; tail = tail->next)
if (tail->id.u == uid)
return tail->name;

pwent = getpwuid (uid);
tail = xmalloc (sizeof *tail);
tail->id.u = uid;
tail->name = pwent ? xstrdup (pwent->pw_name) : NULL;

/* Add to the head of the list, so most recently used is first. */
tail->next = user_alist;
user_alist = tail;
return tail->name;
}