Mozilla/5.0 (X11; Linux x86_64; rv:58.0) Gecko/20100101 Thunderbird/58.0
Just to be clear:
What I'm reporting here is a suspected regression.
The patch I linked, merged into coreutils in 2008, claims to fix the
exact problem I'm having.
The author measured time with `date` (see patch contents) which measures
wall time. So I believe that the statement of the patch is that it
improved `real` time from O(n²) to O(n).
I observe that in the current version of rm, `real` time is O(n²).
This is why I think this is a regression: The intended improvement of
the patch is no longer in effect.