bug#29921: O(n^2) performance of rm -r

[Jim Meyering]

On Mon, Jan 1, 2018 at 2:50 PM, Paul Eggert <address@hidden> wrote:
> Jim Meyering wrote:
>
>> $ i=100000; while :; do mkdir x; (cd x && seq $i|xargs touch); env
>> time -f "%e $i" env rm -rf x; case $i in 8*) break;; esac; i=$[i*2];
>> done
>> 0.48 100000
>> 2.59 200000
>> 12.69 400000
>> 35.61 800000
>
>
> I'm getting similarly bad numbers with recent Fedora 27 x86-64. As this is
> ext4 with reasonably-vanilla options
> (rw,noatime,errors=remount-ro,data=ordered), perhaps we should file an ext4
> bug report? We could point the ext4 hackers to https://bugs.gnu.org/29921.
>
> Here's what I got:
>
> $ i=100000; while :; do mkdir x; (cd x && seq $i|xargs touch); env time -f
> "%e $i" /usr/bin/rm -rf x; case $i in 8*) break;; esac; i=$[i*2]; done
> 0.95 100000
> 2.93 200000
> 17.04 400000
> 74.31 800000
>
> This is more like O(N**2.5) than O(N**2). Ouch.
>
> For what it's worth, smartctl says my file system uses a Western Digital
> Caviar Green 2 TB hard disk (WDC WD20EARS-00MVWB0).

Here's another data point: it's nicely linear with XFS on a >1TB NVMe
card mounted with "allocsize=64k,noatime,nodiratime,rw":

$ i=100000; while :; do mkdir x; (cd x && seq $i|xargs touch); env
time -f "%e $i" env rm -rf x; case $i in 16*) break;; esac; i=$[i*2];
done
2.73 200000
5.90 400000
12.57 800000
25.06 1600000