Paul Eggert <address@hidden> wrote:
> Jim Meyering <address@hidden> writes:
>
>> CONSECUTIVE_READDIR_UNLINK_THRESHOLD = 200
>
> I looked into this a bit, and found myself wondering: why does 'rm'
> need to have this constant? Could rm do the rough equivalent of
> savedir on the directory (copying its file names and perhaps types
> into main memory), and then walk through the in-memory copy of the
> directory?
>
> Such an approach would take more memory, but the extra memory should
> be acceptable these days. Also, this approach would walk through the
> directory twice, but in the normal case this wouldn't hurt performance
> much, and it might even help performance.
>
> An advantage of this approach is that we wouldn't need these fudge
> factors for buggy file systems.
I wrote a prototype savedir-based implementation from scratch.
It is a more efficient when there are many directories
containing many entries, but it demonstrates O(n^2) performance
when the hierarchy is deep and narrow, e.g., /x/x/x/x/x/x/.../x.
So, yes, this is worth investigating.