Re: [PATCH] Add-rm-rf-as-examples-loadables-rm.c

[Tim Ruehsen]

On Monday, October 31, 2016 4:44:21 PM CET Eric Blake wrote:
> On 10/31/2016 04:14 PM, Chet Ramey wrote:
> >> > Nice, thanks for the modifications.
> > 
> > Here's the modified version.
> > 
> > Chet
> > -- ``The lyf so short, the craft so long to lerne.'' - Chaucer ``Ars
> > longa, vita brevis'' - Hippocrates Chet Ramey, UTech, CWRU chet@case.edu
> > http://cnswww.cns.cwru.edu/~chet/
> > 
> >   if ((dir = opendir(dirname)))
> >   
> >     {
> >     
> >       while ((dp = readdir(dir)))
> 
> Ouch.  This version has O(n^2) complexity when dealing with deep
> hierarchies.  GNU Coreutils intentionally prefers using
> openat()/fdopendir() and so on in order to recurse through the tree with
> O(n) complexity instead of O(n^2).

As Chet stated, the purpose was to speed up ./configure runs. For that I can't 
see very deeply nested directories with million of files in it.

> >         {
> >         
> >           if (*dp->d_name == '.' && (dp->d_name[1] == 0 || (dp->d_name[1]
> >           == '.' && dp->d_name[2] == 0)))>           
> >             continue;
> >        
> >        fnsize = dirlen + 1 + strlen(dp->d_name) + 1;
> >        
> >            fname = xmalloc (fnsize);
> >            snprintf(fname, fnsize, "%s/%s", dirname, dp->d_name);
> 
> And here is part of the HUGE speed penalty that you get in large
> directories.  You are mallocing a LOT of memory, and waste a LOT of work
> since the majority of the time (while within a single directory) the
> prefix is unchanged from the previous iteration, while in the deep
> hierarchy; while doing everything directory-relative completely avoids
> the need to construct ever-deeper names.

I agree. My implementation used stack space - which should be fine for real 
file 
names. If in doubt, a simple heap reallocation strategy is just a few lines.
But the purpose argument hits here as well.

> >            if (rm_file (fname) && force == 0)
> >            
> >              err = 1;
> >            
> >            free (fname);
> >         
> >         }
> 
> Another speed sink - your implementation removes names in readdir()
> order; GNU Coreutils has proven benchmark numbers that unlink()ing files
> that are sorted by inode number is measurably faster than unlink()ing in
> readdir() order for directories with a large number of files.  Yes, it
> is more complex to set up the tracking structures to sort things, but it
> pays off in the long run.

Maybe, but very likely is that completely dependent on the type of file system, 
sounds very hacky.
I wonder why there isn't a system call that recursively removes a directory + 
content, at least for Linux.
Again the purpose argument hits.

> >   while ((opt = internal_getopt (list, "rf")) != -1)
> >   
> >     {
> >     
> >       switch (opt)
> >     
> >     {
> >     
> >     case 'r':
> >       recursive = 1;
> >       break;
> 
> Per POSIX, 'rm -R' and 'rm -r' are identical; a couple tweaks to this
> patch will make support for 'rm -R' work out of the box.

Not needed for the purpose, but doesn't hurt.

> >     case 'f':
> >       force = 1;
> >       break;
> >     
> >     CASE_HELPOPT;
> >     
> >     default:
> >       builtin_usage ();
> >       return (EX_USAGE);
> >     
> >     }
> 
> You do NOT support the POSIX-mandated 'rm -i'.  I don't necessarily
> blame you (since it is complex), but what you should REALLY do is that
> any time you don't recognize an option, your builtin should silently
> call the real rm utility, rather than failing.  That way, your builtin
> can be a faster drop-in when it recognizes the simple cases, but remains
> POSIX-compliant (assuming the fallback app is POSIX compliant), as well
> as offer ALL extensions that the normal fallback understands, rather
> than being a crippled version that causes failures to code expecting
> POSIX or particular extension behaviors.

[*]
Such a fallback on unknown options is a good thing. I simply didn't know how 
to do that in an acceptable manner (within a loadable bash builtin). This 
should be done for other loadables as well (e.g. 'cat'). It would serve it's 
purpose as 'example' even better.

> 
> >     }
> >   
> >   list = loptend;
> >   
> >   if (list == 0)
> >   
> >     return (EXECUTION_SUCCESS);
> 
> This does not match the behavior of GNU coreutils.  'rm' without
> arguments prints a usage error and exits with nonzero status.  But note
> that POSIX requires 'rm -f' without arguments to silently exit with
> success.  POSIX only specifies the behavior of 'rm -f' without
> arguments; with 'rm', you can do what you want (therefore you comply
> with POSIX), but it's still nice to match what other implementations do.

[**]
As you say, preferable it should match with GNU coreutils in this point.

> While I think that it is neat that this builtin can be used to speed up
> configure scripts, I don't think it is ready for prime time yet.  It's
> tough to recommend that autoconf be taught to use this sub-standard
> implementation.

It works with all my configure scripts so far.  I put the two enable commands 
into my config.site inside -n "$BASH" check, so nothing but ./configure is 
affected.
With my current project, it gives me ~7% boost, just started a wiki page to 
document my effords 
(https://github.com/rockdaboot/wget2/wiki/Developer-hints:-Increasing-speed-of-GNU-toolchain).
 Still under construction, comments 
welcome.

Back to "prime time"... IMO [*] and [**] would be enough for prime time. I 
don't see that further performance tuning and code complexity gives us any 
benefit with autotools. But if any project proofs the contrary, the responsible 
people are free to offer patches here.

Anyways, a big *thank you* for your review.
That also gave me a new view onto diropen/readdir complexity.

Regards, Tim

signature.asc
Description: This is a digitally signed message part.