archive mirror
 help / color / mirror / Atom feed
* O(n^2) deletion performance
@ 2018-01-02  0:21 Niklas Hambüchen
  2018-01-02  1:20 ` Niklas Hambüchen
                   ` (2 more replies)
  0 siblings, 3 replies; 11+ messages in thread
From: Niklas Hambüchen @ 2018-01-02  0:21 UTC (permalink / raw)
  To: linux-fsdevel; +Cc: Paul Eggert, Jim Meyering, Pádraig Brady

Hello filesystem hackers,

Over in coreutils issue we have found that
unlink()ing `n` many files seems to take in general O(n²) wall time.

So far me and others (in CC) have benchmarked `rm -r` and other methods
of unlink()ing multiple files and we've found approximately quadratic
performance across:

* ext4, XFS and zfs-on-linux on spinning disks
* ext4 on SSDs
* the other combinations were not tested yet

Please find the exact numbers

So far we've observed apparently linear deletion time on:

* XFS on NVMe

It would be great to hear any kind of insights you may have regarding
this issue, implementation details that might be relevant here, or even
some quick benchmarks on your systems to confirm or refute our findings.

Unless instructed otherwise, I would also go ahead and file bugs for the
respective filesystem types, as quadratic deletion time makes for a bad
user experience and lots of sysadmin tears.

Happy new year,

^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2018-01-04 11:42 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-01-02  0:21 O(n^2) deletion performance Niklas Hambüchen
2018-01-02  1:20 ` Niklas Hambüchen
2018-01-02  1:59 ` Theodore Ts'o
2018-01-02  2:49   ` Andreas Dilger
2018-01-02  4:27     ` Jim Meyering
2018-01-02  6:22       ` Theodore Ts'o
2018-01-04  4:16         ` Jim Meyering
2018-01-04  7:16           ` Theodore Ts'o
2018-01-04 11:42           ` Dave Chinner
2018-01-02  4:33     ` Theodore Ts'o
2018-01-02  4:54 ` Dave Chinner

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).