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

[Eric Blake]

On 11/01/2016 10:41 AM, Tim Ruehsen wrote:

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

Except that gnulib DOES have a ./configure test that intentionally DOES
create a very deeply nested directory in order to prove whether the OS
has bugs that it needs to work around.  See
http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=m4/getcwd-path-max.m4;h=2531ccff.
 Okay, that's stretching my argument a bit, since that test DOES try
hard to clean up its deep hierarchy in C rather than making the shell do
it after the fact with rm -r.  But my point is you cannot assume that
the rm module would never be called on to delete deep hierarchies.

[Side note - that particular gnulib test runs in a fraction of a second
with O(n) time on sane OS and file systems, but at least the Windows
2000 NTFS driver had a bug, since fixed in newer versions of Windows,
where the test took O(n^2) time because the OS/file system layer was
tracking things by absolute name even though the test itself was taking
great pains to track things relatively and avoid the user-space O(n^2)
penalty of absolute names.  For several years, I had to pre-prime my
config.site on my Cygwin machines to skip to the correct answer of that
test if I didn't want configure to take several minutes]

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

If you're going to use stack space, you also have to make sure that deep
hierarchies don't overflow a stack page.  But switching to a heap
strategy may cause speed penalties on the common case of not having deep
hierarchies, so the best code has both styles with a switch based on
heuristics.

> But the purpose argument hits here as well.

And my counterargument hits here as well: If you can cleanly fall back
to the REAL rm any time that you find you are no longer dealing with
your purpose-built quick version, then your quick version can take
shortcuts.  That is, code that calls the real rm once it hits 4k in
depth doesn't even have to worry about heap allocation (that's the real
rm's job, at that point) - but you can only make that dichotomy of fast
for the common case but correct for the corner case if you handle the
corner case by calling into the real rm, rather than failing spectacularly.

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

Yes, this I can agree with - having a GOOD example of how to make a
loadable builtin sanely fall back to the real counterpart would be
useful for all of the loadables to follow.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature