Mercurial > hg > octave-nkf > gnulib-hg
changeset 10481:47fe4e48e158
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 | 170726b202f9 |
children | e8d1a5b2c49c |
files | ChangeLog lib/fts.c m4/fts.m4 modules/fts |
diffstat | 4 files changed, 113 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,21 @@ +2008-09-26 Jim Meyering <meyering@redhat.com> + + 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. + 2008-09-26 Bruno Haible <bruno@clisp.org> * modules/sigpipe: New file.
--- a/lib/fts.c +++ b/lib/fts.c @@ -91,6 +91,29 @@ # define DT_MUST_BE(d, t) false #endif +enum +{ + NOT_AN_INODE_NUMBER = 0 +}; + +#ifdef D_INO_IN_DIRENT +# define D_INO(dp) (dp)->d_ino +#else +/* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */ +# define D_INO(dp) NOT_AN_INODE_NUMBER +#endif + +/* If there are more than this many entries in a directory, + and the conditions mentioned below are satisfied, then sort + the entries on inode number before any further processing. */ +#ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD +# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000 +#endif +enum +{ + _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD +}; + enum Fts_stat { FTS_NO_STAT_REQUIRED = 1, @@ -911,6 +934,57 @@ return (sp->fts_child); } +#if defined HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE +# include <sys/statfs.h> +/* FIXME: what about when f_type is not an integral type? + deal with that if/when it's encountered. */ +static bool +fs_handles_readdir_ordered_dirents_efficiently (uintmax_t fs_type) +{ +/* From coreutils' src/fs.h */ +#define S_MAGIC_TMPFS 0x1021994 +#define S_MAGIC_NFS 0x6969 + switch (fs_type) + { + case S_MAGIC_TMPFS: + case S_MAGIC_NFS: + return true; + default: + return false; + } +} + +/* Return true if it is easy to determine the file system type of the + current directory, and sorting dirents on inode numbers is known to + improve traversal performance with that type of file system. */ +static bool +dirent_inode_sort_may_be_useful (FTS const *sp) +{ + struct statfs fs_buf; + /* Skip the sort only if we can determine efficiently + that it's the right thing to do. */ + bool skip = (ISSET (FTS_CWDFD) + && fstatfs (sp->fts_cwd_fd, &fs_buf) == 0 + && fs_handles_readdir_ordered_dirents_efficiently + (fs_buf.f_type)); + return !skip; +} +#else +static bool dirent_inode_sort_may_be_useful (FTS const *sp) { return true; } +#endif + +/* A comparison function to sort on increasing inode number. + For some file system types, sorting either way makes a huge + performance difference for a directory with very many entries, + but sorting on increasing values is slightly better than sorting + on decreasing values. The difference is in the 5% range. */ +static int +fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b) +{ + return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? 1 + : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? -1 : 0); +} + /* * This is the tricky part -- do not casually change *anything* in here. The * idea is to build the linked list of entries that are used by fts_children @@ -1111,6 +1185,9 @@ if (dp->d_type == DT_WHT) p->fts_flags |= FTS_ISW; #endif + /* Store dirent.d_ino, in case we need to sort + entries before processing them. */ + p->fts_statp->st_ino = D_INO (dp); /* Build a file name for fts_stat to stat. */ if (ISSET(FTS_NOCHDIR)) { @@ -1206,6 +1283,18 @@ return (NULL); } + /* If there are many entries, no sorting function has been specified, + and this file system is of a type that may be slow with a large + number of entries, then sort the directory entries on increasing + inode numbers. */ + if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD + && !sp->fts_compar + && dirent_inode_sort_may_be_useful (sp)) { + sp->fts_compar = fts_compare_ino; + head = fts_sort (sp, head, nitems); + sp->fts_compar = NULL; + } + /* Sort the entries. */ if (sp->fts_compar && nitems > 1) head = fts_sort(sp, head, nitems);
--- a/m4/fts.m4 +++ b/m4/fts.m4 @@ -1,5 +1,5 @@ -#serial 13 -dnl Copyright (C) 2005-2007 Free Software Foundation, Inc. +#serial 14 +dnl Copyright (C) 2005-2008 Free Software Foundation, Inc. dnl This file is free software; the Free Software Foundation dnl gives unlimited permission to copy and/or distribute it, dnl with or without modifications, as long as this notice is preserved. @@ -23,6 +23,7 @@ dnl Prerequisites of lib/fts.c. gl_FUNC_OPENAT - # Checks for header files. - AC_CHECK_HEADERS_ONCE([sys/param.h])dnl + AC_CHECK_FUNCS_ONCE([fstatfs]) + AC_CHECK_HEADERS_ONCE([sys/param.h sys/vfs])dnl + AC_CHECK_MEMBERS([struct statfs.f_type]) ])