Re: fts: make find *much* faster on dirent.d_type-challenged FS

[Ralf Wildenhues]

Hi Jim,

* Jim Meyering wrote on Thu, Feb 12, 2009 at 10:58:24PM CET:
> Following up on this thread,
> 
>   http://thread.gmane.org/gmane.comp.gnu.findutils.bugs/3894
> 
> Here are the gnulib pieces to make find stop stat'ing
> non-directories on reiserfs file systems.

Nice speedup!  A couple of comments, reading the patch:

> diff --git a/lib/fts.c b/lib/fts.c
> index 164834c..735f23f 100644
> --- a/lib/fts.c
> +++ b/lib/fts.c

> +    case S_MAGIC_PROC:
> +      /* Explicitly listing this or any other file system type for which
> +      the optimization is not applicable is not necessary, but we leave
> +      it here to documentat the risk.  Per http://bugs.debian.org/143111,

s/documentat/document/

> +      /proc may have bogus stat.st_nlink values.  */
> +      /* fall through */


> +/* Ask the same question as leaf_optimization_applies, but query
> +   the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
> +   update that cache.  */
> +static bool
> +link_count_optimize_ok (FTSENT const *p)
> +{
> +  FTS *sp = p->fts_fts;
> +
> +  /* If we're not in CWDFD mode, don't bother with this optimization,
> +     since the caller is not serious about performance. */
> +  if (!ISSET(FTS_CWDFD))
> +    return false;
> +
> +  /* map st_dev to the boolean, leaf_optimization_works */
> +  if (sp->fts_leaf_optimization_works_ht == NULL)
> +    {
> +      sp->fts_leaf_optimization_works_ht
> +     = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
> +                        LCO_compare, free);
> +      if (sp->fts_leaf_optimization_works_ht == NULL)
> +     return false;
> +    }
> +  Hash_table *h = sp->fts_leaf_optimization_works_ht;

Does this code need to be C89 compatible (several declaration after
statement here)?

> +  struct LCO_ent tmp;
> +  tmp.st_dev = p->fts_statp->st_dev;
> +  struct LCO_ent *ent = hash_lookup (h, &tmp);
> +  if (ent)
> +    return ent->opt_ok;
> +
> +  int fd = p->fts_fts->fts_cwd_fd;
> +  struct LCO_ent *t2 = malloc (sizeof *t2);
> +  if (t2 == NULL)
> +    return false;
> +  t2->st_dev = p->fts_statp->st_dev;
> +
> +  /* Is it ok to perform the optimization in the dir on which FD is open?  */
> +  bool opt_ok = leaf_optimization_applies (fd);
> +  t2->opt_ok = opt_ok;
> +
> +  struct LCO_ent *e = hash_insert (h, t2);
> +  if (e == NULL)
> +    {
> +      /* insertion failed */
> +      free (t2);
> +      return false;
> +    }
> +  fts_assert (e == t2);
> +
> +  return opt_ok;
> +}

Cheers,
Ralf