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

[Paul Eggert]

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