Ralf Wildenhues wrote:
> Jim Meyering writes:
>> Here's post-7.6 NEWS so far:
>>
>> ** Improvements
> [...]
>> rm -r deletes deep hierarchies more efficiently. Before, it took O(N^2)
>> time, now it takes O(N).
>
> What is N? The number of files removed, the number of directories removed,
> the maximal subdirectory depth?
Hi Ralf,
It's the latter, as implied by the preceding "deep hierarchies".
Here's the log message:
rm: improve efficiency of rm -r (without -f) from O(N^2) to O(N)
where N is the depth of the deepest hierarchy rm is processing.
* src/remove.c (write_protected_non_symlink): Use faccessat to
avoid O(N)-per-entry cost of calling euidaccess.
* m4/jm-macros.m4 (coreutils_MACROS): Check for faccessat.
* NEWS (Improvements): Mention it.
