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

[Jim Meyering]

Ralf Wildenhues <address@hidden> 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 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)
>> +{
>> +  int diff = (b[0]->fts_statp->st_ino
>> +          - a[0]->fts_statp->st_ino);
>
> This can over- resp. underflow and then give the wrong sign, no?

Hi Ralf,

Thanks for the quick feedback.
You're right, of course, and I'll fold in this change:

diff --git a/lib/fts.c b/lib/fts.c
index cd14ec4..3cf49fa 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -981,9 +981,8 @@ static bool dirent_inode_sort_may_be_useful (FTS const *sp) 
{ return true; }
 static int
 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
 {
-  int diff = (b[0]->fts_statp->st_ino
-             - a[0]->fts_statp->st_ino);
-  return diff;
+  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);
 }

 /*