On Wed, Jan 03, 2018 at 08:16:58PM -0800, Jim Meyering wrote: > > Still wondering how this happened... deliberate optimization for > something else, probably. > And wishing I'd written a relative (not absolute) test for it in 2008, > so I would have noticed sooner. > In 2008 when I wrote this coreutils extN performance test: > > https://git.savannah.gnu.org/cgit/coreutils.git/tree/tests/rm/ext3-perf.sh > > there was no O(N^2) or even "just" O(N^1.5) component when using the > then-just-improved rm. Many of us plotted the curves. How high (how many files) did you plot the curves back in 2008? Do you remember? > Any idea when ext4's unlink became more expensive? Ext4's unlink hasn't really changed. What *has* changed over time is the block and inode allocation algorithms. 2008 is before we optimized allocation algorithms to read/write operations to large files more efficient, and to try to avoid free space fragmention as the file system aged. Given that on large / fast NVMe device everything looks linear, it's pretty clear that what you're seeing is essentially seek time on spinning rust, and probably SSD GC overhead on flash devices. > I've just run a test on the spinning-disk file system mentioned above, > and it took 75 minutes to delete 12.8M entries. That's rather nasty. Yes, but how long did it take to *create* the 12.8M entries? My guess is that it was roughly comparable? - Ted
