[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs
From: |
Jim Meyering |
Subject: |
Re: fts: avoid O(n^2) ext3/ext4 performance hit on million+-entry dirs |
Date: |
Thu, 25 Sep 2008 18:40:39 +0200 |
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);
}
/*