Mercurial > gnulib
comparison ChangeLog @ 30172:b76e9423366a
fts: sort dirent entries on inode number before traversing
This avoids a quadratic, seek-related performance penalty when
operating on a directory containing many entries (measurable at 10k;
3.5 hours at 2 million entries with a cold cache) on certain types
of file systems, including ext3 and ext4, but not tmpfs.
* lib/fts.c (DT_MUST_BE, NOT_AN_INODE_NUMBER, D_INO): Define.
(FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD): Define if not defined.
(S_MAGIC_TMPFS, S_MAGIC_NFS): Define.
(fs_handles_readdir_ordered_dirents_efficiently): New function.
(dirent_inode_sort_may_be_useful, fts_compare_ino): Likewise.
(fts_build): Set the stat.st_ino member from D_INO.
If it is likely to be useful, sort dirent entries on inode number.
* m4/fts.m4 (gl_FUNC_FTS_CORE): Check for fstatfs, sys/vfs.h,
and the struct statfs.f_type member.
* modules/fts (Depends-on): Add d-ino.
author | Jim Meyering <meyering@redhat.com> |
---|---|
date | Tue, 16 Sep 2008 10:05:47 +0200 |
parents | eeaa0c743274 |
children | e8d1a5b2c49c |
comparison
equal
deleted
inserted
replaced
30171:eeaa0c743274 | 30172:b76e9423366a |
---|---|
1 2008-09-26 Jim Meyering <meyering@redhat.com> | |
2 | |
3 fts: sort dirent entries on inode number before traversing | |
4 This avoids a quadratic, seek-related performance penalty when | |
5 operating on a directory containing many entries (measurable at 10k; | |
6 3.5 hours at 2 million entries with a cold cache) on certain types | |
7 of file systems, including ext3 and ext4, but not tmpfs. | |
8 * lib/fts.c (DT_MUST_BE, NOT_AN_INODE_NUMBER, D_INO): Define. | |
9 (FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD): Define if not defined. | |
10 (S_MAGIC_TMPFS, S_MAGIC_NFS): Define. | |
11 (fs_handles_readdir_ordered_dirents_efficiently): New function. | |
12 (dirent_inode_sort_may_be_useful, fts_compare_ino): Likewise. | |
13 (fts_build): Set the stat.st_ino member from D_INO. | |
14 If it is likely to be useful, sort dirent entries on inode number. | |
15 * m4/fts.m4 (gl_FUNC_FTS_CORE): Check for fstatfs, sys/vfs.h, | |
16 and the struct statfs.f_type member. | |
17 * modules/fts (Depends-on): Add d-ino. | |
18 | |
1 2008-09-26 Bruno Haible <bruno@clisp.org> | 19 2008-09-26 Bruno Haible <bruno@clisp.org> |
2 | 20 |
3 * modules/sigpipe: New file. | 21 * modules/sigpipe: New file. |
4 * m4/sigpipe.m4: New file. | 22 * m4/sigpipe.m4: New file. |
5 | 23 |