Commit 2f2978ede97205c49d3e568ccffa5a04fb53326b
2008-09-16T10:05:47
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.