Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Bruno Haible wrote: Jim Meyering wrote: + 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); +

Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Jim Meyering <[EMAIL PROTECTED]> wrote: > Here is a patch that makes it so tools using fts, > like chmod, chown, chgrp, chcon, du, and find are no > longer susceptible to an O(n^2) performance penalty when > processing very large directory-entry counts (as in millions). > I first noticed the proble

Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Jim Meyering <[EMAIL PROTECTED]> wrote: > Bruno Haible <[EMAIL PROTECTED]> wrote: >> Jim Meyering wrote: >>> + if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD >>> + && !sp->fts_compar >>> + && dirent_inode_sort_may_be_useful (sp)) { >>> + sp->fts_compar = fts_compare_ino;

Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Bruno Haible <[EMAIL PROTECTED]> wrote: > Jim Meyering wrote: >> +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,

Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Jim Meyering wrote: > + 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 =

Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Ralf Wildenhues <[EMAIL PROTECTED]> wrote: > * Jim Meyering wrote on Thu, Sep 25, 2008 at 06:16:58PM CEST: >> --- a/lib/fts.c >> +++ b/lib/fts.c > >> +/* A comparison function to sort on increasing inode number. >> + For some file system types, sorting either way makes a huge >> + performance d

Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Hi Jim, * Jim Meyering wrote on Thu, Sep 25, 2008 at 06:16:58PM CEST: > --- a/lib/fts.c > +++ b/lib/fts.c > +/* 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 e

fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs

Hello, Here is a patch that makes it so tools using fts, like chmod, chown, chgrp, chcon, du, and find are no longer susceptible to an O(n^2) performance penalty when processing very large directory-entry counts (as in millions). I first noticed the problem on ext3 and ext4 file systems, but the p