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

[Ralf Wildenhues]

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 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?

> +  return diff;
> +}

Cheers,
Ralf